Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Quick question

  1. Nov 14, 2005 #1
    The antisymmetric relations on a set {a,b} are those, which do not contain both of the pairs (a,b) and (b,a) because that would imply a = b, however a can't equal b since they are elements of a set?

    PS: In our course we allow only one copy of an element in a set, so {a,b} is a set only if a doesn't equal b.

    edit: major typo

    - Kamataat
    Last edited: Nov 14, 2005
  2. jcsd
  3. Nov 14, 2005 #2
    That's a bit restrictive. The set {a} is the same as the set {a,a}. It's just pointless to write the latter, not wrong (multiplicity is ignored, not illegal). Your {a,b} where a=b is still a set that only contains a (or b depending on your labelling preference).
    Asymmetric relations are indeed those which do not contain the pairs (a,b) and (b,a). You disprove the inclusion of elements like (a,a) by the trivial fact that if a=b, then (a,a) = (a,b) = (b,a) cannot be in the relation by definition.
    Last edited: Nov 14, 2005
  4. Nov 14, 2005 #3
    Grrrr, there's a typo in my original post. I meant antisymmetric not asymmetric. Sorry.

    edit: My lecturers textbook has this written in it: "... {a,a,b,c} and {{a,b},{b,a}} do not denote sets, because the elements of a set are distinct." I have read about multiplicity the way you write about it, but my lecturer doesn't seem to take this approach. It's a first year course for students in the maths department, so it doesn't cover advanced axiomatic set theories (but its still pretty hard, we do nothing but proofs).

    - Kamataat
    Last edited: Nov 14, 2005
  5. Nov 14, 2005 #4


    User Avatar
    Science Advisor

    A relation is "asymmetric" if and only if it is not symmetric. That is, there exist some pair (a,b) in the relation for which (b,a) is not in the relation. There might be some other pair, say (x,y) such that (y,x) is in the relation. A relation is "anti-symmetric" if and only if whenever (a,b) is in the relation, (b,a) is not in the relation. It is impossible for another (x,y) to be in the relation with (y,x) also in the relation.

    If I read this correctly, you are talking about relation on the two member set U= {a, b}. The cross-product UxU contains exactly 4 members: UxU= {(a,a), (a,b), (b,a), (b,b)}. Any relation must be a subset of that. In order to be anti-symmetric, a relation cannot contain (a,a) or (b,b) (since, in that situation, it would also contain the reverse: (a,a) or (b,b)!). It may contain (a,b) but then it can't contain (b,a). Conversely, it may contain (b,a) but then it can't contain (a,b). The only antisymmetric relations on {a,b} are
    {(a,b)} and {(b,a)}.
  6. Nov 15, 2005 #5
    Still having trouble with this. Here's what I know:

    Definition 1: [tex]xRy \wedge yRx \Rightarrow x=y[/tex]
    Definition 2 (equivalent to #1): [tex]x\neq y \Rightarrow \rceil(xRy) \vee \rceil(yRx)[/tex].

    I have the set {a,b}. The cross-product {a,b}x{a,b}={(a,a),(a,b),(b,a),(b,b)} and a relation on {a,b} is a subset of that cross-product. The subsets (relations) are:

    0 elements: [tex]\emptyset[/tex]
    1 element: {(a,a)}, {(a,b)}, {(b,a)}, {(b,b)}
    2 elements: {(a,a),(b,a)}, {(a,a),(a,b)}, {(a,a),(b,b)}, {(b,a),(a,b)}, {(b,a),(b,b)}, {(a,b),(b,b)}
    3 elements: {(a,a),(b,a),(a,b)}, {(a,a),(b,a),(b,b)}, {(a,a),(a,b),(b,b)}, {(b,a),(a,b),(b,b)}
    4 elements: {(a,a),(a,b),(b,a),(b,b)}

    From the definiton of anti-symmetric above, I see that the anti-symmetric relations are those that don't contain (a,b) or (b,a) or both:

    [tex]\emptyset[/tex], {(a,a)}, {(a,b)}, {(b,a)}, {(b,b)}, {(a,a),(b,a)}, {(a,a),(a,b)}, {(a,a),(b,b)}, {(b,a),(b,b)}, {(a,b),(b,b)}, {(a,a),(b,a),(b,b)}, {(a,a),(a,b),(b,b)}. Twelve in total (that's what my lecturer said also).

    My understanding is that (a,b) and (b,a) can't be both in the relation, because that would imply a=b, however that is not true. The lecturer has made it clear verbally and in his book, that to him things like {a,a} and {a,b}, where a=b, are not sets at all. Hence a=b can't be true (since the problem assumes {a,b} is a set) and if a=b isn't true, then either (a,b) or (b,a) must be excluded from an anti-symmetric relation (my understanding of definition 2).

    - Kamataat
    Last edited: Nov 15, 2005
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook