A formal system S is syntactically complete or deductively complete or maximally complete or simply complete if and only if for each formula φ of the language of the system either φ or (not φ) is a theorem of S. This is also called negation completeness. In another sense, a formal system is syntactically complete if and only if no unprovable axiom can be added to it as an axiom without introducing an inconsistency.

Truth-functional propositional logic and first-order predicate logic are semantically complete, but not syntactically complete (for example, the propositional logic statement consisting of a single variable “a” is not a theorem, and neither is its negation, but these are not tautologies). Godel’s incompleteness theorem shows that any recursive system that is sufficiently powerful, such as Peano arithmetic, cannot be both consistent and complete.

— Wikipedia on Completeness

2012.12.11 Tuesday ACHK

The branch of mathematical logic that deals with what is true in different models is called model theory. The branch called proof theory studies what can be formally proved in particular formal systems. The completeness theorem establishes a fundamental connection between these two branches, giving a link between semantics and syntax.

The completeness theorem should not, however, be misinterpreted as obliterating the difference between these two concepts; in fact Godel’s incompleteness theorem, another celebrated result, shows that there are inherent limitations in what can be achieved with formal proofs in mathematics.

The name for the incompleteness theorem refers to another meaning of complete (see model theory – Using the compactness and completeness theorems). In particular, Godel’s completeness theorem deals with formulas that are logical consequences of a first-order theory, while the incompleteness theorem constructs formulas that are not logical consequences of certain theories.

— 14 February 2012

— Wikipedia on Godel’s completeness theorem

2012.12.07 Friday ACHK

This theorem implies that the only way a language can be incomplete is [that] there is a model of the language in which a particular statement is true, and another in which the statement is false.

For example, we can see that [for] the language [comprising] the symbols 0, 1, +, -, and , [] the statement []   is true [] if we take the structure to be C or R, but not if we choose Q. So it is clear that the formula a*a = 2 is not true in every model of the language and the thus the language is incomplete.

What the completeness theorem asserts is that this is the only way that a theory (set of formulas) can be incomplete and that every formula that satisfies every structure is provable in the language.

— Godel’s Completeness And Incompleteness Theorems

— Ben Chaiken

2012.12.04 Tuesday ACHK

Now when you combine the Completeness and Incompleteness Theorems, you can get some really remarkable results. If you work with the axioms of number theory, call them N (which include many of the above axioms F along with axioms for < and axioms for mathematical induction), for example, we know by the Incompleteness Theorem that there is a statement X such that neither X nor (not X) is provable. Hence, by the Completeness Theorem, there is a model of N in which X is true and a model of N in which X is false.

It follows that there are mathematical universes which look and act very much like the regular natural numbers, but do in fact have some subtle differences. One of the most fascinating results I’ve seen is that there is a model of number theory which “thinks” (in a precise sense) that the axioms N are inconsistent, even though they are not (roughly, the “proof” of an inconsistency that it “sees” is infinitely long, and so is not a real proof).

— Godel’s Completeness Theorem

— Joe Mileti

2012.12.02 Sunday ACHK