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
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:
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
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.
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:).
...
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:
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:
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 Cimplies
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).
Introduce
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.