In Computational Complexity by Papadimitriou (page 107), he outlines the basic idea for a proof of the completeness theorem for first-order logic - namely, that given a consistent set $\Delta$ of expressions over a vocabulary $\Sigma$, we can build a syntactic model for it where the universe will be the set of terms over $\Sigma$. Then he says :

There are serious difficulties in implementing this plan. First, the universe of all terms may not be rich enough to provide a model : Consider $\Delta = \{\exists x\ P(x)\}\ \cup\ \{\neg P(t) : t\text{ is a term of }\Sigma\}$. Although this is a consistent set of expressions, it is easy to see that there is no way to satisfy it by a model whose universe contains just the terms of $\Sigma$.

But is that really so? Suppose we have a vocabulary $\Sigma$ with only two constants, $A$ and $B$.

Then $\Delta = \{ \exists x\ P(x), \neg P(A), \neg P(B), \neg P(x), \neg P(y), \neg P(z), \dots \}$ where $x,y,z,\dots$ are variables.

But then there is a model $M$ having the universe of all terms, $\{A, B, x,y,z,\dots\}$, which to the relation symbol $P$ assigns the unary relation $R = \{B\}$, and to the constants $A$ and $B$ and also to all variables assigns the same element $A$ from its universe. This model satisfies $\Delta$, since

  1. "$\exists x\ P(x)$" is satisfied when $x$ is assigned to $B$, and
  2. "$\neg P(A)$", "$\neg P(B)$", ... are all satisfied because "$P(A)$", "$P(B)$", ... each map to $R(A)$, and $A \not\in R$.
  • 1
    $\begingroup$ But in your "model" you are trying to "map" $P(B)$ twice : according to 1. you have that $P(B)$ is true, because the "interpretation" of $P$ is the set $R$, and $B \in R$; if so, you cannot, in 2., define again $P(B)$ in order to make it false ...A model, by "construction" contains no contradictions. The "trick" of the above construction is that if you use all terms in $\Delta$, you have no enough terms to build-up a model made only of "syntactical" stuff; thus, tou have to "add" an infinite supply of new terms ... $\endgroup$ Apr 29 '14 at 7:11
  • $\begingroup$ In 2., the interpretation given by the model to the term "B" is the term A. Hence, P(B) is interpreted to refer to R(A), which is false, and does not contradict that R(B) is true. $\endgroup$
    – Tim
    Apr 29 '14 at 18:04
  • $\begingroup$ but you say : "∃x P(x) is satisfied when x is assigned to B" that means $P$ holds of $B$ ... and $x$ is also in the set $\Delta$ which contains $\lnot P(x)$; thus you have that also $\lnot P$ holds of $B$. I think it does not work... $\endgroup$ Apr 29 '14 at 19:23

Somewhat unstated in the naïve plan outlined by Papadimitriou is that not only does the universe of the syntactic model $M$ consist precisely of the terms of $\Sigma$, but that for each closed term $t$ of $\Sigma$, the interpretation of $t$ in $M$ is $t$ itself.1

So while you can "rearrange" the elements of this syntactic structure to give rise to an actual model of this particular $\Delta$, it fails to actually be a syntactic model in the spirit intended (but unstated). Also, there is to me no obvious way to carry out such a construction for arbitrary sets $\Delta$.

1This is not quite accurate, since if two different terms $t,s$ are provably equal from $\Delta$, then the interpretation of these terms in $M$ should be the same, so we will instead take the universe to consist of precisely the equivalence classes of terms of $\Sigma$ according to the relation "are $\Delta$-provably equal". Even here, we want for every closed term $t$ of $\Sigma$ the interpretation of $t$ in $M$ to be the equivalence class containing $t$. Note that in the example given, any two different terms of $t$ are not $\Delta$-provably equal.

  • $\begingroup$ Thanks! One follow up question - you mentioned the requirement that the interpretation of provably equal terms should be the same in M. Is this requirement necessary for the proof of completeness theorem to go through? How would the proof fail if we assigned different interpretations to provably equal terms (i.e. if to a term t we assigned t itself, and not its equivalence class)? $\endgroup$
    – Tim
    Apr 29 '14 at 18:00
  • $\begingroup$ @Tim: Note that in order for $M$ to be a model of $\Delta$, every sentence provable from $\Delta$ must be true in $M$ (this is the Soundness Theorem). In order for $M \models s = t$ to hold, it must be that $s^M$ and $t^M$ (the interpretations of $s$ and $t$ in $M$) are the same object: we're not allowed to alter the meaning of $=$ between models: it means equals, as in the left- and the right-hand-side objects are literally the same time. (Oh, and you're welcome!) $\endgroup$
    – user642796
    Apr 29 '14 at 18:18

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.