Lezione 22

L'ordinamento degli alberi radicati

Sia $(T,r)$ un albero radicato, sull'insieme dei vertici si definiscono le due relazioni $\to^+$ e $\to ^*$, ovvero la chiusura transitive e la chiusura transitiva e riflessiva della relazione $\to$ di paternità ponendo:

$$v \to^+ w \iff \exists v_0,\dots,v_n\in V : v=v_0\to v_1\to\dots \to v_n=w$$

$$v \to^* w \iff v \to^+ w v = w$$

Proposizione 22.1   La relazione $\to ^*$ è un ordinamento parziale. E la relazione $\to^+$ è l'ordinamento stretto associato a $\to ^*$ ossia $v\to ^+ w$ se e solo se $v \to^* w$ e $v \ne w$.

Dimostrazione. 

    $\square$

Induzione sugli alberi radicati

Teorema 22.2   Sia $(T,r)$ un albero radicato e per ogni $v\in V(T)$ sia $P(v)$ una proposizione. Si supponga che:

1. $P(r)$ sia vera;
2. per ogni $v,w\in V(T)$ tali che $v\to w$ si ha che $P(v)\Rightarrow P(w)$

. Allora $P(v)$ è vera per ogni $v\in V(T)$.

Teorema 22.3 (Induzione sugli alberi)   Sia $(T,r)$ un albero radicato e per ogni $v\in V(T)$ sia $P(v)$ una proposizione. Si supponga che:

1. $P(r)$ sia vera;
2. per ogni $v\in V(T)$ si ha che $(\forall w \to^+ w P(w))\Rightarrow P(v)$. Allora $P(v)$ è vera per ogni $v\in V(T)$.

Dimostrazione. 

    $\square$

Osservazione 22.4   Si osservi che nella dimostrazione del teorema precedente non si è mai usato il fatto che si stesse parlando di alberi radicati, ma soltanto che $\to ^*$ fosse un ordinamento ben fondato ovvero che ogni successione discendente ha minimo, e che tutto l'insieme dei vertici ha un minimo rispetto a tale ordinamento. La stessa dimostrazione può quindi essere usata per dimostrare il seguente teorema di induzione per insiemi ben fondati.

Definizione 22.5   Sia $X$ un insieme e sia $\preccurlyeq$ un ordinamento parziale su $X$. Diremo che $\preccurlyeq$ è ben fondato se ogni successione discendente ha minimo, ossia se per ogni $n\in \mathbb{N}$ $x_n\in X$ sono tali che $x_{n+1}\preccurlyeq x_n$ allora esiste un $\overline{n}$ tale che $x_{\overline{n}} \preccurlyeq x_n$ per ogni $n\in \mathbb{N}$ (in particolare se $n\succcurlyeq \overline{n}$ allora $x_n=x_{\overline{n}}$)).

Teorema 22.6 (Induzione ben fondata)   Sia $X$ un insieme e sia $\preccurlyeq$ un ordinamento ben fondato su $X$ cha ammette minimo $x_0$ (i.e.esiste $x_0\in X$ tale che $x_0\preccurlyeq x$ per ogni $x\in X$). Per ogni $x\in X$ sia $P(x)$ una proposizione. Si supponga che:

1. $P(x_0)$ sia vera;
2. per ogni $x\in V(T)$ si ha che $(\forall y \prec x P(y))\Rightarrow P(x)$ (dove $\prec$ è una abbreviazione per $\preccurlyeq$ e $\neq$).

Allora $P(x)$ è vera per ogni $x\in X$.

Il lemma di König

Domanda. È vero che in un albero infinito esiste un ramo infinito?

Per ramo infinito intendiamo un cammino infinito (i.e. un sottografo isomorfo a $P_\infty$).

In generale la risposta a questa domanda è negativa. Si consideri ad esempio il grafo $G=(\mathbb{N},\{\{0,i\}\mid i\ge 1\}$ (vedi figura).

Figura 13: Un contresempio al Lemma di König, senza l'ipotesi dei gradi finiti

$G$ è un albero. Infatti $G$ è connesso dato che ogni vertice è congiungibile al vertice 0. Inoltre se $e=\{0,i\}$ è un lato, allora $G-e=(\mathbb{N}-\{0,i\},\varnothing )$ che è sconnesso. Quindi $G$ è un albero per la terza delle proprietà caratterizzanti degli alberi.

D'altra parte i cammini più lunghi che si possono trovare sono i cammini del tipo $(i,0,j)$ con $i\ne j$, che hanno lunghezza $2$.

Il problema sta nel fatto che nell'albero dell'esempio c'è un vertice di grado infinito (su 0 arrivano infiniti lati). In effetti vale il seguente teorema:

Teorema 22.7 (Lemma di König)   Sia $T$ un albero infinito tale che ogni vertice ha grado finito, allora $T$ ha rami infiniti.

Dimostrazione.  Fissiamo una radice $r$ per $T$ e sia $\to$ la relazione di paternità indotta da tale radice. Costruiremo una funzione $f:\mathbb{N}\to V(T)$ con la seguente proprietà:

$$f(n-1) \to f(n)$$    e $$\big\{v\in V(T) \bigm \vert f(n)\to^* v\big\}$$    è infinito$$\forall n \ge 1$$

Chiaramente, una tale funzione risolve il problema.

Definiamo $f$ ricorsivamente. Poniamo $f(0)=r$. Chiaramente i discendnti di $f(0)$ sono infiniti (tutti i vertici sono discendenti della radice).

Supponiamo di aver definito $f(n)$ (che sia figlio di $f(n-1)$ e che abbia una discendenza infinita). Per ipotesi $\deg(f(n))$ è finito, siano quindi $v_1,\dots,v_k$ i figli di $f(n)$ (i.e. $f(n)\to v_i$). Per ogni $i=1,\dots,k$ sia

$$V_i=\big\{v\in V(T)\bigm\vert v_i\to^* v\}$$

Chiaramente

$$\big\{v\in V(T) \bigm \vert f(n)\to^* v\big\} = \{f(n)\} \cup V_1\cup\dots\cup V_k$$

Pertanto esiste un $i$ tale che $V_i$ è infinito. Basta allora porre $f(n+1)=v_i$. Chiaramente $f(n)\to f(n+1)$ e la discendenza di $f(n+1)$, che è $V_i$, è infinita.     $\square$