Αριθμήσιμα σύνολα

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

Μέγεθος ενός άπειρου συνόλου

Να προσδιορίσουμε το μέγεθος ενός πεπερασμένου συνόλου είναι απλό, μετράμε το πλήθος των στοιχείων. Έτσι το σύνολο M = {a, b, c, d, e} έχει μέγεθος 5, γράφουμε |M| = 5.

Στα άπειρα σύνολα η κατάσταση είναι αρκετά πιο περίπλοκη. Πώς θα μπορούσαμε να συγκρίνουμε το μέγεθος άπειρων συνόλων; Είναι καν δυνατό ή όλα τα άπειρα σύνολα είναι «το ίδιο μεγάλα»;

Για παράδειγμα ας πάρουμε το σύνολο των φυσικών αριθμών και το σύνολο των άρτιων φυσικών αριθμών. Έχουμε έτσι τα σύνολα ℕ^∗ = {1, 2, 3, 4, 5, 6, …} και S = {2, 4, 6, …}. Θα ήθελε κανείς να πει ότι το σύνολο των φυσικών αριθμών είναι μεγαλύτερο από το σύνολο των άρτιων αριθμών, επειδή οι φυσικοί αριθμοί περιέχουν όλους τους άρτιους αριθμούς και επιπλέον κάποια στοιχεία παραπάνω – τους περιττούς αριθμούς.

Θα μπορούσαμε λοιπόν να γράψουμε ότι ισχύει S ⊂ ℕ^∗, το σύνολο S είναι γνήσιο υποσύνολο του συνόλου ℕ^∗. Και θα μπορούσαμε να πούμε ότι αν S ⊂ ℕ^∗, τότε το σύνολο ℕ^∗ είναι μεγαλύτερο – περιέχει δηλαδή περισσότερα στοιχεία από το σύνολο S.

Ένας από τους λόγους για τους οποίους δεν μπορούμε να μετράμε σύνολα με βάση τη σχέση του υποσυνόλου είναι ότι τα σύνολα μπορεί να έχουν διαφορετικό μέγεθος, ακόμα κι αν κανένα σύνολο δεν είναι υποσύνολο του άλλου. Αυτό φαίνεται και σε πεπερασμένα σύνολα: A = {1, 3, 4, 9} και B = {b, u, r, z, m}. Ισχύει: |A| = 4 και |B| = 5. Το σύνολο B είναι μεγαλύτερο από το σύνολο A, κι όμως δεν ισχύει A ⊂ B. Στην περίπτωση των άπειρων συνόλων μπορούμε να το δούμε στους άρτιους και στους περιττούς αριθμούς. Κανένα από τα δύο σύνολα δεν είναι υποσύνολο του άλλου.

Η σχέση του υποσυνόλου δεν θα είναι λοιπόν ιδανικός υποψήφιος για να αποφασίσουμε αν ένα σύνολο είναι μεγαλύτερο από ένα άλλο.

Αμφιμονοσήμαντη απεικόνιση

Θα δοκιμάσουμε διαφορετική προσέγγιση. Έχουμε δύο σύνολα, A και B. Μπορούμε να πούμε ότι έχουν το ίδιο μέγεθος, αν ανάμεσά τους υπάρχει αμφιμονοσήμαντη απεικόνιση. Τι σημαίνει αυτό; Ότι παίρνουμε ένα στοιχείο από το σύνολο A, ένα στοιχείο από το σύνολο B και φτιάχνουμε ένα ζεύγος (a, b). Αυτά τα στοιχεία των συνόλων τα αφαιρούμε και συνεχίζουμε. Αν καταφέρουμε να «αδειάσουμε» και τα δύο σύνολα, βρήκαμε αμφιμονοσήμαντη απεικόνιση.

Παράδειγμα σε πεπερασμένα σύνολα: A = {a, b, c} και B = {1, 2, 3}. Το πρώτο ζεύγος θα μπορούσε να είναι (a, 1), το επόμενο (b, 2) και τελικά (c, 3). Εξαντλήσαμε όλα τα στοιχεία και των δύο συνόλων, βρήκαμε αμφιμονοσήμαντη απεικόνιση. Σημαντικό είναι ότι αυτή δεν είναι η μοναδική αμφιμονοσήμαντη απεικόνιση. Και αυτή είναι έγκυρη λύση: (a, 3), (b, 1), (c, 2).

