Next: Lezione 23 (30 maggio
Up: Matematica Discreta
Previous: Lezione 21 (28 maggio
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^*$](img1611.gif)
è un ordinamento parziale. E la relazione
![$\to^+$](img1610.gif)
è
l'ordinamento stretto associato a
![$\to^*$](img1611.gif)
ossia
![$v\to ^+ w$](img1613.gif)
se e solo se
![$v
\to^* w $](img1614.gif)
e
![$v \ne w$](img1615.gif)
.
Dimostrazione.
Teorema 22.2
Sia
![$(T,r)$](img1586.gif)
un albero radicato e per ogni
![$v\in V(T)$](img1546.gif)
sia
![$P(v)$](img1616.gif)
una
proposizione. Si supponga che:
sia vera;
- per ogni
tali che
si ha che
.
Allora
![$P(v)$](img1616.gif)
è vera per ogni
![$v\in V(T)$](img1546.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^*$](img1611.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$](img17.gif)
un insieme e sia
![$\preccurlyeq$](img1620.gif)
un ordinamento parziale su
![$X$](img17.gif)
. Diremo
che
![$\preccurlyeq$](img1620.gif)
è
ben fondato se ogni successione discendente ha
minimo, ossia se per ogni
![$x_n\in X$](img1621.gif)
sono tali che
![$x_{n+1}\preccurlyeq x_n$](img1622.gif)
allora esiste un
![$\overline{n}$](img1623.gif)
tale che
![$x_{\overline{n}}
\preccurlyeq x_n$](img1624.gif)
per ogni
![$n\in\mathbb{N}$](img157.gif)
(in particolare se
![$n\succcurlyeq \overline{n}$](img1625.gif)
allora
![$x_n=x_{\overline{n}}$](img1626.gif)
)).
Teorema 22.6 (Induzione ben fondata)
Sia
![$X$](img17.gif)
un insieme e sia
![$\preccurlyeq$](img1620.gif)
un ordinamento ben fondato su
![$X$](img17.gif)
cha
ammette minimo
![$x_0$](img1022.gif)
(i.e.esiste
![$x_0\in X$](img360.gif)
tale che
![$x_0\preccurlyeq x$](img1627.gif)
per
ogni
![$x\in X$](img66.gif)
). Per ogni
![$x\in X$](img66.gif)
sia
![$P(x)$](img1628.gif)
una proposizione. Si supponga
che:
sia vera;
- per ogni
si ha che
(dove
è una abbreviazione per
e
).
Allora
![$P(x)$](img1628.gif)
è vera per ogni
![$x\in X$](img66.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 12:
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}](img1635.gif) |
è un albero. Infatti
è connesso dato che ogni vertice è
congiungibile al vertice
. 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
arrivano infiniti lati). In effetti vale il seguente teorema:
Teorema 22.7 (Lemma di König)
Sia
![$T$](img1485.gif)
un albero infinito tale che ogni vertice ha
grado finito, allora
![$T$](img1485.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 (30 maggio
Up: Matematica Discreta
Previous: Lezione 21 (28 maggio
Luminati Domenico
2002-06-07