# Math Help - question in logic

1. ## question in logic

how to show that the following sentence has a denumerable model but not finite model:
for all x there exist y R(x,y) and for all x for all y negation of (R(x,y) and R(y,x) ) and for all x for all y for all z ((R(x,y) and R(y,z) implies R (x,z)).
NOte: I uesd and to mean conjunction ,
R is a binary relation

2. So, this is a conjunction of three sentences.

(1) $\forall x\exists y\,R(x,y)$
(2) $\forall x\forall y\,\neg(R(x,y)\land R(y,x))$
(3) $\forall x\forall y\forall z\,(R(x,y)\land R(y,z)\to R(x,z)$

(2) and (3) mean that R is asymmetric and transitive, respectively. (Relations satisfying (1) are sometimes called serial.) Note that (2) implies that R is irreflexive: $\forall x\,\neg(R(x,x)$.

Suppose $M\models(1)\land(2)\land(3)$. Pick any $a_0$ from the domain of M. Then (1) guarantees that there exists an $a_1$ such that $M\models R(a_0,a_1)$. Similarly, there exists an $a_2$ such that $M\models R(a_1,a_2)$ and so on. This way, we can build a sequence $a_0,a_1,a_2,\dots$ where, due to (3), $R(a_i,a_j)$ for all $i. Now, the sequence has to be infinite, i.e., it is not possible that $a_{i+k}=a_i$ for some $i$ and $k>0$. Indeed, suppose $a_{i+k}=a_i$. If $k=1$, then $R(a_i,a_i)$, which contradicts irreflexivity of R. If $k>1$, let $k'=i+k-1$; then $k'>i$ and $a_{{k'}+1}=a_i$. So, $R(a_i,a_{k'})$ and $R(a_{k'},a_i)$, which again contradicts (2).