Results 1 to 2 of 2

Math Help - 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,559
    Thanks
    785
    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).
    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: October 3rd 2011, 06:28 PM
  2. [SOLVED] A logic question!!
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: July 11th 2010, 03:05 PM
  3. logic question
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 21st 2009, 12:52 AM
  4. Question about logic
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 5th 2008, 06:51 AM
  5. Logic Question
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: June 24th 2008, 12:24 AM

Search Tags


/mathhelpforum @mathhelpforum