question in logic

**Mike12** · March 20th 2011, 09:45 AM

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

**emakarov** · March 20th 2011, 11:26 AM

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<j$ . 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).

Thread: question in logic

LinkBack

Thread Tools

Display

question in logic

Similar Math Help Forum Discussions

Logic question

[SOLVED] A logic question!!

logic question

Question about logic

Logic Question

Search Tags