Συνάρτηση Επιλογής

Μια συνάρτηση επιλογής είναι μια συνάρτηση f που ορίζεται σε κάποια συλλογή X μη κενών συνόλων και αντιστοιχεί κάποιο στοιχείο κάθε συνόλου S αυτής της συλλογής στο S κατά f (S). Η f (S) αντιστοιχίζει το S σε κάποιο στοιχείο του S . Με άλλα λόγια, η f είναι συνάρτηση επιλογής για το X αν και μόνο αν ανήκει στο ευθύ γινόμενο του X .

Ένα παράδειγμα[Επεξεργασία | επεξεργασία κώδικα]

Έστω Χ = { {1,4,7}, {9}, {2,7} }. Τότε, η συνάρτηση που αντιστοιχεί το 7 στο σύνολο {1,4,7}, το 9 στο {9} και το 2 στο {2,7} είναι συνάρτηση επιλογής στο X .

Ιστορία και σημασία[Επεξεργασία | επεξεργασία κώδικα]

Ο Ernst Zermelo (1904) εισήγαγε τις συναρτήσεις επιλογής καθώς και το αξίωμα της επιλογής (AC) και απέδειξε το θεώρημα της καλής διάταξης ^[1] που δηλώνει ότι κάθε σύνολο μπορεί να είναι καλά διατεταγμένο ή πιο συγκεκριμένα ότι έχει ελάχιστο στοιχείο. Το AC δηλώνει ότι κάθε σύνολο μη κενών συνόλων έχει μια συνάρτηση επιλογής. Μια πιο αδύναμη μορφή του AC, το αξίωμα της αριθμήσιμης επιλογής (AC _ω ) δηλώνει ότι κάθε αριθμήσιμο σύνολο μη κενών συνόλων έχει μια συνάρτηση επιλογής. Ωστόσο, ελλείψει του AC ή AC _ω, ορισμένα σύνολα μπορεί ακόμα να αποδειχτεί ότι έχουν συνάρτηση επιλογής.

Αν $X$ είναι ένα πεπερασμένο σύνολο μη κενών συνόλων, τότε μπορεί να κατασκευαστεί μια συνάρτηση επιλογής για το $X$ επιλέγοντας ένα στοιχείο από κάθε σύνολο του $X.$ Αυτό απαιτεί μόνο πεπερασμένο αριθμό επιλογών, επομένως δεν χρειάζεται το AC ή το AC _ω.
Αν κάθε μέλος του $X$ είναι ένα μη κενό σύνολο, και η ένωση $\bigcup X$ είναι καλά διατεταγμένη, τότε μπορεί κανείς να επιλέξει το ελάχιστο στοιχείο από κάθε σύνολο του $X$ . Σε αυτή την περίπτωση, είναι δυνατή η καλή διάταξη κάθε συνόλου του $X$ κάνοντας μόνο μία επιλογή καλής διάταξης της ένωσης, οπότε δεν χρειάζεται το AC ή το AC _ω. (Αυτό το παράδειγμα αναδεικνύει ότι το θεώρημα της καλής διάταξης συνεπάγεται το AC. Το αντίστροφο ισχύει επίσης, αλλά είναι λιγότερο τετριμμένο.)

Συνάρτηση επιλογής πλειότιμης συνάρτησης[Επεξεργασία | επεξεργασία κώδικα]

Δεδομένων δύο συνόλων X και Y, έστω F μια πλειότιμη συνάρτηση από το X στο Y (ισοδύναμα, $F:X\rightarrow {\mathcal {P}}(Y)$ είναι μια συνάρτηση από το X στο δυναμοσύνολο του Y ).

Μια συνάρτηση $f:X\rightarrow Y$ λέγεται ότι είναι μια επιλογή του F, εάν:

\forall x\in X\,(f(x)\in F(x)).

