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.

• Quaderno a quadretti
• Calcolatrice scientifica
• Matita
• gomma
• PC
• Connessione internet

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.

La dimostrazione di Dedekind del teorema di Cantor-Bernstein si basa sulla sua teoria delle catene, non sul principio di buon ordinamento di Cantor. Un'attenta analisi della dimostrazione estrae una struttura argomentativa che può essere vista nelle molte altre dimostrazioni che sono state fornite da allora. Sostengo che ci sia essenzialmente una prova che arriva in due varianti dovute rispettivamente a Dedekind e Zermelo. Questo articolo è un caso di studio sull'analisi delle dimostrazioni di un singolo teorema all'interno di un dato quadro metodologico, qui la teoria degli insiemi di Zermelo ? Fraenkel (ZF). Utilizza strumenti della teoria della dimostrazione, ma si concentra su idee euristiche che modellano le dimostrazioni e su strategie logiche che aiutano a costruirle. È radicato in una prospettiva su Beweistheori e ciò precede la sua stretta connessione e l'attenzione quasi esclusiva agli obiettivi del programma di coerenza finitista di Hilbert. Questa prospettiva precedente può essere realizzata (solo) con il supporto di potenti strumenti computazionali. 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.

Il teorema di Cantor-Bernstein (CBT) o Schröder-Bernstein teorema o, semplicemente, l' equivalenza teorema afferma l'esistenza di una biiezione tra due insiemi un e b , assumendo la presenza di iniezioni f e g da una a b e da b ad una , rispettivamente. Dedekind fu il primo a dimostrare il teorema senza fare appello al principio di buon ordinamento di Cantor in un manoscritto del 1887. La dimostrazione fu pubblicata con una nota di Emmy Noether nel terzo volume della sua Gesammelte matematische Werke. In una lettera del 29 agosto 1899, Dedekind comunicò a Cantor una prova leggermente diversa; la lettera è stata inclusa nella Gesammelte Abhandlungen di Cantor con Zermelo come editore. Zermelo menziona nella sua Nota alla corrispondenza che non era a conoscenza della dimostrazione di Dedekind quando, pubblicò la propria dimostrazione e fece esplicito appello alla teoria della catena di Dedekind. Noether afferma nella sua Nota che la prova di Dedekind è "esattamente la stessa" di Zermelo, mentre Zermelo considera più cautamente le due prove come solo "inessenzialmente diverse".La biiezione h *: a? ?? d che si ottiene 'dal diagramma' è appunto quella di Dedekind, così come è definita da h * ( x ) =? h ( x ) se x è in ? [ h n [ a ? d ] |?n ??] e h * ( x ) =? id ( x ) se x è in a ? ? [ h n [ a ? d ] | n ? N]. Tuttavia, Dedekind voleva evitare qualsiasi appello ai numeri naturali nello sviluppo della sua teoria generale delle catene; dopotutto, i numeri naturali dovevano essere fondati su di esso. Una volta che i numeri naturali era stata data una caratterizzazione catena teoria, Dedekind stabilito che l'approssimazione dal basso e dall'alto (come l'intersezione di tutte le catene contenenti un ? d e chiuso sotto h ) cede lo stesso insieme. Quest'ultima caratterizzazione verrà discussa di seguito per affrontare le due questioni problematiche e profondamente correlate che ho appena indicato: un'esplicita definizione teorica degli insiemi di c e c * così come la dimostrazione delle identità strutturali.

• Lemma fondamentale : sia h una biiezione da a a e e sia d un insieme con e  ⊆  d  ⊆  a ; poi c'è una biiezione da a a d.

• Teorema di Cantor-Bernstein-Schröder

• Come riconoscere le sequenze in un testo