Let $Q$ be the formula arising from the conjunction of the following formulas (of first-order classical logic with equality):

  • $\exists x P(x)$
  • $\exists x \neg P(x)$
  • $\forall xy (P(x) \wedge P(y) \rightarrow x = y)$
  • $\forall xy (\neg P(x) \wedge \neg P(y) \rightarrow x = y)$

How many models does $Q$ have? How many of them are non isomorphic?

I'm having trouble with counting or giving a formal proof regarding the models of $Q$. Also, I don't exactly get what it means with non-isomorphic models.


Let's first see what the axioms say.

(i) The first axiom says there is an object that has property $P$. More formally, in any model $M$ of the axiom system, there is an object $a$ such that $P_M(a)$ is true in $M$.

(ii) The second axiom says there is an object which doesn't have property $P$.

(iii) The third axiom says there is no more than one object with property $P$. It does so by saying that if the objects $x$ and $y$ have property $P$, then $x$ must be the same as $y$.

(iv) The fourth axiom says there is no more than one object that doesn't have property $P$.

So any model of the full set of $4$ axioms has exactly two elements, one of which has property $P$, and the other of which doesn't. And any two element structure $M$, where $P$ is interpreted to be true at one of the elements and false at the other, is a model.

There are infinitely many models. The underlying set of the model could be $\{1,2\}$, or $\{17,24\}$, or $\{a,b\}$ where $a$ is the set of integers and $b$ the set of reals. Any two-element set can be made the underlying set of a model, by interpreting $P$ to be true at one of the objects and false at the other.

However, up to isomorphism there is only one model. More precisely, if $M$ and $M'$ are any two models, then $M$ and $M'$ are isomorphic.

For let $M=\{a,b\}$, and $M'=\{a',b'\}$, where $P_M(a)$ holds and $P_{M'}(a')$ holds. Then the mapping $\varphi$ that takes $a$ to $a'$ and $b$ to $b'$ is a (structure-preserving) isomorphism from $M$ to $M'$.

  • $\begingroup$ If I understood you correctly, in the case of isomorphism we have just one model, because all the models will map to the same thing. Can you give me an actual example with it? On the other hand, when you say $\{1,2\}$ can be a model, can take for example $P(x)$ being "x is prime". So, in the case of $P(1)$ it will be false, in the case of $P(2)$ it will be true. So, first two axioms hold, for the third and forth one, conjunction will be false, and equality will be false, so I will get $0 \implies 0$, is my logic correct? $\endgroup$ – user72151 Nov 11 '15 at 21:26
  • $\begingroup$ All four axioms hold for your example. As I wrote, there are infinitely many models. But they are all abstractly "the same." More precisely, as done in the answer, for any two models $M$ and $M'$ there is an isomorphism from $M$ to $M'$. $\endgroup$ – André Nicolas Nov 11 '15 at 21:48
  • $\begingroup$ Thanks, good to hear that my example is a valid one too. $\endgroup$ – user72151 Nov 11 '15 at 21:51
  • $\begingroup$ How can I extend the notion of isomorphism a bit? I mean, instead of just saying "there is an isomorphism from $M$ to $M'$, can I explain it a bit more? Like maybe also an example or something, or a simpler explanation that explains your notion "they are all abstractly the same"? $\endgroup$ – user72151 Nov 13 '15 at 10:29
  • $\begingroup$ I don't know what you mean by extending the notion. In (abstract) algebra, the notion comes up frequently, and is even of practical importance (it can be useful to know whether two graphs are isomorphic). More general notion is homomorphism, in which a mapping preserves structure but is not necessarily one to one. $\endgroup$ – André Nicolas Nov 13 '15 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy