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

Στην εισαγωγή στην αριθμησιμότητα ορίσαμε ότι ένα σύνολο X είναι αριθμήσιμο αν υπάρχει 1-1 συνάρτηση f: X \to \mathbb{N} και είδαμε ορισμένα σύνολα όπως τα \mathbb{N},\mathbb{Z},\mathbb{Q} τα οποία είναι αριθμήσιμα. Παρέμεινε όμως το ερώτημα αν υπάρχει σύνολο το οποίο δεν είναι αριθμήσιμο.

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

Λήμμα: Ένα μη κενό σύνολο X είναι αριθμήσιμο αν και μόνο αν υπάρχει επί συνάρτηση f:\mathbb{N} \to X.

(Εξ ορισμού το κενό σύνολο \emptyset είναι αριθμήσιμο, όμως δεν υπάρχει επί συνάρτηση f:\mathbb{N} \to \emptyset.)

Απόδειξη: Αν υπάρχει επί συνάρτηση f:\mathbb{N} \to X τότε για κάθε x\in X ορίζω ως g(x) το ελάχιστο στοιχείο του \{n \in \mathbb{N}:f(n) = x\}. Η συνάρτηση g:X \to \mathbb{N} είναι προφανώς 1-1 και άρα το X είναι αριθμήσιμο.

Για το αντίστροφο, ας υποθέσουμε πως το X είναι αριθμήσιμο. Οπότε υπάρχει 1-1 συνάρτηση g:X \to \mathbb{N}. Επιπλέον, αφού το X είναι μη κενό, έστω x ένα οποιοδήποτε στοιχείο του X. Θέλω να ορίσω μια επί συνάρτηση f:\mathbb{N} \to X. Για n \in \mathbb{N} αν το n ανήκει στο πεδίο τιμών της g τότε υπάρχει μοναδικό x_n\in X με g(x_n)=n (αφού η g είναι 1-1). Σε αυτήν την περίπτωση ορίζω f(n) = x_n. Αν το n δεν ανήκει στο πεδίο τιμών τότε ορίζω f(n) = x. Είναι άμεσο ότι η f είναι επί. \square

Τώρα είμαστε έτοιμοι να δείξουμε την ύπαρξη ενός συνόλου που δεν είναι αριθμήσιμο. Τέτοια σύνολα θα τα ονομάζουμε υπεραριθμήσιμα.

Θεώρημα: Το σύνολο \mathcal{P}(\mathbb{N}) είναι υπεραριθμήσιμο.

(Ας θυμηθούμε ότι αν έχουμε ένα σύνολο X, τότε το \mathcal{P}(X) είναι το σύνολο όλων των υποσυνόλων του X.)

Απόδειξη: Αν ήταν αριθμήσιμο τότε από το λήμμα θα υπήρχε επί συνάρτηση f:\mathbb{N} \to \mathcal{P}(\mathbb{N}). Έστω A = \{n \in \mathbb{N}: n \notin f(n)\}. Αυτό είναι ένα υποσύνολο του \mathbb{N} και αφού η f είναι επί τότε υπάρχει n \in \mathbb{N} με f(n) = A. Δεν μπορούμε να έχουμε n \in f(n) αφού τότε n \in A και άρα n \notin f(n). Ομοίως δεν μπορούμε να έχουμε n \notin f(n) αφού τότε n \in A και άρα n \in f(n). Αυτό όμως είναι άτοπο οπότε τέτοια συνάρτηση δεν μπορεί να υπάρχει. \square

Το πιο πάνω είναι ουσιαστικά το διάσημο διαγώνιο επιχείρημα του Cantor. Ξαναγράφουμε λοιπόν την ίδια ουσιαστικά απόδειξη με διαφορετικό τρόπο για να δούμε καλύτερα από που πήρε αυτό το όνομα. Αντί του συνόλου \mathcal{P}(\mathbb{N}) θα δουλέψουμε με το σύνολο \{0,1\}^{\mathbb{N}} όλων των συναρτήσεων f:\mathbb{N} \to \{0,1\}. Υπάρχει μια προφανής 1-1 και επί συνάρτηση μεταξύ των δύο συνόλων (στέλνει το A \subseteq \mathbb{N} στο f_A:\mathbb{N} \to \{0,1\} με τύπο f_A(n) = 1 αν n \in A και f_A(n) = 0 αν n \notin A) οπότε αν δείξουμε ότι το ένα είναι υπεραριθμήσιμο τότε και το άλλο είναι υπεραριθμήσιμο.

Θεώρημα: Το σύνολο \{0,1\}^{\mathbb{N}} είναι υπεραριθμήσιμο.

Απόδειξη: Αν ήταν αριθμήσιμο τότε θα είχαμε μια ακολουθία f_1,f_2,f_3,\ldots που θα περιλάμβανε όλα τα στοιχεία του \{0,1\}^{\mathbb{N}}. Θα καταλήξουμε σε άτοπο κατασκευάζοντας μια συνάρτηση f:\mathbb{N} \to \{0,1\} που δεν ανήκει σε αυτήν την ακολουθία. Η ιδέα είναι απλή και όμορφη. Θέλουμε η f να διαφέρει από την f_1 οπότε ορίζουμε f(1) = 1 αν f_1(1) = 0 και f(1) = 0 αν f_1(1) = 1. Ισοδύναμα, ορίζουμε f(1) = 1-f_1(1). Θέλουμε επίσης η f να διαφέρει από την f_2 οπότε ορίζουμε f(2) = 1-f_2(2) κ.τ.λ. Διαγραμματικά αν κατασκευάσουμε τον εξής πίνακα