Στα άπειρα σύνολα τα πράγματα γίνονται λίγο πιο ενδιαφέροντα. Θα δοκιμάσουμε τους περιττούς και τους άρτιους φυσικούς αριθμούς. Διαισθητικά νιώθουμε ότι θα έπρεπε να είναι εξίσου πολλοί. Ας το δοκιμάσουμε. Παίρνουμε τον πρώτο περιττό αριθμό και τον απεικονίζουμε στον πρώτο άρτιο αριθμό: (1, 2). Μετά τον δεύτερο περιττό και τον δεύτερο άρτιο: (3, 4). Κ.ο.κ. Παίρνουμε έτσι τα ζεύγη: (1, 2), (3, 4), (5, 6), (7, 8), … Θα μπορούσαμε να γράψουμε ότι κάθε περιττός αριθμός l απεικονίζεται στον άρτιο αριθμό l + 1 και κάθε άρτιος αριθμός s είναι εικόνα του περιττού αριθμού s − 1. Για κάθε περιττό και για κάθε άρτιο αριθμό έχουμε έτσι κάποιο ζεύγος που περιέχει αυτόν τον αριθμό. Τα σύνολα των περιττών και των άρτιων αριθμών είναι λοιπόν το ίδιο μεγάλα.

Άρτιοι και φυσικοί αριθμοί

Τώρα θα δοκιμάσουμε την ίδια διαδικασία και θα συγκρίνουμε το σύνολο των φυσικών και των άρτιων αριθμών. Έχουμε έτσι τα σύνολα ℕ^∗ = {1, 2, 3, 4, 5, 6, …} και S = {2, 4, 6, …}. Διαισθητικά περιμένουμε ότι το σύνολο των φυσικών αριθμών θα είναι μεγαλύτερο.

Ας προσπαθήσουμε όμως να βρούμε την αμφιμονοσήμαντη απεικόνιση. Μπορούμε να πούμε ότι κάθε φυσικός αριθμός n απεικονίζεται στο διπλάσιό του, στο 2n. Έτσι παίρνουμε τα ζεύγη (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), … Για κάθε φυσικό αριθμό n έχουμε λοιπόν το ζεύγος (n, 2n) και για κάθε άρτιο αριθμό s έχουμε το ζεύγος (s/2, s). Βρήκαμε αμφιμονοσήμαντη απεικόνιση, το σύνολο των άρτιων αριθμών και το σύνολο των φυσικών αριθμών είναι λοιπόν το ίδιο μεγάλα, έχουν τον ίδιο πληθάριθμο.

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

Σύγκριση με τους φυσικούς αριθμούς

Οι φυσικοί αριθμοί στην πραγματικότητα καθορίζουν το ελάχιστο μέγεθος ενός άπειρου συνόλου. Το αν κάποιο άλλο σύνολο έχει το ίδιο μέγεθος με το σύνολο των φυσικών αριθμών μπορεί συχνά να διαπιστωθεί σχετικά εύκολα – αρκεί να βρούμε αμφιμονοσήμαντη απεικόνιση στους φυσικούς αριθμούς, που στην πράξη σημαίνει ότι αρκεί να μπορούμε να αριθμήσουμε, να διατάξουμε τα στοιχεία του συνόλου μας M.

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

Εύκολα βλέπουμε ότι οι άρτιοι και οι περιττοί φυσικοί αριθμοί είναι αριθμήσιμοι, επειδή ξέρουμε να προσδιορίσουμε τον πρώτο, τον δεύτερο, τον τρίτο κ.λπ. άρτιο/περιττό αριθμό. Και οι άρτιοι ακέραιοι; Δηλαδή το σύνολο S = {…, −4, −2, 0, 2, 4, …}. Μπορούμε να τους διατάξουμε; Μπορούμε, αρκεί να πάρουμε την ίδια διάταξη όπως πριν και αμέσως μετά τον θετικό άρτιο αριθμό να γράψουμε και τον αρνητικό του: S = {0, 2, −2, 4, −4, 6, −6, …}. Παρόμοια, για παράδειγμα, και για τους ακέραιους αριθμούς.

Μέγεθος των ρητών αριθμών

Ένα πιο ενδιαφέρον παράδειγμα είναι οι ρητοί αριθμοί, τα κλάσματα. Μπορούμε να τους διατάξουμε; Μπορούμε, αλλά θα είναι ήδη λίγο πιο δύσκολο. Κατασκευάζουμε έναν πίνακα που έχει άπειρες γραμμές και στήλες. Σε κάθε κελί θα υπάρχει ένα κλάσμα. Στην n-οστή στήλη και στην m-οστή γραμμή θα έχουμε το κλάσμα n/m. Δηλαδή στην 1η στήλη και στη 2η γραμμή έχουμε το $\frac{1}{2}$ και στην τρίτη στήλη και στην τέταρτη γραμμή έχουμε το 3/4.

$$\begin{array}{ccccc}1/1& 2/1& 3/1& 4/1& \dots \\ 1/2& 2/2& 3/2& 4/2& \dots \\ 1/3& 2/3& 3/3& 4/3& \dots \\ 1/4& 2/4& 3/4& 4/4& \dots \\ \dots & \dots & \dots & \dots & \dots \end{array}$$

Πώς να τακτοποιήσουμε τώρα αυτούς τους αριθμούς, να τους αριθμήσουμε; Δεν μπορούμε να τους αριθμήσουμε κατά γραμμές ή κατά στήλες, επειδή αμέσως θα πνιγόμασταν στη συγκεκριμένη γραμμή/στήλη. Αντί γι' αυτό παίρνουμε τους αριθμούς κατά διαγωνίους: (πρώτη διαγώνιος:) 1/1, (δεύτερη διαγώνιος:) 2/1, 1/2, (τρίτη διαγώνιος:) 3/1, 2/2, 1/3, (τέταρτη διαγώνιος:) 4/1, 3/2, 2/3, 1/4, … Υπάρχουν ακόμα πολλά επαναλαμβανόμενα κλάσματα, αλλά δεν πειράζει. Αυτό που πειράζει περισσότερο είναι ότι λείπουν οι αρνητικοί αριθμοί. Αυτό λύνεται εύκολα, κάθε φορά που γράφουμε ένα κλάσμα, βάζουμε αμέσως μετά από αυτό τον αρνητικό του. Και τότε μας λείπει ακόμα το μηδέν, εντελώς στην αρχή. Και αυτό είναι όλο, έχουμε όλους τους ρητούς αριθμούς σε μια ακολουθία.

Συνολικά παίρνουμε λοιπόν την ακολουθία: 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

Μέγεθος των πραγματικών αριθμών

Είναι οι πραγματικοί αριθμοί το ίδιο μεγάλοι με τους φυσικούς αριθμούς; Η απόφαση θα είναι ακόμα πιο δύσκολη απ' ό,τι στην περίπτωση των ρητών αριθμών. Θα κάνουμε απόδειξη με απαγωγή σε άτοπο. Ας υποθέσουμε ότι οι πραγματικοί αριθμοί είναι αριθμήσιμοι και ότι υπάρχει αμφιμονοσήμαντη απεικόνιση στους φυσικούς αριθμούς. Ας υποθέσουμε δηλαδή ότι μπορούν να διαταχθούν. Και ας πούμε ότι η ακόλουθη απεικόνιση είναι αυτή η διάταξη:

$$\begin{array}{ccccccccc}0,& 3& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& 9& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& 3& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& 7& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& 7& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& 6& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& 0& \dots \\ \dots \end{array}$$

Στον πίνακα υπάρχουν οι πρώτοι επτά πραγματικοί αριθμοί που είναι στη διάταξή μας. Αυτή η διάταξη βέβαια μπορεί να είναι οποιαδήποτε, δεν χρειάζεται να είναι ταξινομημένη κατά το μέγεθος των αριθμών.

