Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
In both cases you switched from $\wedge$ to $\vee$ by accident. –  Christoph Nov 3 '13 at 22:40
1  
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
1  
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
1  
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

2 Answers 2

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

share|improve this answer

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 …

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.