]>
Using the action of the the naturals on relations via repetition, we can identify a collection of relations, that subsumes (|repeat:{naturals}), 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) 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. I shall,
in due course, establish such composites in a rôle analogous
to repeat(m/n)
, thereby providing us with a model of fractions.
For n = 0, repeat(0) is a constant mapping, so its reverse is not very interesting: its only right value is the universal identity; so composing it before repeat(m) gives a composite that relates every left value (output) of repeat(m) to the universal identity; and composing it after repeat(m) gives a composite that relates every relation to all those relations that, when repeated m times, give the universal identity. Note, in particular, that reverse(repeat(0))&on;repeat(0) is the universal all-relation, which relates every value to every value; this is not the same as the universal identity. None of these are much fun, so I'll stick to n > 0.
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.
We're left with a choice of two ways round to compose N = repeat(n) and W = reverse(repeat(m)). First, N&on;W relates repeat(n, r) to repeat(m, r) for every relation r; and, whenever it relates h to g they must indeed be h = repeat(n, r) and repeat(m, r) = g for some r; which also ensures repeat(m, h) = repeat(n.m, r) = repeat(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 repeat(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(repeat(q))&on;repeat(p), which subsumes repeat(p)&on;reverse(repeat(q)) which, in turn, subsumes N&on;W.
Let's pause to see what we get when we replace each output of repeat with its restriction to A, so N becomes (A: N |A) and W becomes (A| W :A). Since q.n = p.m, we have repeat(n, add(q)) = repeat(m, add(p)), so W&on;N relates add(p) to add(q), just as reverse(repeat(q))&on;repeat(p) and repeat(p)&on;reverse(repeat(q)) do; however, when k > 1, so n > p, (: N :A)&on;(A: W :) doesn't relate add(p) to add(q) because add(p) isn't repeat(n, add(i)) for any natural i. I read this as an argument in favour of W&on;N over N&on;W as the composite to work with.
Of course, it's possible to construct some suitably convoluted relation that, when repeated n times, does give us add(p) and when repeated m times does give us add(q); but to do so we have to go outside A by, in one guise or another, representing fractional steps equivalent to 1/k. Having to do so, however, would encumber the reasoning below, where being able to stay within A is a great convenience.
So define
Note that (since n = 1 makes reverse(repeat(n)) the identity on
relations) this subsumes {repeat(m): m is natural}, so repeat embeds the
naturals in Q; as we'll see, it does so in an entirely suitable way. Since
reverse(repeat(n))&on;repeat(m) has n on the left, it may be easier to think of
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 its
representative 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.
Now, given q in Q, look at (A: q :A) and suppose q relates both add(j) and add(i) to some add(k); as q is reverse(repeat(n))&on;repeat(m) for some naturals n, m with n > 0, we have both repeat(n, add(i)) and repeat(n, add(j)) equal to repeat(m, add(k)), whence add(n.i) = add(m.k) = add(n.j). As add is monic, we get n.i = n.j; as n is non-zero and non-zero multiplication is cancellable in {naturals}, we get i = j; thus, in fact, each (A: q :A) is a mapping. 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.
The multiplication on naturals commutes, so n.i = m.k arises precisely if
repeat(i, add(n)) = repeat(k, add(m)), which happens precisely when
(reverse(repeat(k))&on;repeat(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)
precisely if j\i's representation maps add(n) to add(m); which results in (A: q
:A) being equal to (A: reverse(repeat(j))&on;repeat(i) :A) precisely when q
relates add(i) to add(j). Furthermore, if the intersection of two members of Q
has non-empty restriction to A, so the intersection's restriction relates some
add(i) to add(j), then the restrictions to A of the two members of Q are in fact
equal to (A: reverse(repeat(j))&on;repeat(i) :A); and the two members of Q
represent equivalent fractions (in the usual n/m ~ i/k iff k.n = i.m
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(repeat(c.h))&on;repeat(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-empty (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(repeat(h))&on;repeat(k), which is in Q. So, given q in Q, we can intersect all members of Q whose intersection with q has non-empty (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-empty (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-empty (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(repeat(n))&on;repeat(m) for coprime naturals n, m. In particular, each natural m gives rise to repeat(m) = reverse(repeat(1))&on;repeat(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
repeat(0) as a positive ratio
. We can now define the
division of naturals by, for natural n, m,
The result is, by construction, a natural ratio and, when m is
non-zero, a positive ratio. In either text n/m or m\n, n is known as
the numerator
and m as
the denominator
. We can, further, define multiplication
between naturals and natural ratios and division of natural ratios by naturals
by: for natural k, positive natural h and q = reverse(repeat(n))&on;repeat(m)
representing n\m in Q,
I'll return to what this implies, but first let's take a closer look at R.
Now, R is defined (Q: :{relations}), so that I can apply it to any relation, 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-empty 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(repeat(m))&on;repeat(n), and not by any other member of Q except those equivalent to this.
So consider any (A: r :A) right value of R; the associated left value R(r) is necessarily reverse(repeat(m))&on;repeat(n) for some natural n and positive natural m. From the specification of R, there must be some positive natural k for which reverse(repeat(k.m))&on;repeat(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 empty (A: :A) restriction, which no member of Q has, so r wouldn't be a right value of R). This last, in particular, implies that r is non-empty; as all its values are in A, r relates add(i) to add(j) for some naturals i and j; for each such i, j we know repeat(k.m, add(i)) = repeat(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 r whenever r is (A: r :A) and 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 repeat on the
left of the composite, to make Q's members, has achieved its stated goal of
eliminating common factors, at least within 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-empty, it suffices to determine R(r) entirely; but we aren't guaranteed that R(r) subsumes r. R(r) is reverse(repeat(n))&on;repeat(m) for some (coprime) naturals n, m and every member of Q that subsumes r is reverse(repeat(k.n))&on;repeat(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 natural ratios) we get reverse(repeat(q))&on;repeat(p)&on;reverse(repeat(n))&on;repeat(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(repeat(q))&on;reverse(repeat(n))&on;repeat(p)&on;repeat(m). For the same reason as lead me to put the reversed denominator after the numerator, these two aren't generally equal; but reverse(repeat(n))&on;repeat(p) does subsume repeat(p)&on;reverse(repeat(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), so their intersection's (A: :A) restriction is non-empty 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 repeat(1) = {relations} in place of either r or s, the composite is the other and r.repeat(1) = r = repeat(1).r, so repeat(1) serves as an identity for this multiplication.
On the positive ratios, reverse maps reverse(repeat(n))&on;repeat(m) to reverse(repeat(m))&on;repeat(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), as does repeat(1); hence every member of Q that subsumes (n/m)&on;(m/n) also subsumes repeat(1) and we have (n/m).(m/n) = repeat(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. We have naturals h, i, j, k, n, m with x = reverse(repeat(h))&on;repeat(i), y = reverse(repeat(j))&on;repeat(k) and z = reverse(repeat(n))&on;repeat(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 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 the former (being in Q) 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.
In particular, since R cancels out common factors, for naturals n, m with m positive, we get (n/m).m ≡ (m.n)/m = (m.n)/(m.1) = n/1, the natural ratio representing n. Taken with (n/m)/q ≡ n/(m.q), when q is another positive natural, this ensures that our ratios and naturals interact orthodoxly under multiplication and division; the multiplication and division of ratios by naturals, defined above, is exactly equivalent to treating the natural involved as synonymous with its image under repeat.
Now let's consider addition. For naturals, we had repeat(n, f)&on;repeat(m, f) as repeat(n+m, f); and we want (n\m) +(q\p) to be (q.n)\(q.m +p.n). So suppose we have natural ratios x, y and some relation f for which x relates some relation g to f and y relates some relation h to f. If x and y were mappings, like repeat(n) for natural n, g would be x(f) and h would be y(f), so 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 repeat(n, g) = repeat(m, f) and repeat(q, h) = repeat(p, f). Applying repeat(q) to the former and repeat(n) to the latter, we get repeat(n.q, h) = repeat(n.p, f) and repeat(n.q, g) = repeat(m.q, f); when we compose these, we get repeat(n.q, g)&on;repeat(n.q, h) = repeat(n.p +m.q, f). Thus if h&on;g = g&on;h, reverse(repeat(n.q))&on;repeat(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 repeat(n.q, g&on;h) isn't repeat(n.q, g)&on;repeat(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 = {({naturals}: add(i) |{naturals}): i is natural} 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. So define, for natural ratios x and y,
Every member of A is repeat(i, add(1)) for some natural i, so the members of A all commute, ensuring g&on;h = h&on;g and, thus, repeat(n.q, g)&on;repeat(n.q, h) = repeat(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-empty and the only natural ratio that can subsume it is (n.q)\(m.q +n.p); so our specification of x +y is unambiguous.
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 repeat(n, add(G)) = repeat(m, add(F)) and repeat(q, add(H)) = repeat(p, add(F)), whence n.G = m.F and q.H = p.F. Thus repeat(n.q, add(G)&on;add(H)) = add(n.q.G +n.q.H) = add(m.q.F +n.p.F) = repeat(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 binary operator. In particular, for naturals m, n, p, q with n, q positive, we have (m/n) +(p/q) = (m.q +n.p)/(n.q).
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.
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. As (n/m) +(p/q) = (n.q +m.p)/(m.q), each n/m has (n/m) +(0/1) = (n.1 +m.0)/(m.1) = (n +0)/m = n/m, so 0/1 = repeat(0) is an additive identity, as was surely to be expected.
I showed above 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) subsum 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-empty, 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, whence r relates g&on;h&on;k to f and r is indeed non-empty. 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 k. 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-empty (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) > 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.
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 dot 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 series 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.
Written by Eddy.