The Completeness Proof
Henkin's result was not novel; it had first been proved by Kurt Gödel in his doctoral dissertation which was completed in 1929. (See Gödel's completeness theorem. Gödel published a version of the proof in 1930.) Henkin's 1949 proof is much easier to survey than Gödel's and has thus become the standard choice of completeness proof for presentation in introductory classes and texts.
The proof is non-constructive (a pure existence proof): while it guarantees that if a sentence α follows (semantically) from a set of sentences Σ, then there is a proof of α from Σ, it gives no indication of the nature of that proof.
Henkin originally proved the completeness of Church's higher-order logic, and then observed that the same methods of proof could be applied to first-order logic. Henkin's proof for higher-order logic uses a variant of the standard semantics. This variant uses general models (also called Henkin models): the higher types need not be interpreted by the full space of functions; a subset of the function space may be used instead.
Read more about this topic: Leon Henkin
Famous quotes containing the words completeness and/or proof:
“Poetry presents indivisible wholes of human consciousness, modified and ordered by the stringent requirements of form. Prose, aiming at a definite and concrete goal, generally suppresses everything inessential to its purpose; poetry, existing only to exhibit itself as an aesthetic object, aims only at completeness and perfection of form.”
—Richard Harter Fogle, U.S. critic, educator. The Imagery of Keats and Shelley, ch. 1, University of North Carolina Press (1949)
“He who has never failed somewhere, that man can not be great. Failure is the true test of greatness. And if it be said, that continual success is a proof that a man wisely knows his powers,—it is only to be added, that, in that case, he knows them to be small.”
—Herman Melville (1819–1891)