This is a minor generalisation of orthodoxy's ring theory; the main difference here is that a ring presumes addition forms a group (i.e. there's a 0 and, for each x, a −x), where a ringlet only requires addition to be cancellable.
I characterise a combiner as an addition precisely if it's flat (so combines any two of its operands), commutative (so the answer doesn't depend on order of operands) and cancellable (so combining an operand with each of two others only gives the same answer if the two others were equal). In such a case I denote it in the usual way and induce the usual subtraction from it. The appropriate sense of homomorphism between additions is then a mapping f for which f(a +b) = f(a) +f(b) for all appropriate a and b, using one addition on inputs and the other on outputs; as usual, a homomorphism from an addition to itself (so we're using the same addition on inputs as on outputs) is known as an automorphism.
The automorphisms of an addition support a pointwise addition induced from that on their operands, (f+g)(u) = f(u) +g(u), and can be composed. They include natural scalings that arise from repeated addition; these commute with all automorphisms and composing them corresponds to multiplying the naturals by which they scale.
A mapping from operands to automorphisms gives a way of combining two operands, one as input to that mapping, the other as input to the resulting automorphism, to get another operand; this gives us a second binary operator on the same operands that (from the nature of automorphisms) left-distributes over the addition; it's also closed, as its composite value is always an output of an automorphism of a closed addition, hence an operand.
If the mapping, s, that generates it is also an automorphism from this second binary operator to the composition on the addition's automorphisms – s(s(a, b)) = s(a)&on;s(b) for all operands a, b – then this second binary operator is associative, making it a combiner. To make this combiner also right-distribute over the addition, we need transpose(s) to be a cohomomorphism, again from the combiner expressed by s to the composition of automorphisms of addition.
Since the action is via automorphisms, that include natural scalings –
which feel like
a multiplication and whose composition represents natural
multiplication – it makes sense to regard this binary operator, induced
from embedding the addition's values in its automorphisms, as a multiplication
on the same values as the addition. I
thus denote it in the usual
manner for a multiplication.
It is common to define the multiplication directly; none the less, it can be represented by the mapping (: (: a.b ←b :) ←a :); if the multiplication has all the properties above, this is a homomorphism from the multiplication to composition of automorphisms of addition and its transpose is a cohomomorphism from the multiplication to the same composition.
When we have an addition and a multiplication that embeds the addition's
operands in the addition's automorphisms, homomorphically when read as (: (: x.y
←y :) ←x :) and cohomomorphically when read as the transpose of this,
I'll describe the combination as a ringlet
– on
the collection of operands – precisely if some operand
is embedded as the identity on operands (which is always an automorphism of the
addition) by both of these embeddings; this operand is
then an identity for the
multiplication and is usually denoted 1 – except when we need to
distinguish the identities of distinct multiplications (e.g. that of the
naturals from that of our ringlet).
The multiplication and addition on the natural numbers meet these requirements; so do those on polynomials. The automorphisms of any addition form a ringlet under pointwise addition with composition as multiplication (as should not be too surprising, given how I just developed the above from considering such automorphisms).
On collections, we can treat intersection as a multiplication and
the symmetric difference
(the odd union; the result of combining several
collections has, as members, those values that are members of an odd number of
the collections combined) as addition; the interested reader can have fun
showing that these make a ring (see below) of all the sub-collections of any
given collection. (This example is mainly of interest to illustrate, below, why
we need to explicitly state a particular constraint on homomorphisms.) We shall
meet more examples in due course.
The point of studying ringlets is to establish various results that hold in all cases, to save repeatedly establishing these results in each of the cases separately; at the same time, we get to introduce a common notation for use in all cases, which saves on repeatedly defining equivalent notations.
Although it is really the arithmetic that forms a ringlet, the arithmetic is usually taken for granted in each context, so it is usual to speak of the collection of operands, to which the arithmetic applies, as the ringlet; but this is just a short-hand referring to the implied arithmetic on the collection of values. When the mutliplication is also commutative (the addition always is), I'll describe the ringlet as commutative, and say that it commutes, again as a short-hand, really referring to its multiplication.
A ringlet's addition is a commutative cancellable
combiner: taken on their own, these properties have
assorted consequences – some of which I now summarise. I shall follow
orthodoxy in usually denoting addition's identity, if it has one, as 0 and, when
a value u has an additive inverse, denoting this as −u. For values s, r,
if there is some x for which s = r +x, I shall refer to this x as s
−r
; note, however, that this is only meaningful when there is some
such value and use of this notation doesn't necessarily imply that r has an
additive inverse. When it does, we do indeed get s +(−r) = s
−r, though. If, for any r, there is a value r −r then this shall
indeed be an additive identity. When there is an additive identity, 0, then b
+0 = b implies, for any value b, that there is a b −b, namely 0; in
particular, we can apply this to 0 −0 = 0. Any value which
is not an additive identity is described as non-zero
, regardless
of whether there is a zero for it to not be equal to.
When we can subtract s from r in some ringlet, so we have a value x, a.k.a. r −s, for which x +s = r: multiplying by any value t gives t.r = t.x +t.s, so we can also subtract t.s from t.r, yielding t.r −t.s = t.x = t.(r −s); and likewise r.t −s.t = x.t = (r −s).t; thus multiplication also distributes over subtraction. (Note that multiplication need not commute, so we have to prove things both ways round.) When there is an additive identity, 0 = t.0 −t.0 = t.(0 −0) = t.0 and 0 = 0.t −0.t = (0 −0).t = 0.t implies that it is preserved by arbitrary multiplication; in particular, multiplication (on either side) by 0 is not monic (unless the ringlet has only one value) so not cancellable.
If the multiplicative identity, 1, is also the additive identity, 0 = 1,
then b = 1.b = 0.b = 0 for every value b implies that the ringlet is {0}, with
the fatuous addition and multiplication. (This is the one case, just alluded
to, where multiplication by 0 is monic; indeed, 0 is multiplicatively
self-inverse.) In a ringlet with only one value, that value is necessarily the
multiplicative identity 1; since 1 +1 must have a value, it is necessarily 1 +1
= 1 whence we can subtract 1 from 1, making 1 = 1 −1 an additive identity
so our ringlet is in fact {0} again. The {0} ringlet is even, indeed, a ring
(see below); but it is not normally considered interesting ! It is known
as the trivial
ringlet (or ring) and most often mentioned
for the sake of excluding it, introducing a non-trivial
ringlet or ring
as one in which, implicitly, the multiplicative identity is not an
additive identity.
Where a value s has an additive inverse, multiplying it by arbitrary t gives t.(−s) = t.(0 −s) = t.0 −(t.s) = 0 −(t.s) = −(t.s) and (−s).t = (0 −s).t = 0.t −(s.t) = −(s.t), implying that every multiple of s also has an additive inverse, which is simply the corresponding multiple of −s. As for any addition, the collection of values that have additive inverses is closed under addition and subtraction; taken with closure under scaling it thus forms an ideal.
If r and s both have additive inverses, we obtain (−r).(−s) =
−(r.(−s)) = −(−(r.s)) = r.s,
as negation is self-inverse. In particular, if
the multiplicative identity 1 has an additive inverse −1, so does every
value (r.(−1) = −(r.1) = −r) and the ringlet is additively
complete (so its addition forms a
group); conversely, if the (cancellable) addition is complete it does have
an inverse for 1 (the completion x = −1 of 1 +x = 0, with y = 0 being the
completion of 1 +y = 1). It also has (−1).(−1) = 1; when present,
the additive inverse of the multiplicative identity is multiplicatively
self-inverse. (Note that 1 may be additively self-inverse, in which case
−1 = 1; this then makes −r = r for all r, so every value is
additively self-inverse; the addition then has
characteristic 2.) An additively complete ringlet is what orthodoxy refers
to as a ring
.
A homomorphism is a mapping that preserves structure: so
a homomorphism
of ringlets, (R: f |S) with suitable
additions and multiplications on R and S, is just
a homomorphism of the addition that is also
a (binary operator) homomorphism of the
multiplication and maps S's
multiplicative identity to R's. Thus f(s+t) = f(s)+f(t), f(s.t) = f(s).f(t),
for each s, t in S, and f(1) = 1. Being a homomorphism of the addition ensures
that the image of an additive identity is necessarily an additive identity; and,
when s in S has an additive inverse, f(−s) = −f(s).
Without the requirement f(1) = 1, it would be possible for f to respect addition and multiplication without satisfying this, provided the multiplication, even by non-zero, isn't cancellable: for example, in the rings of subsets of some given sets A, B under the symmetric difference as addition and intersection as multiplication: when B is a subset of A, the identity mapping on B's subsets can be construed as a mapping to A's subsets (since each subset of B is a subset of A) and thus as a mapping from B's ring to A's ring; it respects the addition and multiplication, but the multiplicative identity in B's ring is B, which it maps to B, which is not the multiplicative identity in A's ring (that would be A). When multiplication by R's non-zero values is cancellable, of course, f(1).f(s) = f(1.s) = f(s) = 1.f(s), applied to any value s of S with non-zero f(s), suffices to prove f(1) = 1 for any (R: f |S) that respects both addition and multiplication, unless kernel(f) is all of S.
As a homomorphism of addition, any ringlet homomorphism has kernel and image defined. The image of (R: f |S) is necessarily a sub-ringlet (and, when S is a ring, also a sub-ring; see below) of R, while its kernel is an ideal.
As addition is commutative in every ringlet, there is no
difference between a homomorphism
and a cohomomorphism between the
additions of ringlets; requiring f(a +b) = f(b) +f(a) is no different from
requiring f(a +b) = f(a) +f(b). However, as multiplication need not be
commutative, cohomomorphisms (with f(r.s) = f(s).f(r)) and homomorphisms (with
f(r.s) = f(r).f(s)) of the multiplication may be distinct. We thus have just
one order we might want to toggle, so I define
a cohomomorphism
of ringlets to be a cohomomorphism both
of addition and of multiplication, respecting the multiplicative identity as for
a homomorphism.
An automorphism or coautomorphism of a ringlet is then, as ever, simply a homomorphism or cohomomorphism (respectively) from the ringlet to itself. Since it preserves 1 and is an automorphism of the addition, it necessarily commutes with natural scalings and preserves the prime subringlet (introduced below). When multiplying each non-zero value of a ringlet by its image under a self-inverse coautomorphism gives a suitably real result, within the ringlet, that coautomorphism can be particularly interesting.
Given the above, we can define modules where we know how to add things that we can also multiply by members of some ringlet; and we can define ideals within a ringlet and specify which ideals are prime, maximal and principal. I'll return, below, to how those can help us to learn more about our ringlet; but, first, we need to know more about the properties a ringlet may have.
When a ringlet's collection of values Z subsumes another collection S on
which Z's multiplication and addition are closed, I'll describe the arithmetic's
restriction to S as a sub-ringlet
of the arithmetic on Z
precisely if it does form a ringlet, with the same multiplicative identity.
The need to explicitly require the same multiplicative identity arises from the same issue as obliged us to say that a homomorphism maps 1 to 1; the same example as given above for that would otherwise give a sub-ring with a different multiplicative identity, which would mess up things like taking intersections of sub-rings.
Note that the addition on S need only be closed (i.e. adding two members of S gives a member of S); it need not be closed within Z – there may be some z in Z and s in S for which z +s is in S but z is not in Z; for example, {positive naturals} is a sub-ringlet of {naturals} despite 0 not being in the former.
For a ring, we must also insist that the sub-ring is complete under addition (or that the sub-ring be closed within the ring, under addition, which is an equivalent constraint in this case); and note that a sub-ringlet of a ring need not be a sub-ring of the ring. (This makes the image of a ringlet homomorphism from a ringlet to a ring be a sub-ringlet of the ring, though it isn't always a sub-ring.)
In any ringlet on a collection Z of values, let S be {s in Z:
for all r in Z, r.s = s.r}; this is known as the centre
of
the ringlet and is necessarily a subringlet, and a sub-ring when the ringlet was
a ring. The multiplicative identity satisfies 1.r = r = r.1 for all r in Z, so
is in the centre. Any a, b in the centre give us, for any z in Z, (a +b).z =
a.z +b.z = z.a +z.b = z.(a +b) and (a.b).z = a.(b.z) = a.(z.b) = (a.z).b =
(z.a).b = z.(a.b) hence a.b and a +b are in the centre. Likewise, given some c
with a +c = b for some a, b in the centre: for all z we get a.z +c.z = (a +c).z
= b.z = z.b = z.(a +c) = z.a +z.c = a.z +a.c whence, cancelling a.z, we infer
c.z = z.c, so c is in the centre also; so the centre of a ringlet is always
closed within that ringlet, under addition. (In a ring, this just says the
centre is closed under both addition and subtraction.)
Any intersection of sub-rings of a ring is a sub-ring; and any intersection of sub-ringlets of a ringlet is a sub-ringlet. All sub-rings or sub-ringlets have 1 as a value, hence so does their intersection. The arithmetic on the intersection naturally inherits from its context that the addition is commutative and cancellable, both addition and multiplication are associative and the multiplication distributes over the addition. Any two values in the intersection are necessarily in all the sub-rings or sub-ringlets intersected, each of which is closed under the arithmetic, so the sum and product of our two values are also in each of the intersected parts, hence also in the intersection, which is thus closed under addition and multiplication. If all the intersected sub-ringlets are closed within the ringlet then any c in the ringlet for which a +c = b for some a, b in the intersection has a, b in each of the intersected sub-ringlets, each of which is closed within the ringlet, hence c is also in each sub-ringlet, hence in the intersection; so intersecting sub-ringlets closed within the ringlet, under addition, proudces an intersection that is also closed within the ringlet, under addition. For sub-rings of a ring, this ensures the intersection is indeed additively complete, like each of the sub-rings intersected; hence it is indeed a sub-ring (rather than merely a sub-ringlet).
If (R: f |S) is a ringlet (or ring) homomorphism, then its image (: r←r :f) necessarily forms a sub-ringlet (or sub-ring) of R. The definition of homomorphism ensures f(1) = 1 is in the image. Any two members of the image are f(s) and f(t) for some s, t in S, with s+t and s.t in S, hence f(s) +f(t) = f(s +t) and f(s).f(t) = f(s.t) are also in the image, which is duly closed under addition and multiplication. The image inherits all the usual properties of the arithmetic from R. For a ring homomorphism, being an additive homomorphism propagates additive completeness from S to its image within R (but not necessarily to the rest of R); so f's image of S is a sub-ring of R.
For the purposes of this sub-section and the next section, discussing naturals alongside a ringlet, I shall refer to the ringlet's additive identity, if it has one, as z; and to its multiplicative identity as e, to avoid confusion with the naturals 0 and 1. By the time we're done, there shall no longer be any problem with conflating z with 0 and e with 1; we need to distinguish them for just long enough to demonstrate that we don't.
As for any addition, we can use repeated
addition to induce a multiplicative action of naturals on the values of our
ringlet. This can only include scaling by 0 if the ringlet has an additive
identity, z (in which case r.0 = z for each r); so describe every positive
natural as a count
and include 0 as also a count precisely if our ringlet
has an additive identity. We then have a multiplication between values of our
ring and counts, characterised by r.1 = r and r.(1 +n) = r +r.n for each natural
n, for each value r of our ringlet.
Now, for values r, s of our ring, consider which naturals n satisfy (r.s).n = r.(s.n) = (r.n).s, mixing the two multiplications. When we have an additive identity, (r.s).0 = z, r.(s.0) = r.z = z, (r.0).s = z.s = z, so n = 0 does indeed work. In any case n = 1 is fatuously true, as all three expressions are simply r.s. If all three are equal for some given n, consider: (r.s).(1 +n) = r.s +(r.s).n; by hypothesis, (r.s).n = r.(s.n), giving us r.s +r.(s.n) = r.(s +s.n) = r.(s.(1 +n)); likewise, (r.s).n = (r.n).s so we get r.s +(r.n).s = (r +r.n).s = (r.(1 +n)).s; thus (r.s).(1 +n) = r.(s.(1 +n)) = (r.(1 +n)).s; thus truth of the equation for n implies its truth for n +1 and, from its truth for 1 (and, where relevant, 0) we can induce that it is true for every count n. Thus our multiplication between naturals and our ring's values associates with the ring's own multiplication.
Now let f = (R: e.n ←n |{counts}), the natural scalings of our multiplicative identity. Since natural scaling distributes over addition in the naturals and associates with natural multiplication, we have f(n +m) = e.(n +m) = e.n +e.m = f(n) +f(m) and f(n.m) = e.(n.m) = (e.n).m = ((e.n).e).m = (e.n).(e.m) = f(n).f(m); along with f(1) = e, this makes f a ringlet homomorphism (R: |{counts}), implying that its image constitutes a sub-ringlet of R. Furthermore, we can perform the same construction in any sub-ringlet of R, starting from the same e; the only possible difference is that the sub-ringlet might lack an additive identity, hence not have 0 as a count; so f's image of {positive naturals} is a sub-ringlet of every sub-ringlet of R. In particular, f's image lies within R's centre (a sub-ringlet), so e.n commutes with every r in R. For any r in R, we have r.(e.n) = (r.e).n = r.n, so f also suffices to characterise our natural scaling on all of R.
We thus obtain a homomorphic image that represents the naturals by a
sub-ringlet, {e.n: n is a positive natural}, of every sub-ringlet of R. This is
known as the prime subringlet
(prime, this time, in the sense
of first
or principal
, although it is
also indivisible
) of the ringlet. When R is a ring, additive completion
shall turn this sub-ringlet into a sub-ring representing the integers; this is
likewise a sub-ring of every sub-ring of R; it is known as
the prime subring
of R.
This representation of counts within our ringlet makes it practical and reasonable to drop the distinction between a count n and its image e.n under f, so we can forget f and just treat naturals as if they were members of R. At the same time, because each e.n commutes with ever value of our ringlet, we no longer need to limit ourselves to right-multiplication by naturals (which is how I defined natural scaling) and can instead freely multiply by naturals on either side, since each now just represents a relevant value of our ring that commutes with all others. So I can now write n.r, for natural n and any value r of our ringlet, tacitly representing (e.n).r = r.n; but I shall continue writing n.e (or e.n) when I want to make clear the distinction between a natural and the value of the ringlet that represents it. I'll also, for the next section, continue to distinguish 0 from z and 1 from e.
The only remaining complication to treating naturals as if
they were members of our ringlet is that distinct naturals may have equal
representations in our ringlet, which is the topic of the next section and shall
lead to a classification of the sub-ringlets as which {positive naturals} gets
embedded in a ringlet's center. In this, the need to distinguish naturals from
their images in R arises from the need to be able to say n.e = m.e in R even
though the naturals n and m are not equal; this can normally be expressed
as n = m in R
or n = m modulo E
for some equivalence E; but I find
the n.e = m.e
form makes the following clearer.
As for any addition, for each value v, (: v.n
←n |{counts}) may be monic – in which case we say v has order
0 – otherwise, there is an additive identity, z, among its outputs and v's
order is the least positive n for which v.n = z. An additive identity, when
present, always has order 1. If any value has order 0, then 0 is also the
ringlet's characteristic
(and the ringlet has infinitely many distinct
values); otherwise, the ringlet's characteristic is the maximum of the orders of
its values.
If the multiplicative identity, e, has order zero then the ringlet has characteristic zero; otherwise, the additive order of e is some positive natural m and the ringlet does have an additive identity, z = m.e. In this latter case, consider any r in the ringlet; we have m.r = m.(e.r) = (m.e).r = z.r = z; so the order of r is at most m (and no value of the ringlet has order zero). Thus, if the multiplicative identity has non-zero order, it has the maximal order of any member of the ringlet. The characteristic of any ringlet is thus equal to the (additive) order of its multiplicative identity.
If the (additive) characteristic of a ringlet is 1, the multiplicative identity is an additive identity and our ringlet is {0}; no other ringlet has characteristic 1. (The other trivial ring, {0, 1}, has characteristic 2, since 1 +1 = 0.) If the characteristic is 0, the embedding of the naturals in the ringlet is monic and the sub-ringlet, in the center, that represents the naturals is a faithful copy of the naturals. Otherwise, the ringlet has characteristic n > 1 and the image of {naturals} under its embedding is just the quotient of {naturals} by the principal ideal (in {naturals}) generated by n. In each case, the kernel of the homomorphism that embeds the naturals in the ringlet is the principal ideal generated by the ringlet's characteristic.
A value in a ringlet is described as
a proper zero-divisor
precisely if the value itself, r, is
non-zero and there is some non-zero value s in the ringlet for which either r.s
or s.r is an additive identity. Trivially, a ringlet with no additive identity
has no proper zero-divisors. In a ringlet with no proper zero-divisors,
consider any non-zero value r with non-zero order n (hence the ringlet has an
additive identity, z = n.r) and consider any value s; z = z.s = (n.r).s =
r.(n.s), thanks to (associativity and) n being in our ringlet's center. Now, r
is not a proper zero-divisor, so n.s must be z and the order of s is at most n;
thus r has maximal order. Thus if any non-zero value of the ringlet has
non-zero order, all non-zero values have non-zero order and each has maximal
order; otherwise, all non-zero values have zero order; either way, all non-zero
values have the same (additive) order, in the absence of proper
zero-divisors.
If the (additive) characteristic of a ringlet is n.m for some naturals n, m both > 1, then the ringlet's multiplicative identity e has z = n.m.e = (n.e).(m.e) with both n and m less than n.m, hence neither n.e nor m.e is z, yet their product is z; so any ringlet with non-trivially factorisable characteristic has proper zero-divisors. Conversely, a ringlet with no proper zero-divisors has, as characteristic, a natural with (in the sense I'll introduce at the end of the next section) no proper divisors (this may be 0; in naturals, 0 has no proper divisors). When the characteristic isn't 0 or 1 (note that the trivial ringlet {0} has no proper zero-divisors), this lack of proper divisors shall make the ringlet's characteristic a prime.
We're now done with the distinction between naturals and their images in our ringlet; we know enough that no confusion should result from treating a natural n as synonymous with its product, n.e, with e the ringlet's multiplicative identity. So we can safely go back to using 0 for the ring's additive identity (when it has one) and 1 for its multiplicative identity.
In a ring, the absence of proper zero-divisors implies cancellability of non-zero multiplication: if we have r.s = t.s with s non-zero, we can re-write this as 0 = (r −t).s and, as s is non-zero, infer r −t = 0, hence r = t. Furthermore, if a ringlet has proper zero-divisors, r.s = 0 with r, s non-zero, this violates cancellability of multiplication at least for: r.s = r.0 with r non-zero, yet s ≠ 0; r.s = 0.s with s non-zero, yet r ≠ 0.
So I'll describe a ringlet R as descalable
precisely
if, for each non-zero r in R, the mappings (: s.r ←s :R) and (: r.s ←s
:R) are monic. In this case, since each of these monics maps any additive
identity to itself, when there is one, neither maps any non-zero value to an
additive identity, so R has no proper zero-divisors. We also get multiplicative
cancellability except where the common factor is zero – which is as much
multiplicative cancellability as we can hope for in a ringlet (or ring).
I'll describe a commutative descalable ringlet as
an integral ringlet
: when it is a ring, it is called
an integral domain
. (Orthodoxy defines an integral domain as a
commutative ring with no proper zero-divisors; as shown above, the lack of
proper zero-divisors is equivalent to descalability.) The naturals are an
integral ringlet; when their addition is completed, we get the integers, which
are an integral domain.
I'll describe a value of a ringlet that has a multiplicative inverse
as invertible
. (It's orthodox to call it a unit
,
but I find that highly confusing, when it makes all non-zero members of a field
be units, for all that they may be vastly bigger or smaller than 1. If I need
to refer to additive invertibility, I'll qualify it with additive
or talk
about negateable values.) The multiplicative identity is always invertible, as
it's its own inverse, and there needn't be any other invertible values in a
ringlet; in a ring, the additive inverse of the multiplicative identity,
−1, is also invertible, as it's likewise its own inverse. In the natural
ringlet, only 1 is invertible; in the integer ring, only ±1 are
invertible. If every non-zero value in a ringlet is invertible, I'll call it
a division ringlet
(and, when it's a ring, orthodoxy calls
it a division ring
); if its multiplication commutes, I'll call it
a fieldlet
(if it's also a ring, orthodoxy calls it a
field). Note that having multiplicative inverses is a stronger condition than
being descalable: the multiplication on positive naturals is cancellable (hence
descalable), without having multiplicative inverses.
One value, f, of a ringlet R is said to divide
another, p, precisely if there are some q, s in R for which s.f.q = p. In such
a case, f is described as a divisor
or factor
of p; while p is said to
be disivible by
f and described as
a multiple
of f. When no member of {f, s, q} is a
multiple of the product p = s.f.q, then p is described as
a proper
multiple of f and f as a proper divisor (or
factor) of p. (Thus a proper zero-divisor is exactly a proper divisor of zero.)
Note that no invertible value has any proper divisors, as every value is a
multiple of 1 and, thus, of every invertible value.
I now pick up the subject of ideals, briefly alluded to above. An ideal is a sub-addition of the ringlet's addition, closed within the ringlet under addition, that forms a module over the ringlet.
In an integral ringlet
that cancels down completions, if all ideals
are principal, I'll describe the ringlet as
a principal ideal ringlet
. When the ringlet is a ring, it
is then (orthodoxly) known as a principal ideal domain
(not infrequently
abbreviated PID). The natural ringlet is a
principal ideal ringlet; its additive completion, the ring of integers, is a
principal ideal domain.
Each ideal in a principal ideal ringlet is then {c.r: r in R} for some c; hence every prime ideal is then of this form and the c that generates it is a prime. A prime generates a prime ideal by definition; so, in a principal ideal ringlet, an ideal is prime precisely if it is generated by a prime.
Every proper maximal ideal is prime, in a commutative ringlet. In a principal ideal ringlet R, consider any prime ideal C and any ideal J that subsumes it. Each is a principal ideal, so C = {r.c: r in R} and J = {r.j: r in R} for some c, j in R. J subsumes C, so c is in J and c = k.j for some k in R. As C is prime and k.j is in C, either j is in C or k is in C. If j is in C, then C subsumes J, which was given to subsume C, so C = J. If k is in C then k is h.c for some h in R and 1.c = k.j = h.j.c and, as C is proper, c is non-zero, so we can cancel it, leaving 1 = h.j in J, so J = R. Thus any ideal that subsumes a prime ideal, in a principal ideal ringlet, is either the prime ideal or the whole ringlet; so prime ideals are maximal in principal ideal ringlets (which are commutative). Thus, in a principal ideal ringlet, a proper ideal is prime precisely if it is maximal. This paves the way to prime factorisation (which is a big enough deal to warrant a page all of its own).
Suppose we have a ringlet R with an additive identity, 0, and a mapping
({naturals}: d |R) for which: for any non-zero r in R, d(r) > d(0); and, for
any non-zero x in R and each y in R, there are some q, r in R for which y = q.x
+r and d(r) < d(x). In such a case, I'll describe R as
a Euclidean ringlet
(because it lets us implement Euclid's
algorithm; see below); if R is a ring, it is orthodoxly known as a Euclidean
domain
. The naturals are a Euclidean ringlet, using the identity as d; the
integers are a Euclidean domain, using absolute value as d.
Every Euclidean ringlet is a principal ideal ringlet. Proof: let C be a non-trivial ideal in Euclidean R; I must show it to be principal. Let m = intersect({d(i): non-zero i in C}), the smallest value of d among non-zero members of C; and let x be any member of ({m}&on;d: r ←r :R), i.e. any x in C for which d(x) = m. Thus if d(i) < d(x) for any i in C, that i must be 0. Now, for any y in C, we have some q, r in R with y = q.x +r and d(r) < d(x); since y and q.x are in C, so is r; so r = 0 and y = q.x, so C = {p.x: p in R} is a principal ideal. In particular, every Euclidean domain is a principal ideal domain.
Hopefully it's clear that d(r) is a sort of generalised measure of how far r
is from zero: what the definition of a Euclidean ringlet is saying is that we
can express any y in a ringlet as a multiple of x plus a remainder smaller
than
x. When we can decompose each y in a ringlet as y = q.x +r in this
manner, for some x, the decomposition is known as division with
remainder
, the multiplier q of x is known as the quotient
(of y when
divided by x) and r is known as the remainder
(when y is divided by
x). Notice that, if y and x share a common factor, say c, and our ringlet
cancels down completions, then y = n.c and q.x = m.c give us n.c = m.c +r,
whence there is some i with n = m +i, leading to r = i.c, so the remainder is
also a multiple of c. Thus every common factor of x and y is also a factor of
r. Furthermore, every common factor of r and x is manifestly a factor of q.x +r
= y, so the common factors of r and x are exactly the common factors of x and
y.
This gives rise to Euclid's algorithm
for computing
highest common factors (defined in the next section): to find the highest common
factor of two values, pick the one with larger value under d; if they are equal,
pick either; label the chosen one y and the other x. If x is zero, it is
(fatuously) a multiple of y, so y is their highest common factor. Otherwise,
decompose y as y = q.x +r with d(r) < d(x) ≤ d(y); the common factors of r
and x are exactly the common factors of y and x, so we can now use x, r in place
of y, x and repeat. Since, each time round this procedure, we have d(r) <
d(x) smaller than the previous time round, and d's outputs are all naturals, we
must get down to d(r) = d(0) within at most d(y) −d(0) rounds. In python,
where y % x is the remainder on dividing y by x, this can be written as:
def hcf(y, x):
if d(y) < d(x): x, y = y, x # swap, so d(x) ≤ d(y)
while d(x) > d(0): y, x = x, y % x
return y
A highest common factor
(commonly abbreviated HCF;
also called a greatest common divisor
and abbreviated GCD) of two values
r, s of a ringlet R is a value h of R for which:
Multiplying an invertible value, u, by a highest common factor, h, of
two values gives another highest common factor of those values, since everything
that divides or is divisible by h is equally divided or divisible by u.h, via
u's inverse. Thus the nearest to uniqueness we can hope for in highest common
factors is modulo multiplication by invertible values. Two values in a ringlet
are described as coprime
(to one another) precisely if
their highest common factors are all invertible.
Note that the term highest
(or greatest
) is used
here without reference to whether there is actually an
ordering on our ringlet, for which the given common factor is > all
others; it is really a most comprehensive
common divisor. Among positive
naturals, multiples are always greater than their proper divisors, so a highest
common factor is indeed greater than all others. This breaks down if we involve
0, which is a multiple of every natural yet (in the sense of the usual ordering)
less than each of them; in this sense, 0 is the greatest divisor
among
naturals (if it divides some value, so do all other naturals), even though it's
the lowest natural. Indeed, for any natural n, the greatest common divisor of n
and 0 is n, even when n is 0.
In a principle ideal ringlet R, given two non-zero values r, s, we can use {r, s} to generate an ideal; as all ideals in R are principal, this ideal must be generated by {c} for some c in R. As R is integral, its multiplication commutes and it cancels down completions, so this ideal is just {t.c: t in R} and we have r, s as members, so c divides r and s. Now, the ideal generated by {r, s} manifestly subsumes {n.r +m.s: m, n in R}, which is closed under addition and under multiplication by members of R, so the ideal it generates is just its collection of differences; and this ideal must in fact be the one generated by {r, s}, of which we know c is a member. Thus there exist n, m, p, q in R for which n.r +m.s +c = p.r +q.s (and we can think of c as (p −n).r +(q −m).s). So, whenever some k in R divides both r and s, giving us r = a.k, s = b.k for some a, b in R, we have (n.a +m.b).k +c = (p.a +q.b).k and R cancels down completions, so there's some h in R for which n.a +m.b +h = p.a +q.b, whence c = h.k and k divides c. Thus c is a highest common factor for r, s; in a principal ideal ringlet, any pair of non-zero values has a highest common factor.
Now consider two highest common factors h, k of some pair of values; as each is a highest common factor, each must be a multiple of the other. We thus have n, m in R for which h = n.k and m.h = k, giving rise to n.m.h = h and n.m.k = k. If either h or k is zero, this makes the other (and the values of which they are factors) also zero. Otherwise – since we're working in a principal ideal ringlet, which is an integral ringlet, which is thus descalable – we can cancel a non-zero multiplier and n.m.k = 1.k implies n.m = 1, so n and m are inverses to one another. Thus highest common factors are unique modulo invertible factors (which is as unique as they could ever hope to be). In {naturals}, highest common factors are thus unique, as the only invertible is 1.
Given a pair of values c.h and c.k, with c their highest common factor, h and k can have no common proper factor, as this would yield a proper multiple of c as a higher common factor of c.h and c.k; thus the highest common factor of h and k is 1 (or any other invertible value); h and k are coprime. Suppose, now, that we have another pair of values, p, q, for which p.h = q.k, with h and k coprime; since k is a factor of p.h yet has no common factor with h, k must in fact divide p; likewise h must divide q; and cancelling the common factor of k.h in p.h = q.k when p and q are written as multiples of k and h, respectively, we see that p, q must in fact be p = c.k, q = c.h for some c.
Given values r, s of a ringlet R, we define the lowest
common multiple
of r and s to be that value k of R for which: r and s divide
k and; whenever r and s both divide some value of R, so does k. (This may also
be called the least
common multiple; either way, it gets abbreviated LCM.
In this case, 0 does count as lower than other values; the lowest common
multiple of 0 and any value is 0 since this is the only multiple 0 has
and is a multiple of whatever other value you pair it with.) When our values
are c.h and c.k with highest common factor c, their lowest common multiple is
c.h.k, at least when multiplication commutes.
As for highest
above, this notion of lowest
need
not fit with notions of ordering that the values might otherwise use; just as 0
is greater than all other factors, every multiple is lower than
0 for the
purposes of the lowest common multiple. Among naturals, for example, the lowest
common multiple of n and m can only be 0 if n = 0 = m, even though 0 is
manifestly a multiple of every natural. Furthermore, when we go to the integers
(so we have negative whole numbers as well as positives and zero), each negative
value is deemed greater than the corresponding positive value; otherwise,
arbitrarily large negative common multiples of a pair of values would give us
lower common multiples than any proposed lowest. Just as highest
, above,
really means most comprehensive
, here we need to read lowest
as
something like simplest
.
Written by Eddy.