Lezione 23

Il lemma di Zorn

Definizione 23.1   Sia $X$ un insieme e sia $\preccurlyeq$ un ordinamento parziale su $X$. Diremo che $x_0\in X$ è un maggiorante di $Y\subseteq X$ se e solo se $y \preccurlyeq x_0$ per ogni $y\in Y$.

Diremo che $Y\subseteq X$ è una catena se è totalmente ordinato da $\preccurlyeq$, ossia se

$$\forall y_1,y_2\in Y \quad y_1\preccurlyeq y_2$$    o $$y_2\preccurlyeq y_1$$

Un elemento $x_0\in X$ sarà detto massimale se

$$\forall x \in X\quad x_0 \preccurlyeq x \Rightarrow x=x_0$$

ossia non esiste in $X$ niente di strettamente più grande di $x_0$.

Osservazione 23.2   Si osservi che essere massimale non implica massimo, ($x_0$ è massimo se $x\preccurlyeq x_0$ per ogni $x\in X$). Potrebbero infatti esserci elementi massimali diversi ma non confrontabili tra loro. Si consideri ad esempio l'ordinamento $\to ^*$ sui vertici dell'albero radicato $(T,r)$ essendo $V(T)=\{r,a,b\}$ e $E(T)=\{\{r,a\},\{r,b\}\}$ (vedi figura 14). Evidentemente $a$ e $b$ sono entrambi massimali, ma non $a\not\to^* b$ e $b \not\to^* a$.

Figura 14: L'albero dell'esempio 23.2

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.

Teorema 23.3 (Lemma di Zorn)   Sia $X$ un insieme non vuoto e sia $\preccurlyeq$ un ordinamento parziale su $X$. Se ogni catena di $X$ ammetta un maggiorante, allora $X$ ha elementi massimali (se per ogni catena $Y\subseteq X$ esiste $x\in X$ maggiorante di $Y$, allora esiste $x_0\in X$ massimale).

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.

Esistenza di alberi generatori: il caso infinito

Teorema 23.4   Sia $G$ un grafo connesso non vuoto. Allora $G$ ha un albero generatore.

Dimostrazione.  Consideriamo l'insieme

$${\cal T}=\{T\mid T$$ è un albero sottografo di $$G\}$$

Chiaramente ${\cal T}\ne\varnothing$, dato che se $v$ è un vertice di $G$, allora il grafo $(\{v\},\varnothing )\in{\cal T}$.

Definiamo la relazione $\preccurlyeq$ su ${\cal T}$, ponendo per ogni $T_1,T_2\in{\cal T}$

$$T_1\preccurlyeq T_2 \iff T_1$$    è sottografo di $$T_2$$

ovvero

$$T_1\preccurlyeq T_2 \iff V(T_1)\subseteq V(T_2)$$    e $$E(T_1)\subseteq E(T_2)$$

Chiaramente $\preccurlyeq$ è un ordinamento parziale su ${\cal T}$.

Proviamo che tale ordinamento verifica le ipotesi del lemma di Zorn. Sia ${\cal S}\subset {\cal T}$ una catena e proviamo che ha un maggiorante. Poniamo

$$\overline{S} = \Big(\bigcup_{T\in{\cal S}} V(T),\bigcup_{T\in{\cal S}} E(T)\Big)$$

Chiaramente, se $\overline{S}\in {\cal T}$ allora è un maggiorante, dato che se $S\in {\cal S}$, allora

$$V(S) \subseteq \bigcup_{T\in{\cal S}} V(T) = V(\overline{S})$$

$$E(S) \subseteq \bigcup_{T\in{\cal S}} E(T) = E(\overline{S})$$

ossia $S \preccurlyeq \overline{S}$.

Proviamo nell'ordine che $\overline{S}$ è un grafo, che è un sottografo di $G$, che è connesso e che non ha cicli.

$\overline{S}$ è un grafo. Se $e \in E(\overline{S})$ allora esiste $S\in {\cal S}$ tale che $e\in E(S)$. Dato che $S$ è un grafo allora $E(S)\subseteq{V(S) \choose 2}$, e dato che $V(S)\subseteq V(\overline{S})$ allora ${V(S) \choose 2}\subseteq {V(\overline{S}) \choose 2}$. Quindi $e\in {V(\overline{S}) \choose 2}$, e per l'arbitrarietà di $e \in E(\overline{S})$ si ha che $E(\overline{S})\subseteq {V(\overline{S}) \choose 2}$.

$\overline{S}$ è un sottografo di $G$. Dato che ogni $S$ è sottografo di $G$, si ha che per ogni $T\in{\cal S}$ si ha che $V(T)\subseteq V(G)$ e $E(T)\subseteq E(G)$, da cui segue immediatamente che $V(\overline{S})=\bigcup_{T\in {\cal S}}V(T)\subseteq V(G)$ $E(\overline{S})=\bigcup_{T\in {\cal S}}E(T)\subseteq E(G)$.

