What's wrong with my proof involving anti-symmetry

Printable View

February 12th 2011, 02:14 PM
MSUMathStdnt

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!).
February 12th 2011, 02:33 PM
Plato

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?
April 4th 2011, 09:25 AM
MSUMathStdnt

Quote:

Originally Posted by Plato

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?
April 4th 2011, 12:23 PM
MoeBlee

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.