Principio del massimo e principio di induzione

[dissonance]

Studiando un po' di Analisi Funzionale mi sono imbattuto in dimostrazioni basate sul principio di massimalità di Hausdorff, come questa che cito -per grandi linee- ad esempio:

Lemma. (Principio di massimalità di Hausdorff)
Ogni insieme parzialmente ordinato ammette un sottoinsieme totalmente ordinato massimale.

Teorema di Hahn-Banach
Sia $X$ uno spazio normato, $M$ un suo sottospazio, $f$ un funzionale lineare continuo definito su $M$. Allora $f$ può essere esteso ad un funzionale lineare $F$ definito su tutto $X$ e con la stessa norma di $f$.
dim. (sketch)
1)Ingrandiamo il sottospazio $M$ di una dimensione ottenendo un sottospazio $M_1$ ($M_1="span"(Muu{x_0})$, dove $x_0$ è un vettore non in $M$). Su $M_1$ si può estendere $f$ ad $f_1$ verificando la tesi.

Ora viene la parte interessante.
Quante dimensioni dobbiamo aggiungere ad $M$ per ottenere $X$?
Se fossero in quantità finita non ci sarebbe da fare altro.
Se fossero in quantità numerabilmente infinita potremmo applicare il principio di induzione.
Ma in generale non abbiamo informazioni su questa cardinalità.

2)Perciò usiamo questa costruzione:
chiamiamo $P$ l'insieme delle coppie $(M', f')$, dove $M\subM'$, $M'$ è un sottospazio, $f'$ estende $f$ ad $M'$ verificando la tesi del teorema. La costruzione di sopra ci dice che questo insieme non si riduce alla sola coppia $(M, f)$ (tranne nei casi banali), ovvero che esistono delle estensioni proprie di $f$ verificanti la tesi. Infine, dotiamo $P$ di un ordinamento parziale nella maniera più ovvia.

E allora, principio del massimo di Hausdorff: 3) in $P$ troviamo una catena $Omega$ massimale. Se denotiamo con $(hat{M}, hat{f})$ gli elementi di $Omega$, unendo tutti gli $hat(M)$ otteniamo ancora un sottospazio, che dimostriamo essere tutto $X$ e sul quale è allora possibile costruire una estensione di $f$ come richiesto dalla tesi. /////

Chiaramente non mi interessa la parte analitica. Ma credo di leggere nella dimostrazione una analogia con il principio di induzione: qui il "passo base" è ovvio (se non aggiungiamo nessuna dimensione ad $M$, ponendo $F=f$ la tesi è verificata dalla coppia $(M, F)$).

Come "passo induttivo" c'è il punto 1), in cui si aggiunge una dimensione. Ci sarebbero gli estremi per il principio di induzione se non fosse che non abbiamo una quantità numerabile di dimensioni da aggiungere - detto altrimenti:
l'insieme $P$ del punto 2) non è necessariamente numerabile.

E allora, invece del principio di induzione usiamo il 3), basato sul principio del massimo di Hausdorff. Fine.

Conclusione.
Mi sbaglio a leggere questa analogia con il principio di induzione? Se no, esiste una formalizzazione di questa tecnica?

[fields]

La tua intuizione e' giusta. Si tratta di applicare l'induzione transfinita.

Pensa a come dimostreresti il principio di Hausdorff.

Poni $F_0=\emptyset$. Se e' massimale sei a posto. Altrimenti esiste $F_1\supset F_0 $ totalmente ordinato. Se $F_1$ e' massimale sei a posto. Altrimenti esiste $F_2\supset F_1$ tale che...

Se ti va male avrai costruito un $F_n$ per ogni $n\in NN$, nessuno dei quali e' massimale. Ma allora prendi $\bigcup_n F_n$, lo chiami $F_{\omega}$ e vai avanti. Crei $F_{\omega+1}\supset F_{\omega}$, $F_{\omega+2}\supset F_{\omega+1}$,.... e dopo tutti questi $F_{\omega +\omega}=\bigcup_n F_{\omega +n}$.

E' evidente che puoi andare avanti cosi' finche' non ti stufi. Alla fine avrai generato cosi' tanti insiemi che avrai esaurito gli elementi nuovi a disposizione e non sara' possibile piu' estendere il tuo $F_\alpha$ "attuale", che sara' massimale.

Questa e' l'induzione transfinita

[gugo82]

Apro e chiudo parentesi: per Hahn-Banach si può usare benissimo anche il lemma di Zorn.

