Come dimostrare il Teorema di Bernstein

Prima di iniziare col discorrere del Teorema di Bernstein, è d'obbligo un piccolo chiarimento al fine di evitare ogni dubbio o fraintendimento nel lettore. Ed è bene aggiungere che i vari Bernstein non sono la stessa persona: si tratta di un curioso caso di molteplice omonimia! Ciò di cui ci occuperemo in questa guida è il Teorema di Bernstein per la Teoria degli Insiemi, dovuto al matematico tedesco Felix Bernstein (1878-1956): questi cominciò a studiare il Teorema, formulato per la prima volta da Georg Cantor (che però non lo dimostrò), nel 1897, sotto la supervisione proprio di Cantor, del quale era allievo, e ne concluse la dimostrazione discutendola come tesi per il proprio Ph. D. Nel 1901. Precedentemente anche il matematico Ernst Schröder aveva tentato di provare un risultato simile ma la sua dimostrazione era incompleta. Per tali ragioni tale Teorema è anche noto, alle volte, come Teorema di Bernstein-Cantor o Teorema di Bernstein-Cantor-Schröder. In questa guida oltre a dimostrare il Teorema ne vedremo anche un'importante conseguenza.

Per prima cosa vediamo qual è l'enunciato del Teorema. Siano S e T insiemi non vuoti: se esiste un'applicazione iniettiva di S in T ed un'applicazione iniettiva di T in S, allora esiste un'applicazione biiettiva di S in T. Tale risultato è ovvio quando si ha a che fare con insiemi finiti: infatti, poiché un'applicazione è iniettiva quando ad elementi distinti del dominio sono associati elementi distinti del codominio, dire che esiste un'applicazione iniettiva di S in T significa dire cha S ha un numero di elementi minore o uguale a quello di T, viceversa dire che esiste un'applicazione iniettiva di T in S significa dire che T ha un numero di elementi minore o uguale a quello di S, sicché, allora i due insiemi hanno lo stesso numero di elementi ed è allora facile porre in una corrispondenza "uno a uno" gli elementi dei due insiemi. Tale risultato vale però anche quando gli insiemi hanno un numero infinito di elementi ed è in questo che risiede la sua importanza, come più avanti vedremo.

Prima di addentrarci nella dimostrazione, produciamo un esempio, in modo tale da avere chiaro il senso della dimostrazione. Consideriamo allora due insiemi S e T infiniti. Supponiamo di indicare con i numeri i primi elementi di S e con le lettere i primi elementi di T di modo che potremo inizialmente scrivere: S = {1,2,3,4,5,6, ?} e T = {a, b, c, d, e, f, ?}. Supponiamo a questo punto di avere un'applicazione iniettiva di S in T, che chiameremo F, le cui iniziali corrispondenze sono, per esempio, F (1)=c, F (2)=b, F (3)=e, F (5)=f mentre 4 e 6 vanno associati con elementi di T diversi da quelli elencati ed inoltre supponiamo che ci sia un elemento di S non in elenco che va associato con a. Supponiamo anche di avere un'applicazione iniettiva di T in S, che chiameremo G, le cui iniziali corrispondenze sono, per esempio, G (a)=1, G (b)=2, G (c)=4, G (d)=5, G (e)=6 mentre f va associato con un elemento di S che non è tra quelli elencati. Prendiamo adesso gli elementi di T, uno per volta, e costruiamo una sequenza grazie alle due funzioni F e G, mettendo in successione gli elementi secondo le corrispondenza sopra riportate. Per esempio: se prendo a posso far seguire 1 (perché G (a)=1), e dopo 1 posso far seguire c (perché F (1)=c), e dopo c posso far seguire 4 (perché G (c)=4), dopo di che non posso aggiungere alcun altro elemento perché non conosco 4 con chi va associato per mezzo di F, inoltre non so F quale elemento di S abbia associato ad a ma so che l'ha fatto (lo abbiamo detto sopra), quindi la mia sequenza è ?, a,1, c,4, ? Se invece prendo b, la sequenza è 2, b,2. Se invece prendo e la sequenza è 3, e,6, ? Se prendo d la sequenza è d,5, f, ? Cosa si vede? Si vede che si formano delle sequenza in cui o il primo elemento è in S (sequenza 3, e,6?) o è in T (sequenza d,5, f, ?) oppure non sappiamo dove sia (sequenza ?, a,1, c,4, ?) oppure primo e ultimo elemento coincidono (sequenza 2, b,2). Poiché F e G sono invettive non possono esserci due sequenze che differiscano per un termine, ovvero tutte le sequenza sono uniche. Più precisamente, sono unici i primi due termini di ogni sequenza. E sono proprio i primi due termini di ogni sequenza, presi in coppia, ad indicare l'associazione da compiere per costruire l'applicazione biiettiva H. Per esempio: vogliamo capire chi associare al 3 di S? Prendiamo la sequenza 3, e,6, ? i cui primi due termini sono 3, e. Allora è H (3)=e. Vogliamo capire chi associare al 5? Prediamo la sequenza d,5, f, ? i cui primi due termini sono d,5. Allora è H (5)=d. Vogliamo capire chi associare a 1 e 4? Prendiamo la sequenza ?, a,1, c,4, ?: se usiamo F allora è H (1)=c e, di conseguenza, H (4)=c, se invece usiamo G, abbiamo H (1)=a e H (4)=c! L'immagine a lato può aiutare a capire quanto è stato fatto.

Vediamo ora come formalizzare l'idea esposta sopra. Siano S e T due insiemi non vuoti. Sia f un'applicazione iniettiva di S in T e sia g un'applicazione iniettiva di T in S. Sia x un elemento di S: diremo che y elemento di T è il suo predecessore se x=g (y). Sia y un elemento di T: diremo che z elemento di S è il suo predecessore se y=f (z). Costruiamo le sequenza di predecessori che possono iniziare in S, in T oppure in alcuno dei due. Inoltre potremo avere anche sequenze di tre termini chiuse con il termine con cui iniziano. Diremo S-stopper una sequenza del primo tipo, T-stopper una sequenza del secondo tipo, doppiamente infinita una del terzo tipo e ciclica una del quarto.

• Come dividere un brano in sequenze
• Come riconoscere le sequenze in un testo