Lezione 22 (30 maggio 2001 h. 10.30-11.30)

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:

$$\begin{eqnarray*}v \to^+ w &\iff& \exists v_0,\dots,v_n\in V : v=v_0\to v_1\to\d... ... v_n=w\\ v \to^* w &\iff& v\to^+ w \hbox{\rm { oppure }} v = w \end{eqnarray*}$$

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₀ (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₀) 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).

  

Figure 10: 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) \hbox{\rm { e }} \big\{v\in V(T) \bigm \vert f(n)\to^* v\big\} \hbox{\rm { \\lq e 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$