Ad ogni modo, il principio di massimalità di Hausdorff, così come il lemma di Zorn, è una versione mascherata dell'Assioma della Scelta (AC).
E, devo dire la verità, mi stupisce sempre constatare come una cosa "ovvia" come AC possa essere equivalente a tante proposizioni così diverse ed utili (come ad esempio i teoremi di esistenza delle basi negli spazi vettoriali, di esistenza degli ideali massimali in anelli non banali e di Tychonoff).

[dissonance]

Apro e chiudo parentesi: per Hahn-Banach si può usare benissimo anche il lemma di Zorn.

Per curiosità ho dato una scorsa al Brezis Analisi funzionale, e ho visto che segue questa strada. In effetti mi pare di capire che il lemma di Zorn sia una specie di versione moderna del principio di Hausdorff, di respiro più ampio. Ciò nonostante preferisco usare il principio di Hausdorff perché per le mie limitatissime set-theoretic skills è MOLTO più intuitivo.




________________________________________
@ fields: Scusa il ritardo, ho avuto bisogno di TUTTO questo tempo per leggere un po' di materiale sulla set theory (mi sono appoggiato al manuale di topologia di J.Munkres). Non ti nascondo che incontro GRANDE difficoltà su questo argomento, fino al malessere fisico (mal di pancia, colite, eruzioni cutanee).

Vabbé, a parte gli scherzi... Se afferro bene quello che mi vuoi dire, la generalizzazione del principio di induzione c'è, ma è nascosta nella dimostrazione del principio di Hausdorff. Infatti, proviamo a dimostrare (alla buona) questo principio:

