Diremo che è una catena se è totalmente ordinato da
, ossia se
Un elemento sarà detto massimale se
Enunciamo ora un teorema di cui omettiamo la dimostrazione, ma che è uno degli strumenti più potenti per dimostrare l'esistenza di ``oggetti'' che sono in qualche senso più grandi possibili. Daremo subito nel seguito un'applicazione di tale teorema.
L'unica osservazione che facciamo sulla dimostrazione di questo teorema, è che essa usa im modo sostanziale l'assioma della scelta, anzi si può dimostrare che il lemma di Zorn è equivalente all'assioma della scelta. Si osservi che come l'assioma della scelta anche il lemma di Zorn ha una natura non costruttiva: garantisce l'esistenza di elementi massimali, ma non dà alcuna ``ricetta'' per individuarli.
Dimostrazione.
Consideriamo l'insieme
Definiamo la relazione su
, ponendo per ogni
Proviamo che tale ordinamento verifica le ipotesi del lemma di
Zorn. Sia
una catena
e proviamo che ha un maggiorante.
Poniamo
Proviamo nell'ordine che è un grafo, che è un sottografo di
,
che è connesso e che non ha cicli.
è un grafo. Se
allora esiste
tale che
. Dato che
è un grafo allora
, e dato che
allora
. Quindi
, e per l'arbitrarietà di
si ha che
.
è un sottografo di
. Dato che ogni
è
sottografo di
, si ha che per ogni
si ha che
e
, da cui segue immediatamente che
.
è connesso. Siano
, allora
esistono
tali che
e
. Dato che
è totalmente ordinato da
uno tra
e
è più grande
dell'altro. Supponiamo che sia
. Aallora
e quindi
. Dato che
è un albero, esiste un
cammino in
che congiunge
a
, sia questo
.
Tale cammino è un cammino anche in
dato che per ogni
si ha che
e
.
non ha cicli. Supponiamo per assurdo che
abbia un ciclo
. Per ogni
,
quindi esiste un
tale che
. Usando iterativamente il
fatto che a due a due i
sono uno più grande dell'altro, se ne trova uno
che è più grande di tutti gli altri, ossia esiste
tale che
per ogni
. In modo analogo per ogni lato
e quindi per ogni
esiste un
tale
che
. In modo analogo a quanto fatto sopra si
trova un
tale che
per ogni
. Detto infine
il
più grande tra
e
si ha che per ogni
si ha che
Siamo allora nelle ipotesi per applicare il lemma di Zorn. Sia allora un elemento massimale.
Quindi
è un albero che è un sottografo di
, massimale rispetto
all'ordinamento
. Proviamo che
. Per assurdo, sia
ma
. Dato che
è connesso (è qui che si usa la
connessione di
), preso
esiste un cammino
,
sia allora
tale che
e
. Allora il grafo
sarebbe
ancora un elemento di
, sarebbe diverso da
e
, che
è contro la massimalità di
.
Si provi inoltre che se i sono tutti connessi e
per ogni
allora
è connesso.
Resta vero l'enunciato precedente se si sostituisce la parola connesso con
-connesso? In caso di risposta negativa si determini l'ipotesi giusta
affinché lo sia.
Soluzione