Page 1 of 4 1234 LastLast
Results 1 to 15 of 46
Like Tree3Thanks

Math Help - Reflexive and Anti-symmetric

  1. #1
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Reflexive and Anti-symmetric

    Using the abstract definition of relation among elements of set A as any subset of AXA (AXA: all ordered pairs of elements of A), give a relation among {1,2,3} that is antisymmetric other than {(1,1), (2,2, (3,3).
    Last edited by Hartlw; November 8th 2012 at 05:21 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Reflexive and Anti-symmetric

    The standard non-strict order.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Reflexive and Anti-symmetric

    Quote Originally Posted by emakarov View Post
    The standard non-strict order.
    This would include, for example, (1,2) and (2,1). How does this imply 1=2 (the requirement for anti-symmetric)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Reflexive and Anti-symmetric

    It is not true that 1 ≤ 2 and 2 ≤ 1 in the standard order.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Reflexive and Anti-symmetric

    Quote Originally Posted by emakarov View Post
    It is not true that 1 ≤ 2 and 2 ≤ 1 in the standard order.
    < and = are irrelative to the abstract definition of relation, but I see your point- for example, the relation (1,2) is not anti-symmetric by your judgement.

    However, wliki defines antisymmetry as: If R(a,b) and R(b,a) then a=b.

    So in order to judge R as anti-symmetric, R(a,b) and R(b,a) must both be present. So you can't call (1,2) (or the strict order) anti-symmetric because (a,b) and (b,a) are not both present to make the judgement.

    Thanks for your challenging and informative response.
    Last edited by Hartlw; November 8th 2012 at 06:59 AM. Reason: Thanks
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    758

    Re: Reflexive and Anti-symmetric

    Quote Originally Posted by Hartlw View Post
    < and = are irrelative to the abstract definition of relation, but I see your point- for example, the relation (1,2) is not anti-symmetric by your judgement.

    However, wliki defines antisymmetry as: If R(a,b) and R(b,a) then a=b.

    So in order to judge R as anti-symmetric, R(a,b) and R(b,a) must both be present. So you can't call (1,2) (or the strict order) anti-symmetric because (a,b) and (b,a) are not both present to make the judgement.

    Thanks for your challenging and informative response.
    huh?

    [R(a,b) & R(b,a)] → (a = b) is logically equivalent to (this equivalence is known as "equivalence of the contrapositive to the implication"):

    (a ≠ b) → ¬[R(a,b) & R(b,a)] which is equivalent to (by DeMorgan's laws):

    (a ≠ b) → ([¬R(a,b)] v [¬R(b,a)])

    which says that if a and b are unequal, only ONE of the pairs (a,b) and (b,a) will be in R, at MOST (it might be that neither one is, a and b might be "incomparable").

    here is a SECOND relation R that is anti-symmetric and reflexive on {1,2,3}:

    R = {(1,1),(1,2),(1,3),(2,2),(3,3)}, how do we normally express this relation?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Reflexive and Anti-symmetric

    Please stick to subject and definitions.
    Your example R is reflexive but not anti-symmetric. You can't judge it to be anti-symmetric unless (a,b) and (b,a) are both present.

    Is ($,%,#,!) in alphabetical order? You can't judge it to be in alphabetical order unless letters are present. The absence of letters does not mean it is in alphabetical order, except in a very silly sense: it is not not in alphabetical order therefore it is in alphabetical order. Is the null set in alphabetical order because it is not not in alphabetical order?

    EDIT: reflexive is necessary for anti-symmetric but not sufficient for {1,2,3} because the only relation that is reflexive and anti-symmetric is {(1,1),(2,2),(3,3)}. {(1,1),(2,2),(3,3),(1,2)} is reflexive but not anti-symmetric.

    CORRECTION to EDIT {(1,1),(1,2)} is anti-symmetric but not reflexive: (a,b) and (b,a) are present and a=b=1
    Last edited by Hartlw; November 8th 2012 at 08:20 AM. Reason: noted
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,935
    Thanks
    337
    Awards
    1

    Re: Reflexive and Anti-symmetric

    Quote Originally Posted by Hartlw View Post
    Your example R is reflexive but not anti-symmetric. You can't judge it to be anti-symmetric unless (a,b) and (b,a) are both present.
    I think a more emphatic way to phrase this statement is "If R(a,b) and R(b,a) then we must have a = b." I think this is clearer in the contrapositive: "If R(a,b) but a is not equal to b, then R(b,a) must not hold." (Also from Wiki.)

    I think Devano's post was correct and quite relevant on this point. As was emakarov's example.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    758

    Re: Reflexive and Anti-symmetric

    you seem to feel that for an assertion "x implies y" to be true, we must actually have some x's to "test it". this is not the case, google "vacuous truth".

    the assertion aRb & bRa → a = b only tells us when we can conclude a = b. if (a,b) or (b,a) is not in R, it might be that a = b, or it might not. we can't tell.

    for example the relation R on the integers defined by aRb if a < b is anti-symmetric, but not reflexive. so neither (2,1) nor (2,2) is in R, but we cannot conclude just from "non-membership" in R that the second coordinate isn't equal to the first. both can happen.

    i know what an anti-symmetric relation is. i don't believe you do.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Reflexive and Anti-symmetric

    Let me simplify my question:
    Based on the following definitions:

    A) Relation R: Subset of AXA (Plato)
    B) Antisymmetric Relation: If R(a,b) and R(b,a), then a=b (wiki)

    Are the following relations antisymmetric:

    1) {(1.2), (2,1)}
    2) {(1,2), (1,3)}
    3) {(1,1), (1,2)}
    Last edited by Hartlw; November 8th 2012 at 04:07 PM. Reason: wiki reference
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Reflexive and Anti-symmetric

    1) No. 2) Yes. 3) Yes.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Reflexive and Anti-symmetric

    Quote Originally Posted by emakarov View Post
    1) No. 2) Yes. 3) Yes.
    Thanks for your reply.

    I would answer 1) No. 2) No. 3) Yes, on the basis that for "if A then B" to be true A has to exist.

    I forgot to add,

    4) {(2,2)}.

    Presumably we would agree that this is "Yes."

    EDIT: Deveno wrote: " the assertion aRb & bRa → a = b only tells us when we can conclude a = b. if (a,b) or (b,a) is not in R, it might be that a = b, or it might not. we can't tell." If we can't tell we can't conclude that it is anti-symmetric.

    PS: I couldn't find a definition of standard non-strict order. A simple set of number pairs would have sufficed to answer my original question, and avoided a lot of subsequent discussion. I guess this is partially my fault. In retrospect, the essence of the discussion is: Is {(1,2)} anti-symmetric? (easy for mathemiticians), but why?
    Last edited by Hartlw; November 9th 2012 at 07:55 AM.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    758

    Re: Reflexive and Anti-symmetric

    yes R = {(1,2)} is anti-symmetric on the set {1,2} (it is important to specify the underlying set the relation is on). why? because (2,1) is NOT in R.

    symmetric and anti-symmetric have a geometric interpretation:

    one can view a set SxS as a plane, of sorts (especially if S is a subset of a field). the diagonal of S is the subset of SxS that lies on the "diagonal line" s2 = s1.

    a symmetric relation is one that if it includes a point (a,b) also includes its "reflection across the diagonal".

    an anti-symmetric relation is one that includes only one of a "reflection-pair" {(a,b),(b,a)} (if a = b there is only one element in this set, anyway).

    some "typical" anti-symmetric relations (ones the "general idea" is modeled on, or abstracted from):

    a,b belong to some (subset) of an ordered field (like the real numbers), and R = ≤

    a,b are natural numbers and R = | (that is: aRb means a divides b).

    A,B are elements of a power set, P(S), and R = ⊆.

    an anti-symmetric relation need not induce a dichotomy: it need not be that case that one of aRb, bRa hold (a total non-strict order will).

    for example, with R = divisibility, and S = N, the natural numbers, we do not have 4 divides 6 OR 6 divides 4. but we DO have: if a|b and b|a, then a = b.

    or: for R = ⊆, we cannot say that {a,c} ⊆ {b,c} or vice versa, but we CAN say if A ⊆ B and B ⊆ A, then A and B are the same set.

    usually, the anti-symmetric relations of most interest to mathematicians are those which are reflexive AND transitive, which form partial orders (these are very different from their symmetric counter-parts, the equivalences).
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Reflexive and Anti-symmetric

    Quote Originally Posted by Hartlw View Post
    Are the following relations antisymmetric:

    1) {(1.2), (2,1)}
    2) {(1,2), (1,3)}
    3) {(1,1), (1,2)}
    Quote Originally Posted by Hartlw View Post
    I would answer 1) No. 2) No. 3) Yes, on the basis that for "if A then B" to be true A has to exist.
    One cannot say "A exists" when A is a proposition. A proposition can be either true or false. And an implication "if A then B" can be true even if A is false. In fact, in this case the implication is true regardless of whether B is true. Recall that "if A, then B" is true iff A is false or B is true; this means the implication is false iff A is true and B is false.

    Why is {(1,2), (1,3)} antisymmetric? We need to check "For all a, b, if R(a, b) and R(b, a), then a = b." Let's substitute all possible pairs of a and b. For example if a = 1 and b = 1, then both R(a, b) and R(b, a) are false, so "R(a, b) and R(b, a)" is false. Therefore, the implication is automatically true. If a = 1 and b = 2, then R(a, b) is true, but R(b, a) is false, so "R(a, b) and R(b, a)" is again false.In fact, you can't find a single pair (a, b) such that "R(a, b) and R(b, a)" is true. This means that the implication "if R(a, b) and R(b, a), then a = b" is true solely because the premise is always false. Therefore, the relation is antisymmetric.

    Quote Originally Posted by Hartlw View Post
    PS: I couldn't find a definition of standard non-strict order.
    A strict order is irreflexive while a non-strict order is reflexive, i.e., it contains the equality relation. The standard strict order on reals and its subclasses is <, and the standard non-strict order is <=.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Reflexive and Anti-symmetric

    Thanks Deveno:
    If R is divisibility, only 2|4 belongs to R, not 4|2, in which case R is not anti-symmetric in my opinion based on:

    “If A implies B, then C” requires A for C.

    In which case, R is anti-symmetric iff it is reflexive, because, by def,
    if aRb and bRa implies a=b, then reflexive, in my opinion.


    Thanks Emakorov:
    You are taking this into the realm of semantics and logic. I don’t think that fast. If that is what is required to understand the definition of anti-symmetric, then either the necessary logic, or reference to it, should be included in the definition. There is , of course, the possibility that I am the only one that does not understand the definitiion, in which case I can safeley be ignored. But note, I can only be safeley ignored if "I am the only one that does not understand the definitiion" is true, ie, exists.

    I really should take this to “Math Forum” before I get canned. I’ll have to gather my thoughts first.
    Last edited by Hartlw; November 9th 2012 at 10:38 AM.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 4 1234 LastLast

Similar Math Help Forum Discussions

  1. Reflexive And Symmetric
    Posted in the Discrete Math Forum
    Replies: 17
    Last Post: November 7th 2012, 12:58 PM
  2. reflexive, anti symmetric etc... for a set
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 23rd 2012, 04:52 PM
  3. Symmetric, transitive, not reflexive?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 2nd 2010, 12:32 AM
  4. Reflexive, symmetric, and transitive
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 5th 2009, 11:08 AM
  5. Reflexive and symmetric
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: March 12th 2009, 04:56 AM

Search Tags


/mathhelpforum @mathhelpforum