Αρχή του περιστερώνα

Στα μαθηματικά, η αρχή του περιστερώνα δηλώνει πως αν τοποθετήσουμε  αντικείμενα σε  δοχεία, με , τότε τουλάχιστον ένα δοχείο πρέπει να περιέχει περισσότερα από ένα αντικείμενα. Το κλασσικό παράδειγμα περιγράφει 9 περιστερώνες με 10 περιστέρια, οπότε και κάποιος περιστερώνας θα έχει τουλάχιστον 2 περιστέρια. Πρόκειται για μια αρχή όπου αν και επιφανειακά δηλώνει το προφανές, μπορεί να χρησιμοποιηθεί έμπρακτα ως αποδεικτικό εργαλείο στην συνδυαστική, στη θεωρία κανονικών γλωσσών, και στη στατιστική, μεταξύ άλλων. Η αρχή του περιστερώνα αποδίδεται κυρίως στον Γερμανό μαθηματικό G. Lejeune Dirichlet, οπού στην εργασία του χρησιμοποιούσε την αρχή με το όνομα  ("αρχή του συρταριού" ή "αρχή του ραφιού").

Η αρχή του περιστερώνα έχει πολλές γενικεύσεις και μπορεί να διατυπωθεί με διάφορους τρόπους. Η συνηθισμένη γενίκευση είναι η εξής:Αν , και  αντικείμενα κατανέμονται σε  δοχεία, τότε τουλάχιστον ένα δοχείο περιέχει τουλάχιστον αντικείμενα.Αν και η πιο απλή εφαρμογή είναι σε πεπερασμένα σύνολα (όπως περιστέρια και κουτιά), χρησιμοποιείται επίσης με άπειρα σύνολα που δεν μπορούν να τεθούν σε αντιστοιχία ένα προς ένα . Για να γίνει αυτό απαιτείται η επίσημη δήλωση της αρχής του περιστερώνα: δεν υπάρχει "ένα-προς-ένα" συνάρτηση της οποίας το σύνολο τιμών είναι μικρότερο από πεδίο ορισμού της. Προηγμένες μαθηματικές αποδείξεις όπως το λήμμα του Siegel βασίζονται σε αυτή τη γενικότερη ιδέα.

Παραπομπές

Συνδυαστική