$\overline{S}$ è connesso. Siano $v,w\in V(\overline{S})$, allora esistono $T_1,T_2\in {\cal S}$ tali che $u\in V(T_1)$ e $w\in V(T_2)$. Dato che ${\cal S}$ è totalmente ordinato da $\preccurlyeq$ uno tra $T_1$ e $T_2$ è più grande dell'altro. Supponiamo che sia $T_1\preccurlyeq T_2$. Aallora $V(T_1)\subseteq V(T_2)$ e quindi $v,w\in V(T_2)$. Dato che $T_2$ è un albero, esiste un cammino in $T_2$ che congiunge $v$ a $w$, sia questo $(v=v_0,v_1,\dots,v_k=w)$. Tale cammino è un cammino anche in $\overline{S}$ dato che per ogni $i$ si ha che $v_i\in V(T_2)\subseteq V(\overline{S})$ e $\{v_i,v_{i+1}\}\in E(T_2)\subseteq E(\overline{S})$.

$\overline{S}$ non ha cicli. Supponiamo per assurdo che $\overline{S}$ abbia un ciclo $(v_0,v_1,\dots,v_k=v_0)$. Per ogni $i$ $v_i\in V(\overline{S}$, quindi esiste un $T_i\in {\cal S}$ tale che $v_i\in V(T_i)$. Usando iterativamente il fatto che a due a due i $T_i$ sono uno più grande dell'altro, se ne trova uno che è più grande di tutti gli altri, ossia esiste $j$ tale che $T_i\preccurlyeq T_j$ per ogni $i$. In modo analogo per ogni lato $\{v_i,v_{i+1}\}\in E(\overline{S})$ e quindi per ogni $i$ esiste un $S_i\in{\cal S}$ tale che $\{v_i,v_{i+1}\}\in E(S_i)$. In modo analogo a quanto fatto sopra si trova un $h$ tale che $S_i\preccurlyeq S_h$ per ogni $i$. Detto infine $U$ il più grande tra $S_h$ e $T_j$ si ha che per ogni $i$ si ha che

$$T_i \preccurlyeq U \Rightarrow V(T_i)\subseteq V(U) \Rightarrow v_i\in V(U)$$

$$S_i \preccurlyeq U \Rightarrow V(S_i)\subseteq V(U) \Rightarrow \{v_i,v_{i+1}\}\in E(U)$$

Ma allora $(v_0,v_1,\dots,v_k=v_0)$ sarebbe un ciclo in $U$, ma ciò è assurdo dato che $U$ è un albero.

Siamo allora nelle ipotesi per applicare il lemma di Zorn. Sia allora $T\in {\cal T}$ un elemento massimale. Quindi $T$ è un albero che è un sottografo di $G$, massimale rispetto all'ordinamento $\preccurlyeq$. Proviamo che $V(T)=V(G)$. Per assurdo, sia $v\in V(G)$ ma $v\notin V(T)$. Dato che $G$ è connesso (è qui che si usa la connessione di $G$), preso $w\in V(T)$ esiste un cammino $(v=v_0,\dots,v_k=w)$, sia allora $i$ tale che $v_i\notin V(T)$ e $v_{i+1}\in V(T)$. Allora il grafo $T'=\Big(V(T)\cup\{v_{i+1}\},E\cup\big\{\{V_i,v_{i+1}\}\big\}\Big)$ sarebbe ancora un elemento di ${\cal T}$, sarebbe diverso da $T$ e $T \preccurlyeq T'$, che è contro la massimalità di $T$.     $\square$

Esercizio 23.1   Sia $\{G_i\}_{i\in I}$ un insieme di grafi, e si ponga

$$\bigcup_{i\in I} G_i = \Big( \bigcup_{i\in I}V(G_i), \bigcup_{i\in I}E(G_i)\Big)$$

$$\bigcap_{i\in I} G_i = \Big( \bigcap_{i\in I}V(G_i), \bigcap_{i\in I}E(G_i)\Big)$$

Si provi che $\bigcup_{i\in I} G_i$ e $\bigcap_{i\in I} G_i$ sono grafi.

Si provi inoltre che se i $G_i$ sono tutti connessi e $V(G_i)\cap V(G_j)\ne\varnothing$ per ogni $i,j\in I$ allora $\bigcup_{i\in I} G_i$ è connesso.

Resta vero l'enunciato precedente se si sostituisce la parola connesso con $2$-connesso? In caso di risposta negativa si determini l'ipotesi giusta affinché lo sia.
Soluzione