Using the action of the the naturals on relations via repetition, we can identify a collection of relations, that subsumes (|repeat:{positive naturals}) and includes a representation of zero, to serve as a model of the non-negative rationals, the ratios between naturals. Their arithmetic flows naturally from the properties of relations.
Each repeat(n) for natural n is a mapping ({relations}: |{relations}). As
such it is a relation and we can take its reverse, albeit this shall not
generally be a mapping, nor shall it be (: |{relations}); none the less
it is a relation. As such, we can compose it before or after repeat(m)
for any natural m; the composite will be a relation and need not be either monic
or a mapping. I shall, in due course, establish such composites in a rôle
analogous to repeat(m/n)
, thereby providing us with a model of ratios of
positive naturals. In the special case n = 1, repeat(1) is the identity on
relations so the composite of its reverse with repeat(m), either way round, is
simply repeat(m), for any natural m; this will give us repeat(m/1)
=
repeat(m) as an entirely natural consequence of how we obtain ratios.
To make sense of what our composites of repeats and their reverses are doing, it'll help to have some definite relations to let them act on, so as to see what they do in an intelligible way. To that end, introduce the collection of translations of {naturals}, A = (| add :) where add = (: ({naturals}: i+j ←j :{naturals}) ←i :{naturals}). These have the convenient property that repeat(n, add(i)) = add(n.i), notably including repeat(i, add(1)) = add(i). Furthermore, add and each add(i) are monic, as is (: repeat(n) :A) for each positive n, thanks to the cancellability of addition and non-zero multiplication, respectively, on the naturals. Thus repeat(n)&on;add is also monic, for each positive n.
Note that, for any relations u, v, reverse(reverse(u)&on;v) = reverse(v)&on;u and reverse(u&on;reverse(v)) = v&on;reverse(u), so the reverse of one of our relations to be understood as ratios is another; this shall, indeed, emerge as the natural form of the multiplicative inverse.
Given that the outputs of repeat are essentially
the Church
numerals, we can think of the ratios I'll be arriving at below as Church
rationals
.
The special case m = 0 gives us ({(: x←x :)}: repeat(0) |{relations}), a constant mapping that maps every relation to the universal identity. Some foundations may not support such universal relations (for example, Zermelo-Fraenkel Set Theory does not); these also preclude repeat(0). However, the reason repeat(0) is universal has to do with ensuring that, when relations f and g commute, so do the results of repeating them. However, we're only going to need that to work for members of A, so we can sidestep the problem.
So let ρ be a mapping from naturals to (relations: |relations) for which ρ(n) is repeat(n) for every positive natural n, but ρ(0) maps each relation to its own collection of values. Thus, for example, ρ(0, a) = add(0), the identity on naturals, for every a in A. I can then use ρ in place of repeat, even if your foundation has no suitable relation for repeat to relate to 0. In particular, this ensures ρ(0, add(i)) = add(0.i) for each natural i, which we'll need below – and which repeat wouldn't have given us, although repeat(0, add(i)) does subsume add(0).
We're left with a choice of two ways round to compose N = ρ(n) and W = reverse(ρ(m)). First, N&on;W relates ρ(n, r) to ρ(m, r) for every relation r; and, whenever it relates h to g, they must indeed be h = ρ(n, r) and ρ(m, r) = g for some r; which also ensures ρ(m, h) = ρ(n.m, r) = ρ(n, g). This last is exactly the condition for W&on;N to relate h to g, so W&on;N subsumes N&on;W. When n = m, N&on;W is just the collection of outputs of ρ(n); in contrast, W&on;N is an equivalence on relations, that identifies two relations if repeating them n times gets the same answer; as a result, W&on;N subsumes {relations} subsumes N&on;W.
Now let's consider the effect of a common factor; so suppose n = k.p and m = k.q for some natural k and (ideally coprime) naturals p, q. Each of our composites is then the corresponding composite for p and q but with the matching composite for k and k inserted in the middle; as a result, W&on;N subsumes reverse(ρ(q))&on;ρ(p), which subsumes ρ(p)&on;reverse(ρ(q)) which, in turn, subsumes N&on;W.
Let's pause to see what we get when we replace each output of ρ with its restriction to A: for any ouput r of ρ we have r(a) in A for all a in A because ρ(i, add(j)) = add(i.j) for all naturals i, j. Thus N becomes (A: N |A) and W becomes (A| W :A). Since q.n = k.p.q = p.m, we have ρ(n, add(q)) = ρ(m, add(p)), so W&on;N relates add(p) to add(q), just as reverse(ρ(q))&on;ρ(p) and ρ(p)&on;reverse(ρ(q)) do; however, when p > 0 and k > 1, so n > p, (: N :A)&on;(A: W :) doesn't relate add(p) to add(q) because add(p) isn't ρ(n, add(i)) for any natural i. Thus, while (A: W :)&on;(: N :A) subsumes (: N :A)&on;(A: W :), the latter need not subsume the former.
Furthermore, although (: N :A)&on;(A: W :) is (A: :A), it is not the same relation as (A: N&on;W :A) because the latter can bypass the former's restriction to the composition going via members of A. In particular, for the case just considered of the former not relating add(p) to add(q), the latter may, by (in effect) going via some form of representation of steps essentially equivalent to 1/k. Contrast this with (A: W&on;N :A) which is, indeed, exactly (A: W :)&on;(: N :A).
I read the foregoing as an argument in favour of W&on;N over N&on;W as the composite to work with. This will allow us to use restriction to A to pin down the details we need, thanks to the composition helpfully being constrained to go via A.
So define
Since reverse(ρ(n))&on;ρ(m) has n on the left, it may be easier
to think of this as
doing division in the form
n\m, n under m
, rather than m/n, m over n
. As shown above, Q's
representation of (k.n)\(k.m) subsumes Q's representation of n\m for every
positive natural k: this shall let us, in due course, narrow our attention to
the members of Q that represent fractions in coprime form.
I shall refer to the various reverse(ρ(n))&on;ρ(0) as zero members of Q since, indeed, they shall turn out to correspond to zero. As each output of ρ(0) is an identity and thus a fixed point of each ρ(n), each zero member of Q subsumes reverse(ρ(1))&on;ρ(0) = ρ(0), which is itself one of these zero members; it is therefore their intersection. The restriction to A of any zero member of Q is simply ({add(0)}: |A) = (: ρ(0) :A) since n.i = 0 for n > 0 implies i = 0 because natural multiplication has no proper zero-divisors. This restriction is non-trivial, since most of its right values are not identities.
Now, given q in Q, look at (A: q :A) and suppose q relates both add(j) and add(i) to some add(k); when q is reverse(ρ(n))&on;ρ(m) for some naturals n > 0 and m, we have both ρ(n, add(i)) and ρ(n, add(j)) equal to ρ(m, add(k)). As noted above, ρ(n)&on;add is monic; since it maps i and j to the same value, we can infer i = j. (This still works when m is zero but would fail for n = 0, since (: ρ(0) :A) isn't monic; this is why n > 0 is specified in the definition of Q.) Thus, in fact, each (A: q :A) is a mapping. By analogous reasoning, each (A: q :A) for non-zero q is also monic, hence iso (between the (|q:A) and (A:q|) subsets of A). When q represents n\m, q(add(k)) = add(i) precisely if n.i = m.k. In particular, as n.m = m.n, we get q(add(n)) = add(m), so q is non-empty: no member of Q is empty, or has empty restriction to A.
Furthermore, every identity is a fixed point of every output of ρ, hence
also of every member of Q. As a result, each member's restriction to A relates
add(0) to itself, and this will be the intersection of any two members of Q that
represent distinct ratios. So I'll describe the intersection of two members of
Q, or a restriction of such an intersection, as trivial
if it only
relates identities to themselves.
The multiplication on naturals commutes, so n.i = m.k arises precisely if
ρ(i, add(n)) = ρ(k, add(m)), which happens precisely when
(reverse(ρ(k))&on;ρ(i))(add(n)) = add(m). This gives us an equivalence
on members of Q, where n\m's representation maps add(k) to add(i), as k\i does,
precisely if k\i's representation maps add(n) to add(m), as n\m does. This
results in (A: q :A) being equal to (A: reverse(ρ(j))&on;ρ(i) :A)
precisely when q relates add(i) to add(j). Furthermore, if the intersection of
two members of Q has non-trivial restriction to A – so the intersection's
restriction relates some add(i) to add(j), with at least one of i, j non-zero;
and this, in turn, implies j is non-zero – then the restrictions to A of
the two members of Q are in fact equal to (A: reverse(ρ(j))&on;ρ(i) :A);
and the two members of Q represent equivalent fractions (in the usual m/n ~
i/k iff m.k = n.i
sense).
We can write any pair of naturals as multiples of their unique highest common factor; so each member q of Q is uniquely expressible as q = reverse(ρ(c.h))&on;ρ(c.k) for some natural c and coprime naturals h and k, representing (c.h)\(c.k). Any member of Q whose intersection with q has non-trivial (A: :A) restriction has the same (A: :A) restriction as q; this restriction relates add(k) to add(h) and each such member of Q represents (e.h)\(e.k) for some natural e; all such subsume the representative of h\k, which is one such (with e = 1), so their intersection is in fact reverse(ρ(h))&on;ρ(k), which is in Q. So, given q in Q, we can intersect all members of Q whose intersection with q has non-trivial (A: :A) restriction; the result shall be one of the members of Q intersected and represents the same fraction as q, but in coprime form.
We can obtain the same coprime representation of q in Q just by taking the intersection of those members of Q that q subsumes, since each of these is among the members of Q intersected above and one of them, the coprime representative, is the only one that actually matters, since it's the intersection. However, later, I shall want to be able to take a general relation r (with non-trivial (A: :A) restriction) subsumed by some member q of Q and map r to the coprime-form member of Q that represents q. When q represents (c.h)\(c.k) as above, with h, k coprime, each of the members of Q whose intersection with q has non-trivial (A: :A) restriction represents (e.h)\(e.k) for some natural e and another of those intersected represents (c.e.h)\(c.e.k), which subsumes both this and q; so each member of q intersected to get the coprime member is subsumed by some member of Q that subsumes q, hence also r.
So I define:
and note that (: R :Q) = (Q: intersect({p in Q: q subsumes p}) ←q :Q). If we look at a left value r of R, it's a member of Q that subsumes no other member of Q; it is, in this sense, a minimal member of Q. Each left value is thus, furthermore, a fixed point of R, so R&on;R = R. The reasoning that lead us here ensures that the fixed points (i.e., in this case, left values) of R are in fact exactly the reverse(ρ(n))&on;ρ(m) for coprime naturals n, m. In particular, each natural m gives rise to ρ(m) = reverse(ρ(1))&on;ρ(m) as a fixed point of R.
The interesting ratios are then the fixed points of R,
representing ratios in coprime form. So describe each fixed point of R as
a natural ratio
; and each natural ratio other than
ρ(0) as a positive ratio
. We can now define the
division of naturals by, for natural n, m with n > 0,
The result is, by construction, a natural ratio and, when m is
positive, a positive ratio. In either text m/n or n\m, m is known as
the numerator
and n as
the denominator
.
When the numerator is actually a multiple of the denominator, we get n\(k.n) = 1\k = reverse(ρ(1))&on;ρ(k) = ρ(k), so ρ maps positive naturals to positive ratios (and naturals to natural ratios) in a manner consistent with the division intrinsic to their own multiplication, as distinct from the one defined here.
Now, R is defined (Q: :{relations}), so that I can apply it to any relation with non-trivial A-restriction, provided the q in Q that subsume the given relation do all have, as the intersection of those p in Q that they subsume, some member of Q. In particular, any non-trivial relation (A: :A) that is subsumed by some member of Q is a right value of R; it's also necessarily a mapping, as any q in Q that subsumes it gives us a mapping (A: q :A) that subsumes it. Even an atomic relation such as add(n)←add(m) for n, m natural, with m non-zero, will do: this is subsumed by reverse(ρ(m))&on;ρ(n), and not by any other member of Q except those equivalent to this.
So consider any right value r of R; the associated left value R(r) is necessarily reverse(ρ(m))&on;ρ(n) for some natural n and positive natural m. From the specification of R, there must be some positive natural k for which reverse(ρ(k.m))&on;ρ(k.n) subsumes r; and no member of Q subsumes r except those of this form (since, if any others did, the intersection would have trivial (A: :A) restriction, which no member of Q has, so r wouldn't be a right value of R). If r relates add(i) to add(j), for some naturals i and j (as we know it must, since (A: r :A) is non-trivial), we know ρ(k.m, add(i)) = ρ(k.n, add(j)) whence k.m.i = k.n.j and, as k is positive, m.i = n.j and R(r) also relates add(i) to add(j). Thus, in fact, R(r) subsumes (A: r :A) whenever r a right value of R.
In particular, for any q in Q, (A: q :A) is a right value of R and subsumed
by R(q), which q subsumes; thus (A: q :A) = (A: R(q) :A) for every q in Q. The
restrictions of members of Q to A are ready-simplified
to their coprime
form on A, for all that members of Q representing non-coprime ratios may be more
complicated on relations in general. Thus putting the reversed ρ on the
left of the composite, to make Q's members, has achieved its stated goal of
eliminating common factors, at least for the restriction to A.
Given a general right value r of R; some q in Q subsumes it and each such q has R(q) = R(r), which subsumes (A: r :A); when this is non-trivial, it suffices to determine R(r) entirely; but we aren't guaranteed that R(r) subsumes r. R(r) is reverse(ρ(n))&on;ρ(m) for some (coprime) naturals n, m and every member of Q that subsumes r is reverse(ρ(k.n))&on;ρ(k.m) for some positive natural k. This still leaves plenty of freedom in right values of R (i.e. the inputs it accepts), but I'll largely ignore it as the only right values I'll actually be interested in are members of Q and relations (A: :A).
When we compose two members of Q (e.g. two positive ratios) we get reverse(ρ(q))&on;ρ(p)&on;reverse(ρ(n))&on;ρ(m) representing (q\p).(n\m), which we'll want to identify with (n.q)\(p.m), which (given the multiplication on naturals) is represented by reverse(ρ(q))&on;reverse(ρ(n))&on;ρ(p)&on;ρ(m). For the same reason as lead me to put the reversed denominator after the numerator, these two aren't generally equal; but reverse(ρ(n))&on;ρ(p) does subsume ρ(p)&on;reverse(ρ(n)), so Q's representation of (n.q)\(p.m) shall at least subsume the composite of those of (q\p) and (n\m). In particular, both inevitably relate add(n.q) to add(p.m) and n.q > 0, so their intersection's (A: :A) restriction is non-trivial and we can infer that all members of Q that subsume (q\p)&on;(n\m) are in fact equivalent; we can duly specify the coprime one of these to be the product of q\p and n\m. For r, s in Q, I thus define
This ensures that r.s is always a natural ratio, in particular that natural ratios are closed under this multiplication. With the identity 1\1 = ρ(1) = {relations} in place of either r or s, the composite is the other and r.(1\1) = r = (1\1).r, so 1\1 serves as this multiplication's identity.
R maps every zero member of Q to ρ(0) = 1\0. For any n, p, q with n and q positive, reverse(ρ(n))&on;ρ(0)&on;reverse(ρ(q))&on;ρ(p) = (: reverse(ρ(n))&on;ρ(0) :(|reverse(ρ(q))&on;ρ(p):)) which is non-trivial and subsumed by reverse(ρ(n))&on;ρ(0) so R will map it to ρ(0), thus (n\0).(q\p) = 1\0. The other way round, reverse(ρ(n))&on;ρ(m)&on;reverse(ρ(q))&on;ρ(0) subsumes reverse(ρ(n))&on;reverse(ρ(q))&on;ρ(m)&on;ρ(0) = reverse(ρ(n.q))&on;ρ(0) so, again, R will map it to 1\0 and (n\m).(q\0) = 1\0. Any product of natural ratios that includes a zero factor will, furthermore, be 1\0, regardless of the order of multiplication: ((q\p).(1\0)).(n\m) = (1\0).(n\m) = 1\0 = (q\p).(1\0) = (q\p).((1\0).(n\m)), for example.
On the positive ratios, reverse maps reverse(ρ(n))&on;ρ(m) to reverse(ρ(m))&on;ρ(n), so maps each n/m to m/n and vice versa. Since every positive ratio is n/m for some positive naturals n, m, its reverse is m/n and the composite (n/m)&on;(m/n) necessarily relates add(n.m) to add(n.m), making the composite's restrcition to A non-trivial. As 1\1 also relates add(n.m) to itself, every member of Q that subsumes (n/m)&on;(m/n) also subsumes 1\1 and we have (n/m).(m/n) = 1\1, providing each positive ratio with an inverse.
Now consider members, x, y and z, of Q and compare x.(y.z) with (x.y).z. As covered above, if any of them is n\0 both products are zero, so it only remains to study the case where R maps each to a positive ratio. We have positive naturals h, i, j, k, n, m with x = h\i, y = j\k and z = n\m. Since y.z relates add(k.m) to add(j.n) it is in fact (k.m)/(j.n), so x.(y.z) relates add(i.k.m) to add(h.j.n) – and the multiplication of naturals is associative, so I can indeed write i.k.m without having to indicate which of (i.k).m = i.(k.m) I mean by it; and likewise for h.j.n. As x.y relates add(i.k) to add(h.j) it is in fact (i.k)/(h.j) and (x.y).z also relates add(i.k.m) to add(h.j.n); since x.(y.z) and (x.y).z have this in common (and neither i.k.m nor h.j.n is zero) they must in fact be the same natural ratios. Thus our multiplication is associative and, under this multiplication, the positive ratios form a group.
For naturals n, p and positive naturals m, q, since Q's representation of (n.p)/(m.q) subsumes the composite of its representations of (n/m) and (p/q), each of which subsumes what R maps it to, the former is one of the members of Q intersected to make (n/m).(p/q); and (being in Q) it also subsumes its image under R, (n.p)/(m.q), which is a minimal member of Q in the intersection that makes the product, so (n/m).(p/q) = (n.p)/(m.q). Since the multiplication of naturals commutes, this ensures that our multiplication on Q also commutes.
Our natural identification of each natural m with ρ(m) = 1\m in Q duly delivers for us a multiplication between naturals and natural ratios; combining that with reverse as multiplicative inversion on positive ratios, we duly obtain division of natural positive ratios by positive naturals. These give, for natural k, positive natural h and q = reverse(ρ(n))&on;ρ(m) in Q representing n\m = m/n,
Since R cancels out common factors, for naturals n, m with m positive, we get m.(n/m) = (m.n)/m = (m.n)/(m.1) = n/1, the natural ratio representing n. Taken with (n/m)/p = n/(m.p), when p is another positive natural, this ensures that our ratios and naturals interact orthodoxly under multiplication and division, with behaviour exactly equivalent to treating the natural involved as synonymous with its image under ρ.
Now let's consider addition. For naturals, we had ρ(n, f)&on;ρ(m, f) as ρ(n+m, f); and we want (n\m) +(q\p) to be (q.n)\(q.m +p.n). So suppose we have positive ratios x, y and some relation f for which x relates some relation g to f and y relates some relation h to f; we're looking for x+y to relate g&on;h to f. We have some naturals m, n, p and q for which x is n\m and y is q\p, so ρ(n, g) = ρ(m, f) and ρ(q, h) = ρ(p, f). Applying ρ(q) to the former and ρ(n) to the latter, we get ρ(n.q, h) = ρ(n.p, f) and ρ(n.q, g) = ρ(m.q, f); when we compose these, we get ρ(n.q, g)&on;ρ(n.q, h) = ρ(n.p +m.q, f). Thus if h&on;g = g&on;h, reverse(ρ(n.q))&on;ρ(n.p +m.q) shall relate it to f; in particular, this shall arise whenever h and g can both be expressed as repetitions of some single relation. Thus (: g&on;h ←f; x relates g to f, y relates h to f :) looks like a half-way sensibe thing to use as x +y. However, it isn't necessarily a natural ratio (as it may relate some g&on;h to f where ρ(n.q, g&on;h) isn't ρ(n.q, g)&on;ρ(n.q, h); this can arise when g&on;h isn't h&on;g).
We thus need to work a little harder to get this right; fortunately, we can restrict attention to A and then use the intersection of all members of Q that subsume this restriction to recover the correct positive ratio to serve as x +y.
Where 1\0, or more generally n\0, is involved, there's a problem with the step from h and g commuting to reverse(ρ(n.q))&on;ρ(n.p +m.q) relating their composite to f, unless h, g and their composite have the same collection of values as each other. Indeed, the reason repeat(0) maps every relation to a universal identity is precisely that only this can ensure that step. However, fortunately, we're only interested in members of A, all of which do have the same collection of values, so we can still get away with using ρ in place of repeat.
So define, for natural ratios x and y,
Note that the definition can equally be written as x +y = R(: ((A:x:A)(f))&on;((A:y:A)(f)) ←f :), if you happen to find that more readable; each of (A:x:A) and (A:y:A) is a mapping, so the input passed to R just maps each member of A that's a right value of both to the composite of the left values each maps it to. I find the superfluity of parentheses a little distracting, though.
The members of A all commute (and have the same collection of values as each other and their composite), ensuring g&on;h = h&on;g and, thus, ρ(n.q, g)&on;ρ(n.q, h) = ρ(n.q, g&on;h) for each g, h in A. In particular, when x = n\m and y = q\p, we have f = add(n.q), g = add(m.q) and h = add(n.p) for which x relates g to f, y relates h to f and thus s = (: g&on;h ←f; (A:n\m:A) relates g to f, (A:q\p:A) relates h to f :) is non-trivial and the only natural ratio that can subsume it is (n.q)\(m.q +n.p); so our specification of x +y is unambiguous.
For x = 1\0 we get 1\0 +y = R(: add(0)&on;h ←f; (A:y:A) relates h to f :) = R(A: y :A) = y and, likewise, x +1\0 = x. Thus 1\0 serves as identity for our addition. In particular, 1\0 +q\p = (1.q)\(0.q +1.p) and n\m +1\0 = (n.1)\(m.1 +n.0). Otherwise, x and y are positive ratios and…
In so far as s relates any left value to any right value, the left value is add(G)&on;add(H) and the right value is add(F), for some naturals G, H and F, for which n\m relates add(G) to add(F) and q\p relates add(H) to add(F); thus ρ(n, add(G)) = ρ(m, add(F)) and ρ(q, add(H)) = ρ(p, add(F)), whence n.G = m.F and q.H = p.F. Thus ρ(n.q, add(G)&on;add(H)) = add(n.q.G +n.q.H) = add(m.q.F +n.p.F) = ρ(m.q +n.p, add(F)) and (n.q)\(m.q +n.p) does relate add(G)&on;add(H) to add(F), just as s does; thus (n.q)\(m.q +n.p) subsumes s. Thus the specification of x +y does actually specify some natural ratio, for any natural ratios x and y; and we've already seen that it does so uniquely.
Our addition is thus a well-behaved unambiguous binary operator on natural ratios, with identity 1\0 = ρ(0). In particular, for naturals m, n, p, q with n, q positive, we have (m/n) +(p/q) = (m.q +n.p)/(n.q).
As the (A: :A) relation passed to R in the definition of addition only looks at members of A, all of which commute, interchanging x and y changes nothing in the definition, so x +y = y +x for any natural ratios x and y. I've shown above that 1\0 = ρ(0) is an additive identity, as was surely to be expected.
I showed earlier that, when a relation (A: r :A) is a right value of R, R(r) subsumes r; so, when u, v are in Q, u +v subsumes s(u, v) = (: g&on;h ←f; (A:u:A) relates g to f, (A:v:A) relates h to f :). Given natural ratios x, y, z, this ensures that both (x +y) +z and x +(y +z) subsume r = (: g&on;h&on;k ←f; (A:x:A) relates g to f, (A:y:A) relates h to f, (A:z:A) relates k to f :), since this is just s(x, s(y, z)) = s(s(x, y), z). As long as this is non-trivial, it suffices to ensure (x +y) +z = x +(y +z), given that it's (A: :A) by specification (combined with associativity of natural addition, which ensures that g&on;h&on;k is indeed an output of add whenever g, h and k are). If x, y and z are n/m, p/q and u/v for some naturals n, p, u and positive naturals m, q, v, then f = add(m.q.v) gives us g = add(n.q.v), h = add(m.p,v) and k = add(m.q.u) for which (A:x:A) relates g to f, (A:y:A) relates h to f and (A:z:A) relates k to f, with f not an identity (as m.q.v > 0), whence r relates g&on;h&on;k to f and r is indeed non-trivial. Thus our addition on natural ratios is associative.
Suppose we have x +y = x +z for some natural ratios x, y and z. There are naturals n, p, u and positive naturals m, q, v for which x = n/m, y = p/q and z = u/v: these give (n.q +m.p)/(m.q) = x +y = x +z = (n.v +m.u)/(m.v) whence, multiplying by m.q.v, we get n.q.v +m.p.v = n.q.v +m.q.u in {naturals}, where we can cancel addition of n.q.v to get m.p.v = m.q.u; and m is positive, so we can cancel multiplication by it to get p.v = q.u whence p/q = u/v, i.e. y = z. Thus x +y = x +z implies y = z and our addition on ratios is cancellable.
When we have naturals i, j, k with k > 0, we get both (i/k) +(j/k) and (i +j)/k. The latter relates add(i +j) to add(k); and the former relates add(i)&on;add(j) to add(k), which is not an identity. The addition on naturals is associative, so add(i)&on;add(j) = add(i +j), so the intersection of (i/k) +(j/k) and (i +j)/k has non-trivial (A: :A) restriction whence (as each is an output of R) the two are in fact equal. Thus division by a non-zero natural distributes over addition in its numerator.
For natural ratios n/m, p/q and u/v, we have (n/m) +(p/q) = (n.q +m.p)/(m.q) and multiplying both sides by u/v gives
by distributivity on {naturals}
as division by a non-zero natural distributes over addition in its numerator (we have m, q, v all positive, hence their product is also non-zero)
by cancelling common factors
Thus our multiplication on ratios distributes over their
addition. That division by a positive ratio also distributes over addition
follows simply from the positive ratio having a multiplicative inverse. Given
distributivity, it makes sense to adopt the usual convention of letting division
and multiplication bind more tightly
than addition (and, where it arises,
subtraction) so as to cut back on how many parentheses we need to disambiguate
expressions.
If two natural ratios sum to zero, they are n/m and p/q with (n.q +m.p)/(m.q) = 0/1, whence n.q +m.p = 0, with both n.q and m.p natural; for their sum to be 0, both must be 0, so we have n.q = 0 = m.p. This, in turn (given that m and q are non-zero and {naturals} has no zero-divisors) implies n = 0 = p, so n = 0.m, p = 0.q and n/m = 0/1 = p/q. Thus two natural ratios can only sum to zero if both are zero; no positive ratio has an additive inverse (in the natural ratios).
Suppose we have natural ratios x = n/m, y = p/q with n, p natural and m, q positive naturals. Both n.q and m.p are naturals, so one of them subsumes the other; let us have labelled our two ratios the way round that makes n.q ≥ m.p, so that there is some natural r for which n.q = m.p +r. Dividing by m.q we thus get n/m = (m.p +r)/(m.q) = p/q +r/(m.q), so there is some natural ratio, r/(m.q), that we can add to y to get x. Thus, for any two natural ratios, there is some natural ratio that we can add to one to get the other.
Combining the two preceding paragraphs, if we have natural ratios x, y for
which there are natural ratios r, s for which x = y +s and x +r = y, we get 0
+(x +y) = 0 +y +s +x +r = s +r +(x +y) and additive cancellation reduces this to
0 = s +r, whence s = 0 = r and x = y; in particular, for every natural ratio x,
we do indeed have r = 0 for which x +r = x. If we have natural ratios x, y, z
with x = y +r and y = z +s for some natural ratios r, s then we have x = z +(r
+s) with r +s a natural ratio. We can thus define a relation ≤ on natural
ratios for which x ≤ y
precisely if y = x +r for some natural ratio
r
; this is transitive and reflexive, by the foregoing; its union with its
reverse is the all-relation on natural ratios (i.e. for all x, y either x ≤ y
or y ≤ x) while their intersection is just the identity on natural ratios
(i.e. x ≤ y ≤ x precisely if x = y). Observing that x ≤ y has x = y
precisely when the r for which x +r = y is r = 0, we can likewise define < on
natural ratios by x < y
precisely if y = x +r for some positive
ratio r
; this is transitive, has empty intersection with its reverse and the
union of it, its reverse and {natural ratios} is the all-relation on natural
ratios. We can duly define ≥ = reverse(≤) and > = reverse(<) to
complete the familiar ordering on natural ratios.
If we have natural ratios x, y, z with x ≤ y, then the r for which x +r =
y gives us z +x +r = z +y whence z +x ≤ z +y, with equality precisely when x
= y; order is preserved by translations. Likewise, z.x +z.r = z.(x +r) = z.y so
z.x ≤ z.y, with equality precisely when z.r = 0, i.e. when either z = 0 or x
= y. Thus order is preserved by positive scaling. In particular, when n/m +r/s
= p/q we get n.s.q +m.r.q = m.s.p so n.s.q ≤ m.s.p, with equality precisely
if r = 0, and (as s > 0) n.q ≤ m.p. Conversely, n.q ≤ m.p for natural
n, m > 0, p, q > 0 implies some natural r for which n.q +r = m.p, whence
n/m +r/(m.q) = p/q so n/m ≤ p/q, with equality precisely if n.q = m.p.
Thus n/m ≤ p/q
precisely if n.q ≤ m.p
with equality in
either precisely if also in the other: our ordering of ratios fits in the
expected way with that on naturals.
In particular, the ordering of naturals (just like their arithmetic) is preserved by their embedding in the natural ratios; n < m in {naturals} implies n/1 < m/1 in {natural ratios}. We can thus treat the naturals, via this embedding, as if they were natural ratios; this I shall normally do; however, for the purposes of this page, it seems prudent to distinguish a natural n from the natural ratio n/1 that represents it.
For any natural ratio p/q, we have q positive, so q ≥ 1 and q.(p +1) ≥ p +1 > p, whence p/q < (p +1)/1; for every natural ratio, there is some natural whose representation as a natural ratio is greater than the given ratio. All naturals less then a given ratio are also less than any natural greater than this ratio (by transitivity of the ordering of natural ratios) and there are only finitely many naturals less than any given natural, hence there are only finitely many naturals less than any given natural ratio. This allows us to define
(the former's name is short for cieling
; we are metaphorically
splitting the natural ratios into a stack of rooms
, each between n and
n+1 for some natural n; the cieling of each room is the floor of the next one
up). Since the ordering on natural ratios is consistent with that on naturals,
each natural n has ciel(n/1) = n = floor(n/1). For convenience in the following
discsusion, I shall also define
so that floor = unite&on;F. Since 0 < every other natural, 0/1 < every other natural ratio and 0 is in ciel(r) for every positive ratio r; similarly, 0/1 ≤ every natural ratio, so 0 is in F(r) for every natural ratio r. In particular, F(r) is non-empty for every natural ratio r, hence equal to the successor of its union, F(r) = floor(r) +1. By construction, F(r) subsumes ciel(r) for every natural ratio r, so floor(r) +1 = F(r) ≥ ciel(r).
No natural is a member of itself, hence (from their respective specifications, again) ciel(r)/1 isn't < r and F(r)/1 isn't ≤ r, so ciel(r)/1 ≥ r and F(r)/1 > r. Since floor(r) is in F(r), we have floor(r)/1 ≤ r < F(r)/1. There are thus natural ratios s, t, with t positive, for which r = floor(r)/1 +s and F(r)/1 = r +t, with s +t = 1/1 (by cancellation from floor(r)/1 +s +t = floor(r)/1 +1/1) implying s < 1/1 and t ≤ 1/1. From orderings already given, we have ciel(r)/1 ≥ r ≥ floor(r)/1, so floor(r) ≤ ciel(r) ≤ F(r) = floor(r) +1, so ciel(r) is either floor(r) or floor(r) +1. In the former case, we have ciel(r)/1 ≥ r ≥ floor(r)/1 = ciel(r)/1 implying r = ciel(r)/1, i.e. r is the natural ratio that represents some natural. Otherwise, r is a natural ratio between naturals with floor(r) < r < ciel(r) = floor(r) +1.
Thus, for every natural ratio r, there are natural ratios a, b each <
1/1, for which floor(r)/1 +b = r and r +a = ciel(r)/1; when r represents a
natural a = 0 = b; otherwise, ciel(r) = floor(r) +1 and a +b = 1. The
difference, b = r −floor(r)/1, between a natural ratio and its floor is
known as the fractional part
of that natural ratio.
We can now extend our numeral notation for the naturals to a corresponding notation for natural ratios. Any natural ratio r can be written as floor(r) +f for some natural ratio f < 1/1. We then proceed to represent r by combining the already-defined numeral denotation for the natural floor(r) with a representation of its fractional part, f, that uses a modified form of the same notation. The two parts are then joined using a separator (distinct from any separator that may be in use to group the digits in either part).
In my writings (following the usual localization of anglophone languages),
when the digits are characters, I use a dot as the separator between natural and
fractional parts; unhelpfully, this coincides with one of the symbols I use to
denote multiplication, obliging me to specify that two sequences of digits
joined by a dot are to be read as a denotation for a natural ratio, rather than
as the result of multiplying two naturals. When I need to write a product of
numerals, I use × instead of a dot. When talking about numerals for
ratios, I use the name point
for the dot, if it appears.
We'll be doing this, as ever, using a natural base b > 1, and some digits
representing the members of the natural b; as for the numeral denotations of
naturals, these digits
and the fractional-part separator are texts at
some choice of textual decomposition granularity (single character, word,
etc.)
and the denotation we'll be consructing is at the next coarser
level of textual decomposition granularity (word, phrase, etc.)
Feel free
to just think of the digits and separator as characters and the resulting
denotation as conventional word-like numerals, such as 3.14159 (one of the
natural ratios close to the transcendental number π); but the same
specification equally applies to three point one four one five nine
meaning exactly the same thing, but with words as digits and separator
and the phrase
made up of them being the denotation for a natural
ratio.
Once we come to additive completion, i.e. to allowing negative values, as
well as positive, we'll be able to extend floor and ciel; the floor of a
negative ratio shall be less than it, hence (in magnitude) bigger than it, while
its ciel shall be greater (hence smaller) than it. We'll then have an integer
denotation for floor, a negative integer, to which we could (but shall not) join
a positive fractional part; the integer denotation is obtained by
applying −
as a unary negation (rather than binary subtraction)
operator to a numeral denoting a natural. However, I prefer to follow orthodoxy
and apply the unary negation operator to the whole denotation for a natural
ratio, rather than having the unary negation apply only to the natural number
part, leaving the fractional part always positive (or zero). If nothing else,
this fits with the point I'm using as fractional-part separator being understood
to bind more tightly than arithmetic operators; recognising which sub-texts of a
text are numeral denotations happens before (at the lexical
stage)
recognition of identifiers and operators in arithmetic expressions.
The usual numeral notation for a natural requires us always to have at least
one digit, so that zero is represented by 0 rather than an empty text; when we
come to combine this with a fractional part, however, the result won't be empty
as long as the fractional part isn't; so it's common to allow that an empty
numeral
joined to a non-empty representation of a fractional part,
like .3183
, is a valid denotation for a ratio (that happens to be fairly
close to the value of 1/π). While I like that in a programming language, I'm
not going to do it in the specification here.
So, given a natural ratio r, we already know how to denote floor(r); this shall be followed by a fractional-part separator, then a representation of the fractional part of r. When the fractional part is 0/1, we can omit it – after all, r is equal to a natural – but the following does also allow a zero fractional part to be denoted by a sequence of zero digits, joined using the usual separator to the usual numeral denotation of floor(r).
We have a natural b > 1 that we're using as our number base. For any
fractional part p/power(n, b) with p, n natural; since this fractional part is
less than 1/1, we have p < power(n, b) and can represent p to base b using a
digit sequence with at most n digits in it; and we can pad this with leading
zero digits to produce an equivalent numeral in exactly n digits. In such a
case, the representation of p/power(n, b) as fractional part is this n-digit
numeral representing p. Such a denotation is said (to distinguish it from the
one below) to terminate
(for the given base); some writers
apply this term also to those natural ratios whose denotations, to some
particular base (usually ten), terminate.
Note that the equivalent representation of this fractional part as p.power(m, b)/power(n +m, b) leads to an alternate representation that simply appends m zero digits to that of p/power(n, b); where the numeral denotation of naturals allows and ignores leading zeros, the numeral denotation of fractional parts allows and ignores trailing zeros. In contrast, note that I required the representation of p/power(n, b) to use n digits, requiring it to include leading zeros even when p has a shorter base-b representation; leading digits in a fractional part are significant, just as trailing digits are in numerals denoting naturals. In both cases, zeros adjoining the fractional-part separator are significant, while those at the start and end of the representation of the natural ratio are optional and ignored.
That suffices to represent all ratios whose denominator is, or divides, a
power of our base; however, there are plenty of denominators coprime to our
base, so what do we do about those ? One answer is to approximate –
when we come to represent real numbers, this shall be
the best we can do with positional numeral notation – and this is often
sufficient for practical purposes. However, we can do better for natural
ratios: we can represent endlessly-repeating sequences of digits. To this end,
we need some way to mark a trailing sequence of digits as to be repeated
indefinitely
; a context using this extension to the numeral notation should
make clear what mechanism it uses for that. One approach is to enclose the
repeated sequence in paretheses, so that 0.(142857) denotes 1/7 (as we'll see
below).
Unfortunately, enclosing the last digits of a number in parentheses is also used, in some contexts, to indicate a best estimate value in which the last few digits are given despite being uncertain; so this notation is not universally accepted by orthodoxy. Another common notation puts a dot above the first and last of the digits to be repeated. Some confusion can arise with this, however, as I have seen some put dots above the first digit of the repeat-cycle and above the instance of that same digit that starts the next cycle; so the repeated digits are those from the first dot to just before the second. Orthodoxy is not entirely settled, in short, on a single way to do this; so I specify it generically and leave context to chose.
It suffices that each context, that uses it, makes clear what convention for
endless repetition it uses. When a fractional part is equal to (p + q/(power(m,
b) −1))/power(n, b) for some naturals p, q, n, m with q < power(m, b)
−1, this fractional part may be represented by marking an m-digit numeral,
representing q in base b, for endless repetition and appending the result to the
foregoing representation of p/power(n, b). Such a denotation is said
to recur
or repeat
, implicitly endlessly.
Note: the requirement q < power(m, b) −1 excludes the
decimal denotation 0.(9) and all its relatives, since these only cause
ambiguity. When performing arithmetic on numeral denotations, if the result
comes out looking like one of these, this rule requires that it be canonicalized
to the equivalent terminating representation of the p/power(n, b) type. As
before, the requirement of an m-digit numeral to represent q makes leading zeros
significant. Note also that 1 +1/(power(m, b) −1) = power(m, b)/(power(m,
b) −1), so (p + q/(power(m, b) −1))/power(n, b) = (p.power(m) +q
+q/(power(m, b) −1))/power(n+m, b) so unrolling
the first repeat of
the repeating part doesn't change the number represented. Exercise for the
interested student: show that (even when m > 1) cycling the first digit of q
round to the end of q's denotation, while appending a copy of that digit to p's,
also gives an equivalent representation of the same natural ratio.
Because every natural k co-prime to b has power(m, b) equivalent to 1 mod k for some m, every denominator co-prime to b is a divisor of power(m, b) −1 for some m; as a result, every natural ratio can be represented using one of the forms given above. A denominator not coprime to b, yet not a divisor of a power of b, is reduced to one that is coprime to b by multiplying the fractional part by power(n, b) for some n to get the p +q/(power(m, b) −1) that, when divided by power(n, b) is descbribed by the notational form for repetition.
Example, in base ten: 7×11×13 = 1001; multiplying that by 999 gets us 999999 = power(6, 10) −1; 11×13 = 143; 143×999 = 143000 −143 = 142857; so 1/7 = 142857/999999 is represented by 0.(142857), when enclosure in parentheses is used to mean endless repetition, as noted above. Likewise, 7×11×999 = 77000 −77 = 76923 so 1/13 = 0.(076923), with the same repeat length. For 1/11, this gives us 7×13×999 = 91000 −91 = 90909 and 1/11 = 0.(090909), which is equivalent to the 0.(09) that arise from 1/11 = 9/99.
Written by Eddy.