# The Positive Rationals

Composition of lists of relations can be used to construct a notion of repetition.

For any natural n and relation r, there is a unique ({r}:|n) – i.e. relation whose left values are all r, with all members of n as right values. As this is has only one left value, it is trivially a mapping; as its (:|) is a natural, it's thus a list, of length n, each entry in which is r. For n = 0, that's [] regardless of r; ({r}:|1) = [r], ({r}:|2) = [r,r], … ({r}:|n) being thus [r,…,r] of length n.

Composition of lists is implemented by a mapping

• compose({relations}: a&on;…&on;z ← [a,…,z] :{lists ({relations}::)})

where a&on;…&on;z relates p to q iff a relates p to some f, which … relates to some g, which z relates to q. If we apply this to ({r}:|n), we get the result of r repeated n times; when r is a displacement in some linear space, compose({r}:|n) is a displacement n times as big. Now, while I can give compose([]), hence repeat(0), a sensible meaning, it proves unhelpful in the following, so I'll define:

• repeat = (: ({relations}: compose({r}:|1+n) ←r :{relations}) ←1+n :{naturals})

whose typical output is repeat(1+n) for some natural n; i.e. repeat(m) for some positive natural m; and I shan't give repeat(0) a value. Now, repeat(1+n,successor,0) is unavoidably 1+n, so repeat has an inverse, namely s(successor,0) ←s, which guarantees that it is a monic mapping.

Now, for any list h of positive naturals, repeat&on;h is a list of outputs of repeat so repeat begets

• (:product:{non-empty lists of positive naturals}) = reverse(repeat)&on;compose&on;(: repeat&on;h ←h :)
• (:sum:{non-empty lists of positive naturals}) = reverse(repeat)&on;compose&on;transpose&on;(: repeat&on;h ←h :)

wherein: transpose maps repeat&on;h to p = (: (: p(r,i) ←r :) ←r :{relations}), in which p(r,i) is repeat(h(i),r), so that p(r) is a list for each r; its entries are all repeats of r; compose maps this list to compose(: repeat(h(i),r) ←i :) which is compose(: compose({r}:|h(i)) ←i ) which – using @ as the list-append operator, [a,…,f]@[g,…,z] = [a,…,f,g,…z], and supposing h to be (:h|1+n) – is compose(({r}:|h(0))@…@({r}:|h(n))), which is compose({r}:|k) for some natural k since the input to compose is a list whose entries are all r; thus compose(p(r)) is indeed repeat(k,r) for some k, so compose&on;p = repeat(k) is an output of repeat. Thus sum may be construed as a pull-back of compose&on;transpose, through repeat; in like manner, product is a pull-back of compose itself.

Now, repeat(1) is the identity on relations – repeating once is better known as simply doing – because compose([r]) = r for every relation r; so every relation is an output of repeat(1). There is no particular reason to suppose that the same is true of repeat(n) for any larger n; indeed, I would suspect that no n>1 has successor = (: s←r; s relates x to y iff x = r = y or r relates x to y :{relations}) as an output, though I wouldn't gamble on it. None the less, each output s of repeat is ({relations}:s|{relations}); and any two such outputs can be distinguished, as described above.

## fixed points and coincidences

For any relation f and any s in (|repeat:), (|f:) subsumes (|s(f):) and (:f|) subsumes (:s(f)|), trivially; whence, for any r in (|repeat:), (|r(f):) subsumes (|(s&on;r)(f):) and likewise for (:|) and for s(f)&on;r(f) in place of (s&on;r)(f). Thus if f is a fixed point of repeat(2+n), any i+j=n gives us r = repeat(1+i), s = repeat(1+j) for which s(f)&on;r(f) = f so (:f|) subsumes (:r(f)|), which subsumes (:s(f)&on;r(f)|) = (:f|), hence (:f|) = (:r(f)|) and likewise for (|:). Thus (using 1+k=i) if f = repeat(2+n,f) it has the same left and right values as each repeat(2+k,f) with k in n. Furthermore, as f is a fixed point of repeat(2+n) it is also a fixed point of repeat((2+n).(1+p)) for any natural p; with (2+n).(1+p) = 2 +(n +2.p +n.p) and every natural k is in n+2.p+n.p for some natural p; so if f is a fixed point of any repeat(2+n), all outputs of repeat map f to relations with the same left and right values as f.

For a relation f and a mapping g with f&on;g = g, we can infer that both (|f:) and (:f|) subsume (|g:) = (:x←x:g) = g&on;reverse(g). Thus (:f:g) = f&on;g&on;reverse(g) = g&on;reverse(g) = (:x←x:g), so (:f:g) is an identity (and, in particular, a mapping), i.e. f acts as the identity on g's left values (outputs).

Thus, if a mapping g is a fixed point of repeat(2+n), take f = repeat(1+n,g) to get f&on;g = g, whence repeat(1+n,g) acts as the identity on (|g:), as well as having the same right and left values as g, with (:g|) subsuming (|g:). Any fixed point, r, of repeat(2), i.e. relation r for which repeat(2,r) = r&on;r = r = repeat(1,r), is described as transitive; if it happens also to be a mapping, it is described as a projection. The above tells us (via n = 0, f = g) that every projection acts as the identity on its outputs. Equally, any mapping which acts as the identity on its outputs is a projection.

That's what happens when a mapping is a fixed point of one of repeat's outputs (other than repeat(1), of which everything is a fixed point). How, then, if two outputs of repeat agree with one another on some relation ? We've already dealt with the case where one of the repeat outputs is repeat(1); and clearly the question is of no interest unless the two repeat outputs are distinct, so we're concerned with repeat(2+n,f) = repeat(3+n+m,f) for some relation f and naturals n, m.

