SI242: Adding order to a ring

Order: a place for everything and everything in its place

Our long-term goal is to really understand the integers. We started with the observation that the integers are a number system in we can "do arithmetic", and so we investigated what it means to be a number system in which you can do arithmetic. Mathematicians number systems in which you can do arithmetic "rings", and the last few classes have been about the ring axioms. They explain some of the properties of the integers that we know and love, like the fact that $0*x=0$ or $-x=-1*x$. But there are many number systems that are rings, but are definitely not the integers, like the ring boolean ring from last class's activity. So the integers must have some other properties beyond just being a ring, and next we will consider one of them: the integers are ordered.

In Homework 6, problem 4, we looked at the properties that are required of a predicate that defines an ordering - as we now say, what the axioms are for such a predicate. We called it "before", and these were the axioms:

$\forall x[\neg\text{before}(x,x)]$, i.e. no object is before itself in the order
$\forall x,y,z[\text{before}(x,y) \wedge \text{before}(y,z) \Rightarrow \text{before}(x,z)]$, i.e. the ordering is transitive

... and we proved that $\text{before}(a,b)\Rightarrow\neg\text{before}(b,a)$. These axioms define what's called a partial order, which means that we leave open the possiblity that there are some pairs of objects that the order doesn't tell us anything about. For example, in a universe of sugar cereals and pets, we know that Lucky Charms are better than Captain Crunch, and we know that cats are better than hamsters, but we don't know which whether Captain crunch is better or worse than hamsters. To be a total order, means that for any two objects $a$ and $b$, either they are equal, or $a$ comes before $b$ or $b$ comes before $a$. I.e.:

$\forall x,y[x=y \vee \text{before}(x,y) \vee \text{before}(y,x)]$

In the next section, we will define a total ordering for rings.

Defining < : A total order for rings

In this section we want to define a total ordering for rings. For starters, we will allow ourselves to write it in its usual notation, so we will write $a \lt b$ to mean $before(a,b)$.

Axioms for total order for rings
Restating the total ordering axioms using the "<" notation we have:

$\forall x[x \nless x]$, i.e. no object is less than itself in the order [note: $a \nless b$ is short-hand for $\neg (a \lt b)$]
$\forall x,y,z[x \lt y \wedge y \lt z \Rightarrow x \lt z]$, i.e. the ordering is transitive
$\forall x,y[x=y \vee x \lt y \vee y \lt x]$, i.e. we have a total order

However, since the objects that are being "ordered" are elements of a ring, we want "$\lt$" to interact with $+$ and $*$ in the way we expect. Technically, we say that the order needs to be compatible with addition and multiplication in the ring. This means:

$\forall x,y,z[x \lt y \Rightarrow x + z \lt y + z]$
$\forall x,y,z[0 \lt z \wedge x \lt y \Rightarrow z*x \lt z*y]$

Consequences: additive inverses and $\lt$

Our experience with integers, rationals and the real numbers tells us that if $0 \lt x$ then $-x \lt 0$. But is that actually a consequence of being a ring with a total order, or does this require another axiom?

(Negation & Order) In a ring with a total order, for any $x$ we have: if $0 \lt x$ then $-x \lt 0$; if $x \lt 0$ then $0 \lt -x$.

ACTIVITY
Prove the above theorem! Remember, your only givens are the ring axioms and the above axioms for a total order for a ring.

1: ∀x,y,z[x < y => x + z < y + z]    [Axiom iv of order for rings]
2: 0 < x => 0 + -x < x + -x          [specialize 1 with x=0,y=x,z=-x]
3: 0 < x => -x < x + -x              [additive identity on 2]
4: 0 < x => -x < 0                   [additive additive inverse on 3]

1: ∀x,y,z[x < y => x + z < y + z]    [Axiom iv of order for rings]
2: x < 0 => x + -x < 0 + -x          [specialize 1 with x=x,y=0,z=-x]
3: x < 0 => x + -x < -x              [additive identity on 2]
4: x < 0 => 0 < -x                   [additive additive inverse on 3]

Consequences: Positive, negative and zero

With the definition of < in place, we can finally define something we think of as an obvious an intrinsic part of the integers: "positive" and "negative". So, first:

(Trichotemy Law) In a ring with a total order, for any $x$, exactly one of $x \lt 0$, $x = 0$, $0 \lt x$ is true.

ACTIVITY
Prove the above theorem!
Note 1: This is called the "trichotemy law".
Note 2: So the only things you may take as givens are the ring axioms and the axioms for "<" from above.
Note 3: Your proof should have four parts:

Prove that at least one of $x \lt 0$, $x = 0$, $0 \lt x$ is true
Prove that if $x=0$ then $x \nless 0$ and $0 \nless x$. Note: remember that $a \nless b$ is short-hand for $\neg (a \lt b)$.
Prove that if $x \lt 0$ then $x \neq 0$ and $0 \nless x$. Note: remember that $a \nless b$ is short-hand for $\neg (a \lt b)$.
Prove that if $0 \lt x$ then $x \neq 0$ and $x \nless 0$. Note: remember that $a \nless b$ is short-hand for $\neg (a \lt b)$.

With this result, it makes sense to say $x$ is negative if $x \lt 0$, $x$ is positive if $0 \lt x$, and otherwise $x$ is zero.

1: x = 0 ∨ x < 0 ∨ 0 < x [specializing axiom iii (total order) x=x,y=0]
2: ¬(x < x) [specializing axiom i with x=x]
A.1: x = 0  [Assumption A]
A.2: ¬(x < 0) [Substitutivity of equality on 2 using equation A.1]
A.3: ¬(0 < x) [Substitutivity of equality on 2 using equation A.1]
A.4: ¬(x < 0) ∧ ¬(0 < x) [and introduction]
3: x = 0 => ¬(x < 0) ∧ ¬(0 < x) [Close assumption A]

4: x < 0 ∧ 0 < x => x < x  [Axiom ii (transitivity) x=x,y=0,z=x]
5: ¬(x < x) => (¬(x < 0) ∨ ¬(0 < x)) [contrapositive of 4, with some simplification]
6: ¬(x < 0) ∨ ¬(0 < x) [Modus ponens 5, 2]
				 
7: (x < 0 ∨ 0 < x) => ¬(x = 0) [Contrapositive of 3]
B.1: x < 0 [Assumption B]			       
B.2: x < 0 ∨ 0 < x [or introduction]
B.3: ¬(x = 0) [Modus ponens 4, B.2]	 
B.4: x < 0 => ¬(0 < x) [implication rewriting on 6]
B.5: ¬(0 < x) [Modus ponens B.4, B.1]
B.6 ¬(x = 0) ∧ ¬(0 < x) [And introduction B.3, B.6]
8: x < 0 =>  ¬(x = 0) ∧ ¬(0 < x) [Close assumption B]

C.1: 0 < x [Assumption C]			       
C.2: x < 0 ∨ 0 < x [or introduction]
C.3: ¬(x = 0) [Modus ponens 4, C.2]	 
C.4: 0 < x => ¬(x < 0) [implication rewriting on 6]
C.5: ¬(x < 0) [Modus ponens C.4, C.1]
C.6 ¬(x = 0) ∧ ¬(x < 0) [And introduction C.3, C.6]
9: 0 < x =>  ¬(x = 0) ∧ ¬(x < 0) [Close assumption C]

So, by line 1, at least one of x=0, x < 0, 0 < x must be true. By lines 3, 8 and 9, as soon as one of them is true, the other two must be false. Therefore, exactly one of the three is true!