The addition and multiplication of every-day arithmetic respect the ordering
of numbers by the usual notion of bigger
or higher
– at
least on positive numbers, with complications for negatives (where bigger is
lower) and zero. As it happens, this respect for ordering is a strong property
of familiar arithmetic, that sets its ringlets
(and rings) apart from others. So I'll here
set out to formalise that familiar relationship so as to draw out its
consequences.
In general, an ordering is any transitive relation; for example, subsumes is an ordering on relations. There are many pairs of relations where neither relation subsumes the other, hence this is only a partial ordering. For the familiar ordering of the numbers in everyday arithmetic, in contrast, every pair of distinct numbers has one less than the other.
A strict order
on a collection Q is a transitive
relation – usually written using an
infix comparison operator –
which, with its reverse and (the identity on) Q forms a disjoint partition of
the all-relation on Q. I'll use the symbol ~
for my comparison (but feel
free to think of < or > in its place); the order relates x to y
is
then written as x ~ y
. If x ~ y and y ~ z then the infix operator
templates let us write that as x ~ y ~ z and the fact that our order is
transitive means that this implies x ~ z too. The disjoint partition
bit
of the specification means that, for every x and y in Q, exactly one of the
following holds true: x ~ y
, y ~ x
or x = y
.
The disjoint partitioning here is sometimes expressed by
describing the relation as antisymmetric
, in contrast to symmetric
relations being those unchanged by reverse; here, the reverse of our ordering is
its own complement, less the identity. I chose to reserve the
term antisymmetric
for its quite different meaning in linear
algebra. Other discourses are also apt to describe the ordering in terms of
the or equal
version of the ordering, so that the relation and its
reverse have the identity as their intersection and the all-relation as their
union; this describes the same thing in an equivalent way. In some contexts it
may be desirable to talk about a hybrid between these, where the collection of
values subsumes the intersection of ~ and its reverse while the union of the
collection, ~ and its reverse is the all-relation on the collection; most of
what appears here can be said of such an order, but I don't feel the need to
accommodate it, for the present topic, and suspect it would require a little
more care than I can spare the enthusiasm to take.
To accompany that, a full order
is a transitive relation whose union
with its reverse and its collection of values is the all-relation on those
values, while the collection of values subsumes the intersection of the order
with its reverse. Every strict order is full, as is the or equal
companion to that order; and a full order could be reflexive on a proper
sub-collection of its values (as for
the pigeonholing I introduce to define
finiteness, although this isn't full as there are ample collections that it
doesn't relate either way).
So suppose we have a cancellable addition with at least one value that's not an additive identity, call this value e; and suppose we have a strict ordering on the addition's values. In particular, this means we have a strict ordering on the values obtained by repeatedly adding e to itself; e = e.1, e+e=e.2, e.2+e = e.3 and so on; we can think of these as the natural multiples of e. Since e is not an additive identity, e+e and e are distinct; so our strict order gives us either e.2 ~ e or e ~ e.2.
One of the simplest things we expect of ordering and arithmetic is that
adding a value to both sides of a comparison doesn't change the comparison;
i.e. x ~ y
implies x+a ~ y+a
for any value a. Applying this to
the multiples of e, suppose we have e.2 ~ e; add e to each side and we get e.3 =
e.2+e ~ e+e = e.2 ~ e and transitivity tells us that e.3 ~ e as well; we can do
the same for each successive natural and duly conclude that ~ coincides, on the
multiples of e, with the usual > ordering on the naturals used to scale
e. If we started with e ~ e.2, we'd get just the same but reversed, so ~ would
coincide with < on the naturals.
In particular, as every natural other than 0 or 1 is > 1, so not equal to 1, our strict order on the multiples of e precludes any e.n, with n > 1, being equal to e; consequently, no natural n > 0 gives an additive identity as e.n, so the order of e is 0 (i.e. no two of its multiples are equal). This being true for any value e that isn't an additive identity, we infer that either our addition is trivial (we have only one value, 0) or it has characteristic 0 (every non-zero value has order 0).
Suppose we have mutually inverse u, v; if u ~ u.2 = u +u then we can add v to both sides repeatedly to get 0 ~ u, v ~ 0 and v.2 = v +v ~ v. We can clearly go the other way by adding u to each side repeatedly; and swapping their names then shows us we get the natural converse had u.2 ~ u been our case. So the multiples of u and of v compare the opposite way round and u, v compare oppositely to 0; this shall turn into additive inverses having opposite sign, one positive the other negative. Suppose we have values u, v with u ~ v and each has an additive inverse; then −v = u +(−u) +(−v) ~ v +(−u) +(−v) = −u, so order is reversed by additive inversion (in so far as it's available).
Of course, along with the rule x ~ y implies x +a ~ y +a for all a
for adding to both sides of a comparison, we naturally want the ability to
cancel from both sides: x +a ~ y +a for any a implies x ~ y
(which can,
as ever, be inferred from the former whenever a has an additive inverse). If we
have an e with e.2 = e +e ~ e then we can add any value k to both sides and
cancel an e to turn this via e +e +k ~ e +k into e +k ~ k; likewise, if we had e
~ e.2 we would get k ~ e +k. If we have an additive identity, we can use this
as k; shortly, in a ringlet, I'll use 1 as k. So the direction of comparison
between the multiples of a value is the same as the direction of comparison when
adding that value to some constant; this should be no surprise.
As a somewhat twisted example, consider {n←m: n, m are natural with n+m > 0}, the collection of not-both-zero pairs of naturals, subject to the obvious addition (u←v) +(p←q) = (u+p←v+q) and the contrived multiplication (n←m).(p←q) = (n.p +2.m.q)←(m.p +n.q); this effectively treats n←m as n −m.√2. This arithmetic forms an integral ringlet and its values are dense in {reals}. For (n←m).(p←q) to have zero as its right value it must have either both m and q or both n and p zero with the other pair non-zero, with the result that n.p +2.m.q isn't zero and the product isn't zero; thus no product of values has zero on both sides; nor does any sum. It can be given a strict ordering (induced by looking at its embedding ({reals}: n −m√2 ←(n←m) :) and using the ordering on reals; the positive values are precisely those n←m for which n.n > 2.m.m), for which (0←1) < (1←0) yet there is no value we can add to either (0←1) or (1←0) to get the other.
Now consider another notable property of the addition in real, rational and
whole arithmetic (but not of the example just given): if a < b then there is
some (positive) x for which a +x = b. In the language I've built up for binary
operators, this means that our ordering assures us of some completions; for the
strict order discussed above, this would mean that a ~ b implies a completion
one way round or the other: a difference a −b or b −a, is available
as a value. In particular, since the order is strict, for any a distinct b
there is some x for which either a +x = b or a = b +x; and a ~ b selects one of
these cases, while b ~ a selects the other. We've not, up to this point,
imposed any condition that makes ~ distinguish whether it's > or < and, as
a result, its reverse has all the same properties; so we can now chose to rename
~ and its reverse to be, one way round or the other, < and > such that we
get: a > b implies a difference a −b
, i.e. a > b implies
there's a c for which a = b +c, whence b +c > b and each natural multiple of
c is > all earlier multiples of c; if we have an additive identity, 0, then c
> 0. Of course, this is only interesting if our addition is incomplete; if
it's complete, it's also true that a < b implies a difference a
−b
, because we can take that difference as given, regardless of
whether a < b or b < a.
Still, the positive naturals, rationals or reals each have an ordering given by unite(: ({a}: |add(a)) ←a :), i.e. a < b precisely if b = a +x for some x. (This is just the reverse of the union of the completable pairs, since each is (a+x)←a for some a, x.) We can extend this to include zero and even negative values for a and b if we just constrain x to be positive; and we can avoid the need to define that as > 0 by identifying the sub-addition on positives as the generator for the ordering. I construct the rationals and reals out of their positive values, obtained from the non-zero naturals, by an additive completion; this ensures we do have the original addition's values to label as positive, before we use them to define the ordering for which each positive is indeed > 0. For the naturals, the ordering does indeed come before the arithmetic, but the sub-addition on positives does indeed induce the same ordering as the successor operation that generates the naturals from 0; and the positive naturals do generate the order on the integers.
Note that the addition on negative integers (and similarly for rationals or reals) does consistently order its operands; and this does generate a strict order on the integers (or rationals, or reals, as appropriate) in this sense; albeit this is the exact reverse of the usual order. It's only when we come to consider multiplication that we get to distinguish the negative from positive in the familiar way. The twisted addition above is not positively-ordered, despite being the addition of an ordered ringlet.
I'll describe an addition as orderly
precisely if
unite(: ({a}: |add(a)) ←a :) is a strict order on its values; and I'll
describe an addition as add-ordered
precisely if its
restriction to some collection P of its values is an add-ordered sub-addition
and a < b precisely if a +p = b for some p in P
is a strict order on
the addition's values. Every orderly addition is trivially add-ordered. For
the order to be strict, P must lack an additive identity, so no orderly addition
is complete. On the other hand, any two values of an add-ordered addition are
ordered one way round or the other and a < b does imply a completion of b
from a, namely some p in P for which a +p = b; so every add-ordered addition is
at least half complete
in the sense that every pair of distinct values
has a completion at least one way round.
Given an ordering on an addition's values, consider P = {value x: a < a +x for some value a}. For x, y in P, we have some values a, b for which a < a +x and b < b +y; adding these, we get a +b < a +b +x +y so a+b serves as witness that x +y is in P. Thus P is closed under addition, making it a sub-addition. Given x in P and a value a for which a < a +x, consider any value b; we have a +b < a +x +b; cancelling thus gives b < b +x; so one value as witness that x is in P actually makes all values witnesses that x is in P. Consequently, unite(: ({a}: |(:add(a):P)) ←a :) does generate a transitive relation subsumed by our order. We have an orderly sub-addition exactly when this relation is a strict order; which happens precisely when it subsumes (hence is) our original order. (Notice that it needn't, as shown by the twisted addition above.) In particular, if an addition has an orderly sub-addition, this sub-addition is entirely determined by the order that it induces on the addition's values; it is consequently unique. Furthermore, for any given value a of our addition, {value x: a < a +x} is in fact P.
In an add-ordered addition, with P as the collection of values of its orderly addition, consider any n not in P. Since n +n isn't > n, with > strict, we must have either n +n = n, making n an additive identity (and self-inverse), or n +n < n. In the latter case, we have some p in P for which n +n +p = n, making n +p an additive identity and p an additive inverse for n. So if an add-ordered addition has any values other that those of orderly sub-addition, it has an additive identity; and each such value has an additive inverse in the orderly sub-addition.
All of this required nothing more than an addition; so it shall apply to any order on a module over a ring; these, indeed, shall be the one-dimensional modules over sub-ringlets of the reals; and the symmetry between < and > shall remain unbroken for them. Before we move on to multiplication, hence ringlets, let's just recap the properties we've assumed of our ordering and its relationship to addition:
a < b precisely if a +p = b for some p in Pfor some collection P of values, with P closed under addition.
So a strict order can only respect an addition, in the limited sense given, if the addition has characteristic 0, i.e. we can add any non-zero value to itself arbitrarily many times and the succession of resulting values never gives us an additive identity or repeats any value. So we have infinitely many values, if we have any non-zero value at all.
In a non-trivial ringlet, with a strict order
that respects its addition, we have in particular the multiplicative identity 1
and its natural multiples (as above) naturally serve as an image of the natural
numbers in our ringlet; these constitute
the prime subringlet
.
Now, a ringlet isn't given to have an additive identity, so I can't
define positive
in terms of it; however, I can easily get round that by
just adding 1 to both sides of what I would have said otherwise. Since our
ordering is strict, for any value v of our ringlet, one of the following must
hold true: v+1 > 1
, v+1 < 1
or v+1 = 1
. The last
implies that v is an additive identity; and we can use the other two to classify
all other values. So describe a value v of our ringlet
as positive
precisely if v+1 > 1; or
as negative
precisely if v+1 < 1. We saw above that
this implies that v +k compares to k exactly the same way as v +1 compares to 1,
via adding k and cancelling 1. Whether or not our addition is complete, we can
now stop using the name ~ for the ordering; and we can use the familiar
short-hand forms, x ≤ y
standing for x < y or x = y
while x ≥ y
stands for x > y or x = y
. Every value except
(if there is one) the additive identity is either positive or negative.
So now consider the addition on positive values of our ringlet; as above,
this generates a transitive relation on our ringlet, subsumed by it ordering; if
this relation subsumes the ordering then it is the ordering and our additon on
positive values is add-ordered. The twisted example
above doesn't do this, so it won't always be true; but when the positive values
of an ordered ringlet do form a sub-addition, we get at least one-sided
completion for our ringlet's addition, namely a < b implies a + x = b for
some x
.
As derived above, for any ringlet whose addition is add-ordered, any value other than those of the orderly sub-addition implies an additive identity and, if it isn't that identity, has an additive inverse that is a value of the orderly sub-addition.
So the next obvious thing to say about how arithmetic interacts with order
is that positive scaling doesn't change order; i.e. x > y
implies x.a > y.a
for every positive a. In particular, positive p has
1 +p > 1; positive q then gives q +p.q > q and we can infer that p.q is
positive, so every product of positives is positive.
When (e.g. due to add-ordered addition) every negative has a positive additive inverse, every product of negatives is (−p).(−q) = p.q for some positive p, q; hence is positive. (This can also happen without the additive inverses, as it does in the twisted example above.) In particular, multiplying any non-zero value by itself gives a positive square; notably, 1.1 = 1 is positive, so the images of positive naturals in the prime subringlet are all positive. For negative v we have 1 +v < 1; for positive p we infer p +p.v < p and thus that p.v is negative; so a product of positive and negative is negative.
Now, if v is negative, hence −p for some positive p, given any x < y, consider x.v and y.v; we know these are −(x.p) and −(y.p); and additive inversion reverses order; as p is positive, we have x.p < y.p, hence y.v < x.v; so multiplying by a negative reverses the directions of comparisons, just as multiplying by a positive preserves it.
Can we cancel ? If p is positive and we're given values x, y for which p.x > p.y, we can use the fact that our order is strict to infer x > y, since x = y would imply p.x = p.y and x < y would imply p.x < p.y, contradicting what we were told; so we can indeed cancel.
Since multiplication need not be abelian, we strictly need to assert that x > y implies, for each positive p, both p.x > p.y and x.p > y.p; the reverse shall hold for a negative in place of p; and we can cancel in each case, with suitable reversing if the common factor was negative.
If a positive value p has multiplicative inverse q, we have p.q = 1 positive; i.e. p.q +k > k for any value k; in particular, this holds true for p.k for any k, giving us p.q +p.k > p.k and cancelling leaves us with q +k > k, whence q is also positive; so any multiplicative inverse of a positive is necessarily also positive. A multiplicative inverse q of a negative n will, when multiplied by −n in P, give us −1, which is negative;, whence q.(−n) +k.(−n) < k.(−n) and cancelling the positive factor leaves q +k < k so any multiplicative inverse of a negative is negative, likewise.
To tidy off one complication noted above, suppose we have a ringlet R whose addition is add-ordered by an orderly sub-addition, N, but that 1 isn't one of N's values. This implies 1 has an additive inverse, which is a value of N; and multiplying the values of N by −1 gives us a collectin P of values that can easily be seen to form an orderly sub-addition that does indeed generate a strict order on R (the reverse of the one generated by N). So the case of a negatively add-ordered addition easily enough turns into the more intuitively familiar positive add-ordering; albeit, in the process, establishing that every value has an additive inverse, hence that the ringlet is in fact a ring.
So we can now refine the notion of an add-ordered
addition to the case of a ringlet: I'll describe a ringlet R
as positively-ordered
precisely if 1 is a value of some
orderly sub-addition, whose collection P of values gives unite(: ({a}: |(:
add(a) :P)) ←a :R) as a strict order, <, on R's values (the add(a) here
is using the addition in R) that satisfies:
a +y < b +yfor any y implies
a < b; which, in turn, implies
a +x < b +xfor all x; and
a < bimplies
p.a < p.bfor all p in P.
A function from an ordered set to an ordered set is described
as monotonic
precisely if the order of its inputs implies
the order of its ouptuts, that is: f is monotonicly increasing precisely if x
≥ y implies f(x) ≥ f(y), monotonically decreasing precisely if x ≥ y
implies f(x) ≤ f(y) and monotonic in either case. The function is described
as strictly monotonic
if the ≥ and ≤ in that can be
replaced by > and < – i.e. the function is both monotonic and
monic.
On an ordered ringlet's positive values, every positive power is strictly monotonicly increasing with positive output; that is, x > y positive implies power(n, x) > power(n, y) positive. This is manifestly true for power(1), so suppose it true for some positive natural n; when we examine power(n +1), for given x > y positive, we have power(n, x) > power(n, y) positive inductively; mutiplying each by (positive) x, we get power(n +1, x) > power(n, y).x; likewise, multiplying positive power(n, y) by x > y we get power(n, y).x > power(n +1, y), whence, by transitivity, power(n +1, x) > power(n +1, y).
Scaling a power by a positive preserves ordering among its outputs and adding two strictly monotonic functions necessarily gives a strictly monotonic function; consequently, every polynomial with positive coefficients is strictly monotonically increasing and positive on positive values.
Likewise, for any k > 1 in our ringlet, (: power(n, k) ←n :{naturals}) is also necessarily monotonically increasing, since each power(n +1, k) > power(n, k) as a result of k > 1; and, > being transitive, this (inductively) implies power(m, k) > power(n, k) whenever m > n in {naturals}.
Written by Eddy.