2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Which book are you reading? $\endgroup$ – user 170039 Aug 6 '18 at 14:56
  • $\begingroup$ "My book states ..." You are asking a question about a certain book, but you do not identify the book? How come? If the competeness theorem is badly stated in your book, that could be of interest to other people, who might be considering buying that book. $\endgroup$ – bof Aug 6 '18 at 14:57
  • $\begingroup$ @bolf I added the reference to book, the theorem is presented as corollary to Skolem theorem, and is not called "Goedel theorem" by the way. $\endgroup$ – Markus Steiner Aug 6 '18 at 15:03
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I struggle to understand how we reconcile the "seemingly-stronger" version with GIT2. Is it the case that $Con(F)$ is not true in every model of arithmetics? $\endgroup$ – Daniil Kozhemiachenko Sep 10 '18 at 22:34
  • 1
    $\begingroup$ @DaniilKozhemiachenko Exactly. There are models of PA which think that PA is inconsistent! (And we can replace PA with any similarly-appropriate theory - ZFC, NBG, ...) Of course, a "natural number" coding a proof of a contradiction in such a model isn't actually a natural number. $\endgroup$ – Noah Schweber Sep 10 '18 at 22:37
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This isn't the OP's confusion. They're asking why "Every validity is provable from the empty theory" implies "Every sentence true in every model of $T$ is provable from $T$," and this isn't quite trivial since $T$ might be an infinite theory. $\endgroup$ – Noah Schweber Aug 6 '18 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.