Witness property implies scapegoat theory in first-order logic

200 Views Asked by At

In Elliott Mendelson's Introduction to Mathematical Logic (Sixth Edition) page 92, the Exercise 2.63(b) asks to prove

A first-order theory $K$ is a scapegoat theory, if and only if, for any formula $B(x)$ with $x$ with its only free variable such that $\vdash_K (\exists x)B(x)$, there is a closed term $t$ such that $\vdash_K B(t)$

The latter part above is essentially saying $K$ has witness property, which seems a "weaker" version of scapegoat property.

In Mendelson's book, scapegoat property for first-order theories is defined as: for any $B(x)$, there is some closed term $t$ such that $\vdash_K (\exists x)\neg B(x) \Rightarrow \neg B(t)$.

So my question is: how come the (weak) witness property is equivalent to the (strong) scapegoat property?

1

There are 1 best solutions below

1
On

This is not true. Are you sure Mendelson isn't assuming $K$ is a complete first-order theory?

Here's a counterexample. Consider the language $\{P\}\cup \{c_i\mid i\in \mathbb{N}\}$, where $P$ is a unary relation symbol and the $c_i$ are constant symbols. Let $K$ be the theory $\{c_i\neq c_j\mid i\neq j\}$.

Now $K$ is not a scapegoat theory. The only closed terms in this language are the constant symbols $c_i$. And for all $i$, $$\not\vdash_K (\exists x)\lnot P(x)\rightarrow \lnot P(c_i).$$ Why? Because $K$ has a model in which all of the constants $c_i$ satisfy $P$, but some other element fails to satisfy $P$.

On the other hand, $K$ does satisfy the supposedly equivalent condition, just because there are so few formulas $\varphi(x)$ such that $\vdash_K (\exists x)\varphi(x)$. Note that the formula used in the example above to show that $K$ is not a scapegoat theory was the formula $\lnot P(x)$. But we do not have $\vdash_K (\exists x)\lnot P(x)$, since $K$ has a model in which every element satisfies $P$.

To make this argument precise, it is possible to show that $K$ has quantifier elimination, so we only need to consider formulas $\varphi(x)$ which are conjunctions of atomic and negated atomic formulas. But now $\not\vdash_K (\exists x)P(x)$ and $\not\vdash_K (\exists x)\lnot P(x)$, so if $\vdash_K (\exists x)\varphi(x)$, then $\varphi(x)$ doesn't mention $P$. So $\varphi(x)$ either says $x = c_i$ for some $i$, or $\bigwedge_{j=1}^n x\neq c_{i_j}$ for some $c_{i_1},\dots,c_{i_n}$. In the first case, $c_i$ itself is a closed term witness, and in the second case, we can pick some $c_k$ which is not among the finitely many $c_{i_j}$, and $c_k$ is a closed term witness.