Lezione 23 (30 maggio 2000 h. 11-13)

   
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 \hbox{\rm { 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₀.

Osservazione 23.2   Si osservi che essere massimale non implica massimo, (x₀ è 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 12). Evidentemente a e b sono entrambi massimali, ma non $a\not\to^* b$ e $b \not\to^* a$.

  

Figure 12: 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\hbox{\rm { \\lq e 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 \hbox{\rm { \\lq e sottografo di }} T_2$$

ovvero

$$T_1\preccurlyeq T_2 \iff V(T_1)\subseteq V(T_2) \hbox{\rm { 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

$$\begin{eqnarray*}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}) \end{eqnarray*}$$

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₁ e T₂ è 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₂ è un albero, esiste un cammino in T₂ 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

$$\begin{eqnarray*}T_i \preccurlyeq U &\Rightarrow& V(T_i)\subseteq V(U) \Rightarr... ...ow& V(S_i)\subseteq V(U) \Rightarrow\{v_i,v_{i+1}\}\in E(U) \\ \end{eqnarray*}$$

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

$$\begin{eqnarray*}\bigcup_{i\in I} G_i & = & \Big( \bigcup_{i\in I}V(G_i), \big... ...= & \Big( \bigcap_{i\in I}V(G_i), \bigcap_{i\in I}E(G_i)\Big) \end{eqnarray*}$$

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