Alcune dimostrazioni con Aleph Zero e dispense

[amatrix92]

Ciao a tutti sto preparando la tesina (sui lavori di Cantor e gli infiniti in geerale) e ho pensato che sarebbe meglio conoscere la dimostrazioni di tutti i teoremi / fatti che cito. Nello specifico non saprei come dimostrare formalmente queste 2 cose:

1) $ \displaystyle \aleph _ 0 + 1 = \aleph _ 0 $

2)$ \aleph _ 0 \cdot \aleph_0 = \aleph _0 $

Inoltre se qualche utente esperto conosce qualche dispensa sull' ipotesi del continuo e sulle teorie sugli infiniti con le verie evoluzioni nella storia di carattare non solo divulgativo ma più specifico mi farebbe un gran favore a linkarle !

[fph]

Traduciamo i problemi in linguaggio più umano:
1) devi trovare una bigezione tra $\mathbb{N}$ e $\mathbb{N} \cup \left\{\text{un altro oggetto, chiamiamolo -1 per comodità}\right\}$
2) devi trovare una funzione biiettiva tra $\mathbb{N}$ e le coppie $(a,b)$ con $a,b\in\mathbb{N}$
Viene in mente qualche idea ora? (1) è facile, per (2) può aiutarti molto fare un disegno...

[amatrix92]

Per l'1) ho pensato di costruire una bigezione mandando ogni numero nel suo successivo e poi l'elemento in più mandandolo in 1. Però non so se è sufficiente

[Valenash]

Esiste un libro molto bello che mi è piaciuto molto sugli infiniti, scritto in un linguaggio semplice ma non per questo banale (tra l'altro l'autore è un prof che insegna nella mia scuola )
Si intitola: Verso l'ininito ma con calma (un dialogo su matematica, insiemi e numeri)
Autore: Roberto Zanasi
Casa editrice: scienza express

spero ti possa servire..

per la bigezione dell'1), credo di avere capito come la vuoi costruire e va bene

EDIT: il libro costa 12€ e son 134 pagine giusto per dare qualche informazione in più =)
comunque complimenti per la scelta dell'argomento, credo che di tutta la matematica sia quello che mi affascina di più =)

[SkZ]

ricorda che esiste una funzione bigettiva tra $\mathbb{N}\times\mathbb{N}$ e $\mathbb{Q}$ e della cardinalita' di $\mathbb{Q}$ se ne e' parlato molto anche qui

in 1 o in 0 a seconda se 0 lo consideri un numero naturale o meno

[amatrix92]

Bo ci provo.
Step 1: I numeri primi sono infiniti: se $ p $ fosse il più grande numero primo allora $ 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot ... \cdot p +1 $ che è anche esso primo sarebbe più grande.Assurdo. Posso quindi associare ad ogni numero il relativo numero primo: 2 è il primo numero primo, 3 è il secondo numero primo e così via.

Step 2 Considero ora i due insiemi: il primo formato dai numeri primi contrassegnati da un numero pari nel loro ordinamento, il secondo formato dai numeri primi contrassegnati da un numero dispari nel loro ordinamento.
Ad ogni coppia di primi $ p $ e $ q $ appartenenti rispettivamente ai due insiemi associo la frazione $ \frac {p}{q} $ che essendo $ p $ e $ q $ primi è univocamente determinata. Quella che ho costruito è quindi una funzione bigettiva.

Temo però che non vada bene, o per lo meno non va del tutto bene. Non dovrei ora far vedere che esiste un'altra funzione bigettiva tra le frazioni come le ho create io e $ \mathbb Q $ ?
E in ogni caso anche se mettiamo caso lo avessi fatto, non ho semplicemente spostato il problema a dimostrare che $ \mathbb Q $ è numerabile?

[SkZ]

prima un mio errore: si puo' dimostare che esiste una funzione iniettiva da $\mathbb{Q}$ a $\mathbb{N}\times\mathbb{N}$, ovvero una suriettiva dal secondo al primo, ovvero il secondo contiene il primo.

la dimostrazione che $\mathbb{Q}$ e' numerabile passa per la dimostrazione che l'altro e' numerabile ed e' una dimostrazione famosa e facile da reperire. per questo ne avevo parlato

