27/06/16

Gli infiniti di Cantor-Parte dodicesima: Il teorema di Bernstein

Stiamo affrontando un fase preparatoria ; dobbiamo introdurre uno strumento di confronto per semplificare alcune dimostrazioni sulla cardinalità degli insiemi. Quando andremo a confrontare insiemi come l'insieme delle parti di N con R, oppure R (retta euclidea) con R x R (piano euclideo) non sarà così facile trovare un corrispondenza biunivoca fra i due. La cosa più difficile in genere non è dimostrare che una corrispondenza sia iniettiva, ma dimostrarne la suriettività.  C'è un metodo più semplice, dovuto a Bernstein. Riprendo prima una definizione  usata precedentemente in altri articoli.

Confrontare la cardinalità di due insiemi 

Vogliamo  definire quando la cardinalità di un insieme X sia minore di quella di un insieme Y.  Diremo che |X|<=|Y| se esiste una funzione iniettiva f di X in Y: f: X--->Y .  Ma se fosse anche |Y|<=|X| ? Ovvero se esistesse una funzione iniettiva   g di X in Y: g: Y--->X? Saremmo tentati di dire che |X|=|Y|, come faremmo con due numeri reali. Nel caso di due insiemi finiti A, B è abbastanza ovvia; se f:A--> B è iniettiva, manda punti distinti in punti distinti, quindi se indichiamo con a,b il numero di punti di A,B allora a<=b ; per lo stesso motivo, se c'è una g:B--> A iniettiva, b<=a,  quindi a=b.

Nel caso di insiemi infiniti invece la dimostrazione non è banale e prende il nome di Teorema di Cantor-Bernstein , ed è stata realizzata  da Felix Bernestein, che si dice sia stato allievo di Cantor e a cui Cantor affidò lo dimostrazione del teorema, essendo probabilmente già certo della soluzione.

Lemma preparatorio

Sia  X\subseteq Y \subseteq Z;  supponiamo che esista una applicazione biunivoca

f: Z--->X; allora esiste anche una applicazione biunivoca g di

g: Z---->Y

GF

Osserviamo che questo è possibile solo se gli insiemi in gioco sono infiniti; infatti nel caso finito non può esistere una corrispondenza fra un insieme e un suo sottoinsieme proprio, ma nel caso infinito si (basta ricordare l'esempio di N e dei numeri pari). Sappiamo poi che ciò è possibile nel caso dei tre insiemi N,Z,Q. Vogliamo dimostrare che è vero nel caso generale di insiemi infiniti qualsiasi.

 

Dimostrazione  del lemma preparatorio.

Poniamo Ao=Z-Y,  ovvero la parte in rosso della figura qui sotto.

1

Definiamo una famiglia di insiemi in modo ricorsivo; A0=Z-Y,

A1=f(Ao) ;

A2=f(A1) ...

An=f(An-1);

An+1=f(An)

(non lasciatevi spaventare da questa definizione:è stata generata dall'intuito di un grande matemarico, vedremo in seguito a cosa serve)

osserviamo che  A1,A2, ..An, An+1 sono sottoinsiemi di X, essendo f una applicazione di Z-->X

Chiamiamo  A=(\bigcup_{n}A_{n}) ovvero l'unione di tutti gli An; possiamo anche dire che A=Ao \bigcup (\bigcup_{n>1}A_{n})   quindi , ponendo B=\bigcup_{n>1}A_{n},A= A_{0} \cup B .  f(A) risulta contenuta  in X ( gli Ai sono tutti sottoinsiemi di X, quindi anche la loro unione è contenuta in X) e quindi anche  in Y, essendo X sottoinsieme di Y; f(A)\subseteq X\subseteq Y. Notiamo poi che su B=A \cap Y f è suriettiva; infatti comunque prendiamo un elemento in A, tale elemento apparterà a qualcuno degli Ai, ma ogni  Ai è immagine di qualche altro elemento della famiglia di insiemi. A questo serve la definizione ricorsiva di A.

2
la parte rossa del disegno individua A=Ao U B

 

Costruiamo adesso una funzione di Z---> Y in questo modo: (la funzione f è definita su tutto Z e ha valori in X; dobbiamo in qualche modo estenderla perchè f non ha valori in Y, ma solo in X)

g(z)=\left\{\begin{matrix} f(z) ; z\in A\\ z ; z\in Z-A \end{matrix}\right.

In questo modo riusciamo a coprire gli elementi della parte viola di Y.

4
la parte rossa del disegno è A, quella viola Z-A

 

dimostriamo per prima cosa che g è iniettiva ;possiamo distinguere tre casi:

1)z_{1},z_{2} appartengano ad A; ma essendo g definita in tal caso interamente da f, z_{1}\neq z_{2}  implica

g(z_{1})= f(z_{1})\neq f(z_{2})= g(z_{2}) ;quindi g(z_{1})\neq g(z_{2})

2) z_{1},z_{2} appartengono a Z-A,z_{1}\neq z_{2}; ma allora la definizione della funzione è: g(z_{1})=z_{1}\neq z_{2}=g(z_{2}) ;quindi g(z_{1})\neq g(z_{2})

3)z_{1} appartiene ad A ,z_{2} appartiene a Z-A ;

