# Proving that $aRb \iff a = b \lor a = b^2$ is antisymmetric.

Over $\mathbb{N}$, $aRb \iff a = b \lor a = b^2$.

I'm having problems determining if this relation is antisymmetric.

I think it is. I did the following:

## Direct proof attempt (got stucked)

We have to prove that $aRb \land bRa \implies a = b$.

Our premise is the fact that $aRb \land bRa$.

Based on our premise, we know that the following occurs:

$$(a = b \lor a = b^2) \land (b = a \lor b = a^2)$$

Distribute:

$$[(a = b \lor a = b^2) \land b = a] \lor [(a = b \lor a = b^2) \land b = a^2]$$

Absortion:

$$(a = b) \lor [(a = b \lor a = b^2) \land b = a^2]$$

Clearly I need to get rid of the rightmost part. But I'm not sure how. How can I proceed here?

## Proof by contradiction attempt (almost worked)

We have to prove that $aRb \land bRa \implies a = b$.

Our premise is the fact that $aRb \land bRa$.

Suppose that $a \not = b$.

Based on our premise, we know that the following occurs: $$(a = b \lor a = b^2) \land (b = a \lor b = a^2)$$

Since we're supposing that $a \not = b$, it is simplified to

$$a = b^2 \land b = a^2$$

Alright, so this is where I'm not sure: since $a \not = b$, can I affirm that the square of either number will always be different from the other number, in $\mathbb{R}?$ Because if that's the case, clearly $a = b^2 \land b = a^2$ won't hold, contradicting the premise, proving that it is indeed antisymmetric.

-
In both cases you switched from $\wedge$ to $\vee$ by accident. – Christoph Nov 3 '13 at 22:40
Based on our premise, we know that the following occurs: $$(a = b \lor a = b^2) \color{red}\lor (b = a \lor b = a^2)$$ – Git Gud Nov 3 '13 at 22:41
Goodness. I'll try to correct it as soon as possible. Thank you. – Zol Tun Kul Nov 3 '13 at 22:47
Edited. Fortunately (or not), I still got stuck. – Zol Tun Kul Nov 3 '13 at 22:52
Since $a=b$ is equivalent to $b=a$ you end up with $a=b \vee (a=b^2 \wedge b=a^2)$, try to conclude $a=b$ in the second case. – Christoph Nov 3 '13 at 22:53

HINT: Note that in $\Bbb N$ if $a=b^2$ then either $a=0$ or $a=1$ or $b<a$.

-

The hypothesis “$a\mathrel{R}b$ and $b\mathrel{R}a$” splits into four cases:

• $a=b$ and $b=a$

• $a=b$ and $b=a^2$

• $a=b^2$ and $b=a$

• $a=b^2$ and $b=a^2$

The only case that needs work is the fourth one, where $a=a^4$, that is $a=0$ or $a=1$. But …

-
It is a bit unclear to me how did you split that into four cases. Could you elaborate on that? Thanks! – Zol Tun Kul Nov 4 '13 at 5:09
@Omega I just did $(A\lor B)\land(C\lor D)\equiv(A\land C)\lor(A\land D)\lor(B\land C)\lor(B\land D)$. – egreg Nov 4 '13 at 7:24