Next: Lezione 22 (29 maggio
Up: Matematica Discreta (II modulo)
Previous: Lezione 20 (22 maggio
Subsections
Sia (T,r) un albero radicato, sull'insieme dei vertici sono allora definite le
due relazioni
e
,
ovvero la chiusura transitive e la
chiusura transitiva e riflessiva della relazione
di
paternità.
Ricordiamo la seguente
Definizione 21.1
Un
ordinamento parziale su un insieme
X è una relazione
![$\preccurlyeq$](img793.gif)
che sia
- 1.
- riflessiva (i. e.
)
- 2.
- antisimmetrica (i.e.
e
)
- 3.
- transitiva (i.e.
e
)
un ordinamento partziale
![$\preccurlyeq$](img793.gif)
su
X si dice un
ordinamento
totale se in più
- 4
- per ogni
oppure
.
Proposizione 21.2
La relazione
![$\to ^*$](img792.gif)
è un ordinamento parziale. E la relazione
![$\to^+$](img791.gif)
è
l'ordinamento stretto associato a
![$\to ^*$](img792.gif)
ossia
![$v\to ^+ w$](img801.gif)
se e solo se
![$v
\to^* w $](img802.gif)
e
![$v \ne w$](img803.gif)
.
Dimostrazione.
Definizione 21.3
Sia
X un insieme e sia
![$\preccurlyeq$](img793.gif)
un ordinamento parziale su
X. Diremo
che
![$\preccurlyeq$](img793.gif)
è
ben fondato se ogni successione discendente ha
minimo, ossia se per ogni
![$x_n\in X$](img804.gif)
sono tali che
![$x_{n+1}\preccurlyeq x_n$](img805.gif)
allora esiste un
![$\overline{n}$](img806.gif)
tale che
![$x_{\overline{n}}
\preccurlyeq x_n$](img807.gif)
per ogni
![$n\in\mathbb N$](img57.gif)
(in particolare se
![$n\succcurlyeq \overline{n}$](img808.gif)
allora
![$x_n=x_{\overline{n}}$](img809.gif)
)).
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)$](img718.gif)
si ha che l'insieme
![$\{v\in V(T)\mid w \to^* v\}$](img810.gif)
è finito.
Dimostrazione.
Teorema 21.5
L'ordinamento
![$\to ^*$](img792.gif)
è ben fondato.
Dimostrazione.
Teorema 21.6 (Induzione sugli alberi)
Sia (
T,
r) un albero radicato e per ogni
![$v\in V(T)$](img718.gif)
sia
P(
v) una
proposizione. Si supponga che:
- 1.
- P(r) sia vera;
- 2.
- per ogni
si ha che
.
Allora P(v) è vera per ogni
.
Dimostrazione.
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 ^*$](img792.gif)
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$](img793.gif)
un ordinamento ben fondato su
X cha
ammette minimo
x0 (i.e.esiste
![$x_0\in X$](img121.gif)
tale che
![$x_0\preccurlyeq x$](img812.gif)
per
ogni
![$x\in X$](img813.gif)
). Per ogni
![$x\in X$](img813.gif)
sia
P(
x) una proposizione. Si supponga
che:
- 1.
- P(x0) sia vera;
- 2.
- per ogni
si ha che
(dove
è una abbreviazione per
e
).
Allora
P(
x) è vera per ogni
![$x\in X$](img813.gif)
.
Next: Lezione 22 (29 maggio
Up: Matematica Discreta (II modulo)
Previous: Lezione 20 (22 maggio
Domenico Luminati
2000-06-14