Results 1 to 14 of 14

Math Help - Relational Composition Problem - Please help!

  1. #1
    Newbie
    Joined
    Sep 2006
    Posts
    6

    Relational Composition Problem - Please help!

    Hi, I have a problem which says this:

    Prove that if r;s is reflexive, then r is total and s is surjective.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by iazz View Post
    Hi, I have a problem which says this:

    Prove that if r;s is reflexive, then r is total and s is surjective.

    Thanks.
    Reflexsive on what?
    Surjective on what?
    I assume you want to prove a certain set (or all sets having this property) are totaliy ordered sets.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    It appears that both each of R and S is a relation on some set A: that is, each is a subset of AXA. Some authors say a relation is total if each element of A is the first term of some pair in the relation. (Now that may not be meant here! But it fits.)
    Suppose that we are given that SoR is reflexive. Thus if t is an element of A then the pair (t,t) belongs to SoR. That means that there exists an element w in A such that the pair (t,w) belongs to R and the pair (w,t) belongs to S. This means that t is comparable to some element is A by way of R making R total. And t is the second term of some pair is S making S surjective.

    [Now, I know that the problem is written as “r;s”. But the statement is true only for SoR. Again, the author may have meant something else entirely.]
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Sep 2006
    Posts
    6
    That is how the problem is exactly written. It is taken from a past paper of our type of examination. These are the type of problems we are given. So plato that is the type of answer I should give?

    Thanks a lot. To be honest I am more confused about how to answer these type of problems rather than not understanding them.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    You do realize that that is just a guess as to what the terms mean.
    This is the painful fact: There are no standard definitions in mathematics.
    When you post such a problem it is helpful to include definitions were possible.
    That answer may not be correct. It depends upon the definitions.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Sep 2006
    Posts
    6
    Right .. according to the book we use these are the definitions:

    Relational Composition:
    R ; S = {x :X, y:Y, z :Z | x -> y is an element of R /\ y -> z is an element of
    S . (x,z)}

    Reflexivity:
    for all x : X . (x,x) is an element of R

    Totality:

    for all x,y : X . (x,y) is an element of R \/ (y,x) is an element of R \/ x = y

    Symmetry:

    for all x,y : X . (x,y) is an element of R => (y,x) is an element of R


    Thanks again.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    My, my; I have never seen a definition for totality like that except for posets. Reflexive and symmetric are rather standard. But composition is backward from most other texts in the field. What text is it anyway?

    Now back to the problem. The above proof still works for S being surjective.
    But I do not see right away how to get totally for R.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Sep 2006
    Posts
    6
    Text is Discrete Maths By Example - Andrew Simpson. So any easier definitions which can help me solve my problem? I'd appreciate them

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Sep 2006
    Posts
    6
    Thanks for the wiki, I am starting to understand. I have only got one question: when you have a relational composition R ; S how can you write the definition as reflexive? I can write a single relation such as R, as reflexive by using the definition (for all x : X . (x,x) is an element of R) but I can't figure how to write it as a relational composition.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Apr 2006
    Posts
    399
    Awards
    1
    Quote Originally Posted by iazz View Post
    Text is Discrete Maths By Example - Andrew Simpson. So any easier definitions which can help me solve my problem? I'd appreciate them.
    Plato gave you a definition of total that works for this problem. This Wikpedia page talks about the different definitions for total. Are you sure you have the right one?

    Quote Originally Posted by Plato View Post
    It appears that both each of R and S is a relation on some set A: that is, each is a subset of AXA. Some authors say a relation is total if each element of A is the first term of some pair in the relation. (Now that may not be meant here! But it fits.)
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    JakeD, you know that we have to be care with both Wikipedia and MathWorld.
    That definition of ‘Left Total’ given there is the same as Ken Rosen uses for total.
    Using that definition then the proof I gave above goes through. But Simpson seems to be using the later definition. I do not see a way to prove the statement using that definition. For any x & y, (x,y) or (y,x). Don’t see it.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    Apr 2006
    Posts
    399
    Awards
    1
    Quote Originally Posted by iazz View Post
    Thanks for the wiki, I am starting to understand. I have only got one question: when you have a relational composition R ; S how can you write the definition as reflexive? I can write a single relation such as R, as reflexive by using the definition (for all x : X . (x,x) is an element of R) but I can't figure how to write it as a relational composition.

    Thanks.
    For all x, (x,x) is an element of R; S requires that for all x in X there exists a y such that (x,y) is an element of R and (y,x) is an element of S.

    Quote Originally Posted by iazz View Post
    Relational Composition:
    R ; S = {x :X, y:Y, z :Z | x -> y is an element of R /\ y -> z is an element of S}

    Reflexivity:
    for all x : X . (x,x) is an element of R
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Apr 2006
    Posts
    399
    Awards
    1
    Quote Originally Posted by Plato View Post
    JakeD, you know that we have to be care with both Wikipedia and MathWorld.
    That definition of ‘Left Total’ given there is the same as Ken Rosen uses for total.
    Using that definition then the proof I gave above goes through. But Simpson seems to be using the later definition. I do not see a way to prove the statement using that definition. For any x & y, (x,y) or (y,x). Don’t see it.
    Yes, I've seen a few problems with them, but that Wikipedia page was clear that different authors use different definitions and the definitions it gave looked OK to me.

    I agree with you on the proof.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    Sep 2006
    Posts
    6
    Thank you ppl. You were of great help
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 26th 2010, 02:22 PM
  2. relational algebra
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 16th 2009, 12:49 PM
  3. Relational proof
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: March 16th 2009, 12:38 PM
  4. Prove with relational algebra
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 10th 2009, 11:13 AM
  5. (Discrete Mathmatics) Defining a relational set
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 8th 2009, 06:36 AM

Search Tags


/mathhelpforum @mathhelpforum