Sia $X!=emptyset$ ordinato. Supponiamo che $X$ sia numerabile, ovvero $X={x_1, x_2, ...}$ (non è detto che la numerazione rispetti l'ordine, ovviamente).

Allora è facile: prendiamo un contenitore $B$ e buttiamoci dentro $x_1$. Poi controlliamo $x_2$. E' confrontabile con $x_1$ nella scatola? Se sì lo mettiamo nel contenitore, altrimenti lo buttiamo nella spazzatura. Rifacciamo con $x_3$. E' confrontabile con gli elementi di $B$? eccetera...

Il principio di definizione ricorsiva (cioè sostanzialmente il principio di induzione) ci dice che questo meccanismo funziona, e ci restituisce un insieme totalmente ordinato (per costruzione) e massimale (tutti gli altri elementi di $X$ sono finiti nella spazzatura, e quindi non possiamo aggiungere più nulla alla scatola).

E se $X$ non è numerabile? In quel caso $X={x_1, x_2, ...}$ ce lo scordiamo. Però ci viene in aiuto il teorema del buon ordinamento (ovvero un altro mascheramento -per citare Gugo- di A.C.), che permette di estendere il principio di definizione ricorsiva.

(*) Così $X$ lo indicizzeremo, non più con $NN$ ma con una famiglia di indici $J$ bene ordinata, che esiste per il well-ordering theorem. Su $J$ è definito il concetto di sezione ($S_alpha={j\ :\ j<alpha}$), proprio come in $NN$, e con questo oggetto possiamo introdurre un principio detto General principle of recursive definition. Il resto non sono riuscito a capirlo, ma comunque permette di rifare l'"algoritmo induttivo" di sopra (scatola o spazzatura). E quindi la tesi.

Beh, credo di non sbagliare se dico che questa costruzione è proprio il suggerimento che mi hai dato tu. Quando tu parli di passare dalla numerazione $F_1, F_2, ...$ alla $F_(omega+1), F_(omega+2)...$ e così via, vuoi dire proprio ciò che è scritto al punto (*) (Passare dall'ordinamento di $NN$ a quello di $J$), vero?

[gugo82]

Zorn a volte mi pare più rapido da usare perchè ti fornisce direttamente un elemento massimale, mentre con Hausdorff devi costruirtelo da solo.
Ovviamente questa comodità, di solito, la sconti prima perchè devi provare che ogni parte totalmente ordinata ha un maggiorante...

Però è questione di abitudini, suppongo, e se devo dire la verità mi piace usarli entrambi.

[fields]

Scusa il ritardo, ho avuto bisogno di TUTTO questo tempo per leggere un po' di materiale sulla set theory (mi sono appoggiato al manuale di topologia di J.Munkres). Non ti nascondo che incontro GRANDE difficoltà su questo argomento, fino al malessere fisico (mal di pancia, colite, eruzioni cutanee)

Nonostante le tue difficolta', hai mostrato di aver assimilato le intuizioni fondamentali.

Beh, credo di non sbagliare se dico che questa costruzione è proprio il suggerimento che mi hai dato tu. Quando tu parli di passare dalla numerazione $F_1, F_2, ...$ alla $F_(omega+1), F_(omega+2)...$ e così via, vuoi dire proprio ciò che è scritto al punto (*) (Passare dall'ordinamento di $NN$ a quello di $J$), vero?

Esatto. Il mio suggerimento voleva darti un'intuizione sul fatto che le procedure, le definizioni, le costruzioni possono essere estese oltre l'infinito lineare dei naturali. L'idea e' che la famiglia $J$ rappresenta una successione di "istanti temporali". Ogni sottinsieme proprio $Z$ di $J$ ha un successore $w$, ovvero il piu' piccolo istante che viene dopo tutti gli istanti di $Z$; quindi, supponendo di aver associato una costruzione ad ogni istante di $Z$, tu puoi pensare ad una situazione in cui ogni istante di $Z$ e' trascorso - rappresentata dall'istante $w$ - e associare una nuova costruzione a $w$, che sfrutta tutto il lavoro fatto in $Z$. Questo ti permette di generalizzare il concetto di "costruzione in cui ogni passo di costruzione dipende da un numero finito di passi precedenti", al concetto di "costruzione in cui ogni passo crea qualcosa di nuovo sfruttando tutto il lavoro precedente, che puo' essere anche infinito".

[dissonance]

...Questo ti permette di generalizzare il concetto di "costruzione in cui ogni passo di costruzione dipende da un numero finito di passi precedenti", al concetto di "costruzione in cui ogni passo crea qualcosa di nuovo sfruttando tutto il lavoro precedente, che puo' essere anche infinito".

Fantastico, fields! Pensavo fosse necessario un miracolo per farmi appassionare a questi argomenti. Ma queste tue spiegazioni sono a dir poco illuminanti. Suppongo che sia arrivato il momento di capire che cos'è un ordinale, a questo punto intuisco che sia una maniera per formalizzare quanto fatto. Quindi, per adesso, torno al mio manuale (senza mal di pancia però ).

[fields]

Ok, solo un warning. La moderna trattazione degli ordinali e' molto astratta, ed e' facilissimo perdersi se l'autore non rivela le intuizioni informali alla base. Questo purtroppo accade spesso, per la devastante tendenza bourbakista che affligge molte persone. Per capire gli ordinali bisogna quindi formarsi una propria intuizione informale: grazie a questa, le cose prima impenetrabili, appariranno ovvieta'. Come solo i grandi maestri possono essere chiari e semplici, ecco una gentile introduzione al soggetto (un copia-incolla dal grande Gentzen):

Il concetto di ‘numero ordinale transfinito’ risale a G. Cantor ed in realta' appar-
tiene alla teoria degli insiemi.

I numeri ordinali transfiniti sono costruiti nel seguente modo: prima viene la
successione dei numeri naturali: 1, 2, 3, ecc. Poi viene introdotto un nuovo numero
ω, che per definizione si trova dopo tutti i numeri naturali. ω e' seguito da ω + 1,
quindi da ω + 2, ω + 3, ecc. Al di la' di tutti i numeri della forma ω + n segue ω · 2,
poi ω · 2 + 1, ω · 2 + 2, ecc., dopo di questi ω · 3, quindi ω · 3 + 1, ω · 3 + 2, ecc. Al di
la' di tutti i numeri della forma ω · n + n segue il numero ω^2 , quindi ancora ω^2 + 1,
ω^2 + 2, . . ., ω^2 + ω, ω^2 + ω + 1, ..., ω^2 + ω · 2, ..., ω^2 + ω · 3, ..., ω^2 · 2, ..., ω^2 · 3, ...,
ecc, e finalmente ω^3 , e ancora avanti in questo modo per formare ω^4 , . . ., ω^5 , . . .,
e finalmente ω^ω , e ancora altri numeri, se si desidera. L’intera procedura - che ho
qui solo abbozzato - puo' sembrare disorientante all’inizio. Tuttavia sono coinvolte
fondamentalmente solo due operazioni la cui applicazione ripetuta automaticamente
genera tutti questi numeri:

1. dato un numero gia' esistente, possiamo formare il suo successore (aggiunta di
1);
2. data un’infinita successione di numeri, possiamo formare un nuovo numero che
si trovi al di la' dell’intera successione (passaggio al limite).

La preoccupazione che questa procedura sia non-costruttiva poiche' la concezione
attualista di successione completa dei numeri naturali gia' sembra entrare nella for-
mazione di ω, si rivela infondata. Il concetto di infinito puo', senza dubbio, essere qui
interpretato in modo potenziale dicendo, ad esempio: non importa quanto lontano
possiamo andare nella formazione costruttiva di nuovi numeri naturali, il numero ω
sta nella relazione n < ω con ogni tale numero naturale n. E le successioni infinite
che nascono nella formazione di altri numeri ordinali dovrebbero essere interpretate
precisamente nello stesso modo.

Ora il concetto di ‘induzione transfinita’. Questa induzione e' niente piu' di una
estensione della regola di induzione completa dai numeri naturali ai numeri ordinali
transfiniti. L’induzione completa puo', come noto, essere formulata come segue: se
una proposizione vale per il numero 1, e se e' stato dimostrato che la sua validita' per
tutti i numeri che precedono il numero n si propaga ad n, allora la proposizione vale
per tutti numeri naturali. Se noi rimpiazziamo ‘numeri naturali’ con ‘numeri ordi-
nali transfiniti’, otteniamo la regola di induzione transfinita. Possiamo facilmente
convincerci della correttezza di questa regola per segmenti iniziali della successione dei numeri
transfiniti in questo modo: supponiamo che la proposizione valga per
il numero 1, e che sia stato inoltre dimostrato che se la proposizione vale per tutti
i numeri che precedono un certo numero ordinale vale anche per quel numero or-
dinale. Allora ragioniamo cosı': la proposizione vale per il numero 1 quindi anche
per il numero 2, cosı' anche per il 3, ecc., quindi vale per tutti i numeri naturali.
Conseguentemente vale anche per il numero ω, precisamente perche' vale per tutti
i suoi predecessori. Per la stessa ragione vale anche per il numero ω + 1, cosi' ı per
ω + 2, ecc., e finalmente per ω · 2; e, corrispondentemente, mostriamo la sua validita'
per ω · 3, ω · 4, ecc., e infine per ω^2 . Continuando in questo modo, possiamo convin-
cere noi stessi della validita' della regola di induzione transfinita salendo passo dopo
passo nella successione dei numeri ordinali transfiniti. Come i numeri diventano piu'
grandi, la situazione comincia ad apparire dichiaratamente piu' complicata, ma il
principio rimane sempre lo stesso.

[dissonance]

@ fields: Ti vorrei chiedere una conferma.

Dunque, sto proseguendo la mia lettura. Il testo che sto leggendo, come ho detto, è un manuale di topologia e quindi non approfondisce l'argomento "ordinali" (del resto, al momento non avrei il tempo per una trattazione completa. Mi basta dimostrare principio di Hausdorff e lemma di Zorn). Però pone molto l'accento su questo insieme, che chiama minimal uncountable well-ordered set e indica con $S_Omega\sub[S_Omegauu{Omega}]=bar{S_Omega}$.

La costruzione di questo insieme segue dal well-ordering theorem e non sto a scriverla, ma le proprietà sono:
i) $bar{S_Omega}$ è bene ordinato in maniera tale che $Omega$ sia il massimo;
ii) $S_Omega$ è più che numerabile, ma tutte le sue sezioni sono numerabili.

