Lezione 21 (23 maggio 2000 h. 11-33)

L'ordinamento degli alberi radicati

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

Ricordiamo la seguente

Definizione 21.1   Un ordinamento parziale su un insieme X è una relazione $\preccurlyeq$ che sia

1.

riflessiva (i. e. $\forall x\in X \ x\preccurlyeq x$)

2.

antisimmetrica (i.e. $\forall x_1,x_2\in X \ x_1\preccurlyeq x_2$ e $x_2\preccurlyeq x_1\Rightarrow x_1=x_2$ )

3.

transitiva (i.e. $\forall x_1,x_2,x_3\in X \ x_1\preccurlyeq x_2$ e $x_2\preccurlyeq x_3\Rightarrow x_1 \preccurlyeq x_3$)

un ordinamento partziale $\preccurlyeq$ su X si dice un ordinamento totale se in più

4

per ogni $x_1,x_2\in X$ $x_1\preccurlyeq x_2$ oppure $x_2\preccurlyeq x_1$.

Proposizione 21.2   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$

Gli alberi radicati sono ben fondati

Definizione 21.3   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}}$)).

Lemma 21.4   In un albero radicato l'insieme dei predecessori di un vertice è finito. Formalmente, se (T,r) è un albero radicato, allora per ogni $v\in V(T)$ si ha che l'insieme $\{v\in V(T)\mid w \to^* v\}$ è finito.

Dimostrazione. 

    $\square$

Teorema 21.5   L'ordinamento $\to ^*$ è ben fondato.

Dimostrazione. 

    $\square$

Induzione sugli alberi radicati

Teorema 21.6 (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 21.7   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 sull'insieme dei vertici, e che tale insieme possedesse un minimo rispetto a tale ordinamento. La stessa dimostrazione può quindi essere usata per dimostrare il seguente teorema

Teorema 21.8 (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$.