Verso l'infinito, ma con calma - facciamo ordine

Una relazione d'ordine è una relazione che gode di tre proprietà:

• riflessiva: ogni elemento è in relazione con sé stesso, cioè a ≤ a
• antisimmetrica: se a è in relazione con b e b in relazione con a, allora a è uguale a b; in formule: se a ≤ b e b ≤ a, allora a = b
• transitiva: se a è in relazione con b e b in relazione con c, allora a è in relazione con c; in formule: se  a ≤ b e b ≤ c, allora a ≤ c.

Se esistesse una relazione d'ordine anche tra i numeri cardinali, allora da c ≤ 2^ℵ₀ e 2^ℵ₀ ≤ c potremmo dedurre che c = 2^ℵ₀.

La relazione d'ordine, effettivamente, esiste, ed è definita così: Card(A) è minore o uguale di Card(B) se esiste una funzione iniettiva da A verso B.

Dimostrare la proprietà riflessiva è semplice: esiste certamente una funzione iniettiva da A verso A, è l'identità (cioè la funzione che a ogni elemento associa sé stesso. Funzione che è biunivoca, quindi certamente iniettiva).

Anche per quanto riguarda la proprietà transitiva non ci sono problemi: se esistono una funzione f iniettiva da A verso B e una g iniettiva da B verso C, ne esiste una da A direttamente verso C, basta comporre le due.

È la proprietà antisimmetrica quella che dà più problemi. Per dimostrarla immaginiamo una partita di ping pong.

“Ping pong?”.

“Lo so che si dice tennis tavolo, ma mi piaceva di più dire ping pong”.

“Vabbè, ma cosa c'entra il ping pong?”.

“Le nostre ipotesi sono queste: esiste una funzione f iniettiva da A a B, ed esiste una funzione g iniettiva da B a A”.

“Ok, e la tesi è che esiste una funzione biunivoca da A a B. Ma il ping pong?”.

“Un momento che arrivo. Immagina di prendere un elemento di A qualsiasi”.

“Bene. Lo chiamiamo a?”.

“Chiamiamolo pallina”.

“Non starai esagerando con i nomi esotici?”.

“Questa pallina viene mandata da f in B, giusto?”.

“Giusto. Volendo, potremmo anche dire che viene rimandata da g in A”.

“Perfetto, ecco la tua partita di ping pong. La pallina si trova in A, poi con f(pallina) la mandiamo in B, poi con g(f(pallina)) di nuovo in A, e così via”.

“Non cade mai questa pallina?”.

“Mai”.

“La partita allora è un po' noiosa”.

“Già. Ma invece di seguire la pallina in avanti, vediamo il suo percorso all'indietro”.

“In che senso?”.

“Nel senso che se la pallina ora si trova in A, può darsi che prima si trovasse in B”.

“Come può darsi? Certamente viene da B, no?”.

“Non è detto. Chi l'avrebbe mandata da B verso A?”.

“La funzione g”.

“Vuoi dire che ogni elemento che si trova in A proviene da qualche elemento di B tramite la funzione g?”.

“Eh, sì”.

“Quindi vuoi dire che la funzione g è suriettiva”.

“Sì. Ah, non l'abbiamo detto nelle ipotesi. Abbiamo detto solo che g è iniettiva”.

“Dunque tutti gli elementi di B sono mandati in A, ma non è detto che ogni elemento di A provenga da qualche elemento di B”.

“Ho capito. Immagino che questo valga anche per la funzione f?”.

“Certo. Tornando alla nostra pallina, e seguendo il suo percorso all'indietro, potremmo dire che è partita dall'insieme A, oppure che è partita da B, oppure che non ha avuto un punto di partenza”.

“Quest'ultimo caso non mi è chiaro”.

“Vuol dire che, andando all'indietro, potresti non trovare mai un'origine. La pallina è sempre stata in gioco. Cioè puoi sempre andare indietro nella catena di funzioni f e g”.

“Uhm, una partita eterna”.

“Non solo: una partita eterna senza inizio, mentre gli altri due tipi un inizio ce l'avevano”.

“Va bene”.

“Allora abbiamo diviso l'insieme A in tre parti: A' è l'insieme degli elementi che fanno parte di una partita senza inizio, A_A è l'insieme degli elementi che fanno parte di una partita che ha avuto inizio in A, e analogamente A_B è l'insieme degli elementi che fanno parte di una partita che ha avuto inizio in B”.

“Mamma mia. Credo di esserci: tre tipi di partite, tre parti di un insieme”.

“Sì. E osserva che sono tre parti che non hanno nulla in comune: un elemento può appartenere solo a una delle tre”.

“Ok, se fai parte di una partita che è iniziata in A non puoi far parte anche di una partita senza inizio o con inizio in B”.

