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

Στα μαθηματικά, η αρχή του περιστερώνα δηλώνει πως αν τοποθετήσουμε  αντικείμενα σε  δοχεία, με , τότε τουλάχιστον ένα δοχείο πρέπει να περιέχει περισσότερα από ένα αντικείμενα. Το κλασσικό παράδειγμα περιγράφει 9 περιστερώνες με 10 περιστέρια, οπότε και κάποιος περιστερώνας θα έχει τουλάχιστον 2 περιστέρια. Πρόκειται για μια αρχή όπου αν και επιφανειακά δηλώνει το προφανές, μπορεί να χρησιμοποιηθεί έμπρακτα ως αποδεικτικό εργαλείο στην συνδυαστική, στη θεωρία κανονικών γλωσσών, και στη στατιστική, μεταξύ άλλων. Η αρχή του περιστερώνα αποδίδεται κυρίως στον Γερμανό μαθηματικό G. Lejeune Dirichlet, οπού στην εργασία του χρησιμοποιούσε την αρχή με το όνομα  ("αρχή του συρταριού" ή "αρχή του ραφιού").Jeff Miller, Peter Flor, Gunnar Berg, and Julio González Cabillón. "Pigeonhole principle". In Jeff Miller (ed.) Earliest Known Uses of Some of the Words of Mathematics. Electronic document, retrieved November 11, 2006

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

Παραπομπές

Κατηγορία:Συνδυαστική