Μια εισαγωγή στην αριθμησιμότητα (1)

Πως μπορούμε να συγκρίνουμε δυο σύνολα ως προς το «μέγεθος» τους; Για τα πεπερασμένα σύνολα αυτό είναι εύκολο. Απλά μετράμε τον αριθμό των στοιχείων τους. Για παράδειγμα το σύνολο $A = \{1,2,3,4\}$ έχει περισσότερα στοιχειά από το σύνολο $B = \{1,5,6\}$ . Μπορούμε λοιπόν να πούμε ότι το $A$ έχει μεγαλύτερο «μέγεθος» από το $B$ . Οι δυσκολίες αρχίζουν όταν θέλουμε να συγκρίνουμε άπειρα σύνολα. Για παράδειγμα, πως θα συγκρίνουμε το σύνολο $\mathbb{N} = \{1,2,3,\ldots\}$ των φυσικών αριθμών, με το σύνολο $S = \{1,4,9,\ldots\}$ των τέλειων τετραγώνων;

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

Μια άλλη απάντηση θα μπορούσε να είναι ότι το $\mathbb{N}$ είναι μεγαλύτερο του $S$ εφ’ όσων το $S$ είναι γνήσιο υποσύνολο του $\mathbb{N}$ . Παρόλο που και αυτή η απάντηση δεν είναι λανθασμένη, ουσιαστικά δεν έχουμε κάνει τίποτα καινούργιο. Απλά αντί να πούμε ότι το $S$ είναι γνήσιο υποσύνολο του $\mathbb{N}$ , είπαμε ότι το $\mathbb{N}$ «έχει μεγαλύτερο μέγεθος» από το $S$ . Αυτή η απάντηση παρουσιάζει και το εξής πρόβλημα: Δεν μπορούμε να συγκρίνουμε όλα τα σύνολα μεταξύ τους. Για παράδειγμα δεν μπορούμε καν να συγκρίνουμε τα σύνολα $A$ και $B$ που ορίσαμε πιο πάνω. Παρόλο λοιπόν που η έννοια του υποσυνόλου είναι αρκετά σημαντική στα μαθηματικά, σίγουρα δεν γενικεύει την έννοια του μεγέθους.

Μπορούμε λοιπόν να δώσουμε κάποια άλλη απάντηση στο αρχικό ερώτημα; Η απάντηση είναι ναι και αυτό έχει γίνει από τον Georg Cantor στα τέλη του 19ου αιώνα.

Ας πάμε πίσω στην σύγκριση των συνόλων $A = \{1,2,3,4\}$ και $B = \{1,5,6\}$ . Επειδή το σύνολο $B$ έχει μόνο τρία στοιχεία ενώ το $A$ έχει τέσσερα στοιχεία, μπορούμε να βρούμε μια 1-1 συνάρτηση $f:B \to A$ . Για παράδειγμα μια τέτοια συνάρτηση ορίζεται ως $f(1) = 1, f(5) = 2$ και $f(6) = 3$ . Αντίθετα, δεν υπάρχει 1-1 συνάρτηση $f:A \to B$ .

Αυτή η παρατήρηση ισχύει γενικά για τα πεπερασμένα σύνολα. Ένα πεπερασμένο σύνολο $X$ έχει περισσότερα ή ίσα στοιχεία από ένα πεπερασμένο σύνολο $Y$ αν και μόνο αν υπάρχει 1-1 συνάρτηση $f: Y \to X$ .

Μπορούμε όμως να εξετάζουμε αν υπάρχουν 1-1 συναρτήσεις μεταξύ συνόλων τα οποία δεν είναι απαραίτητα πεπερασμένα. Θα λέμε λοιπόν ότι ένα σύνολο $X$ έχει μεγαλύτερο ή ίσο μέγεθος από ένα σύνολο $Y$ αν και μόνο αν υπάρχει 1-1 συνάρτηση $f:Y \to X$ . Σε αυτήν την περίπτωση θα γράφουμε $|Y| \leqslant |X|$ . Το «μέγεθος» $|X|$ του συνόλου $X$ το ονομάζουμε πληθικότητα του $X$ .

