Next: Lezione 23
Up: Matematica Discreta (II modulo)
Previous: Lezione 21
Subsections
Sia
un albero radicato, sull'insieme dei vertici si definiscono le
due relazioni
e
, ovvero la chiusura transitive e la
chiusura transitiva e riflessiva della relazione
di
paternità
ponendo:
Proposizione 22.1
La relazione
![$ \to ^*$](img1733.gif)
è un ordinamento parziale. E la relazione
![$ \to^+$](img1732.gif)
è
l'ordinamento stretto associato a
![$ \to ^*$](img1733.gif)
ossia
![$ v\to ^+ w$](img1739.gif)
se e solo se
![$ v
\to^* w $](img1740.gif)
e
![$ v \ne w$](img1741.gif)
.
Dimostrazione.
Teorema 22.2
Sia
![$ (T,r)$](img1708.gif)
un albero radicato e per ogni
![$ v\in V(T)$](img1664.gif)
sia
![$ P(v)$](img1742.gif)
una
proposizione. Si supponga che:
sia vera;
- per ogni
tali che
si ha che
.
Allora
![$ P(v)$](img1742.gif)
è vera per ogni
![$ v\in V(T)$](img1664.gif)
.
Dimostrazione.
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 ^*$](img1733.gif)
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$](img28.gif)
un insieme e sia
![$ \preccurlyeq$](img1746.gif)
un ordinamento parziale su
![$ X$](img28.gif)
. Diremo
che
![$ \preccurlyeq$](img1746.gif)
è
ben fondato se ogni successione discendente ha
minimo, ossia se per ogni
![$ x_n\in X$](img1747.gif)
sono tali che
![$ x_{n+1}\preccurlyeq x_n$](img1748.gif)
allora esiste un
![$ \overline{n}$](img1749.gif)
tale che
![$ x_{\overline{n}}
\preccurlyeq x_n$](img1750.gif)
per ogni
![$ n\in \mathbb{N}$](img214.gif)
(in particolare se
![$ n\succcurlyeq \overline{n}$](img1751.gif)
allora
![$ x_n=x_{\overline{n}}$](img1752.gif)
)).
Teorema 22.6 (Induzione ben fondata)
Sia
![$ X$](img28.gif)
un insieme e sia
![$ \preccurlyeq$](img1746.gif)
un ordinamento ben fondato su
![$ X$](img28.gif)
cha
ammette minimo
![$ x_0$](img1106.gif)
(i.e.esiste
![$ x_0\in X$](img431.gif)
tale che
![$ x_0\preccurlyeq x$](img1753.gif)
per
ogni
![$ x\in X$](img97.gif)
). Per ogni
![$ x\in X$](img97.gif)
sia
![$ P(x)$](img20.gif)
una proposizione. Si supponga
che:
sia vera;
- per ogni
si ha che
(dove
è una abbreviazione per
e
).
Allora
![$ P(x)$](img20.gif)
è vera per ogni
![$ x\in X$](img97.gif)
.
Domanda.
È vero che in un albero infinito esiste un ramo infinito?
Per ramo infinito intendiamo un cammino infinito (i.e. un sottografo isomorfo a
).
In generale la risposta a questa domanda è negativa. Si consideri ad esempio
il grafo
(vedi figura).
Figura 13:
Un contresempio al Lemma di König, senza l'ipotesi dei gradi finiti
![\begin{figure}\begin{center}
\psfig{file=koenig.ps,width=.8\hsize} \par\end{center}\end{figure}](img1760.gif) |
è un albero. Infatti
è connesso dato che ogni vertice è
congiungibile al vertice 0. Inoltre se
è un lato, allora
che è sconnesso. Quindi
è 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
con
, che hanno lunghezza
.
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$](img1601.gif)
un albero infinito tale che ogni vertice ha
grado finito, allora
![$ T$](img1601.gif)
ha rami infiniti.
Dimostrazione.
Fissiamo una radice
per
e sia
la relazione di paternità indotta
da tale radice. Costruiremo una funzione
con la seguente
proprietà:
Chiaramente, una tale funzione risolve il problema.
Definiamo
ricorsivamente. Poniamo
. Chiaramente i discendnti di
sono infiniti (tutti i vertici sono discendenti della radice).
Supponiamo di aver definito
(che sia figlio di
e che abbia una
discendenza infinita). Per ipotesi
è finito, siano quindi
i figli di
(i.e.
). Per ogni
sia
Chiaramente
Pertanto esiste un
tale che
è infinito. Basta allora porre
. Chiaramente
e la discendenza di
, che è
, è infinita.
Next: Lezione 23
Up: Matematica Discreta (II modulo)
Previous: Lezione 21
Domenico Luminati
2004-03-18