1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Abstract Algebra: Relations

  1. Sep 16, 2013 #1
    Abstract Algebra: Relations; Find a relation that is symmetric, etc

    1. The problem statement, all variables and given/known data
    Find a relation that is symmetric and transitive but not reflexive.


    2. Relevant equations

    None, other than my chosen condition on the relation, namely: xy > |x + y|.

    3. The attempt at a solution

    I'm sure this is on here every semester, but if possible I'd like some feedback on my attempt. This is a product relation in Z x Z.


    Call the set O.

    O = {(x,y)∈ Z2: xy > |x + y|}


    Symmetric:

    Since in the integers xy = yx and |x + y| = |y + x|, (y,x)∈ O (it is symmetric).


    Transitive:

    This means, if (a,b)∈ O and (b,c)∈ O then (a,c)∈ O, that is, if ab > |a + b| and bc > |b + c|, then ac > |a + c|.

    First of all, none of a, b or c can be zero, otherwise somewhere along here you'd have 0 > a positive number, because the absolute values are taken.

    Second, either a AND b are positive or a AND b are negative, or you'd get a negative number > a positive number.

    In the first case, if a and b are positive, then by the assumption that bc > |b + c|, c has to be positive. In that case, it is true that ac > |a + c| (if a were 1 and c were 2 this would be false, but we're already assuming that ab > |a + b| and bc > |b+ c|).

    HOWEVER, I'm not exactly clear on how I would give a good reason for the above.

    The similar reasoning is done if a and b are negative. The relation seems to be transitive. I need a little help in demonstrating this, assuming I'm right.



    Reflexive:

    It is NOT reflexive for the following reason: (1,1)∉ O. (1)(1) = 1, but |1 + 1| = 2, and 1 > 2 is nonsense.



    What do you think? Thanks for any help.
     
    Last edited: Sep 16, 2013
  2. jcsd
  3. Sep 16, 2013 #2
    Edit: Oops. Irreflexive is not the same as not reflexive.

    (2,3) and (3,2) are in O, but (2,2) is not. So O is not transitive.
     
    Last edited: Sep 16, 2013
  4. Sep 16, 2013 #3

    Mark44

    Staff: Mentor

    Does the relation have to be one like > or < or =? The problem statement, which I quote below, doesn't place any conditions such as that it must be a relation between numbers.
    Do you have any brothers or sisters? Think about brotherhood or sisterhood as relations.
     
  5. Sep 17, 2013 #4
    Okay, but wouldn't that mean that every relation that is symmetric and transitive is also reflexive? Because I know that is actually false.

    EDIT:
    I'm thinking here that a, b, and c have to be distinct. Is that not the case?

    It has to be in Z x Z. Other than that, no.
    I understand that one pretty well. I can't be a brother to myself.

    So we all agree that my example fails, correct?


    How about this one (I was trying to be fancy earlier. I'll try something easier).

    O = {(x,y)∈ Z2: x≠y}

    Well, if x≠y, then y≠x => symmetric

    If a≠b and b≠c, then a≠c => transitive

    And, a≠a is nonsense => reflexive.




    How is that?


    The reason I didn't use that first is that I have to come up with TWO of these in the integers, and I thought x >y and then x<y for the next one would be kind of lame.
     
    Last edited: Sep 17, 2013
  6. Sep 17, 2013 #5
    Wait. No no no no no. Disregard my answer/question to you at the end of that.

    First, if the relation is x ≠ y, then I won't necessarily have a transitive relation, because just because a ≠ b and b ≠ c, it does not follow that a ≠ c (choose a = 1, b = 2, and c = 3, for example).

    Second, x > y stops me from having symmetry, because if x > y it is not true that y > x.

    Likewise with x < y.


    Third:


    If I add one more stipulation to my condition, I think I'll take care of it. If I forbid x from equaling y, I think that solves that problem.


    How about this:

    O = {(x,y)∈ Z2: xy > |x + y| and x ≠ y}.


    Would that not take care of all cases where (a,b), (b,a)∈ O but (a,a) not in O? I can think of no other thing that could prevent that relation from being transitive. Can anyone else?
     
  7. Sep 17, 2013 #6

    Mark44

    Staff: Mentor

    No, that doesn't work. 2 ≠ 3 and 3 ≠ 2, but 2 = 2. Even though (2, 3) and (3, 2) are in your set, (2, 2) is not.


    No, that makes the relation ≠ irreflexive.
     
  8. Sep 17, 2013 #7
    *I meant to put NOT reflexive there, but I realized that that relation would make it not necessarily be transitive. Just because a≠b and b≠c, it does not follow that a≠c.

    But what about my new condition, if you don't mind?

    O = {(x,y)∈ Z2: xy > |x + y| and x ≠ y}

    (I'm trying to make a relation that is symmetric and transitive, but not reflexive)
     
  9. Sep 17, 2013 #8

    Mark44

    Staff: Mentor

    What's the relation itself? Typical relations are =, ≠, <, ≤, >, ≥, divides, and so on. All you have is a set of ordered pairs, but no operation that is defined on each member of the pair.
     
  10. Sep 17, 2013 #9
    Sorry that's the notation the instructor wants used. The relation is:

    xy > |x + y| AND x≠y
     
  11. Sep 17, 2013 #10
    A binary relation on a set X is, by definition, just a subset of X[itex]\times[/itex]X. There's no need to use any well-known "operations" to define the relation.
     
  12. Sep 17, 2013 #11
    Part of your difficulty with this problem stems from the fact that if you have any two distinct elements x and y with xRy, then symmetry forces yRx, and then transitivity forces xRx (and also yRy). So in a symmetric transitive relation, any element that is related to another must also be related to itself. Trying to keep all elements of the form (x,x) out of your relation is a bad idea.

    The easiest example of a relation on a set that is symmetric and transitive and not reflexive that is remotely interesting is to take a three-element set {x,y,z} and let the relation R be given by R={(x,x),(y,y),(x,y),(y,x)}. Note that it's not reflexive since (z,z) is not in R. It's also not irreflexive, since (x,x) and (y,y) are in R.
     
  13. Sep 17, 2013 #12
    But my text specifically says that the above argument is insufficient to show reflexivity (namely, Symmetry implies xRy and yRx, then transitivity implies xRx, hence reflexivity). Or is that not reflexivity? What more is required to show it?

    No wait. I think I might be getting it. Any symmetric and transitive relation will have each element in the SUBSET where the relation applies relate to itself, but NOT necessarily every element in the original set itself?

    I see here that the relation doesn't use every element in the set (it is missing z). However, every element in the subset R is related to itself.


    Now the question is, how do I find one in Z x Z. I will be working on that pending any more responses.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Abstract Algebra: Relations
Loading...