Qualcuno conosce il testo di Algebra De Giovanni-Franciosi?
Salve a tutti.
C'è qualcuno che conosca il seguente testo: "Elementi di Algebra", di De
Giovanni e Franciosi? A p. 40 della seconda edizione c'è la dimostrazione che
l'insieme N x N è numerabile. Questa dimostrazione non la trovo in nessun
altro testo che conosco, e comunque a un certo punto c'è un passaggio che non
mi torna, quando dice che da f(h,k) = f(i,j) consegue tau_k(h) = tau_j(i).
Ci sto sbattendo la testa da giorni ma proprio non riesco a dedurre la
seconda uguaglianza dalla prima! C'è qualcuno di voi in grado di aiutarmi?
Grazie
Rodolfo
C'è qualcuno che conosca il seguente testo: "Elementi di Algebra", di De
Giovanni e Franciosi? A p. 40 della seconda edizione c'è la dimostrazione che
l'insieme N x N è numerabile. Questa dimostrazione non la trovo in nessun
altro testo che conosco, e comunque a un certo punto c'è un passaggio che non
mi torna, quando dice che da f(h,k) = f(i,j) consegue tau_k(h) = tau_j(i).
Ci sto sbattendo la testa da giorni ma proprio non riesco a dedurre la
seconda uguaglianza dalla prima! C'è qualcuno di voi in grado di aiutarmi?
Grazie
Rodolfo
Risposte
Il testo non lo conosco, ma una dimostrazione molto bella (IMHO) del fatto che $NNtimes NN$ è numerabile è la seguente.
Consideriamo l'applicazione $f: NN times NN to NN$ definita da
$f(n, m)=2^n 3^m$.
Questa applicazione è ingettiva, perché $f(n_1, m_1)=f(n_2, m_2)$ equivale a dire che $2^{n_1-n_2}=3^{n_2-n_1}$ e questo può succedere solo quando $n_1-n_2=0$, perché $2,3$ sono numeri primi distinti. Abbiamo così dimostrato che esiste una applicazione ingettiva di $NN times NN$ in un insieme numerabilmente infinito e dunque $NN times NN$ deve essere finito oppure numerabilmente infinito. Siccome evidentemente $NN times NN$ non è finito, esso è numerabilmente infinito.
Consideriamo l'applicazione $f: NN times NN to NN$ definita da
$f(n, m)=2^n 3^m$.
Questa applicazione è ingettiva, perché $f(n_1, m_1)=f(n_2, m_2)$ equivale a dire che $2^{n_1-n_2}=3^{n_2-n_1}$ e questo può succedere solo quando $n_1-n_2=0$, perché $2,3$ sono numeri primi distinti. Abbiamo così dimostrato che esiste una applicazione ingettiva di $NN times NN$ in un insieme numerabilmente infinito e dunque $NN times NN$ deve essere finito oppure numerabilmente infinito. Siccome evidentemente $NN times NN$ non è finito, esso è numerabilmente infinito.
Spero che tu l'abbia comprato fotocopiato :-[
Avendo richiesto che [tex]$ERRATO$[/tex], in breve ti sei perso in un bicchiere d'acqua; un classico per chi studia da esso!
EDIT: Cancellato l'errore!
Avendo richiesto che [tex]$ERRATO$[/tex], in breve ti sei perso in un bicchiere d'acqua; un classico per chi studia da esso!
EDIT: Cancellato l'errore!
Dove è richiesto quello che tu dici?
Nel testo, mi pare, non c'è traccia di tale richiesta.
Rodolfo
Nel testo, mi pare, non c'è traccia di tale richiesta.
Rodolfo
Pardon, avendo definito: [tex]$\forall (i;j)\in\mathbb{N}\times\mathbb{N}:\tau_j(i)=i+j=n+1\stackrel{d e f}{\iff}f(i;j)=\tau_i(f(n-1;1))$[/tex], allora [tex]$f(h;k)=f(i;j)\stackrel{d e f}{\Rightarrow}\tau_k(h)=\tau_j(i)$[/tex].
"j18eos":
Pardon, avendo definito: [tex]$\forall (i;j)\in\mathbb{N}\times\mathbb{N}:\tau_j(i)=i+j=n+1\stackrel{d e f}{\iff}f(i;j)=\tau_i(f(n-1;1))$[/tex], allora [tex]$f(h;k)=f(i;j)\stackrel{d e f}{\Rightarrow}\tau_k(h)=\tau_j(i)$[/tex].
Eppure ti faccio notare che da suddetta definizione non discende affatto $\tau_k(h) = \tau_j(i)$, ma soltanto questo:
$f(h, k) = \tau_h(f(n - 1, 1))$ con $\tau_k(h) = n + 1$,
$f(i, j) = \tau_i(f(m - 1, 1))$ con $\tau_j(i) = m + 1$,
con $n$ ed $m$ non necessariamente uguali.
Cosa ne pensi?
Ciao
OT: io l'ho usato, insieme ad altri, per preparare gli esami di algebra I e II, e mi sono trovato bene!
Io personalmente lo trovo un ottimo testo, anche se di questa cosa in particolare
non riesco a venirne a capo.
non riesco a venirne a capo.
Comunque sono uno scostumato! 
Benvenuto Rodolfo su questo ottimo forum.
Tornando al problema, volendo dimostrare che [tex]$f$[/tex] è iniettiva devi scegliere coppie di numeri naturali tali che (per essere brevi) siano [tex]$m=n$[/tex]; in quanto con tale richiesta puoi porre [tex]$f(h;k)=f(i;j)$[/tex].
Benvenuto Rodolfo su questo ottimo forum.Tornando al problema, volendo dimostrare che [tex]$f$[/tex] è iniettiva devi scegliere coppie di numeri naturali tali che (per essere brevi) siano [tex]$m=n$[/tex]; in quanto con tale richiesta puoi porre [tex]$f(h;k)=f(i;j)$[/tex].
Bè, ma per dimostrare che una funzione $f: A \to B$ è iniettiva bisogna dimostrare che $f(x) = f(y)$ implica
$x = y$ PER OGNI $x, y \in A$ e non solo PER QUALCHE $x, y \in A$.
$x = y$ PER OGNI $x, y \in A$ e non solo PER QUALCHE $x, y \in A$.
La gatta per la fretta partorì i gattini ciechi!
Andando di fretta mi sono espresso troppo sinteticamente!
In principio si sceglie una coppia [tex]$(i;j)\in\mathbb{N}\times\mathbb{N}\mid i+j=\tau_i(j)=n+1$[/tex] con [tex]$n\in\mathbb{N}$[/tex], con tale premessa si definisce (per motivi che non capii all'epoca, e figuriamoci oggi) [tex]$f(i;j)=\tau_i(f(n-1;1))$[/tex]; quindi scegliendo un'altra coppia [tex]$(h;k)\in\mathbb{N}\times\mathbb{N}\mid h+k=\tau_h(k)=n+1$[/tex] tu hai che [tex]$f(h;k)=f(i;j)$[/tex].
Come hai sottolineato, se si prendono coppie con la solo condizione [tex]$f(h;k)=f(i;j)$[/tex] non si combina nulla; e non mi vengono in mente altre idee! -_-
Andando di fretta mi sono espresso troppo sinteticamente!
In principio si sceglie una coppia [tex]$(i;j)\in\mathbb{N}\times\mathbb{N}\mid i+j=\tau_i(j)=n+1$[/tex] con [tex]$n\in\mathbb{N}$[/tex], con tale premessa si definisce (per motivi che non capii all'epoca, e figuriamoci oggi) [tex]$f(i;j)=\tau_i(f(n-1;1))$[/tex]; quindi scegliendo un'altra coppia [tex]$(h;k)\in\mathbb{N}\times\mathbb{N}\mid h+k=\tau_h(k)=n+1$[/tex] tu hai che [tex]$f(h;k)=f(i;j)$[/tex].
Come hai sottolineato, se si prendono coppie con la solo condizione [tex]$f(h;k)=f(i;j)$[/tex] non si combina nulla; e non mi vengono in mente altre idee! -_-
Scusate, ma se aveste la cortesia di spiegare qual è l'idea dietro la definizione degli [tex]$f(i,j)$[/tex] forse potremmo esservi più d'aiuto.
Ad ogni modo, la numerabilità di [tex]$\mathbb{N}^2$[/tex] non segue immediatamente dal fatto che ogni numero naturale si può scrivere in unico modo come prodotto di una potenza di [tex]$2$[/tex] e di un numero dispari?
In altre parole, ad ogni numero naturale [tex]$n$[/tex] si può associare unicamente una coppia di naturali [tex]$k,h$[/tex] tali che [tex]$n=2^{h-1} (2k-1)$[/tex], pertanto l'applicazione [tex]$\mathbb{N}^2 \ni (k,h)\mapsto 2^{h-1}(2k-1)\in \mathbb{N}$[/tex] è una biiezione.
Ad ogni modo, la numerabilità di [tex]$\mathbb{N}^2$[/tex] non segue immediatamente dal fatto che ogni numero naturale si può scrivere in unico modo come prodotto di una potenza di [tex]$2$[/tex] e di un numero dispari?
In altre parole, ad ogni numero naturale [tex]$n$[/tex] si può associare unicamente una coppia di naturali [tex]$k,h$[/tex] tali che [tex]$n=2^{h-1} (2k-1)$[/tex], pertanto l'applicazione [tex]$\mathbb{N}^2 \ni (k,h)\mapsto 2^{h-1}(2k-1)\in \mathbb{N}$[/tex] è una biiezione.
"gugo82":
Ad ogni modo, la numerabilità di [tex]$\mathbb{N}^2$[/tex] non segue immediatamente dal fatto che ogni numero naturale si può scrivere in unico modo come prodotto di una potenza di [tex]$2$[/tex] e di un numero dispari?
"dissonance":Arrivi tardi, Gugo!
Il testo non lo conosco, ma una dimostrazione molto bella (IMHO) del fatto che $NNtimes NN$ è numerabile è la seguente.
Consideriamo l'applicazione $f: NN times NN to NN$ definita da
$f(n, m)=2^n 3^m$[...]
Vabbé, ma la tua non è una biiezione, caro il mio dissonance, ma solo una iniezione...
L'idea che stà celata dietro tale funzione non l'ho capita, altrimenti l'avrei scritta. -_-
Comunque mi viene in mente la dimostrazione originale di Cantor che, purtroppo, "non sò disegnare"; se qualcun* ha capito di che parlo...
EDIT: Confrontarsi con questo disegno preso da wikipedia!
Comunque mi viene in mente la dimostrazione originale di Cantor che, purtroppo, "non sò disegnare"; se qualcun* ha capito di che parlo...
EDIT: Confrontarsi con questo disegno preso da wikipedia!
@j18eos: Non conosco il testo, ma ad occhio, posso tirare un'ipotesi su com'è costruita [tex]$f(i,j)$[/tex].
L'idea che immagino è la seguente: se rappresentiamo $\mathbb{N}^2$ come una tabella da riempire con i naturali, allora dobbiamo dare a questa tabella un ordine lineare per poterci mettere dentro ad uno ad uno in successione tutti i numeri naturali.
Allora, consideriamo una tabella:
[tex]$\begin{pmatrix} f(1,1) & f(1,2) & f(1,3) & f(1,4) & \dots \\ f(2,1) & f(2,2) & f(2,3) & f(2,4) & \dots \\ f(3,1) & f(3,2) & f(3,3) & f(3,4) & \dots \\ f(4,1) & f(4,2) & f(4,3) & f(4,4) & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix}$[/tex]
e guardiamo le diagonali secondarie: esse sono formate dagli elementi:
[tex]$\text{diagonale $1$: $f(1,1)$}$[/tex],
[tex]$\text{diagonale $2$: $f(2,1),f(1,2)$}$[/tex],
[tex]$\text{diagonale $3$: $f(3,1),f(2,2),f(1,3)$}$[/tex],
[tex]$\text{diagonale $4$: $f(4,1),f(3,2),f(2,3),f(1,4)$}$[/tex]...
Ci accorgiamo subito di una particolarità: la somma degli indici degli elementi [tex]$f(i,j)$[/tex] che stanno sulla diagonale [tex]$n$[/tex]-esima è esattamente [tex]$n-1$[/tex], ossia si ha [tex]$i+j=n-1$[/tex] per ogni [tex]$f(i,j)$[/tex] che sta sulla diagonale [tex]$n$[/tex]-esima.
Quindi ora che si fà?
Ebbé, si prende [tex]$1$[/tex] e si piazza in [tex]$f(1,1)$[/tex] ([tex]$\text{diagonale $1$}$[/tex]); poi, si prendono [tex]$2,3$[/tex] e si piazzano in [tex]$f(2,1),f(1,2)$[/tex] ([tex]$\text{diagonale $2$}$[/tex]); si prendono [tex]$4,5,6$[/tex] e si piazzano in [tex]$f(3,1),f(2,2),f(1,3)$[/tex] ([tex]$\text{diagonale $3$}$[/tex]); i numeri [tex]$7,8,9,10$[/tex] si piazzano in [tex]$f(4,1),f(3,2),f(2,3),f(1,4)$[/tex] ([tex]$\text{diagonale $4$}$[/tex])...
A questo punto è facile continuare iterativamente: infatti sulla diagonale [tex]$n$[/tex]-esima si piazzano (dal basso verso l'alto, ossia da [tex]$f(n,1)$[/tex] ad [tex]$f(1,n)$[/tex]) gli [tex]$n$[/tex] numeri consecutivi partendo da [tex]N(n):=1+\sum_{k=0}^{n-1} k=1+\frac{n(n-1)}{2}[/tex]; in particolare, fissato [tex]$n\in \mathbb{N}$[/tex], si assegnerà:
[tex]$f(n,1)=N(n)$[/tex]
[tex]$f(n-1,2)=N(n)+1$[/tex]
[tex]$\ldots$[/tex]
[tex]$f(2,n-1)=N(n)+n-2$[/tex]
[tex]$ f(1,n)=N(n)+n-1$[/tex].
Quindi dalla precedente, con un po' di occhio affinato dall'esperienza, si trova:
[tex]$f(i,j)=N(i+j+1)+j-1=\frac{(i+j+1)(i+j)}{2} +j$[/tex],
se non vedo male.
Credo che l'idea sia questa... Tra l'altro è molto semplice, quindi mi pare strano non sia spiegata sul testo.
L'idea che immagino è la seguente: se rappresentiamo $\mathbb{N}^2$ come una tabella da riempire con i naturali, allora dobbiamo dare a questa tabella un ordine lineare per poterci mettere dentro ad uno ad uno in successione tutti i numeri naturali.
Allora, consideriamo una tabella:
[tex]$\begin{pmatrix} f(1,1) & f(1,2) & f(1,3) & f(1,4) & \dots \\ f(2,1) & f(2,2) & f(2,3) & f(2,4) & \dots \\ f(3,1) & f(3,2) & f(3,3) & f(3,4) & \dots \\ f(4,1) & f(4,2) & f(4,3) & f(4,4) & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix}$[/tex]
e guardiamo le diagonali secondarie: esse sono formate dagli elementi:
[tex]$\text{diagonale $1$: $f(1,1)$}$[/tex],
[tex]$\text{diagonale $2$: $f(2,1),f(1,2)$}$[/tex],
[tex]$\text{diagonale $3$: $f(3,1),f(2,2),f(1,3)$}$[/tex],
[tex]$\text{diagonale $4$: $f(4,1),f(3,2),f(2,3),f(1,4)$}$[/tex]...
Ci accorgiamo subito di una particolarità: la somma degli indici degli elementi [tex]$f(i,j)$[/tex] che stanno sulla diagonale [tex]$n$[/tex]-esima è esattamente [tex]$n-1$[/tex], ossia si ha [tex]$i+j=n-1$[/tex] per ogni [tex]$f(i,j)$[/tex] che sta sulla diagonale [tex]$n$[/tex]-esima.
Quindi ora che si fà?
Ebbé, si prende [tex]$1$[/tex] e si piazza in [tex]$f(1,1)$[/tex] ([tex]$\text{diagonale $1$}$[/tex]); poi, si prendono [tex]$2,3$[/tex] e si piazzano in [tex]$f(2,1),f(1,2)$[/tex] ([tex]$\text{diagonale $2$}$[/tex]); si prendono [tex]$4,5,6$[/tex] e si piazzano in [tex]$f(3,1),f(2,2),f(1,3)$[/tex] ([tex]$\text{diagonale $3$}$[/tex]); i numeri [tex]$7,8,9,10$[/tex] si piazzano in [tex]$f(4,1),f(3,2),f(2,3),f(1,4)$[/tex] ([tex]$\text{diagonale $4$}$[/tex])...
A questo punto è facile continuare iterativamente: infatti sulla diagonale [tex]$n$[/tex]-esima si piazzano (dal basso verso l'alto, ossia da [tex]$f(n,1)$[/tex] ad [tex]$f(1,n)$[/tex]) gli [tex]$n$[/tex] numeri consecutivi partendo da [tex]N(n):=1+\sum_{k=0}^{n-1} k=1+\frac{n(n-1)}{2}[/tex]; in particolare, fissato [tex]$n\in \mathbb{N}$[/tex], si assegnerà:
[tex]$f(n,1)=N(n)$[/tex]
[tex]$f(n-1,2)=N(n)+1$[/tex]
[tex]$\ldots$[/tex]
[tex]$f(2,n-1)=N(n)+n-2$[/tex]
[tex]$ f(1,n)=N(n)+n-1$[/tex].
Quindi dalla precedente, con un po' di occhio affinato dall'esperienza, si trova:
[tex]$f(i,j)=N(i+j+1)+j-1=\frac{(i+j+1)(i+j)}{2} +j$[/tex],
se non vedo male.
Credo che l'idea sia questa... Tra l'altro è molto semplice, quindi mi pare strano non sia spiegata sul testo.
"gugo82":
Credo che l'idea sia questa... Tra l'altro è molto semplice, quindi mi pare strano non sia spiegata sul testo.
E' semplicissima, infatti è spesso usata nei testi di informatica.
@gugo Insomma, la dimostrazione originale di Cantor! Il libro non cita nulla del genere, nemmeno con altre dimostrazioni; ecco perché non mi piace.
OUT OF SELF Un buon libro di matematica, soprattutto per chi deve iniziarla a studiare a livello universitario, deve facilitarne l'apprendimento spiegando le tecniche canoniche di dimostrazione; altrimenti le cose sembrano rivelate da una qualche verità matematica.
OUT OF SELF Un buon libro di matematica, soprattutto per chi deve iniziarla a studiare a livello universitario, deve facilitarne l'apprendimento spiegando le tecniche canoniche di dimostrazione; altrimenti le cose sembrano rivelate da una qualche verità matematica.
[OT]
Cosa che accade molto spesso con i testi di Algebra e gli algebristi italiani...
[/OT]
"j18eos":
Un buon libro di matematica, soprattutto per chi deve iniziarla a studiare a livello universitario, deve facilitarne l'apprendimento spiegando le tecniche canoniche di dimostrazione; altrimenti le cose sembrano rivelate da una qualche verità matematica.
Cosa che accade molto spesso con i testi di Algebra e gli algebristi italiani...
[/OT]
Scusate, ma ero interessato a seguire quel testo in particolare.
Poi mi ero accanito ed ero curioso di vedere come si dimostrava quella cosa.
Alla fine credo di esserci riuscito e ho caricato la dimostrazione qui:
http://www.sendspace.com/file/mpyrmo
Può sembrare astrusa ma secondo me è interessante perché dimostra la numerabilità di $N^2$ facendo a meno di somma e prodotto tra numeri naturali.
In pratica è una formalizzazione del ragionamento per diagonali di Cantor con le sole nozioni di applicazioni strett. crescenti e insiemi naturalmente ordinati.
Grazie a tutti per aver partecipato alla discussione.
Rodolfo
Poi mi ero accanito ed ero curioso di vedere come si dimostrava quella cosa.
Alla fine credo di esserci riuscito e ho caricato la dimostrazione qui:
http://www.sendspace.com/file/mpyrmo
Può sembrare astrusa ma secondo me è interessante perché dimostra la numerabilità di $N^2$ facendo a meno di somma e prodotto tra numeri naturali.
In pratica è una formalizzazione del ragionamento per diagonali di Cantor con le sole nozioni di applicazioni strett. crescenti e insiemi naturalmente ordinati.
Grazie a tutti per aver partecipato alla discussione.
Rodolfo
L'ho letta e mi sembra corretta!
Auguri per l'esame.
Prego, stiamo qui per aiutare.
Auguri per l'esame.
Prego, stiamo qui per aiutare.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo