Results 1 to 15 of 15

Math Help - Relation

  1. #1
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Relation

    Given the definition that a relation on AXA is a subset of AXA, what does "R is a relation on a set A" mean?

    a) R is a subset of AXA every member of which satisfies R (aRb).

    or

    b) R is a subset of AXA consisting of all (a,b) belonging to AXA st aRb.

    Note both statements satisfy the definition that R is a subset of AXA.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,395
    Thanks
    1481
    Awards
    1

    Re: Relation

    Quote Originally Posted by Hartlw View Post
    Given the definition that a relation on AXA is a subset of AXA, what does "R is a relation on a set A" mean?
    You have that wrong.
    The statement that \mathcal{R} is a relation on A means \mathcal{R}\subseteq(A\times A).

    So statement that \mathcal{S} is a relation on A\times A means \mathcal{S}\subseteq[(A\times A)\times(A\times A)].
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Re: Relation

    Sorry about confusion. The book I am looking at takes "R is a relation on A" to mean "R is a subset of AXA" as self-evident.

    R is a relation on AXB means R is a subset of AXB. So back to my original question.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,395
    Thanks
    1481
    Awards
    1

    Re: Relation

    Quote Originally Posted by Hartlw View Post
    R is a relation on AXB means R is a subset of AXB. So back to my original question.
    That is a false statement.
    Read my reply again about \mathcal{S}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,154
    Thanks
    593

    Re: Relation

    Quote Originally Posted by Hartlw View Post
    Sorry about confusion. The book I am looking at takes "R is a relation on A" to mean "R is a subset of AXA" as self-evident.

    R is a relation on AXB means R is a subset of AXB. So back to my original question.
    again, no. R is a relation on AxB means R is a subset of (AxB) x (AxB).

    (sorry, Plato, didn't see you post. i edited this to make it clear i was responding the the thread starter, and not you)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Re: Relation

    Quote Originally Posted by Plato View Post
    You have that wrong.
    The statement that \mathcal{R} is a relation on A means \mathcal{R}\subseteq(A\times A).

    So statement that \mathcal{S} is a relation on A\times A means \mathcal{S}\subseteq[(A\times A)\times(A\times A)].
    OK. Even better.

    What does R is a relation on a set A mean?

    a) R is a subset of AXA every member of which satisfies R (aRb).

    or

    b) R is a subset of AXA consisting of all (a,b) belonging to AXA st aRb.

    Note both statements satisfy the definition that R \subseteq AXA.

    EDIT: I'm trying to sort out statements like "Suppose R is a partial ordering on a set B and A is a subset of B." Then comes def of lub, which is clear if you take def b) above.
    Last edited by Hartlw; October 12th 2011 at 03:02 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,395
    Thanks
    1481
    Awards
    1

    Re: Relation

    Quote Originally Posted by Hartlw View Post
    I'm trying to sort out statements like "Suppose R is a partial ordering on a set B and A is a subset of B." Then comes def of lub, which is clear if you take def b) above.
    Study this webpage
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Re: Relation

    I did. It has the same ambiguity:

    "A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the set, one of the elements precedes the other."

    My question still stands. Is the set an arbitrary subset for which aRb or is it a subset of ALL menbers of A st aRb?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,395
    Thanks
    1481
    Awards
    1

    Re: Relation

    Quote Originally Posted by Hartlw View Post
    "A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the set, one of the elements precedes the other." My question still stands. Is the set an arbitrary subset for which aRb or is it a subset of ALL menbers of A st aRb?
    You are clearly have difficulty with basic set theory do you not?
    If \mathcal{R} is a partial order on B then \mathcal{R} is a relation on B which is reflexive, anti-symmetric, and transitive.
    Now if A\subseteq B the partial order applies to A.
    So WHAT is your problem with that?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Re: Relation

    Quote Originally Posted by Plato View Post
    You are clearly have difficulty with basic set theory do you not?
    If \mathcal{R} is a partial order on B then \mathcal{R} is a relation on B which is reflexive, anti-symmetric, and transitive.
    Now if A\subseteq B the partial order applies to A.
    So WHAT is your problem with that?
    If R is a subset of AXA, does R consist of a subset of AXA for which aRb (possibly partially ordered) or does it consist of ALL elements of AXA for which aRb?

    I could give a very simple example: for A = {1,2,3}. R= {(1,1), (1,2), (2,2)} or R ={(1,1), (1,2), (2,2), (2,3), (3,3)}. Both satisfy the definition of a poset for R, ie, the definition is ambiguous.

    EDIT: Clarified the wording.
    Last edited by Hartlw; October 12th 2011 at 04:26 PM.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Re: Relation

    "If R is a subset of AXA, does R consist of a subset of AXA for which aRb (possibly partially ordered) or does it consist of ALL elements of AXA for which aRb?

    I could give a very simple example: for A = {1,2,3}. R= {(1,1), (1,2), (2,2)} or R ={(1,1), (1,2), (2,2), (2,3), (3,3)}. Both satisfy the definition of a poset for R, ie, the definition is ambiguous."

    I think this qestion got off track originally with some loose wording on my part. So my question is, based on the above, is the standard definition of relation ambiguous? If not, which of the above interpretations is correct

    The question is serious because I don't know how to interpret it used in a theorem, and it isn't obvious to me (shoudn't be necessary if defined unambiguously).
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,154
    Thanks
    593

    Re: Relation

    a relation R on A is a subset of AxA. that's very simple. the following 2 statements are equivalent:

    aRb and (a,b) is in R.

    a partial order (on A) is a relation with certain extra conditions (not every subset of AxA qualifies).

    these extra conditions are:

    1. reflexivity: aRa <=> (a,a) is in R, for all a in A (R contains the diagonal ΔA).
    2. transitivity: aRb & bRc ---> aRc <=> if (a,b) is in R, and (b,c) is in R, then (a,c) is in R (you can "cut out the middle man").
    3. antisymmetry aRb & bRa --> a=b <=> if (a,b) and (b,a) are in R, a=b

    now let's look at your relations on A = {1,2,3}.

    first we'll consider R = {(1,1), (1,2), (2,2)}. right away, we see R is not reflexive. 3 is in A, but (3,3) is not in R. (A,R) is not a poset.

    now we'll consider R' = {(1,1), (1,2), (2,2), (2,3), (3,3)} since ΔA = {(1,1), (2,2), (3,3)} is a subset of R', R' is reflexive.

    transitivity is a bother to check, but here goes:

    the only elements in R' that are of the form (1,a) are (1,1) and (1,2). if we pick (1,1) as our aR'b, we have two choices for bR'c, (1,1) and (1,2).

    (1,1)&(1,2) in R' -->? (1,2) in R'? yes.
    (1,1)&(1,1) in R' -->? (1,1) in R'? yes. we'll just continue....
    (1,2)&(2,2) in R' --> (1,2) in R'? yes.
    (1,2)&(2,3) in R' --> (1,3) in R'? no. well, R' is not transitive. (A,R') is not a poset.

    well, let's just add (1,3) to R', and call this R". R" is still reflexive, no need to re-check that.

    (1,3)&(3,3) in R" --> (3,3) in R"? yes.
    (2,2)&(2,2) in R" --> (2,2) in R"? yes.
    (2,2)&(2,3) in R" --> (2,3) in R"? yes.
    (2,3)&(3,3) in R" --> (2,3) in R"? yes.
    (3,3)&(3,3) in R" --> (3,3) in R"? yes.

    so R" is reflexive and transitive. is R" anti-symmetric? we only need to check the off-diagonal elements (1,2), (1,3), and (2,3).

    since (2,1), (3,1) and (3,2) are not in R we see that the only pairs (a,b) for which (b,a) is also in R, are the diagonal elements (a,a),

    that is, when a = b. R" is anti-symmetric. so (A,R") IS a poset.

    (in fact, R" is the partial order we usually call ≤).
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Re: Relation

    Thanks. Reference previous post.

    Sorry you had to go through all that. I should have checked it myself. But my question still stands about the ambiguity of definition of a relation:

    If R is a subset of AXA, does R consist of a subset of AXA for which aRb (possibly partially ordered) or does it consist of ALL elements of AXA for which aRb?

    Hopefully this is a better example for poset. ab means (a,b) to save typing

    A = (1,2,3,4,5), AXA=
    11 12 13 14 15
    21 22 23 24 25
    31 32 33 34 35
    41 42 44 44 45
    51 52 53 54 55

    R'
    11 12 13 14 15
    ----22 23 24 25
    -------33 34 35
    ----------44 45
    --------------55
    R''
    11 12 13 14
    ----22 23 24
    --------33 34
    ------------44
    R'''
    11 12 13
    ----22 23
    -------33
    R''''
    11 12
    ----22

    R'''''
    11

    All of the above satisfy R \subseteq AXA. Which one is it? The question stands regardless of R being a poset. The question is about R.

    EDITED A should obviously be (1,2,3,4,5), not (1,2,3). I point out the typo so someone doesn't pick it up and take the post into never- never land.
    Last edited by Hartlw; October 13th 2011 at 07:29 AM.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Re: Relation

    Def: R \subseteq AXA
    Def: aRb iff (a,b) in R
    Def: "Total R": for all a,b \epsilon A, aRb or bRa
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Re: Relation

    The cleanest definition which removes all ambiquities is:

    R \subseteq AXA iff aRb

    ie, Picking R defines aRb, or picking aRb defines R
    Last edited by Hartlw; October 18th 2011 at 07:14 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: April 6th 2011, 11:46 PM
  2. Relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 13th 2010, 07:13 PM
  3. Replies: 1
    Last Post: March 1st 2010, 07:24 AM
  4. Relation ( Equivalence Relation)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 5th 2008, 08:55 AM
  5. relation ~
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: May 21st 2005, 12:58 AM

Search Tags


/mathhelpforum @mathhelpforum