“Bene. Ora suddividiamo allo stesso modo anche B, ottenendo i tre insiemi B', B_A e B_B”.

“Perfetto. Mi pare infatti che non ci sia un ruolo privilegiato tra A e B, dovrebbero essere interscambiabili”.

“Giusto. Infatti la proprietà che stiamo dimostrando, pur chiamandosi antisimmetrica, è simmetrica”.

“E non potevamo chiamarla simmetrica?”.

“No, la proprietà simmetrica è un'altra, ricordi le relazioni di equivalenza?”.

“Va bene. Ora cosa facciamo con questi insiemi divisi in tre?”.

“Ora definiamo la corrispondenza biunivoca tra i due. E lo facciamo in tre passi, uno per ogni parte in cui abbiamo diviso i due insiemi”.

“Va bene. Cominciamo da A'?”.

“Sì. Diamo anche un nome alla corrispondenza biunivoca che stiamo definendo: la chiamiamo φ. Allora, se a è un elemento di A, definiamo φ(a) = f(a)”.

“Cioè la nuova funzione biunivoca è uguale alla vecchia f, che era iniettiva?”.

“Sull'insieme A', è così. L'elemento a appartiene a una partita senza inizio, e viene mandato in B', che contiene elementi che fanno anch'essi parte di una partita senza inizio. Siccome non c'è inizio, si può sempre tornare indietro partendo da B', e quindi in questo insieme la funzione f è biunivoca”.

“Va bene, quindi un pezzo è fatto, hai definito una funzione biunivoca tra A' e B'”.

“Ora prendiamo un elemento a appartenente a A_A”.

“Quindi un elemento che fa parte di una partita che ha avuto inizio in A”.

“Sì. Anche in questo caso φ(a) = f(a)”.

“Come prima?”.

“Già. Mediante f(a) lo mandiamo in B, anzi, in B_A, dato che la sua partita è iniziata in A, e invertendo f possiamo riportarlo indietro. Non c'è il pericolo che da B non si possa tornare indietro, dato che le partite di tutti gli elementi che fanno parte di B_A sono iniziate in A”.

“Ho capito, se da B_A possiamo sempre tornare indietro, allora f è biunivoca anche qui”.

“Sì, quindi la funzione φ che stiamo definendo è biunivoca anche tra A_A e B_A”.

“Immagino che il problema salti fuori con A_B e B_B”.

“Sì, perché in questo caso da B_B non è detto che si possa tornare indietro: qualche suo elemento potrebbe costituire l'inizio di una nuova partita”.

“E allora come facciamo?”.

“In questo caso ribaltiamo il problema: se prima abbiamo usato f per andare da A verso B, ora usiamo g”.

“Uhm, in che modo?”.

“Per quanto riguarda l'insieme A_B, definiamo φ(a)=g^-1(a)”.

“Cosa intendi con quell'esponente -1?”.

“Intendo la funzione inversa di g: se g va da B verso A, g^-1 va da A verso B”.

“Ehi, però non sappiamo se g è biunivoca. Anzi, se lo fosse il teorema sarebbe già dimostrato”.

“Giustissimo, infatti non è detto che sia biunivoca. Ma tieni presente che ora stiamo ragionando solo sugli insiemi A_B e B_B. In questo caso calcolare g^-1(a) significa prendere un elemento a di A_B e tornare indietro verso B_B, e questo si può sempre fare perché la partita di cui fa parte a ha avuto origine in B”.

“Ah! E quindi non c'è pericolo che a si blocchi in A_B”.

“Esattamente. Se noti, c'è una simmetria in questa dimostrazione: uso f per A_A e B_A, uso g per A_B e B_B. Per A' e B' ho usato ancora f, ma avrei potuto usare indifferentemente anche g, dato che in questo caso non c'è mai pericolo di non tornare indietro”.

“Ah, bello. Comincio a capire il concetto di eleganza in matematica”.

“E alla fine abbiamo dimostrato anche la proprietà antisimmetrica”.

“Era questo il teorema dal nome altisonante di cui mi avevi parlato?”.

“Sì, si chiama teorema di Cantor-Bernstein-Schröder. Inizialmente Cantor ne aveva data una dimostrazione che faceva uso dell'assioma della scelta, e che aveva anche una tesi più forte”.

“In che senso?”.

“Nel senso che dimostrava anche qualcosa di più, e cioè che l'ordinamento tra i cardinali è totale. Significa che due cardinali sono sempre confrontabili, cosa che ora non abbiamo invece dimostrato. Sarebbe la famosa proprietà di tricotomia”.

“Che a me sembrava tanto ovvia”.

“E che invece è equivalente all'assioma della scelta. Se è ovvia quella, allora è ovvio anche il paradosso di Banach-Tarski”.

“Povero me. Penso che farò come fanno i Veri Matematici”.

“Già. A volte far finta di niente è comodo”.