Teorema di Cantor-Berstein

[Cammy87]

Se non ho capito male il teorema, l'enunciato dovrebbe essere il seguente:
"Dati due insiemi A,B se esistono un'applicazione da A a B iniettiva ed un'applicazione da B ad A anch'essa iniettiva, allora A e B sono equipotenti, cioè cardA=cardB."

Questo si dimostra facilmente per gli insiemi finiti, ma non riesco a farlo nel caso di A e B non finiti.
Per dimostrare che A e B sono equipotenti devo trovare o dimostrare che esiste un'applicazione da A a B bigettiva, ma non riesco a farlo.
Qualcuno sa aiutarmi oppure sa dirmi dove posso trovare la dimostrazione? Grazie.

P.S. Ho postato la richiesta qui anche se il teorema riguarda l'algebra perchè mi sembra che non sia propriamente un teorema "olimpico".

[Marco]

Era già passato sul Forum un paio d'anni fa. Siano f e g le funzioni iniettive da A a B e viceversa rispettivamente. Ogni elemento di A è immagine tramite g [f] di un solo elemento di B [A], oppure di nessuno. In questo modo puoi fare una catena (eventualmente infinita) di predecessori.

L'idea è dividere gli insiemi A e B in tre sottoinsiemi: quelli con predecessore ultimo in A, quielli con predecessore ultimo in B e quelli con infiniti predecessori.

A questo punto è facile fare applicazioni bigettive tra gli elementi di A con un certo tipo di predecessore con gli elementi di B con il medesimo tipo di predecessore.

[hydro]

Io ragionerei in questo modo:
se esiste un'applicazione iniettiva da A in B, allora esiste sicuramente un'applicazione biiettiva $ A \rightarrow B' \subseteq B $. Simmetricamente, esiste un'applicazione biiettiva $ B \rightarrow A' \subseteq A $. Ma allora, essendo $ B' \subseteq B $, esisterà anchè un'applicazione biiettiva $ B' \rightarrow A'' \subseteq A' $. Pertanto si ha che $ |A|=|B'|=|A''| $.
Ma è anche $ A \supseteq A' \supseteq A'' $ per come sono stati costruiti gli insiemi, e questo implica $ |A| \ge |A'| \ge |A''| $.
Avendo però che $ |A|=|A''| $ allora è anche $ |A|=|A'| $ e di conseguenza $ |A|=|B| $

[edriv]

Io starei un po' attento... perchè rischi di mangiarti la coda.
In fatti questo teorema sembra proprio dire che "esiste una funzione iniettiva da A a B" è una relazione d'ordine tra insiemi, con tutte le proprietà che ne derivano.

Quindi, se tu dici $ |A| \ge |A'| \ge |A''| $ intendi "esiste una funzione suriettiva da A in A' e da A' in A''. Sai anche che esiste una funzione bigettiva tra A ed A'' (per $ |A| = |A''| $).

Ma da qui a costruire una funzione bigettiva tra A e A'... boh, sarebbe meglio chiarire.

[Marco]

Questa non l'ho capita...

Ma è anche $ A \supseteq A' \supseteq A'' $ per come sono stati costruiti gli insiemi

Ce la dimostri meglio?

[hydro]

Io starei un po' attento... perchè rischi di mangiarti la coda.
In fatti questo teorema sembra proprio dire che "esiste una funzione iniettiva da A a B" è una relazione d'ordine tra insiemi, con tutte le proprietà che ne derivano.

Quindi, se tu dici $ |A| \ge |A'| \ge |A''| $ intendi "esiste una funzione suriettiva da A in A' e da A' in A''. Sai anche che esiste una funzione bigettiva tra A ed A'' (per $ |A| = |A''| $).

Ma da qui a costruire una funzione bigettiva tra A e A'... boh, sarebbe meglio chiarire.

effettivamente ripensandoci mi sa che questa implicazione non è così scontata...
anche perchè dire $ |A| \ge |A'| \ge |A''| $ vuol dire $ |A| \ge |A'| $
e $ |A''|=|A'| \ge |A| $, che alla fine è la tesi. Pensavo che il fatto che $ A \supseteq A' \supseteq A'' $ (poi provo a spiegarmi meglio, Marco) fosse abbastanza per rendere vera l'implicazione, ma ho da rifletterci un po'...

@Marco: se esiste una funzione f iniettiva tra A e B, esiste anche una funzione biiettiva tra A ed un sottoinsieme B' di B, precisamente quello delle immagini degli elementi di A tramite la f. E ugualmente , esistendo una g iniettiva da B ad A, esiste una funzione biiettiva $ \phi $ tra B e il sottoinsieme A' di A delle immagini degli elementi di B tramite la g. Ma essendo B' un sottoinsieme di B, le immagini di B' tramite la $ \phi $ apparterranno tutte ad un sottoinsieme A'' di A'.... o no? magari mi sto sbagliando di grosso, ma mi sembrava corretto il ragionamento.

