Χαρίτος Χρυσοβαλάντης
Μαθηματικός


Ορισμός$.$ Δυο σύνολα $Α$ και $Β$ ονομάζονται ισοδύναμα (ή ισοπληθικά) αν και μόνο αν υπάρχει συνάρτηση $f:A\rightarrow B$ η οποία είναι $1-1$ και επί του $Β$.

Θεώρημα Cantor. Δεν υπάρχει συνάρτηση $f: A\rightarrow P(A)$ που να είναι επί του $P(A)$.
Απόδειξη. Έστω ότι υπάρχει μια τέτοια συνάρτηση. Θεωρούμε το σύνολο $B = \{x\in A: x\notin F(x)\} \subseteq P(A)$.
Εξ' υποθέσεως η $f$ είναι επί του $P(A)$, συνεπώς υπάρχει $y\in A$ τέτοιο ώστε $f(y) = B$.
Αν $y\in f(y)$ τότε $y\notin B = f(y)$ και αν $y \notin f(y)$ τότε $y\in B = f(y)$. Αμφότερες οι υποθέσεις οδηγούν σε άτοπο, επομένως δεν υπάρχει τέτοια συνάρτηση.

Πόρισμα. Τα σύνολα $Α$ και $P(A)$ δεν είναι ισοπληθικά καθώς δεν υπάρχει συνάρτηση $f: A\rightarrow P(A)$ που είναι $1-1$ και επί.

Θεώρημα. Το σύνολο $S$ των ακολουθιών με στοιχεία του $\{0,1\}$ είναι ισοπληθικό του $P(\mathbb{N})$.
Απόδειξη. Έστω $Α \in P(\mathbb{N})$. Θεωρούμε την ακολουθία $a_n$ με $a_n = 1$ αν $n \in A$ και $a_n = 0$ αν $n \notin A$. H εν λόγω απεικόνιση είναι $1-1$ και επί, συνεπώς $S \sim P(\mathbb{N})$.

Θεώρημα. Το σύνολο (0,1) είναι μη αριθμήσιμο.
Απόδειξη. Θα δείξουμε ότι δεν υπάρχει $1-1$ και επί απεικόνιση $\mathbb{N} \rightarrow (0,1)$. Θεωρούμε ότι υπάρχει τέτοια αντιστοιχία, $F$ η οποία απεικονίζει κάθε θετικό ακέραιο σε ένα στοιχείο του $(0,1)$ γραμμένο στο δεκαδικό του ανάπτυγμα:

$1 \rightarrow 0.a_{11}a_{12}a_{13}...$
$2 \rightarrow 0.a_{21}a_{22}a_{23}...$
$3 \rightarrow 0.a_{31}a_{32}a_{33}...$
$\vdots$

Κατασκευάζουμε τον αριθμό $a\in (0,1)$ με δεκαδικά ψηφία που επιλέγονται έτσι ώστε το δεκαδικό ψηφίο της θέσης $n$ να είναι διάφορο του $a_{nn}$ και ο οποίος προφανώς δεν ανήκει στην παραπάνω λίστα, δηλαδή στο $F(\mathbb{N})$. Συνεπώς το $(0,1)$ είναι υπεραριθμήσιμο και προφανώς το $[0,1]$ ως υπερσύνολο.

Κάθε στοιχείο του [0,1] διαθέτει τουλάχιστον μια αναπαράσταση στο δυαδικό σύστημα και τα δεκαδικά ψηφία αυτής της δυαδικής αναπαράστασης συγκροτούν μια ακολουθία του συνόλου $S$ που περιγράψαμε σε προηγούμενο θεώρημα. Δια μέσου αυτής της αντιστοιχίας, προκύπτει ότι $[0,1] \sim S$ και εφόσον $S \sim P(\mathbb{N})$, καταλήγουμε στο ότι το δυναμοσύνολο του $\mathbb{N}$ έχει τον πληθάριθμο του $[0,1]$, δηλαδή του συνεχούς.