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.

I'm trying to show why it isn't possible to define an order of magnitude on $\mathbb Z_n$ (modular arithmetic) that satisfies the ordering properties of $\mathbb Z$.

By letting addition to be $\oplus$ and multiplication $\otimes$, I know the following about $\mathbb Z_n$:

  1. Closed under $\oplus$ and $\otimes$.

  2. $\oplus$ and $\otimes$ are commutative.

  3. $\oplus$ and $\otimes$ are associative.

  4. $0$ is $\oplus$ identity and $1$ is $\otimes$ identity.

  5. Cancellation: $(-a) \oplus a = 0$.

  6. $$a \otimes (b \oplus c) = a \otimes b \oplus a \otimes c,$$

    $$(b \oplus c) \otimes a = b \otimes a \oplus c \otimes a .$$

How would I prove that at least one of the ordering properties of $\mathbb Z$ does not hold for $\mathbb Z_n$?

I will be definitely using the ordering properties of $\mathbb Z$:

  1. exactly one of $a < b$ or $a = b$ or $a > b$ holds;

  2. if $a < b$ and $b < c$, then $a < c$;

  3. if $a < b$ then $a + c < b + c$;

  4. if $a < b$ and $c > 0$ then $a \cdot c < b \cdot c$.

In a way I can see that one of these properties would collapse in $\mathbb Z_n$, but I cannot prove it. By contradiction perhaps? (start with $a < b$ and find end up with $a > b$?)

Any help much appreciated.

share|improve this question
    
Is this a homework problem? –  Grumpy Parsnip Feb 12 '11 at 13:19
    
No, just some extra exercises. I do my assignments all by myself. –  leqs Feb 12 '11 at 13:28

3 Answers 3

up vote 10 down vote accepted

Prove that $1>0$. Conclude that $n-1 >0$. Now add $1$ to both sides.

share|improve this answer
2  
Actually, you don't need to prove that $1>0$. If $1<0$, then the same argument holds. So you don't need to use property 4. –  lhf Feb 12 '11 at 13:27
    
Is n-1 a convenient choice so I can end up with n ≡ 0 (mod n)? –  leqs Feb 12 '11 at 13:35
    
Keep adding $1$ to both sides of the inequality. (Aka, induction.) –  lhf Feb 12 '11 at 13:37
    
Let's see if I got it: after n-1>0 /+1, I get n>1, which is 0>1, because n=0 [n ≡ 0 (mod n)]? –  leqs Feb 12 '11 at 13:44
    
@leqs, yes, and $0>1$ contradicts $1>0$, by property 1. –  lhf Feb 12 '11 at 14:36

It is a 1943 theorem of F.W. Levi that for a commutative group $(G,+)$ the following are equivalent:

(i) There exists a total ordering relation $\leq$ on $G$ which is compatible with the group law in the sense that for all $x_1,x_2,y_1,y_2 \in G$, $x_1 \leq y_1, \ x_2 \leq y_2 \implies x_1 + x_2 \leq y_1 + y_2$.

(ii) $G$ is torsionfree: for all $x \in G$ and $n \in \mathbb{Z}^+$, $nx = 0 \implies x = 0$.

A proof (and a citation to Levi's paper) is given in $\S 17.2$ of these notes.

Note that the implication (i) $\implies$ (ii) -- which is what was being asked about here -- is by far the easier one, and the argument I give for this is no different than those in the other answers. (So this answer is more for those with a more general interest in ordered commutative groups.)

share|improve this answer
    
I appreciate your assistance, even though I don't understand how your argument is equivalent to what I have asked here. Don't get me wrong, you're most probably right, it's just that I'm not yet able to see it for myself. –  leqs Feb 14 '11 at 17:05
    
lhf's arguments were sufficient anyway. –  leqs Feb 14 '11 at 17:07
    
@leqs: Dear leqs: sure. –  Pete L. Clark Feb 14 '11 at 18:16

HINT $\ \: $ ordered $\Rightarrow$ torsion-free: $\rm\ x>0\ \Rightarrow\ n\cdot x > 0\ \Rightarrow\ n\cdot x \ne 0\ \ $ for integral $\rm\ n > 0$

share|improve this answer

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.