# Thread: What's wrong with my proof involving anti-symmetry

1. ## 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 $\displaystyle R$ on a set $\displaystyle A$ is antisymmetric if and only if $\displaystyle R \cap R^{-1} \subseteq \{(a,a)\colon a \in A\}$.

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

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

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

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

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

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

But since we have that only twin'' elements may be in $\displaystyle R \cap R^{-1}$, $\displaystyle R$ must be antisymmetric (that's my argument and I'm sticking to it!).

2. Start with $\displaystyle (x,y)\in R\cap R^{-1}$.
That means that $\displaystyle (y,x)\in R$ why?
Does that mean $\displaystyle x=y~?$.

Suppose that $\displaystyle R\cap R^{-1}\subseteq\{(a,a):a\in A\}$.
If $\displaystyle (x,y)\in R \text{ and }(y,x)\in R$ then $\displaystyle (x,y)\in R^{-1}$ why?
What does that mean?

3. Originally Posted by Plato
Start with $\displaystyle (x,y)\in R\cap R^{-1}$.
That means that $\displaystyle (y,x)\in R$ why?
Does that mean $\displaystyle x=y~?$.

Suppose that $\displaystyle R\cap R^{-1}\subseteq\{(a,a):a\in A\}$.
If $\displaystyle (x,y)\in R \text{ and }(y,x)\in R$ then $\displaystyle (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 $\displaystyle R$ is antisymmetric, that means that if $\displaystyle xRy$ and $\displaystyle yRx$, then $\displaystyle x=y$.

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

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

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

Then, $\displaystyle (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 $\displaystyle yRx$.

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

Is that right?

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.