Two Place Position and Model Question

Question

!

i get trouble in one multiple choice question in logic course: any one could help me with some description ?

if we have Two-place position predicate, like :

1) all models of $\varphi$ is infinite.

2) all models of $\varphi$ is finite.

3) $\varphi$ has infinite and finite model.

4) $\varphi$ has no model .

which of them is correct? any idea?

Answer 1

The sentence $\varphi$ says that $P$ is totally irreflexive and transitive, and that every element is related to some (necessarily other) element. Let $P$ be the relation $<$ on $Z$, the set of integers; it's easy to check that $\varphi$ is satisfied. Thus, $\varphi$ has infinite models.

However, $\varphi$ has no finite model. HINT: Use the first and third conjunct of $\varphi$ to show that in a finite model the second (transitivity) must be violated. You can do this by showing that there must be a cycle:

$$P(x_0,x_1),P(x_1,x_2),\ldots,P(x_{n-1},x_n),P(x_n,x_0)\;.$$