I have seen people talking about Gödel's complete theorems and Gödel's incomplete theorems on math.SE. I am curious what they are really about, so I try to understand the meaning of completeness first.
My questions are:
- In the following different versions of completeness, are some of them actually the same concept?
When talking about completeness, some refers to completeness of a formal system, some uses completeness of a theory, and some uses completeness of a logic. Are these equivalent?
I know that every formal system has a theory as its component, but I am not sure if every formal system has a logic as its component?
Note that a formal system consists of a language, a set of axioms, a set of inference rules, and a set of theorems (which are derived from the axioms and inference rules), called a theory.
There are some specific questions about each version of completeness below.
Different versions of completeness:
From Wikipedia
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 ¬φ 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.
Does "either φ or ¬φ is a theorem of S" allows both φ and ¬φ to be theorems of S?
Does "for each formula φ of the language of the system ..." mean that there is no formula in the language of the formal system such that neither φ or ¬φ is a theorem of S?
From Wikipedia:
a theory is complete if it is a maximal consistent set of sentences, i.e., if it is consistent, and none of its proper extensions is consistent.
Is this a different completeness concept from the one in part 1? I think they are the same, because part 2 seems same as "no unprovable axiom can be added to it as an axiom without introducing an inconsistency" in part 1.
From Wikipedia
A formal system S is semantically complete or simply complete, if every tautology of S is a theorem of S.
From Wikipedia
a complete logic, which asserts that for every theory that can be formulated in the logic, all semantically valid statements are provable theorems (for an appropriate sense of "semantically valid"). Gödel's completeness theorem is about this kind of completeness.
I wonder if "semantically valid statements" and "tautologies" are the same concept?
Are the above two "completeness" the same concept?
From Wikipedia:
A formal system S is strongly complete or complete in the strong sense if and only if for every set of premises Γ, any formula which semantically follows from Γ is derivable from Γ.
A formal system has its own fixed set of axioms. So I wonder if "every set of premises Γ" means every subset of the set of axioms of the formal system?
Thanks and regards!