Doubts about Goedel Completeness Theorem

Question

My book (Mendelson) states this theorem the following way:

(1) A logically valid formula of a first order theory is a theorem.

On Wikipedia the statement is a little more general:

(2) For any first-order theory T with a well-orderable language, and any sentence s in the language of the theory, there is a formal proof of s in T if and only if s is satisfied by every model of T.

Now “well-orderable language” is implicit in (1), and the “only if” part is fairly obvious. My doubt is about the hypothesis of “validity” used in (1) which is stronger than “true in any model” used in (2).

Because you can have an interpretation of a 1st order language which satisfies all the logic axioms, but doesn’t satisfy proper axioms, so isn’t a model of the theory. Basically valid means true under any interpretation, and there are more interpretations than models.

Am I understanding this right? Is the stronger hypothesis of (1) strictly required? Or it is also possible to prove the theorem:

(1’) A formula true in any model of a first order theory is a theorem.

Answer 1

Rephrasing your question a bit more clearly, you're asking why the seemingly-weaker completeness theorem

Every validity is provable from the empty theory

implies the seemingly-stronger completeness theorem

For every theory $T$ and every sentence $\varphi$ true in every model of $T$, we have $T\vdash\varphi$,

or in symbols why "$\emptyset\models\varphi\implies\emptyset\vdash\varphi$" implies "For all $T$, $T\models\varphi\implies T\vdash\varphi$."

You are right to be suspicious: on the face of it you cannot immediately deduce the stronger version from the weaker version. However, they are nonetheless equivalent:

• First, we handle the case where $T$ is finite. If $\varphi$ is a formula of $T$ then $\varphi\wedge\psi$ is a validity (where $\psi$ is the conjunction of the axioms in $T$), hence by the weak version we have $\emptyset\vdash\varphi\wedge\psi$; this in turn gives $\{\psi\}\vdash\varphi$, and that gives $T\vdash \varphi$ since we have $T\vdash\psi$.

• Next, we handle the case where $T$ is infinite. Here we cannot "put all of $T$ into one sentence." However, the compactness theorem fixes things: if $\varphi$ is true in every model of $T$, then there is some finite subtheory $T_0\subseteq T$ such that $\varphi$ is true in every model of $T_0$. (HINT: note that $T\cup\{\neg\varphi\}$ is unsatisfiable ...) Hence $T_0\vdash\varphi$, and a fortiori $T\vdash\varphi$.

However, this isn't really necessary: the proof of the seemingly-stronger version of completeness is basically the same as the proof of the seemingly-weaker version.

Answer 2

You are confused. A first-order language includes both the logic axioms and the proper axioms; it is not defined by the logic axioms alone. So an 'interpretation' which satisfies the logic axioms but not the proper axioms simply isn't an interpretation of that language, period. An interpretation is a mapping between the 'concepts' (i.e predicates, functions, constant terms, etc) of the language and corresponding objects in the model - ALL of them. In that sense, 'interpretation' and 'model' are synonymous terms.