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 ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Akshar Prabhu Desai
    Commented 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$
    – Bjørn Kjos-Hanssen
    Commented 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$
    – Stefan Geschke
    Commented Aug 30, 2010 at 8:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .