6

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.

Srivatsan
  • 26,311
leqs
  • 117

3 Answers3

11

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

lhf
  • 216,483
  • 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
  • 1
    @leqs, yes, and $0>1$ contradicts $1>0$, by property 1. – lhf Feb 12 '11 at 14:36
  • @leqs Alternatively, you can start from $1 > 0$ to get the conclusion (via induction) $n > 0$, which is essentially $0 > 0$. This is a contradiction to the law of trichotomy since $0=0$. – Srivatsan Aug 13 '11 at 05:28
7

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

Community
  • 1
Pete L. Clark
  • 97,892
2

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

Bill Dubuque
  • 272,048