{f_1:} {\boxed{f_1(1)}} {f_1(2)} {f_1(3)} {f_1(4)} {\cdots}
{f_2:} {f_2(1)} {\boxed{f_2(2)}} {f_2(3)} {f_2(4)} {\cdots}
{f_3:} {f_3(1)} {f_3(2)} {\boxed{f_3(3)}} {f_3(4)} {\cdots}
{f_4:} {f_4(1)} {f_4(2)} {f_4(3)} {\boxed{f_4(4)}} {\cdots}
{\vdots} {\vdots} {\vdots} {\vdots} {\vdots} {\vdots}
{f:} {1-f_1(1)} {1-f_2(2)} {1-f_3(3)} {1-f_4(4)} {\cdots}

παρατηρούμε ότι όντως η f είναι διαφορετική από τις f_1,f_2,\ldots οπότε καταλήξαμε σε άτοπο. \square

Το αφήνουμε ως άσκηση για τον αναγνώστη να παρατηρήσει ότι αυτές οι δυο αποδείξεις είναι ουσιαστικά οι ίδιες.

Για να κλείσουμε αυτό το άρθρο θα σημειώσουμε ότι και το σύνολο \mathbb{R} των πραγματικών αριθμών είναι υπεραριθμήσιμο. Ουσιαστικά το έχουμε σχεδόν δείξει αν παρατηρήσουμε ότι σε κάθε συνάρτηση f:\mathbb{N} \to \{0,1\} μπορούμε να αντιστοιχίσουμε τον πραγματικό αριθμό

\displaystyle x = \sum_{n=1}^{\infty} \frac{f(n)}{2^n} \in [0,1]

Αν αυτή η αντιστοίχιση ήταν 1-1 τότε αμέσως θα παίρναμε ότι και το \mathbb{R} είναι υπεραριθμήσιμο αφού αν δεν ήταν θα μπορούσαμε να συνθέσουμε την πιο πάνω 1-1 συνάρτηση μαζί με την 1-1 συνάρτηση g:\mathbb{R} \to \mathbb{N} που θα υπήρχε αν το \mathbb{R} ήταν αριθμήσιμο, για να κατασκευάσουμε μία 1-1 συνάρτηση h:\{0,1\}^{\mathbb{N}} \to \mathbb{N} κάτι που είναι άτοπο.

Δυστυχώς όμως η πιο πάνω αντιστοίχιση δεν είναι 1-1 π.χ. τόσο η συνάρτηση f_1 με τύπο f_1(n) = 1 αν και μόνο αν n=1 όσο και η συνάρτηση f_2 με τύπο f_2(n) = 0 αν και μόνο αν n=1 αντιστοιχούν στον πραγματικό αριθμό x=1/2. Δεν είναι δύσκολο όμως να τροποποιηθεί η συνάρτηση ώστε να γίνει 1-1. Ένας σύντομος τρόπος (αλλά όχι ο μοναδικός) είναι στην θέση της να αντιστοιχίσουμε στην f τον πραγματικό αριθμό

\displaystyle x = \sum_{n=1}^{\infty} \frac{f(n)}{3^n}.

Είναι μια απλή άσκηση να ελεγχθεί ότι όντως αυτή η αντιστοιχία είναι 1-1. Οπότε και το σύνολο των πραγματικών αριθμών είναι υπεραριθμήσιμο.

Advertisements

About Δημήτρης Χριστοφίδης

Course Leader in Mathematics at UCLan Cyprus.
This entry was posted in 03E10 - Ordinal and cardinal numbers and tagged . Bookmark the permalink.

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

  1. Ο/Η Γ Χάιλος λέει:

    Καλημέρα φίλε. Είμαι ο Γ Χάιλος συνάδελφος μαθηματικός. Είχαμε γνωριστεί στην Ημερίδα για τον Καθηγητή Νεγρεπόντη. Είμαι στο Παν Λευκωσίας.

    Σε συγχαίρω για το εξαίρετο ιστολόγιο. Μια μικρή επισήμανση. Το πρώτο μέρος της απόδειξης του Λήμματος απαιτεί τη χρηση του Axiom of Choice.
    Να είσαι καλά

    • Ευχαριστώ για τα σχόλια. Νομίζω το αξίωμα επιλογής δεν χρειάζεται.

      Στην απόδειξη ότι αν έχουμε μια επί συνάρτηση από το Α στο Β τότε έχουμε και μια 1-1 συνάρτηση από το Β στο Α χρησιμοποιούμε το αξίωμα της επιλογής για να κατασκευάσουμε μια καλή διάταξη για το Α. Εδώ όμως έχουμε ήδη έτοιμη μια καλή διάταξη του \mathbb{N} οπότε νομίζω δεν το χρειαζόμαστε.

      Αν κάνω κάπου αλλού λάθος πες μου.

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

Σχολιάστε

Εισάγετε τα παρακάτω στοιχεία ή επιλέξτε ένα εικονίδιο για να συνδεθείτε:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s