mercoledì 24 settembre 2008

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è aa
  • antisimmetrica: se a è in relazione con b e b in relazione con a, allora a è uguale a b; in formule: se ab e ba, 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  ab e bc, allora ac.

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

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, AA è l'insieme degli elementi che fanno parte di una partita che ha avuto inizio in A, e analogamente AB è 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', BA e BB”.

“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 AA”.

“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 BA, 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 BA sono iniziate in A”.

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

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

“Immagino che il problema salti fuori con AB e BB”.

“Sì, perché in questo caso da BB 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 AB, 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 AB e BB. In questo caso calcolare g-1(a) significa prendere un elemento a di AB e tornare indietro verso BB, 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 AB”.

“Esattamente. Se noti, c'è una simmetria in questa dimostrazione: uso f per AA e BA, uso g per AB e BB. 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”.

10 commenti:

giovanna ha detto...

ah, bella dimostrazione del "teoremone":-)
Prof, la funzione φ (a proposito, io sul mio blog non riesco a scrivere le lettere greche, neppure con copia incolla - ho provato con pi-greco - come fai? qui ho copincollato) ..
è detta bigettiva? E' bruttino il nome vero? non l'hai utilizzato... (te l'avevo detto, ho cercato....:-))

zar ha detto...

Bigettiva è sinonimo di biunivoca. Sarebbe biiettiva, che gli ottocentisti (che non sono quelli che corrono gli ottocento metri, ma quelli che amano scrivere come si faceva nell'ottocento) scrivono bijettiva. Poi qualcuno vede la j e la legge come se fosse una g (facendosi anche ridere dietro un pochino). Purtroppo wikipedia spesso riporta la parola bigettiva.

Per quanto riguarda le lettere greche, io non ho installato quell'estensione java per le formule in TeX, e uso le "html entities". Credo si chiamino così, comunque per scrivere π devo digitare "π", per φ invece "φ", e così via.

Vedi per esempio qua (cerca con google "html entities" oppure "html character codes").

giovanna ha detto...

giusto!
su wikipedia riporta bigettiva ma da altre parti ho trovato anche biiettiva. Ok!

Per le lettere greche: grazie per l'info.
Sì, laTex, ma visto che io ho il caricamento lento della pagina :-(, mi pareva uno "spreco" utilizzarlo per scrivere semplicemente il π.
ora vado a vedere le tue indicazioni.
a presto!

.mau. ha detto...

in tutti i miei appunti universitari ho sempre scritto bijettiva. Mi stai dando del decrepito? :-)

zar ha detto...

Spero, almeno, che tu non lo pronunciassi con la "g" :-)

Però eri in toscana, lì magari dicevano "bisgettiva" (dove con "sg" intendo un suono intermedio tra "g" e "sh").

giovanna ha detto...

[OT]
prof aiuto!
ho sostituito i simboli "x" nelle mie laTex, con il tuo suggerimento, \times.
a meno che non sia un mio problema di caricamento pagina, vedo che in una formula (π/2 =) funziona bene con i primi due fattori, cioè 2 x 2, poi per gli altri ...no!
Ti chiederei la cortesia di dare uno sguardo tu, e/o se si spiega in qualche modo.
Le formule sono davvero più carine a vedersi!
grazie prof.

zar ha detto...

Vedo anche io male. Ma se provo a guardare il sorgente della pagina, vedo degli strani tag "sotto" aperti e chiusi inframezzati al codice LaTeX. Non capisco che roba sia.

giovanna ha detto...

Prof, grazie,
ho risolto però.
c'era un \times al numeratore che risultava non seguito da un fattore. Probabilmente si trattava di questo. l'ho tolto, ora pare ok!
grazie ancora!
il fatto del sorgente pagina... non so neppure io :-)
dò una sbirciata... bo..

Geko ha detto...

Perchè oggigiorno gli insegnanti non usano più il Dialogo, ma si fissano con i Monologhi???? Ahahahah!! Professore, non la conosco, ma il suo stile è degno di Galileo!!!

zar ha detto...

Eh, grazie...