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!

Does a refl/anti-symm relation on a set A have this property?

  1. Dec 2, 2014 #1
    1. The problem statement, all variables and given/known data
    Let ##R## be an ordered relation on a set ##A## that is reflexive and anti-symmetric.
    If there is a chain of elements in ##R## that begins and ends with the same element, say the element ##x \in A## is it true that all the elements of ##R## sandwiched in between the ones beginning and ending in ##x## are equal to each other?

    2. Relevant equations
    For clarification Let the 'chain' of elements in ##R## be the following:
    ##(x,b_0), (b_0,b_1), ..., (b_n, x)##
    let ##Z = \{b_0, b_1, ..., b_n\}##
    If ##R## is a reflexive and anti-symmetric ordered relation are all elements of ##Z## equivalent?
    3. The attempt at a solution
    I came up with a few antisymmetric, reflexive ordered relations and tested the validity of this argument and it passed in each one so I am guessing that the theorem above may be true since I have not found a counter-example yet. I just have no idea how to express it in a proof. The examples I came up with were:

    The set ##G=\{(x,y) \in P\text{ x }P~ |~ x \ \text{genes come from}\ y\}## where ##P## is the set of all people,
    The set ##D=\{(x,y) \in ℤ\text{ x }ℤ ~|~x \ \text{divides}\ y\}##
    And also the standard less than or equal to ordered relation.

    In every case it was implied that if a element of the set under which the relation is ordered under begins and ends a chain of ordered pairs in the ordered relation, then all of the elements are equivalent to one another, as a consequence of anti-symmetry and reflexivity.

    I'm unsure of how to start this proof. I've tried defining a set containing all the intermediate elements (in this case being the ##b_j##'s in the set ##Z## and assuming that there is at least two elements that are not equal to one another in the set and trying to find a contradiction, but I ran into a dead end there as well. Any suggestions? Or perhaps someone can think of a counter example ruling out the theorem completely?
     
    Last edited: Dec 2, 2014
  2. jcsd
  3. Dec 3, 2014 #2

    RUber

    User Avatar
    Homework Helper

    I think in general, you only need to show that it is true for any element y such that x R y R x implies that x=y.
    I do not have a clear mental image of a rigorous proof, but I would start with the basics:

    reflexive means that x R x for all x.
    anti-symmetric means that x R y implies y ~R x.
    So, x ~R x. If y R x and y ~R x, does this mean y = x?

    Also, I think ordering is useful since there should not be anything between x and x in an ordered relation other than more x.
     
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: Does a refl/anti-symm relation on a set A have this property?
Loading...