Δημιουργούνται τώρα ορισμένα ερωτήματα. Πως ακριβώς ορίζουμε την πληθικότητα ενός συνόλου; Προς το παρόν γνωρίζουμε μόνο πως να συγκρίνουμε πληθικότητες δύο συνόλων αλλά δεν ξέρουμε ακόμη τον ορισμό της πληθικότητας. Ο ορισμός μπορεί να δοθεί αλλά χρειάζονται περισσότερα μαθηματικά εργαλεία. Ίσως λοιπόν τον δώσω σε κάποιο άλλο άρθρο. Να προσθέσω όμως ότι αυτό είναι ένα φαινόμενο που παρουσιάζεται συχνά στα μαθηματικά. Πολλές φορές περισσότερη σημασία για να μπορέσεις να δουλέψεις με ένα μαθηματικό αντικείμενο έχουν οι ιδιότητες οι οποίες απορρέουν από τον ορισμό του παρά ο ίδιος ο ορισμός. Παρόμοιο πράγμα συμβαίνει και με τον διαφορικό και ολοκληρωτικό λογισμό στην Γ’ Λυκείου. Μπορεί κάποιος να κάνει πράξεις με όρια χωρίς ακριβώς να γνωρίζει επακριβώς τον ορισμό του ορίου, μπορεί να χρησιμοποιεί περίπλοκους κανόνες για να υπολογίζει παραγώγους και ολοκληρώματα χωρίς να γνωρίζει πως ακριβώς ορίζονται κ.τ.λ. Για να μην υπάρξουν παρεξηγήσεις, δεν λέω πως δεν πρέπει να γνωρίζουμε τους ορισμούς. Λέω ότι πολλές φορές μπορούμε να πετύχουμε αρκετά χρησιμοποιώντας μόνο τις ιδιότητες. Εννοείται πως για καλύτερη κατανόηση πρέπει να γνωρίζουμε τους ορισμούς και ότι αν τα βρούμε σκούρα ίσως χρειαστεί να καταφύγουμε σε αυτούς.

Υπάρχει ακόμη ένα αναπάντητο ερώτημα. Έχω ορίσει πως συγκρίνονται οι πληθικότητες δύο συνόλων. Φυσικά υπάρχουν διαφορετικά σύνολα με ίδιες πληθικότητες. Π.χ. τα $\{1,2\}$ και $\{1,3\}$ . Αυτό δεν είναι πρόβλημα. Άλλωστε αυτός είναι ο σκοπός μας. Να μαζέψουμε σε «ομάδες» σύνολα που έχουν το ίδιο «μέγεθος». Πιο πάνω είχα πει πως αν για την σύγκριση χρησιμοποιούσαμε την έννοια του υποσυνόλου, τότε θα υπήρχαν σύνολα που δεν είναι συγκρίσιμα. Τι γίνεται τώρα; Μήπως μπορούμε αν μας δοθούν δυο σύνολα $X,Y$ να πούμε ότι είτε έχουν την ίδια πληθικότητα είτε κάποιο έχει μεγαλύτερη πληθικότητα από το άλλο; Από τον ορισμό η απάντηση στο προηγούμενο ερώτημα δεν είναι ξεκάθαρη. Φυσικά δεν θα έμπαινα σε όλο αυτόν τον κόπο αν δεν μπορούσαμε. Η απάντηση είναι θετική αλλά πάλι η απόδειξη ξεφεύγει από τους σκοπούς του συγκεκριμένου άρθρου.

Θα κρύψω λοιπόν και τα δυο πιο πάνω ερωτήματα κάτω από το χαλάκι. Ας προχωρήσουμε λοιπόν στις συγκρίσεις και ας δούμε πως συγκρίνονται τα σύνολα $\mathbb{N}$ και $S$ που ορίσαμε πιο πάνω. Προφανώς $|S| \leqslant |\mathbb{N}|$ αφού η συνάρτηση $f:S \to \mathbb{N}$ που δίνεται από τον τύπο $f(s) = s$ για $s \in S$ , είναι 1-1. Ισχύει όμως και ότι $|\mathbb{N}| \leqslant |S|$ . Πράγματι η συνάρτηση $g:\mathbb{N} \to S$ που δίνεται από τον τύπο $g(n) = n^2$ για $n \in \mathbb{N}$ είναι 1-1.

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

