]> Orderly Arithmetic

Orderly Arithmetic

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.

Strict or Full Order

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

Orderly Addition

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

Cancelling and Completing

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.

Inducing order from addition

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:

Ordered Ringlet

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.

Positives and negatives

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.

Positive ordering

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:

Monotonic powers

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

Valid CSSValid XHTML 1.1 Written by Eddy.