Results 1 to 4 of 4

Math Help - What's wrong with my proof involving anti-symmetry

  1. #1
    Junior Member
    Joined
    Feb 2010
    From
    New Jersey
    Posts
    73

    What's wrong with my proof involving anti-symmetry

    Hi Math people. Can someone tell me what's wrong with my proof, below? My professor did not give me credit for it, but did not provide feedback, either. She posted the answers online and her proof took a completely different tack than mine.

    I get that I did the proof differently. But I'm curious what is wrong with my proof, especially the first part which I was pretty confident of. But all feedback is appreciated.

    My approach, for the 'left-to-right' proof, was to take the two possible cases (x=y and x not= y) and show that only the expected on was in R and R inverse. Seems pretty straightforward to me.

    Thanks, everyone.

    Prove: A relation R on a set A is antisymmetric if and only if R \cap R^{-1} \subseteq \{(a,a)\colon a \in A\}.

    Proof: `` \Rightarrow'': Assume R is antisymmetric. That means xRy and yRx implies that x=y.

    Suppose x,y \in A, x=y, and xRy. That means (x,y) \in R and (y,x) \in R^{-1}. Since x=y, we have that (x,x) \in R, (x,x) \in R^{-1}, therefore (x,x) \in R \cap R^{-1}.

    Now, suppose x,y \in A, x \ne y. Since R is antisymmetric, we can't have both xRy and yRx. WLOG, say xRy, then (x,y) \in R, (x,y) \notin R^{-1} and (x,y) \notin R \cap R^{-1}.

    `` \Leftarrow'': Assume R \cap R^{-1} \subseteq \{(a,a)\colon a \in A\}.

    Suppose x,y \in A, x \ne y, (x,y) \in R \cap R^{-1}.\\
    (x,y) \in R \cap R^{-1}\; \Rightarrow\; xRy \text{ and } xR^{-1}y\; \Rightarrow\; yRx.

    So we have xRy,\, yRx, and x \ne y, therefore, R is not antisymmetric. In other words, if x \ne y and (x,y) \in R, and (x,y) \in R^{-1}, then R is not antisymmetric.

    But since we have that only ``twin'' elements may be in R \cap R^{-1}, R must be antisymmetric (that's my argument and I'm sticking to it!).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    Start with (x,y)\in R\cap R^{-1}.
    That means that (y,x)\in R why?
    Does that mean x=y~?.

    Suppose that R\cap R^{-1}\subseteq\{(a,a):a\in A\}.
    If (x,y)\in R \text{ and }(y,x)\in R then (x,y)\in R^{-1} why?
    What does that mean?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2010
    From
    New Jersey
    Posts
    73
    Quote Originally Posted by Plato View Post
    Start with (x,y)\in R\cap R^{-1}.
    That means that (y,x)\in R why?
    Does that mean x=y~?.

    Suppose that R\cap R^{-1}\subseteq\{(a,a):a\in A\}.
    If (x,y)\in R \text{ and }(y,x)\in R then (x,y)\in R^{-1} why?
    What does that mean?
    Since my homework had already been graded, this wasn't a high priority, so I'm returning to this, finally. I get the first half, but I'm not sure about the right to left proof:

    Left to Right
    Assume R is antisymmetric, that means that if xRy and yRx, then x=y.

    Let (x,y)\in R\cap R^{-1} \Rightarrow (x,y)\in R and (x,y)\in R^{-1} \Rightarrow (y,x) \in R.

    But (x,y)\in R and (y,x) \in R and R antisymmetric implies x=y. In other words, R antisymmetric R\cap R^{-1} \Rightarrow \{(a,a): a \in A\}.

    RtoL
    Suppose R \cap R^{-1} \subseteq \{(a,a): a \in A\}.

    Then, (x,y) \in R \cap R^{-1} \Rightarrow (x,y) \in R, (x,y) \in R^{-1} \Rightarrow (y,x) \in R, (y,x) \in R^{-1} \Rightarrow xRy and yRx.

    But (x,y) \in R \cap R^{-1} \Rightarrow x=y. So we have that (x,y) \in R \cap R^{-1} \Rightarrow xRy and yRx \Rightarrow x=y.

    Is that right?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Your use of "=>" is a little off in a few places. Here's how I would write it:

    [I'll use R* for the converse of R]

    Assume appropriate relativization to set A.

    Suppose R is anti-symmetric. Suppose <x y> in R/\R*. So <x y> in R and <y x> in R. So x=y. So <x y> in {<a a> | a in A}. So R/\R* subset of {<a a> | a in A}.

    Suppose R/\R* subset of {<a a> | a in A}. Suppose <x y> in R and <y x> in R. So <x y> in R*. So <x y> in R/\R*. So <x y> in {<a a> | a in A}. So x=y.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Symmetry Group Proof
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 16th 2012, 07:45 AM
  2. Replies: 1
    Last Post: September 4th 2011, 08:17 PM
  3. Matrix Symmetry Proof
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: May 8th 2011, 04:22 PM
  4. Symmetry proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 7th 2010, 01:33 PM
  5. What's wrong with my proof?
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: August 6th 2010, 06:25 PM

Search Tags


/mathhelpforum @mathhelpforum