Θα λέμε ότι ένα σύνολο $X$ είναι αριθμήσιμο αν υπάρχει 1-1 συνάρτηση $f:X \to \mathbb{N}$ . Δηλαδή αν και μόνο αν $|X| \leqslant |\mathbb{N}|$ .

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

Είναι προφανές ότι με τον ορισμό που δώσαμε κάθε πεπερασμένο σύνολο είναι αριθμήσιμο και κάθε υποσύνολο του $\mathbb{N}$ είναι αριθμήσιμο. Είναι επίσης εύκολο να δειχθεί ότι κάθε υποσύνολο ενός αριθμήσιμου συνόλου είναι αριθμήσιμο. Ας δούμε ορισμένα άλλα αριθμήσιμα σύνολα.

Το σύνολο $\mathbb{Z} = \{\ldots,-2,-1,0,1,2,\ldots\}$ των ακεραίων είναι αριθμήσιμο: Μπορούμε να βάλουμε τους ακεραίους σε μια λίστα $0,-1,1,-2,2,-3,3,\ldots$ και μετά μπορούμε να ορίσουμε την συνάρτηση $f:\mathbb{Z} \to \mathbb{N}$ ως εξής: $f(0) = 1,f(-1) = 2,f(1) = 3,f(-2) = 4,f(2) = 5\ldots$ . Με άλλα λόγια ορίζουμε $f(n) = 2n+1$ αν $n \geqslant 0$ και $f(n) = -2n$ αν $n < 0$ . Είναι προφανές ότι η συνάρτηση είναι 1-1 και άρα το σύνολο των ακεραίων είναι αριθμήσιμο.

Το σύνολο $\mathbb{N} \times \mathbb{N} = \{(m,n): m,n\in \mathbb{N}\}$ όλων των ζευγών των φυσικών αριθμών είναι αριθμήσιμο. Πράγματι, μπορούμε να γράψουμε τα στοιχεία του $\mathbb{N} \times \mathbb{N}$ στην λίστα $(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),\ldots$ . Σε αυτήν την λίστα το πρώτο ζεύγος είναι το $(1,1)$ , για κάθε $n \in \mathbb{N}$ το ζεύγος που ακολουθεί το $(n,1)$ είναι το $(1,n+1)$ και για κάθε $n,m \in \mathbb{N}$ , το ζεύγος που ακολουθεί το $(n,m+1)$ είναι το $(n+1,m)$ . Δεν είναι δύσκολο να δειχθεί ότι κάθε ζεύγος $(m,n)$ εμφανίζεται ακριβώς μία φορά στην λίστα, έτσι αν ορίσουμε $f((m,n)) = k$ αν το ζεύγος $(m,n)$ είναι το $k$ -οστό μέλος αυτής της λίστας τότε η $f$ είναι 1-1 και άρα το $\mathbb{N} \times \mathbb{N}$ είναι αριθμήσιμο. Προσέξτε ότι στην απόδειξη δεν δώσαμε «τύπο» για την συνάρτηση $f$ . Θα μπορούσαμε βέβαια να δώσουμε τον τύπο $f((m,n)) = \binom{m+n-1}{2} + m$ και να δουλέψουμε με αυτόν αλλά αυτό δεν είναι απαραίτητο για την απόδειξη. Απαραίτητη είναι απλώς η απόδειξη ότι τέτοια συνάρτηση υπάρχει. Σε επόμενο άρθρο θα συναντήσουμε πιο πολύπλοκες συναρτήσεις όπου είναι αρκετά περίπλοκο να γραφτεί ένας τύπος και έτσι θα περιοριστούμε μόνο στην ύπαρξή του.

