Lemma di König

Da Wikipedia, l'enciclopedia libera.

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.


matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica