0
$\begingroup$

Consider the following FOL sentence:

$\phi = \exists x \forall y \exists z ((x=y) \lor (P(x,y,z) \land \lnot P(y,x,z) ) $

It can be proven that for any natural number n > 0 there exits a model of size n for the above sentence. (Please correct me here if I am wrong. This should be provable using induction.).

Now imagine a FOL sentence that does not use = (and similar) predicate. And if such a sentence has a model of size n can I claim that the sentence will essentially have a model of size n+1 ?

$\endgroup$

1 Answer 1

3
$\begingroup$

Yes. If there is a model $\mathcal M$ of size $n$ of any sentence $\phi$ that does not use = then you can take any element $a$ of $\mathcal M$ (using the fact that $n>0$) and let $\mathcal N$ be $\mathcal M$ with an additional element $b$ which has all the same properties as $a$. Then $\mathcal N$ still satisfies $\phi$.

If $n=0$, however, the answer is no: the sentence $$\exists x(P(x)\vee\neg P(x))\longrightarrow \exists x\exists y(P(x)\wedge\neg P(y))$$ has a model of size 0 but no model of size 1.

$\endgroup$
3
  • $\begingroup$ By syaing b has all properties of a you are trying to say add "another a" and since our FOL cant use "=" we will get away with it. But I feel you have ignored the fact that : size of a model means the cardinality of it's universe. Universe is a set and hence each member of universe has to be distinct isnt it ? $\endgroup$ Aug 29, 2010 at 22:11
  • 1
    $\begingroup$ Well then consider the sentence $\forall x(P(x)\vee\neg P(x))$. This has a model of size 2 but no model of size 3 in your sense. Because of the three elements, two have to agree about whether they satisfy $P$ and so there is nothing left to distinguish them. $\endgroup$ Aug 29, 2010 at 22:17
  • 1
    $\begingroup$ @Akshar Prabhu Desai: $b$ having the same properties as $a$ just means that $b$ is indistinguishable from $a$ with respect to the relations definable in the structure under consideration (except for equality, which we are not allowed to use). They are not indistinguishable as members of the set-theoretic universe. For instance, $i$ and $-i$ are indistinguishable as complex numbers, since there is an automorphism carrying one to the other, yet $\mathbb C$ is a set. Or take the structure with two elements $0$ and $1$ and no relations, functions and constants whatsoever. $\endgroup$ Aug 30, 2010 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.