Lemma di König
Vai alla navigazione
Vai alla ricerca
Il Lemma di König in logica afferma che:
Se un albero, in cui ogni nodo ha un numero finito di successori immediati, ha infiniti nodi allora in esso c'è anche un ramo infinito.
Dimostrazione del lemma. Ogni nodo dell'albero avrà un'etichetta. Si dice che un nodo è prolungabile se e solo se da esso derivano rami di lunghezza finita e arbitraria, quindi la radice dell'albero è prolungabile. Supponiamo un nodo v prolungabile, implica che esiste un figlio di v prolungabile. Se f0 è prolungabile e se ogni nodo ha un figlio prolungabile esiste almeno un discendente che è prolungabile.
Collegamenti esterni[modifica | modifica wikitesto]
- (EN) Eric W. Weisstein, Lemma di König, su MathWorld, Wolfram Research.
