"Syntactic models" and the proof of the Completeness Theorem

173 Views Asked by At

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

There are 1 best solutions below

2
On BEST ANSWER

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.