Μη αριθμήσιμο σύνολο

MoV · #1

Να δείξετε ότι το σύνολο των γνησίως αυξουσών ακολουθιών $\alpha : \mathbb{N} \rightarrow \mathbb{N}$ δεν είναι αριθμήσιμο .

#2

Γράφω την δεύτερη μου προσπάθεια (στην πρώτη προσπάθησα να προσαρμόσω την διαγώνια διαδικασία του Cantor αλλά κάτι δεν δούλευε):
'Εστω $x=0,\xi _{1}\xi _{2}...$ τυχόν στοιχείο του [0,1)

σε δεκαδική μορφή. Στο

αντιστοιχούμε την γνησίως αύξουσα ακολουθία θετικών ακεραίων:
$2^{1+\xi _{1}},\,\,\,2^{1+\xi _{1}}3^{1+\xi _{2}},\,\,\,2^{1+\xi _{1}}3^{1+\xi _{2}}5^{1+\xi _{3}},\,...$
όπου στις βάσεις χρησιμοποιούνται πρώτοι αριθμοί. Η απεικόνιση αυτή είναι 1-1 διότι αν οι αντίστοιχες ακολουθίες δύο αριθμών του [0,1)

είναι ίσες από την ισότητα των όρων προκύπτει και η ισότητα των ψηφίων αφού η γνώση της ακολουθίας μας επιτρέπει την εύρεση των ψηφίων.
Άρα ο πληθάριθμος των γνησίως αυξουσών ακολουθιών πραγματικών αριθμών είναι μεγαλύτερος ή ίσος του πληθαρίθμου των αριθμών του [0,1)

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

#3

Έστω Χ το δεδομένο σύνολο. Ο Νικόλας έδωσε μια 1-1 συνάρτηση $f:[0,1) \to X$ . Θα δώσω μια επί συνάρτηση $g:X \to [0,1]$ που επίσης αποδεικνύει πως το Χ δεν είναι αριθμήσιμο.

Ορίζω $\displaystyle{g(\alpha) = 0.\overline{\alpha(1)} \, \overline{\alpha(2)}\ldots }$ , όπου με $\overline{n}$ συμβολίζω το υπόλοιπο του

όταν διαιρεθεί με το 10.

Για κάθε $x= 0.x_1x_2 \cdots \in [0,1]$ , η ακολουθία $\alpha:\mathbb{N} \to \mathbb{N}; \quad \alpha(n) = 10n + x_n$ ανήκει στο

και ικανοποιεί $g(\alpha) = x$ , άρα η

είναι πράγματι επί.

MoV · #4

Πολύ ωραίες οι κατασκευές σας κ.Μαυρογιάννη και Δημήτρη !

Η διαγώνια διαδικασία του Cantor έχει ως εξής :
Έστω ότι υπάρχει απαρίθμηση όλων των γνησίως αυξουσών ακολουθιών $a:\mathbb{N}\to\mathbb{N}$ :
$(a_0)_n : a_{0,0} , a_{0,1} , a_{0,2} ...$
$(a_1)_n : a_{1,0} , a_{1,1} , a_{1,2} ...$
$(a_2)_n : a_{2,0} , a_{2,1} , a_{2,2} ...$

Όμως η ακολουθία : $b_n=a_{n,n}+1+b_{n-1}$ με $b_0=a_{0,0}+1$
δηλαδή : $b_n=n+1 + \displaystyle \sum_{i=0}^{n} a_{i,i}$
είναι γνησίως αύξουσα αφού : $b_{n+1}-b_n=a_{n+1,n+1}+1>0$
και ταυτόχρονα διαφορετική από κάθε (a_i)_n

(άτοπο).

edit : πρόσθεσα μία μονάδα στην $b_{n}$ καθώς πριν ήταν $b_0=a_{0,0}$

dement · #5

Δινω κι εγω αλλη μια λυση.

Καθε πεδιο τιμων της

ειναι απειρο υποσυνολο του $\mathbb{N}$ . Επισης, για καθε απειρο υποσυνολο του $\mathbb{N}$ μπορει να κατασκευαστει μια ακολουθια

(αφου το $\mathbb{N}$ ειναι καλως διατεταγμενο). Αρα το συνολο μας ειναι ισοπληθες με το συνολο των απειρων υποσυνολων του $\mathbb{N}$ . Αφου το δυναμοσυνολο $P(\mathbb{N})$ ειναι υπεραριθμησιμο και το συνολο των πεπερασμενων υποσυνολων του $\mathbb{N}$ ειναι αριθμησιμο, εχουμε οτι το συνολο μας ειναι υπεραριθμησιμο.

Δημητρης Σκουτερης

Μη αριθμήσιμο σύνολο

Μη αριθμήσιμο σύνολο

Re: Μη αριθμήσιμο σύνολο

Re: Μη αριθμήσιμο σύνολο

Re: Μη αριθμήσιμο σύνολο

Re: Μη αριθμήσιμο σύνολο

Μέλη σε σύνδεση