Domanda: Questo $S_Omega$ è quella $omega$ a cui fa riferimento lo stralcio che hai citato? (quello che c'è "dopo" tutti i numeri naturali).

[fields]

Domanda: Questo $S_Omega$ è quella $omega$ a cui fa riferimento lo stralcio che hai citato? (quello che c'è "dopo" tutti i numeri naturali).

No, $S_\Omega$ corrisponde al famoso - o famigerato - $\aleph_1$. Chi e' costui?

Nel brano che ho riportato, viene descritto il processo di costruzione dei numeri ordinali. Se noti, ognuno degli ordinali "calcolati" nel brano di Gentzen ha la seguente proprieta': l'insieme degli ordinali che lo precedono e' numerabile. $\omega$ e' preceduto da tutti e i soli i naturali; $\omega\cdot 2$ e' preceduto da i naturali piu' gli ordinali della forma $\omega + n$ con $n$ naturale, che sono ancora in quantita' numerabile; etc.

Ora ci potremmo chiedere: con la procedura descritta da Genzten, possiamo spingerci abbastanza lontano nel transfinito fino a costruire un ordinale il cui insieme di predecessori sia non numerabile? La risposta e', sorprendemente, si'. Il piu' piccolo ordinale il cui insieme di predecessori e' non numerabile e' $\aleph_1$, e corrisponde al tuo $S_\Omega$.

PS. Ho definito "famigerato" $\aleph_1$ perche' la famosa ipotesi del continuo afferma che esiste una biettivita' fra $\aleph_1$ e $P(NN)$. Purtroppo il problema non e' decidibile con gli attuali assiomi della teoria degli insiemi...