Η ύπαρξη πιο κανονικών συναρτήσεων επιλογής, δηλαδή συνεχών ή μετρήσιμων επιλογών είναι σημαντική στη θεωρία των διαφορικών εγκλεισμών, στον βέλτιστο έλεγχο και στα μαθηματικά οικονομικά . ^[2] Δείτε το θεώρημα επιλογής .

Συνάρτηση ταφ Μπουρμπάκι[Επεξεργασία | επεξεργασία κώδικα]

Ο Νικόλας Μπουρμπάκι χρησιμοποίησε λογισμό έψιλον για τα θεμέλιά του που είχαν το σύμβολο $\tau$ που θα μπορούσε να ερμηνευθεί ως επιλογή ενός αντικειμένου (αν υπήρχε) που ικανοποιεί μια δεδομένη πρόταση. Οπότε αν $P(x)$ είναι ένα κατηγόρημα, τότε το $\tau _{x}(P)$ είναι ένα συγκεκριμένο αντικείμενο που ικανοποιεί την $P$ (αν υπάρχει, διαφορετικά επιστρέφει αυθαίρετο αντικείμενο). Ως εκ τούτου, μπορούμε να λάβουμε ποσοδείκτες από τη συνάρτηση επιλογής, για παράδειγμα το $P(\tau _{x}(P))$ ισοδυναμεί με το $(\exists x)(P(x))$ . ^[3]

Ωστόσο, ο τελεστής επιλογής του Μπουρμπάκι είναι ισχυρότερος: είναι ένας ολικός τελεστής επιλογής. Δηλαδή, συνεπάγεται το αξίωμα της ολικής επιλογής . ^[4] Ο Χίλμπερτ το συνειδητοποίησε αυτό όταν εισήγαγε τον λογισμό έψιλον. ^[5]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

↑ Zermelo, Ernst (1904). «Beweis, dass jede Menge wohlgeordnet werden kann». Mathematische Annalen 59 (4): 514–16. doi:10.1007/BF01445300. http://gdz.sub.uni-goettingen.de/no_cache/en/dms/load/img/?IDDOC=28526.
↑ Border, Kim C. (1989). Fixed Point Theorems with Applications to Economics and Game Theory. Cambridge University Press. ISBN 0-521-26564-9.
↑ Bourbaki, Nicolas. Elements of Mathematics: Theory of Sets. ISBN 0-201-00634-0.
↑ John Harrison, "The Bourbaki View" eprint.
↑ "Here, moreover, we come upon a very remarkable circumstance, namely, that all of these transfinite axioms are derivable from a single axiom, one that also contains the core of one of the most attacked axioms in the literature of mathematics, namely, the axiom of choice: $A(a)\to A(\varepsilon (A))$ , where $\varepsilon$ is the transfinite logical choice function." Hilbert (1925), “On the Infinite”, excerpted in Jean van Heijenoort, From Frege to Gödel, p. 382. From nCatLab.

[Zermelo,_1904-1] Zermelo, Ernst (1904). «Beweis, dass jede Menge wohlgeordnet werden kann». Mathematische Annalen 59 (4): 514–16. doi:10.1007/BF01445300. http://gdz.sub.uni-goettingen.de/no_cache/en/dms/load/img/?IDDOC=28526.

[2] Border, Kim C. (1989). Fixed Point Theorems with Applications to Economics and Game Theory. Cambridge University Press. ISBN 0-521-26564-9.

[3] Bourbaki, Nicolas. Elements of Mathematics: Theory of Sets. ISBN 0-201-00634-0.

[4] John Harrison, "The Bourbaki View" eprint.

[5] "Here, moreover, we come upon a very remarkable circumstance, namely, that all of these transfinite axioms are derivable from a single axiom, one that also contains the core of one of the most attacked axioms in the literature of mathematics, namely, the axiom of choice: $A(a)\to A(\varepsilon (A))$ , where $\varepsilon$ is the transfinite logical choice function." Hilbert (1925), “On the Infinite”, excerpted in Jean van Heijenoort, From Frege to Gödel, p. 382. From nCatLab.

[1]

[2]

[3]

[4]

[5]