Il Lemma di König in logica afferma che:
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
Categoria:Logica matematica König, lemma di Categoria:Teoria della calcolabilità