Thread: 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) $\displaystyle \forall x\exists y\,R(x,y)$
(2) $\displaystyle \forall x\forall y\,\neg(R(x,y)\land R(y,x))$
(3) $\displaystyle \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: $\displaystyle \forall x\,\neg(R(x,x)$.

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