By replacing 2+n copies of f with 2+n+m of them at each stage, we can show that repeat((1+p).(1+m)+2+n,f) = repeat(2+n,f) for every natural p, including p = 1+n, yielding repeat(2+m, repeat(2+n,f)) = repeat((2+n).(2+m),f) = repeat(2+n,f), so repeat(2+n,f) is a fixed point of repeat(2+m). Thus, if distinct outputs of repeat map a relation to the same value, that value is a fixed point of an output, other than repeat(1), of repeat.

Let g = repeat(2+n,f) and h = repeat(1+m,f), giving h&on;g = g; so g is a fixed point of repeat(2+m) while repeat(2+n) maps both h&on;f and f to g – so we can expect similarities between f and h&on;f – and every output of transpose(repeat,g) has the same left and right values as g. If g is a mapping, (:h:g) is an identity and (:g|) subsumes (|g:).

...

## Rational Contexts

While, in general, repeat's outputs coincide and do strange things together, there is a broad class of collections of relations on which they are well behaved. Specifically, I'll describe a collection, C, of relations as a rational context precisely if:

• its members commute under composition; i.e. f, g in C implies f&on;g = g&on;f.
• it's closed under composition; i.e. f, g in C implies f&on;g in C; consequently, of course, each output s of repeat is (C:s|C).
• every output of repeat is (not only a mapping but also) monic on C, i.e. (C:s|C) is one-to-one, whence ({monic}: (:s:C) ←s |repeat).
• the mapping ({monic}: (:s:C) ←s |repeat) is monic, i.e. if naturals n, m have (: repeat(1+n) :C) = (: repeat(1+m) :C), then n = m.

For example, the translations of a real vector space will always form a rational context; and (|repeat:) is a rational context. I'll describe a rational context, C, as full precisely if, furthermore, each output s of repeat is (C|s:C), which says (effectively, given that (:s:C) is monic) that we can subdivide any member of C into arbitrarily many equal parts. This isn't needed when it comes to characterizing the rationals, but does make for more interesting rational contexts.

Now, the reverse of any monic mapping is a monic mapping; and any composite of monic mappings is another such. The outputs of (: (C:s:C) ←s |repeat) are all monic mappings, hence every composite of such outputs and reverses of such outputs is a monic mapping (C: :C); if C happens to be full, each (C:s:C) is in fact (C|s|C) so such composites will all be (C| |C) as well. The composites in question will provide C's model of the positive rationals. The important thing about rational contexts is that they all induce the same positive rationals as one another.

Note that the last two constraints defining a rational context and the consequence of the previous can all be expressed by:

• ({monics}: (C:s|C) ←s |repeat) is monic

and replacing (C:s|C) with (C|s|C) in this is equivalent to specifying that C is also full. The first two constraints may be expressed as:

• f, g in C implies f&on;g = g&on;f is in C.

If a rational context, C, isn't full, we do need to be confident that, for any outputs s, r of repeat, there are at least some members f, g of C for which s(f) = r(g), otherwise I'll get into trouble when composing one with the reverse of the other; however, any h in C will yield f = r(h), g = s(h) for which this holds true, since repeat's outputs commute with one another. It thus suffices that C is non-empty …

Theorem: for every rational context C and natural n, there is some f in C which is not a fixed point of repeat(2+n). Proof: first note that 2+n and 1 are distinct; whence repeat(2+n) and repeat(1) are distinct (since their images of successor map 0 to 2+n and 1 respectively). We have (: (:s:C) ←s |repeat) monic, whence (:repeat(2+n):C) and (:repeat(1):C) are distinct; let f in C distinguish them, i.e. have repeat(2+n,f) different from repeat(1,f) = f; then f is not a fixed point of repeat(2+n). Q.E.D.

Thus not only is no rational context empty, but every rational context contains at least some member which is not an equivalence (as every equivalence is transitive and reflexive, hence a fixed point of repeat(2), hence of every output of repeat). Note, however, that there need not be any members which have infinite period; it suffices to have a generator of period p for each p in some infinite subset of {naturals} (e.g. {primes} or {naturals} itself) and every element a composite of some list of such generators, all commuting with one another; e.g. with Q = {mapping ({naturals}:p|{naturals}): ({1+i: natural i}:p|) is finite}, P = (Q: p←q; for each natural i, p(i)+n.(1+i) = q(i)+m.(1+i) for some naturals n, m :Q), consider C = {P&on;(Q: (: p(i)+q(i) ←i :) ←q :Q)&on;P: p in Q}, which has a generator with each positive natural period (specifically: that inferred from the p which maps n to 1, and all other naturals to 0, has period 1+n, for each natural n) but every member has finite period (specifically: the member of C obtained from a given p is at most the lowest common multiple of the members of ({1+i: natural i}:p|), which is finite).

## Rationals

Introduce

• {positive rationals} = {reverse(repeat(1+q))&on;repeat(1+p): natural p, q}

the mapping ({positive rationals}: Q :{relations}) = (: reverse(repeat(1+q))&on;repeat(1+p) ← r; r&on;repeat(1+q) subsumes repeat(1+p) :) whose restriction to the positive rationals is their identity, since outputs of repeat commute with one another and reverse(repeat(1+q))&on;repeat(1+q)&on;repeat(1+p) subsumes repeat(1+p) for all natural q, p.

Valid CSS ? Valid HTML ? Written by Eddy.