[amatrix92]

prima un mio errore: si puo' dimostare che esiste una funzione iniettiva da $\mathbb{Q}$ a $\mathbb{N}\times\mathbb{N}$, ovvero una suriettiva dal secondo al primo, ovvero il secondo contiene il primo.

Ah ok allora bhe è più facile basta considerare tutti i naturali (a,b) e Q saranno i numeri della forma a/b

la dimostrazione che $\mathbb{Q}$ e' numerabile passa per la dimostrazione che l'altro e' numerabile ed e' una dimostrazione famosa e facile da reperire. per questo ne avevo parlato

uhmm.. mi sembra un circolo vizioso però... Io inizialmente volevo dimostrare che eiste una bigezione tra $ \mathbb{N}\times\mathbb{N} $ e $ \mathbb N $. Questo equivale a dimostrare che $ Q $ è numerabile, ma ora mi dici che questo si dimostra dimostrando che $ \mathbb{N}\times\mathbb{N} $ è numerabile?

[fph]

Non facciamo casino.
1) occhio, $2\cdot 3 \cdot 5 \cdots \cdot p +1$ non è sempre primo.
2) La dimostrazione classica che $\mathbb Q$ è numerabile si basa su questi due fatti: (a) $\mathbb{N}\times\mathbb{N}$ è numerabile (b) un sottoinsieme infinito di un numerabile è numerabile. Quindi dimostrare che $\mathbb Q$ è numerabile è più difficile che dimostrare che $\mathbb{N}\times\mathbb{N}$ lo è, almeno seguendo questa strada.
3) chiamiamo $P$ l'insieme delle frazioni del tipo $p/q$ con i vincoli che hai detto tu. Tu hai dimostrato che c'è una funzione biiettiva da $\mathbb{N}\times\mathbb{N}$ a $P$, che è come dire che esiste una funzione iniettiva da $\mathbb{N}\times\mathbb{N}$ a $\mathbb{Q}$. Se ho capito bene quello che hai in testa è dire che visto che c'è questa funzione iniettiva $\mathbb{N}\times\mathbb{N}$ è "più piccolo" di $\mathbb{Q}$, ma visto che c'è una funzione iniettiva facile da $\mathbb{Q}$ a $\mathbb{N}\times\mathbb{N}$, allora vale anche il contenimento opposto e quindi sono uguali. Purtroppo questo "quindi" sembra ovvio ma è più difficile da dimostrare di quello che serve a te:
Teorema (Cantor-Schroeder-Bernstein): se esiste una funzione iniettiva da $A$ a $B$ e una da $B$ ad $A$, allora i due insiemi hanno la stessa cardinalità (cioè, esiste una funzione biiettiva tra i due).
Quindi difficilmente questa strada ti porterà a una dimostrazione facile e veloce.

Hint per dimostrare che $\mathbb{N}\times\mathbb{N}$: in fondo quello che devi fare è esibire un modo di "contare" uno dopo l'altro gli elementi di $\mathbb{N}\times\mathbb{N}$, ovvero di collegarli con un tratto di linea senza staccare la penna dal foglio. Rappresenta i suoi elementi in una "tabella infinita"; vedi un modo di collegarli tutti con un tratto di penna?

[amatrix92]

Sì credo di aver capito. Metto sull'asse delle x tutti i numeri naturali e faccio lo stesso sull'asse delle y. Ora comicio a contare partendo dal punto $ (0,0) --> (1 ,0 ) --> ( 0 , 1) ---> ( 0 , 2) --> (1 , 1 ) --> ( 2 , 0 ) --> (3, 0 ) --> (2 ,1) ... $ etc ed è fatta perchè sono riuscito a rendere numerabile la coppia generica (a , b).
Proviamo un po' a generalizzare: Lo stesso discorso lo posso ora fare in un numero finito di dimensioni, posso sempre creare un percorso che passi da tutte le n- uple quindi $ \mathbb N^ n = \mathbb N $ con n finito.
Per quanto riguarda il fatto che Q sia numerabile provo a riciclare la dimostrazione con qualche aggiunta. I numeri sull'asse x rappresentanto il numeratore, quelli sull'asse y il denominatore. Faccio lo stesso percorso di prima. Sì è vero che ci sarà qualche frazione che non è ridotta ai minimi termini e che quindi "la conto più volte" , ma questo non mi interessa se dimostro che $ \mathbb Q + { qualcosa } $ è numerabile allora anche $ \mathbb Q $ lo è.

