0
$\begingroup$

For any first order theory $T$, let's say that $M$ is an ideal existential model of $T$ if and only if, for every formula $\varphi(x)$ in the language of $T$ in which only the symbol "$x$" appears free, we have: $$M \models \exists x (\varphi(x)) \text{ if and only if }T\vdash \exists x (\varphi(x)). $$ In English, there exists $x$ fulfilling $\varphi(x)$ in the domain of the model $M$ of $T$ if and only if $T$ proves the existence of $x$ for which $\varphi(x)$ holds.

Question: Do ideal existential models exist? And if so, then can they exist for [A]ny first order theory? If only [S]ome, then which theories can have such models?

$\endgroup$
  • $\begingroup$ Complete theories? For any incomplete theory let $\phi$ be an undecidable sentence and $\psi$ be $\phi\land x=x.$ $\endgroup$ – spaceisdarkgreen Jan 1 at 23:15
  • $\begingroup$ Why the close vote? The question is fairly trivial, but it's certainly not "off-topic". $\endgroup$ – Alex Kruckman Jan 1 at 23:16
  • $\begingroup$ @spaceisdarkgreen I see we had the exact same idea! :) $\endgroup$ – Alex Kruckman Jan 1 at 23:17
  • 3
    $\begingroup$ Zuhair: Just out of curiosity, why did you put brackets around A and S in [A]ny and [S]ome? $\endgroup$ – Alex Kruckman Jan 1 at 23:22
  • $\begingroup$ @AlexKruckman, nothing special, just to emphasize on them. Thanks for the answer. $\endgroup$ – Zuhair Jan 2 at 17:14
6
$\begingroup$

A theory $T$ has an ideal existential model if and only if $T$ is complete (and if $T$ is complete, then every model is ideal existential!).

Indeed, if $T$ is complete, then for any sentence $\psi$ and any $M\models T$, we have $M\models \psi$ if and only if $T\vdash \psi$.

Conversely, suppose $M$ is an ideal existential model of $T$. Note that for any sentence $\psi$, we can let $x$ be a variable which doesn't occur in $\psi$, and let $\widehat{\psi}(x)$ be the formula $(\psi\land (x = x))$. Then $\exists x\, \widehat{\psi}(x)$ is logically equivalent to $\psi$.

Now if $M\models \psi$, then $M\models \exists x\, \widehat{\psi}(x)$, so $T\vdash \exists x\, \widehat{\psi}(x)$, so $T\vdash \psi$. Since either $M\models \psi$ or $M\models \lnot \psi$, we have $T\vdash \psi$ or $T\vdash \lnot \psi$. Hence $T$ is complete.

(In this answer, I have ignored empty models - if your version of first-order logic allows empty models, then some details above have to be adjusted slightly, since $\psi$ and $\exists x\, \widehat{\psi}(x)$ are only logically equivalent in non-empty models. See Eric Wofsey's comment below. )

$\endgroup$
  • 1
    $\begingroup$ And of course if you do allow empty models, empty models are always ideal existential models. So $T$ has an ideal existential model iff either it is complete or has an empty model. $\endgroup$ – Eric Wofsey Jan 1 at 23:19

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.