[Marco]

Ah, ho capito dove sta il busillis. Hai ridetto la stessa cosa due volte:
$ A \supseteq A' \supseteq A'' $.

Due righe sotto invece usi l'uguaglianza degli insiemi, ma non hai mai dimostrato l'altra inclusione, che del resto è falsa:

Controesempio:

Piglia A = B = N e f(n) = g(n) = n+1. Entrambe iniettive. A' = N \ {0}, mentre A" = N \ {0,1}.

[Cammy87]

[...]
Infatti questo teorema sembra proprio dire che "esiste una funzione iniettiva da A a B" è una relazione d'ordine tra insiemi, con tutte le proprietà che ne derivano.[...]

Questo è vero per insiemi finiti: dire che esiste una funzione iniettiva da A a B è come dire che |A|=<|B| (si può dimostrare che è una relazione d'ordine).
Quindi se, per l'ipotesi, ci sono una funzione iniettiva da A a B ed una iniettiva da B ad A, è come dire |A|=<|B| e |B|=<|A| da cui segue che |A|=|B| e la tesi è dimostrata.
Non sono sicuro, anzi penso che questa dimostrazione non si possa fare per gli insiemi infiniti, perchè in questo caso non posso stabilire relazioni d'ordine, ma soltanto relazioni di equivalenza (|A|=|B|<==>"esiste f da A a B bigettiva").

@ Marco: con il termine "predecessore" intendi la controimmagine di un elemento?

[edriv]

Beh allora...
- riflessiva c'è (la funzione identità è iniettiva)
- transitiva: esistono f,g iniettive f:A ->B e g: B->C. Allora, limitando il dominio di g all'immagine di f, la loro composizione è una funzione iniettiva da A e C.
- antisimmetrica: se esiste f iniettiva da A a B, e g iniettiva da B ad A, se questo teorema è vero, allora esiste f bigettiva tra A e B.
Quindi questo teorema è fondamentale per stabilire che "esiste f iniettiva da A a B" è una relazione d'ordine (NON tra insiemi, perchè nella proprietà antisimmetrica non potrò mai affermare che A=B, ma solo che esiste una funzione bigettiva. La relazione è tra classi di equivalenza tra insiemi per esistenza di funzione bigettiva).
Perchè questa relazione d'ordine non dovrebbe esistere?

Ovviamente tralasciando il fatto che non ha senso considerare l'insieme di tutti gli insiemi o cose del genere, no?

[Cammy87]

Scusami edriv avevo capito male ho anche detto una c....ta
Innanzitutto, come mi hai fatto giustamente notare, questo è sbagliato (non so come mi sia uscito, forse qualche neurone si è bruciato mentre scrivevo):

per gli insiemi infiniti non posso stabilire relazioni d'ordine, ma soltanto relazioni di equivalenza (|A|=|B|<==>"esiste f da A a B bigettiva").

Comunque non avevo proprio capito quello che volevi dire nel tuo primo post.
Io pensavo che tu volessi usare il fatto che questa è una relazione d'ordine per dimostrare il teorema, cioè fare così:

Quindi se, per l'ipotesi, ci sono una funzione iniettiva da A a B ed una iniettiva da B ad A, è come dire |A|=<|B| e |B|=<|A| da cui segue che |A|=|B| e la tesi è dimostrata.

Io volevo dire che questo si può fare tranquillamente per gli insiemi finiti, perchè affinchè esista una funzione iniettiva da A a B, il numero degli elementi di A deve essere minore o uguale di quello di B, cioè |A|=<|B|.
Invece per gli insiemi infiniti è proprio questo teorema a garantirmi la validità della relazione d'ordine, che non può più essere verificata guardando il numero degli elementi, ma si basa sull'iniettività.
Era per questo motivo che mi interessava particolarmente la dimostrazione di questo teorema.
Infatti appena ho un po' di tempo cercherò di scrivere bene una dimostrazione seguendo i suggerimenti di Marco.
Grazie a tutti per l'aiuto.

[Marco]

con il termine "predecessore" intendi la controimmagine di un elemento?

Sì. Dato che ogni elemento ha [eventualmente] un elemento nell'altro insieme che è la sua contrimmagine, puoi fare catene di controimmagini [eventualmente infinite]. Per "predecessore ultimo" intendo [se esiste] l'ultimo elemento della catena di controimmagini che non ha a sua volta controimmagini.

Con queste idee, non è difficile montare una dimostrazione.

Esericizio: dato il controesempio del mio post precedente, chi sono gli elementi con predecessore ultimo in A? e in B? e con infiniti predecessori?

Ciao. M.