Mi è venuta in mente anche questa che non so se è giusta: $ \aleph_0 \cdot \aleph_0 = \aleph_0 $ detto in altri termini $ | \mathbb N | \cdot |\mathbb N | =|\mathbb N | \iff |\mathbb N |^2 = |\mathbb N | \iff |\mathbb N^2 | = |\mathbb N | $ che è vera in quanto, come osservato da Galileo in primis, è sempre possibile associare ad un numero naturale il suo quadrato 1-->1 2-->4 3-->9 .... quindi i due insiemi hanno stessa cardinalità.

Edit: per quanto riguarda il nuemro primo è vero non è sempre primo però posso aggiustare la dimostrazione dicendo che se quel numero ha un divisore primo questo è per forza maggiore di p. Assurdo.

Edit 2: riripensandoci per rendere quanto più formale possibile la prima dimostrazione devo dire che posso associare un numero al suo successivo perchè il suo successivo esiste sempre per il secondo assioma di Peano.

[fph]

$ (0,0) --> (1 ,0 ) --> ( 0 , 1) ---> ( 0 , 2) --> (1 , 1 ) --> ( 2 , 0 ) --> (3, 0 ) --> (2 ,1) ... $ etc ed è fatta perchè sono riuscito a rendere numerabile la coppia generica (a , b).

Ok

Proviamo un po' a generalizzare: Lo stesso discorso lo posso ora fare in un numero finito di dimensioni, posso sempre creare un percorso che passi da tutte le n- uple quindi $ \mathbb N^ n = \mathbb N $ con n finito.

Ok

Per quanto riguarda il fatto che Q sia numerabile provo a riciclare la dimostrazione con qualche aggiunta. I numeri sull'asse x rappresentanto il numeratore, quelli sull'asse y il denominatore. Faccio lo stesso percorso di prima. Sì è vero che ci sarà qualche frazione che non è ridotta ai minimi termini e che quindi "la conto più volte" , ma questo non mi interessa se dimostro che $ \mathbb Q + { qualcosa } $ è numerabile allora anche $ \mathbb Q $ lo è.

Ok, ma sii sicuro di avere chiaro il perché di quest'ultima frase. Nota che $\{1\}+\{\text{qualcosa}\}$ è numerabile, ma $\{1\}$ è finito.

Mi è venuta in mente anche questa che non so se è giusta: $ \aleph_0 \cdot \aleph_0 = \aleph_0 $ detto in altri termini $ | \mathbb N | \cdot |\mathbb N | =|\mathbb N | \iff |\mathbb N |^2 = |\mathbb N | \iff |\mathbb N^2 | = |\mathbb N | $ che è vera in quanto, come osservato da Galileo in primis, è sempre possibile associare ad un numero naturale il suo quadrato 1-->1 2-->4 3-->9 .... quindi i due insiemi hanno stessa cardinalità.

Questa invece temo che non voglia dire nulla --- stai solo giocando con i simboli e con due cose diverse che si indicano entrambe con $\text{qualcosa}^2$. In particolare l'ultima implicazione non funziona.

Edit 2: riripensandoci per rendere quanto più formale possibile la prima dimostrazione devo dire che posso associare un numero al suo successivo perchè il suo successivo esiste sempre per il secondo assioma di Peano.

In fondo sì, ma volendo scendere a quel livello di formalismo, c'è un oceano di cose da precisare. Ti consiglio di lasciar perdere i tentativi di "scendere fino agli assiomi" per ora.

[amatrix92]

@fph: Grazie mille, davvero!
@Valenash: ho iniziato e quasi finito il libro che mi hai consigliato, bhe inutile dirti che mi piace un sacco il modo in cui affronta le cose. Grazie anche a te per il consiglio.