2
$\begingroup$

Let $T_{PA}$, $T_{ZFC}$ be consistent completions of $PA$ and $ZFC$ respectively in the standard languages they are usually presented with.

1) How would you show that these theories don't eliminate quantifiers? 2) How would you show that they are not model complete?

Of course if you answer the second question, the first follows for free. I'm guessing there is an easy way to answer 2) (by exhibiting particular formulas that witness the failure of Tarski-Vaught criterion given $M,N\models{T_{ZFC}}$ with $M\subseteq{N}$ for example) but I'm having a hard time trying to explicitly write these down.

Edit 1: For QE of the $ZFC$ example, I'm fairly certain that $\forall{y}{\neg}({y\in{x}})$ isn't equivalent to any qf-formula. The same should be true for $PA$ if you replace the formula with $x$-is even. But neither help with the failure of model completeness.

$\endgroup$
  • $\begingroup$ ZFC has no function or constant symbols in its language, just one relation symbol. There are no quantifier free sentences. $\endgroup$ – Carl Mummert Nov 28 '16 at 2:49
  • $\begingroup$ @CarlMummert: I'm taking QE to mean that for any formula $\phi$, there is a qf-formula $\varphi$ s.t. $T\models{\forall{(\phi\leftrightarrow{\varphi})}}$ $\endgroup$ – user185596 Nov 28 '16 at 2:52
  • 2
    $\begingroup$ @CarlMummert The correct way to make sense of QE for languages without constant symbols is to include primitive symbols $\top$ and $\bot$ in your logic, i.e. quantifier-free sentences. A consequence is that in a language without constant symbols, QE implies completeness, but in this question the OP is working with completions anyway. $\endgroup$ – Alex Kruckman Nov 28 '16 at 15:19
5
$\begingroup$

Let's look at ZFC first. We want to show that, if $T$ is a completion of ZFC, then $T$ is not model complete; that is, there are $M_1, M_2\models T$ with $M_1\subseteq M_2$ but $M_1\not\preccurlyeq M_2$.

To do this, let $M_1$ be any model of $T$. Now I want to view $M_1$ as a substructure of the hereditarily finite sets of $M_2$ - that is, of $(V_\omega)^{M_2}$. To do this, I'll use Compactness, together with the following fact which ZFC (and hence $T$) proves:

Every finite partial order embeds into $(V_\omega, \in)$.

So consider the expanded language $L'=\{\in\}\cup\{a_i: i\in M_0\}$, and the set of sentences $$\Gamma=T\cup\{a_i\in V_\omega: i\in M_0\}\cup\{a_i\in a_j: i\in^{M_0}j\}.$$ (Of course, "$a_i\in V_\omega$" is an abbreviation for the appropriate, and annoyingly long, actual sentence in the expanded language.) By the above, $\Gamma$ has a model $M_1$, and we can WLOG assume $a_i^{M_1}=a_i$ (so $M_1\supseteq M_0$ in the obvious way).

But ZFC also proves that not every set is hereditarily finite; so $M_0\not\preccurlyeq M_1$.

$\endgroup$
  • $\begingroup$ That's a cool answer. Is there something similar for.PA? Also, if we had the result for PA, can we use the fact that PA is definable in ZFC to somehow get prove things about ZFC? $\endgroup$ – user185596 Nov 28 '16 at 14:58
  • $\begingroup$ Yes it is a cool argument (and a cool question, too). One simple "oops" -- Above the yellow line, you're one-based: $M_1$, $M_2$; but below it, you're zero-based. $\endgroup$ – BrianO Jan 22 '17 at 2:01

Your Answer

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