ma allora g(z_{1})=f(z_{1}) che appartiene ad A, essendo immagine di f di un elemento di A;g(z_{2})=z_{2}  che appartiene a Z-A, ma allora g(z_{1})\neq g(z_{2})  perchè g(z_{1}),g(z_{2}) appartengono ad insiemi complementari.

Suriettività di g:

Se y appartiene  a Y, allora o appartiene a Y-A, oppure appartiene ad A :

4
B sostituisce A nella differenza, perchè Ao è esterno a Y; la parte viola è  Y-A=Y-B

 

(ricordiamo la definizione di g:g(z)=\left\{\begin{matrix} f(z) ; z\in A\\ z ; z\in Z-A \end{matrix}\right. )

supponiamo che y appartenga a Y-A; allora g(y)=y perchè se non appartiene ad A sta in Z-A.

Se y appartiene Ad A (ovvero a B)  allora  essendo B=\bigcup_{n}A_{n>1} ; questo vuol dire che esiste un certo i per cui y appartiene ad A_{i}; ma per come sono definiti gli A_{i} (anzi, sono stati definiti apposta così) esiste z appartenente ad A_{i-1} tale che f(z)=y. ma dato che z appartiene ad A, g(z)=f(z)=y. (osserviamo che essendo n>1, al limite per  i=0, troviamo che z sta in Ao)

 

Il Teorema  di Cantor-Bernstein

Siano X e  Y due insiemi e supponiamo che f:X--->Y e  g:Y--> X siano due funzioni iniettive. Detto con il linguaggio dei numeri cardinali, |X|<=|Y|, |Y|<=|X|;

5

Allora esiste una funzione biettiva  h:X---> Y, ovvero se |X|<=|Y|, |Y|<=|X| allora |X|=|Y|

Osserviamo che

1)|X|=|f(X)|, infatti f:X--->Y è iniettiva, ma considerando come codominio f(X) è anche suriettiva, quindi è una corrispondenza biunivoca.

cardinali

2) |f(X)=|g(f(X)|| infatti g è iniettiva, ed è anche suriettiva su g(f(X))

dal confronto fra 1) e 2) segue allora |X|=|f(X)|=|g(f(X)|; il fatto che |f(X)|=|g(f(X)| implica che esiste una applicazione biunivoca fra X  e g(f(X).

essendo poi g(f( X))\subseteq g(Y) \subseteq X

catena
se y sta in f(x), allora sta anche in Y, ma allora l'immagine g  di y sta in g(Y), quindi g(y)=g(f(x)) sta in  g(Y); inutile poi  dire che  g(y) è un elemento di x

siamo nelle ipotesi del Lemma preparatorio;   esiste una corrispondenza biunivoca fra X e g(f(X)) ma allora esiste anche una corrispondenza biunivoca fra X e g(Y). Ma dato che |g(Y)|=|Y| (g è iniettiva ma anche suriettiva su g(Y)) allora |X|=|g(Y))=|Y|.

 

 

Lascia un commento

*

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)

 

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.