Σύμφωνα με την υπόθεση, σε αυτόν τον άπειρο πίνακα είναι διατεταγμένοι όλοι οι πραγματικοί αριθμοί. (Ο πίνακας είναι πάλι άπειρος, εδώ υπάρχουν μόνο οι πρώτες επτά καταχωρίσεις.) Εμείς τώρα θα προσπαθήσουμε να βρούμε/κατασκευάσουμε έναν αριθμό που είναι πραγματικός, αλλά δεν αναφέρεται σε αυτόν τον πίνακα. Αν βρούμε έναν τέτοιο αριθμό, αυτό είναι αντίφαση με το ότι στον πίνακα υπάρχουν όλοι οι πραγματικοί αριθμοί, από όπου μπορούμε στη συνέχεια να συμπεράνουμε ότι το σύνολο των πραγματικών αριθμών δεν είναι αριθμήσιμο.

Εκείνον τον αριθμό που δεν είναι στον πίνακα τον κατασκευάζουμε ως εξής:

$$\begin{array}{ccccccccc}0,& \boxed{\text{3}}& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& \boxed{\text{9}}& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& \boxed{\text{3}}& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& \boxed{\text{7}}& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& \boxed{\text{7}}& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& \boxed{\text{6}}& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& \boxed{\text{0}}& \dots \\ \dots \end{array}$$

Ξεκινάμε γράφοντας 0,… Έτσι θα μοιάζει στην αρχή ο νέος πραγματικός αριθμός μας. Στην πρώτη δεκαδική θέση θα βάλουμε ένα ψηφίο που δεν βρίσκεται στην πρώτη θέση του πρώτου πραγματικού αριθμού της διάταξής μας (στον πίνακα είναι τονισμένο με πλαίσιο). Εκεί είναι το ψηφίο 3, άρα διαλέγουμε για παράδειγμα το 1 και παίρνουμε τον αριθμό 0,1…

Συνεχίζουμε. Στη δεύτερη θέση θα είναι ένα ψηφίο που δεν είναι στη δεύτερη θέση του δεύτερου πραγματικού αριθμού. Εκεί είναι το 9, άρα για παράδειγμα το 2. Παίρνουμε τον αριθμό 0,12… Στην τρίτη θέση θα είναι ένα ψηφίο που διαφέρει από το τρίτο ψηφίο του τρίτου πραγματικού αριθμού. Εκεί είναι το 3, άρα διαλέγουμε ας πούμε το 7. Παίρνουμε 0, 127…

Και ούτω καθεξής. Πάντα στη θέση n του νέου αριθμού θα είναι ένα ψηφίο που διαφέρει από το ψηφίο που είναι στη θέση n του n-οστού αριθμού της διάταξής μας.

Τι κερδίζουμε με αυτό; Παίρνουμε έναν αριθμό που διαφέρει από όλους τους αριθμούς της διάταξής μας τουλάχιστον κατά ένα ψηφίο. Ας πάρουμε το τελευταίο προσωρινό αποτέλεσμα: 0,127… Αυτός ο αριθμός σίγουρα διαφέρει από τον πρώτο αριθμό της διάταξής μας τουλάχιστον στο πρώτο ψηφίο – επειδή τον φτιάξαμε έτσι. Από τον δεύτερο αριθμό διαφέρει τουλάχιστον στο δεύτερο ψηφίο. Από τον τρίτο στο τρίτο ψηφίο. Γενικά αυτός ο νέος αριθμός διαφέρει από τον αριθμό της διάταξης που είναι στη θέση n τουλάχιστον στο ψηφίο της θέσης n.

Αυτόν τον νέο αριθμό που κατασκευάσαμε δεν θα τον βρούμε λοιπόν στον πίνακα, που έπρεπε να συμβολίζει την αμφιμονοσήμαντη απεικόνιση ανάμεσα στους φυσικούς και στους πραγματικούς αριθμούς. Οι πραγματικοί αριθμοί είναι άρα περισσότεροι από τους φυσικούς. Οι πραγματικοί αριθμοί δεν είναι αριθμήσιμοι, είναι υπεραριθμήσιμοι.

Περισσότερες πηγές

• Are there more odd or even numbers?