Results 1 to 2 of 2

Thread: question in logic

  1. #1
    Junior Member
    Joined
    Jan 2011
    Posts
    46

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Logic question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 3rd 2011, 05:28 PM
  2. [SOLVED] A logic question!!
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Jul 11th 2010, 02:05 PM
  3. logic question
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Oct 20th 2009, 11:52 PM
  4. Question about logic
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Sep 5th 2008, 05:51 AM
  5. Logic Question
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: Jun 23rd 2008, 11:24 PM

Search Tags


/mathhelpforum @mathhelpforum