MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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