Το $A \times B = \{(a,b):a \in A, b\in B\}$ ονομάζεται το καρτεσιανό γινόμενο των συνόλων $A,B$ . Παρόμοια απόδειξη δείχνει ότι το καρτεσιανό γινόμενο δυο αριθμήσιμων συνόλων είναι αριθμήσιμο. Μπορούμε φυσικά να ορίζουμε και καρτεσιανά γινόμενα περισσότερων συνόλων π.χ. $A \times B \times C = \{(a,b,c):a \in A, b\in B,c\in C\}$ κ.τ.λ. Παρόμοια απόδειξη δείχνει ότι το καρτεσιανό γινόμενο πεπερασμένου αριθμού αριθμήσιμων συνόλων είναι αριθμήσιμο. Θα δώσω μια διαφορετική απόδειξη πιο κάτω.

Προς το παρόν έχουμε δει μόνο αριθμήσιμα σύνολα. Μήπως υπάρχουν και μη αριθμήσιμα σύνολα; Ένας καλός υποψήφιος είναι το σύνολο των ρητών αριθμών $\mathbb{Q}$ . Γνωρίζουμε άλλωστε ότι μεταξύ δυο ρητών αριθμών υπάρχει άλλος ένας ρητός αριθμός. Πως λοιπόν θα τα καταφέρουμε να τους βάλουμε σε μια λίστα όπως κάναμε πιο πάνω; Εντούτοις, το σύνολο των ρητών αριθμών είναι αριθμήσιμο. Σχεδόν μάλιστα το έχουμε αποδείξει! Τα σύνολα $\mathbb{Z},\mathbb{N}$ είναι αριθμήσιμα άρα το ίδιο ισχύει και για το σύνολο $\mathbb{Z} \times \mathbb{N}$ . Άρα το ίδιο ισχύει και για κάθε υποσύνολο του $\mathbb{Z} \times \mathbb{N}$ και μπορούμε να θεωρήσουμε το $\mathbb{Q}$ σαν υποσύνολο του $\mathbb{Z} \times \mathbb{N}$ επομένως είναι και αυτό αριθμήσιμο. Πιο αναλυτικά: Έστω μια 1-1 συνάρτηση $f:\mathbb{Z} \times \mathbb{N} \to \mathbb{N}$ και έστω $g:\mathbb{Q} \to \mathbb{Z} \times \mathbb{N}$ η συνάρτηση που στέλνει τον μη μηδενικό ρητό $m/n$ όπου $m \in \mathbb{Z}$ και $n \in \mathbb{N}$ με $|m|,n$ πρώτους μεταξύ τους, στο $(m,n) \in \mathbb{Z} \times \mathbb{N}$ και στέλνει το $0$ στο $(0,0)$ . Τότε η $g$ είναι 1-1 και άρα το ίδιο ισχύει και για την $f \circ g : \mathbb{Q} \to \mathbb{N}$ .

Ας δούμε όμως και μια πιο κομψή απόδειξη ότι το σύνολο των ρητών είναι αριθμήσιμο. Έστω $q$ ένας ρητός αριθμός. Αν είναι θετικός, μπορούμε να γράψουμε με μοναδικό τρόπο $q = m/n$ όπου $m,n \in \mathbb{N}$ είναι πρώτοι μεταξύ τους. Ορίζουμε τότε $f(q) = 2^m3^n$ . Αν ο $q$ είναι αρνητικός με $q = -m/n$ όπου $m,n \in \mathbb{N}$ είναι πρώτοι μεταξύ τους τότε ορίζουμε $f(q) = 2^m3^n5$ . Τέλος αν $q=0$ ορίζουμε $f(q) = 1$ . Από την μοναδικότητα την αναπαράστασης κάθε αριθμού σε γινόμενο πρώτων παραγόντων καταλήγουμε ότι η $f$ είναι 1-1 και άρα οι το σύνολο των ρητών είναι αριθμήσιμο.

