Take the 2-minute tour ×

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 ?

share|improve this question
add comment

1 Answer

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.

share|improve this answer
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 ? –  Akshar Prabhu Desai Aug 29 '10 at 22:11
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. –  Bjørn Kjos-Hanssen Aug 29 '10 at 22:17
@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. –  Stefan Geschke Aug 30 '10 at 8:48
add comment

Your Answer


