# How can I prove that an order (“$<$” say) on $\mathbb Z_n$ cannot be defined?

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.

-
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

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

-
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.)

-
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$

-