Ακριβώς η ίδια απόδειξη μπορεί να χρησιμοποιηθεί και για τον ορισμό ότι το καρτεσιανό γινόμενο πεπερασμένου αριθμού αριθμήσιμων συνόλων είναι αριθμήσιμο. Πράγματι έστω $X_1,\ldots,X_k$ αριθμήσιμα σύνολα και έστω $f_1:X_1 \to \mathbb{N}, \ldots, f_k:X_k \to \mathbb{N}$ 1-1 συναρτήσεις. Έστω επίσης $p_1,p_2,\ldots,p_k$ διαφορετικοί μεταξύ τους πρώτοι αριθμοί. Τότε η συνάρτηση $f:X_1 \times \cdots \times X_k \to \mathbb{N}$ που δίνεται από τον τύπο $f((x_1,\ldots,x_k)) = p_1^{f_1(x_1)} \cdots p_k^{f_k(x_k)}$ είναι 1-1. Πράγματι αν $f((x_1,\ldots,x_k)) = f((y_1,\ldots,y_k))$ τότε θα πρέπει να ισχύει ότι $f_1(x_1) = f_1(y_1),\ldots, f_k(x_k) = f_k(y_k)$ και άρα θα πρέπει $x_1=y_1,\ldots x_k=y_k$ και άρα $(x_1,\ldots,x_k) = (y_1,\ldots,y_k)$ .

Παραμένει βέβαια το ερώτημα αν υπάρχουν σύνολα τα οποία δεν είναι αριθμήσιμα. Αν δεν υπήρχε ουσιαστικά θα είχαμε κάνει μια τρύπα στο νερό. Κάθε δυο άπειρα σύνολα θα είχαν την ίδια πληθικότητα και δεν θα υπήρχε λόγος να χρησιμοποιούμε αυτήν την έννοια. Θα δούμε όμως την ύπαρξή τους σε επόμενο άρθρο.

6 Responses to Μια εισαγωγή στην αριθμησιμότητα (1)

Ο/Η Perastikos λέει:

23 Νοεμβρίου, 2011 στο 10:58

Πολύ καλή παρουσίαση.
Εξόσων γνωρίζω και οι πραγματικές ρίζες μιας πολυωνυμικής εξίσωσης με ακέραιους συντελεστές είναι σύνολο αριθμήσιμο.

Απάντηση
Ο/Η Δημήτρης λέει:

23 Νοεμβρίου, 2011 στο 11:14

Ευχαριστώ.

Σωστό είναι αυτό που λες και θα παρουσιαστεί στο επόμενο άρθρο που σκοπεύω να ανεβάσω.

Απάντηση
Παράθεμα: Μια εισαγωγή στην αριθμησιμότητα (2) | Αποδείξεις από το βιβλίο
Ο/Η DE MOIVRE λέει:

14 Ιουνίου, 2015 στο 19:21

ΘΕΩΡΩ ΤΗ ΜΑΘΗΜΑΤΙΚΗ ΣΚΕΨΗ ΒΑΣΗ ΤΗΣ ΦΙΛΟΣΟΦΙΑΣ ΚΑΙ ΓΙΑΥΤΟ ΑΣΧΟΛΟΥΜΑΙ ΜΕ ΑΥΤΑ . ΕΧΩ ΣΠΟΥΔΑΣΕΙ ΓΕΩΕΠΙΣΤΗΜΕΣ ΑΛΛΑ ΤΑ ΜΑΘΗΜΑΤΙΚΑ ΜΕ ΣΥΝΑΡΠΑΖΟΥΝ. ΑΡΘΡΑ ΤΟΥ ΕΙΔΟΥΣ ΑΥΤΟΥ ΒΟΗΘΟΥΝ ΤΑ ΜΕΓΙΣΤΑ. . ΤΗ ΣΤΗΛΗ ΑΥΤΗ ΤΗΝ ΑΝΑΚΑΛΥΨΑ ΤΥΧΑΙΩΣ ΠΡΟΣΦΑΤΑ
ΣΥΝΕΧΙΣΤΕ ΕΚΛΑΙΚΕΥΟΝΤΑΣ ΤΗ ΜΑΘΗΜΑΤΙΚΗ ΣΚΕΨΗ .

Απάντηση
Ο/Η Δημήτρης Χριστοφίδης λέει:

14 Ιουνίου, 2015 στο 20:33

Ευχαριστώ για τα καλά σχόλια!

Απάντηση
Ο/Η Σωκρατης Βλαχοπουλος λέει:

14 Νοεμβρίου, 2018 στο 12:44

«Για να μην υπάρξουν παρεξηγήσεις, δεν λέω πως δεν πρέπει να γνωρίζουμε τους ορισμούς.» Ίσως λέτε το ακριβώς αντίθετο, πολύ καλό άρθρο.

Απάντηση