This essay is a product of the Department of Philosophical Theology at Christ School of Theology, Institute of Lutheran Theology, and is part of the Disputationes series on important results in logic and their significance for theology.
The foundational work of Frege, Peirce, Cantor, Russell, and Zermelo made possible a remarkable hope. Perhaps mathematics could be placed upon completely explicit foundations, so that one could specify a formal language, identify axioms, formulate rules of inference, and determine exactly what followed from what. Logic would then no longer depend merely upon intuitive judgments concerning valid argument, since proofs themselves could become mathematically tractable objects whose structure and consequences could be precisely investigated.
Kurt Gödel changed our understanding of this project forever, and he did so by proving two results that initially appear to point in opposite directions. His completeness theorem of 1930 demonstrated the extraordinary power of first-order logic, while his incompleteness theorems of 1931 demonstrated equally extraordinary limitations upon sufficiently strong formal theories. To understand why these results are not in conflict, and why both matter for philosophical theology, one must distinguish with some care the logic within which proofs are constructed from the particular theories formulated within that logic.
Completeness: Proof and Truth Meet
Suppose we have a collection of sentences Γ and another sentence φ. We can then ask two different questions, one syntactical and the other semantical. Does φ follow syntactically from Γ, so that φ can be derived from Γ by the rules of a specified proof system, or does φ follow semantically from Γ, so that φ is true in every structure in which all the sentences belonging to Γ are true?
In compact notation we distinguish
Γ ⊢ φ
from
Γ ⊨ φ.
The first expression says that φ is formally derivable from Γ, whereas the second says that every model satisfying all the sentences in Γ also satisfies φ. The distinction is basic, for the first concerns what can be proved by operating with formulas according to formal rules, while the second concerns what must be true in any structure in which the premises are true.
Soundness tells us that proof cannot outrun semantic consequence:
If Γ ⊢ φ, then Γ ⊨ φ.
In ordinary English, if φ can be correctly proved from Γ, then φ is true in every model in which Γ is true. A sound proof system therefore never certifies as a consequence something that fails to hold in a model satisfying the premises.
Gödel's completeness theorem establishes the converse for first-order logic:
If Γ ⊨ φ, then Γ ⊢ φ.
That is, if φ is true in every model satisfying Γ, then there is a formal proof of φ from Γ. Thus, for first-order logic,
Γ ⊨ φ if and only if Γ ⊢ φ.
Semantic consequence and formal derivability therefore coincide at the level of first-order logical consequence. This is a magnificent result, not because every mathematical truth becomes formally provable, but because first-order logic possesses a proof system powerful enough to capture every consequence that follows purely in virtue of first-order logical form.
Then Comes Incompleteness
Only a year later Gödel proved something that can sound contradictory if the distinction between a logic and a theory formulated within that logic is ignored. Consider a formal mathematical theory sufficiently strong to express elementary arithmetic, and suppose that its axioms can be effectively specified, so that there is a mechanical procedure for determining whether a given expression is an axiom.
Gödel showed, roughly speaking, that if such a theory is consistent, there will be statements expressible in its language that the theory can neither prove nor disprove. The first incompleteness theorem therefore says, in simplified form, that for any consistent, effectively axiomatized formal theory strong enough to express elementary arithmetic, there are sentences that the theory cannot decide.
There will be a sentence G such that, under the relevant assumptions,
T ⊬ G
and
T ⊬ ¬G.
Read this as saying that the theory T proves neither G nor its negation. The theory is therefore incomplete in the technical sense that some sentence expressible in its language is neither provable nor refutable within the theory.
Gödel achieved this by discovering how arithmetic could, in effect, speak about its own formulas and proofs. Expressions and finite sequences of expressions were assigned numbers—what we now call Gödel numbers—so that claims about formulas, derivations, and provability could themselves be represented arithmetically. This made possible the construction of a sentence which, in a carefully defined sense, says of itself that it is not provable within the theory.
If the theory proved that sentence, the theory would thereby become inconsistent; yet if the theory is consistent, it cannot prove the sentence. The system therefore contains a statement that escapes its own power of demonstration, not because the rules of inference are defective, but because a sufficiently expressive formal theory cannot, under the relevant conditions, settle every sentence formulable within its own language.
Gödel's second incompleteness theorem deepens the point. A sufficiently strong consistent theory cannot, using only its own formal resources, prove its own consistency; thus the limits disclosed by incompleteness concern not merely this or that recalcitrant sentence, but also the capacity of a formal theory to certify from within itself the consistency upon which its deductive enterprise depends.
Why Completeness and Incompleteness Do Not Conflict
The apparent paradox disappears once we notice that Gödel's two results concern different objects. The completeness theorem concerns first-order logic itself and says that every semantic consequence at the level of first-order logical validity can be captured by formal proof, whereas the incompleteness theorem concerns particular formal theories formulated in languages sufficiently rich to express arithmetic and says that no suitably effective, consistent theory of the relevant strength can decide every sentence expressible within it.
First-order logic can therefore be complete as a logic even though particular first-order theories are incomplete as theories. Logic may provide entirely adequate rules for capturing logical consequence without thereby guaranteeing that a given axiomatic theory will settle every question formulable in its language, and failure to keep these two claims distinct has been responsible for a great deal of confusion in both popular and theological appropriations of Gödel.
What Might Theology Learn?
Gödel's theorem is frequently abused in theological argument. It does not prove that God exists, establish that theological truth transcends reason, show that every worldview must contain mysteries, or entail that because arithmetic is incomplete, systematic theology must be incomplete in Gödel's technical sense. Such conclusions trade upon analogy without first establishing that the formal conditions governing Gödel's results apply to theological systems in the required way.
The genuine theological lesson is subtler, for theology itself regularly identifies primitive concepts, formulates doctrinal commitments, draws distinctions among them, and asks what follows from what. Precisely for that reason, it has something to learn from Gödel about the difference between the rigor with which consequences are drawn and the adequacy or completeness of the theory from which they are drawn.
One may possess completely precise rules of reasoning without thereby possessing a theory capable of deciding every question formulable within the theory's language. The rigor of an inferential procedure and the completeness of a theory are therefore different achievements, and formal precision should never be confused with exhaustive conceptual capture.
This distinction matters particularly for philosophical theology because there is no need to oppose formal reasoning to mystery, as though careful logic were somehow hostile to theological depth, nor is there any warrant for supposing that once doctrines have been sufficiently formalized every further theological question becomes mechanically decidable. Formalization can clarify commitments, expose hidden assumptions, reveal inconsistency, and determine consequences; yet what a theory can express is not identical with what that theory can prove, and what follows rigorously from a set of assumptions does not by itself establish that those assumptions are sufficient for everything theology wishes to say.
The validity of an inference must therefore be distinguished from the adequacy of the theory within which the inference is made. A theological argument may be formally impeccable while the assumptions from which it proceeds remain too weak, too narrow, or otherwise insufficient to determine all that theologians wish to assert; conversely, expanding one's theological vocabulary or axiomatic commitments does not by itself guarantee that the resulting system will be more adequate unless one also asks what structures satisfy it and what consequences genuinely follow.
Gödel consequently belongs in theological education not because he supplies an apologetic shortcut, but because he teaches intellectual discipline. His work forces us to distinguish syntax from semantics, logic from theory, truth from proof, and the expressive resources of a language from the demonstrative resources of an axiomatic system; these are distinctions theology needs whenever it attempts to state with precision what it believes and what follows from those beliefs.
Those distinctions become still more important when we turn from Gödel to model theory, for the next question is unavoidable: even when a first-order theory has models, how tightly can its language determine what those models are like? The Löwenheim–Skolem results show that the answer is stranger than one might initially suppose, and with them the problem shifts from the limits of proof to the relation between a theory and the structures capable of satisfying it.
Bibliographical Note
Gödel's completeness theorem appeared in his 1930 dissertation and in the related publication “Die Vollständigkeit der Axiome des logischen Funktionenkalküls.” His incompleteness results appeared the following year in “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I” (1931).
For philosophical orientation, the crucial distinction to preserve is between the completeness of first-order logical consequence and the incompleteness of sufficiently strong, effectively axiomatized formal theories. Standard introductions to mathematical logic and the philosophy of logic provide fuller treatments of both results, while Gödel's original papers remain models of mathematical economy and conceptual force.
No comments:
Post a Comment