Άπειρα σύνολα και πληθάριθμος

Διάταξη συνόλων

Ένα σύνολο είναι ισοδύναμο με ένα άλλο, δηλαδή έχουν ίδια πληθυκότητα ή πληθάριθμο, αν υπάρχει συνάρτηση αντιστοίχισης τέτοια, ώστε κάθε στοιχείο του ενός ή του άλλου συνόλου να αντιστοιχεί ή να αντιστοιχείται.

Συνάρτηση αντιστοίχισης είναι μια συνάρτηση (βλέπε ανάλυση) αμφιμονοσήμαντη των στοιχείων ενός συνόλου σε ένα άλλο σύνολο.

Δύο πεπερασμένα σύνολα έχουν ίδια πληθικότητα ή πληθάριθμο, αν υπάρχει συνάρτηση αντιστοίχισης από το ένα σύνολο στο άλλο. Με άλλα λόγια, αν όλα τα στοιχεία του ενός συνόλου έχουν αντιστοιχηθεί, το άλλο σύνολο δεν περιέχει στοιχεία χωρίς αντιστοίχιση.

Για παράδειγμα στα σύνολα Α={1,2,3,5,6} και Β={1,7,10,15,16} υπάρχει η εξής συνάρτηση αντιστοίχισης f: f(1)=1 f(2)=7 f(3)=10 f(5)=15 f(6)=16

Στα σύνολα Α={1,2,3} και Β={9,14} δεν υπάρχει συνάρτηση αντιστοίχισης. Σε κάθε αντιστοίχιση στην οποία αντιστοιχήθηκαν όλα τα στοιχεία του Β, θα υπάρχει ένα περισσεύον στοιχείο του Α. Έτσι, τα σύνολα Α και Β έχουν διαφορετική πληθυκότητα.

Δύο ισοδύναμα σύνολα έχουν ίσους πληθάριθμους.

Για παράδειγμα έστω το σύνολο των φυσικών αριθμών Α={1,2,...,κ,...} και το σύνολο των φυσικών αριθμών από το 10 και μετά Β={10,11,...,λ,...}. Έστω η συνάρτηση αντιστοίχισης φ(κ)=κ+9. Παρατηρώ ότι κάθε στοιχείο του Α αντιστοιχεί μέσω της φ σε στοιχεία του Β. Η αντίστροφη συνάρτηση της φ είναι η γ(λ)=λ-9, αφού γ(φ(κ))=φ(κ)-9=κ+9-9=κ. Παρατηρώ ότι κάθε στοιχείο του Β αντιστοιχεί μέσω της γ σε στοιχείο του Α. Άρα η φ είναι συνάρτηση αντιστοίχισης τέτοια, ώστε κάθε στοιχείο του Α ή του Β να αντιστοιχεί ή να αντιστοιχείται. Επομένως, τα Α και Β έχουν την ίδια πληθικότητα:

card(A)=card(B)

Δύο ισοδύναμα σύνολα Α,Β συμβολίζεται με: Α~Β

Ο πληθάριθμος ενός συνόλου είναι μεγαλύτερος από τον πληθάριθμο ενός άλλου, αν δεν είναι ισοδύναμα και υπάρχει υποσύνολό του που είναι ισοδύναμο.

Για παράδειγμα Α={1,2,3} και Β={6,8}. Παρατηρώ ότι τα Α και Β δεν είναι ισοδύναμα. Επιπλέον, το υποσύνολο {1,2} είναι ισοδύναμο με το Β, άρα card(A)>card(B).

Αν ένα σύνολο είναι ισοδύναμο ως προς δύο άλλα σύνολα, τα δύο άλλα σύνολα είναι ισοδύναμα και μεταξύ τους.

Απειροσύνολο και πληθικότητα

Απειροσύνολο είναι ένα σύνολο με άπειρα στοιχεία.

Για παράδειγμα το σύνολο των φυσικών αριθμών είναι απειροσύνολο. Το σύνολο των πραγματικών αριθμών είναι ένα άλλο απειροσύνολο.

Υπάρχει υποσύνολο απειροσυνόλου που είναι ισοδύναμο με γνήσιο υποσύνολό του. Έστω Α το σύνολο των φυσικών αριθμών και Β το σύνολο των τετραγώνων των φυσικών αριθμών. Το Β είναι υποσύνολο του Α, γιατί κάθε τετράγωνο φυσικού αριθμού είναι φυσικός αριθμός. Το 3 δεν είναι τετράγωνο κάποιου φυσικού αριθμού, άρα το Β είναι γνήσιο υποσύνολο του Α. Η συνάρτηση φ(κ)=κ² είναι συνάρτηση αντιστοίχισης, με βάση την οποία κάθε στοιχείο του Α και του Β αντιστοιχεί και αντιστοιχίζεται. Άρα το Β είναι ισοδύναμο με το Α.

Το απειροσύνολο των φυσικών αριθμών δεν είναι ισοδύναμο με το απειροσύνολο των πραγματικών.

Απόδειξη:

Έστω ότι υπάρχει συνάρτηση αντιστοίχιςη f(n)=r η οποία αντιστοιχεί κάθε φυσικό n στο σύνολο των πραγματικών αριθμών. Έστω ο πραγματικός αριθμός q τέτοιος, ώστε το i-στο ψηφίο του στο δεκαδικό σύστημα να είναι 9 πλην το i-στο ψηφίο του f(i). Υπάρχει κάποιος φυσικός m, τέτοιος ώστε f(m)=r. Επομένως, το μιοστό ψηφίο του τ είναι a=9-a, άρα 2a=9, άρα a=4,5 που είναι άτοπο. Επομένως, δεν υπάρχει συνάρτηση f. Άρα το σύνολο των φυσικών δεν είναι ισοδύναμο με το σύνολο των πραγματικών. Το σύνολο των φυσικών είναι υποσύνολο των πραγματικών, άρα ο πληθάριθμος των φυσικών είναι μικρότερος από τον πληθάριθμο των πραγματικών.

Το δυναμοσύνολο 2^A του Α δεν είναι ισοδύναμο με το Α. Απόδειξη:

Αν το Α είναι πεπερασμένο, οι πληθάριθμοι είναι διαφορετικοί άρα ισχύει. Αν το Α είναι απειροσύνολο θεωρούμε τη συνάρτηση f(b)=c όπου c στοιχείο του 2^A και b είναι μια διατεταγμένη card(A)-άδα. Σε αυτήν την card(A)-άδα το a-οστό στοιχείο της είναι 1, αν a ανήκει στο b, και 0, αν a δεν ανήκει στο b. Το σύνολο των b είναι ισοδύναμο με το 2^A, εξορισμού του δυναμοσυνόλου. Έστω ότι υπάρχει συνάρτηση g(a)=b. Έστω το d, ένα b τέτοιο, ώστε το a-οστό ψηφίο του να είναι 1, αν το a-στο ψηφίο του g(a) είναι 0, και 0, αν το a-στο ψηφίο του g(a) είναι 1. Παρατηρείται ότι δεν υπάρχει κάποιο a τέτοιο, ώστε g(a)=d. Όμως το d αντιστοιχεί σε κάποιο στοιχείο του 2^A εκ κατασκευής. Επομένως, τα 2^A και Α δεν είναι ισοδύναμα. Μέσω της συνάρτησης f(a)={a}, το A αντιστοιχίζεται σε ένα υποσύνολο του 2^A, άρα:

card(2^A)>card(A)

Δεν υπάρχει μέγιστος πληθάριθμος, αφού αν υπήρχε έστω Μ σύνολο με το μέγιστο πληθάριθμο θα ήταν card(2^Μ)>card(Μ).