Useful foundations provide, in one guise or another, for an infinite collection, known as the natural numbers. Peano characterised it by: there is a first natural number; every natural number has a successor, which is also a natural number; distinct natural numbers have distinct successors and no natural number's successor is the first natural number. One can equally specify: a natural number is a finite collection, n, of natural numbers, each of which n subsumes.
Either way, one uses inductive
reasoning to prove things about the
naturals; for Peano, one must show something true for the first and for the
successor of any natural of which it's true, if one is to show it true for every
natural; the second specification uses strong induction
, which infers
every natural is blah
from a natural is blah if all its
members are blah
for any property (type) blah.
One valid representation of Peano uses empty = {} as the first
natural and n&unite;{n} ←n as the successor
operation; this yields a
representation (due, as I understand it, to von Neumann) in which each natural
is the collection of earlier
naturals. It can be shown that the strong induction
specification of the naturals leads to exactly this representation: indeed, that
each natural is either empty or the successor of one of its members.
A list is a mapping f for which (f:i←i:), its collection of inputs, is a natural number; the members of (:x←x:f) are known as the list's items or entries; note that each may appear repeatedly in the list as f(i) and f(j) may be equal even when i and j aren't. A list (:f|successor(n)) is written [f(0),...,f(n)]; the empty list (:f:empty) is written [] = empty = {}.
Using the naturals, I can define a mapping, repeat = (: ({relations}: repeat(n) |{relations}) ←n |{naturals}) for which repeat(empty) maps every relation to the universal identity while repeat(successor(n)) is the mapping r&on;repeat(n, r) ←r. Consequently, r&on;repeat(empty, r) = r&on;(:i←i:) = r, so repeat({empty}) is the identity on relations - repeating something once is synonymous with just doing it !
One can also define the transitive closure
of a relation r as unite(:
repeat(successor(n), r) ←n :{naturals}) and its transitive core
as
intersect(: repeat(successor(n), r) ←n :{naturals}), each of which is
necessarily transitive; the former subsumes r, which subsumes the latter. Note
that repeat(empty, r) is carefully left out in both cases by using
repeat(successor(n), r) rather than repeat(n, r).
Composing a monic with a monic always yields a monic; likewise, composing
mappings yields a mapping. [Proof: suppose f and g are mappings; if f&on;g
relates both u and v to some z, then f relates u to some x which g relates to z
and f relates v to some y which g relates to z; but g is a mapping, so g
relates x and y to z
implies x = y
; and f is a mapping, so f
relates u and v to x = y
implies u = v
; thus if f and g are mappings,
then f&on;g is also a mapping. The proof for monic is analogous; or simply note
that the reverse of a monic is a mapping, so if f and g are monic then
reverse(g)&on;reverse(f) is a mapping; but it is equal to reverse(f&on;g) and
the reverse of a mapping is a monic, so f&on;g must be monic.]
Consequently, an arbitrary repeat of a monic is monic and an arbitrary repeat of a mapping is a mapping. [Proof: repeat({}, r) = (:i←i:) is a collection, hence monic and a mapping; given a natural n for which repeat(n,r) is monic or a mapping whenever r is, we have repeat(successor(n),r) = r&on;repeat(n,r) as a composite of mappings or monics, as appropriate, hence likewise monic or a mapping whenever r is; QED.]
One may immediately take an interest, for any naturals n and m, in repeat(n)&on;repeat(m) = (: repeat(n, repeat(m,r)) ←r :), and (: repeat(n,r)&on;repeat(m,r) ←r :). The first of these will yield a multiplication on naturals; the second an addition.
Now, clearly, repeat(n,r)&on;repeat(m,r) is just r repeated some number of times, so we expect it to be repeat(n+m,r) in some sense: this sense must now be dug out. Since n+m should clearly be repeat(n, successor, m), to make sense of our intuitive notions of repetition and succession, it makes sense to look at repeat(repeat(n, successor, m), r) and compare it with repeat(n,r)&on;repeat(m,r).
When m is empty, we know repeat(repeat(n, successor, m), r) is just repeat(n,r); and that repeat(m,r) is the universal identity, which subsumes repeat(n,r)'s collection of right values, so composing the two gives repeat(n,r)&on;repeat(empty,r) = repeat(n,r) = repeat(repeat(n, successor, empty), r). Otherwise, m is successor(i) for some natural i and we can induce that repeat(repeat(n, successor, i), r) = repeat(n,r)&on;repeat(i,r);
First observe that n = repeat(n, successor, empty): when n is empty, we have repeat(n, successor) = (:i←i:), so repeat(empty, successor) does map empty to empty; otherwise, n is successor(i) and we can induce i = repeat(i, successor, empty), whence repeat(n, successor, empty) = (successor&on;repeat(i, successor))(empty) = successor(repeat(i, successor, empty)) = successor(i) = n; QED. Thus repeated use of successor has the meaning intuition demands.
Repeat lets us define an addition, n+m = repeat(n, successor, m) for which it follows immediately that successor(n)+m = successor(n+m) = n+successor(m) and m = empty+m; whence successor(m) = {empty}+m so that, once I write {empty} as 1, I'll be able to abbreviate successor(m) to 1+m. Meanwhile, we have n+empty = repeat(n, successor, empty) = n, from above; so n+empty = n = empty+n.
Furthermore, if n+m = empty we have empty in (| repeat(n, successor) :) but
not in (|successor:), which subsumes (| repeat(n, successor) :) unless n is
empty. This obliges n to to be empty whence n+m = m, so empty = m also. Thus
n+m = empty, n, m natural
implies n = empty = m
.
I need to show that n+m = m+n, again by induction: n+m = empty implies n = empty = m whence m+n = n+m. So consider a natural, N, for which n+m = N implies m+n = n+m. Now consider naturals n, m for which n+m = successor(N); either n is empty - for which case we already know empty+m = m+empty - or n=successor(i) for some natural i. In the latter case, we have successor(N) = n+m = successor(i)+m = successor(i+m); successor is monic on naturals so N = i+m, whence m+i = i+m, so n+m = successor(m+i) = m+successor(i) = m+n. Thus, for any natural N, n+m = N implies n+m = m+n; i.e. for any naturals n, m, n+m = m+n.
Since (: repeat(n, successor) :{naturals}) = repeat(n, (:successor:{naturals})) is monic, for each n, our addition is cancellable. [Directly left-cancellable, a+b = a+c implies b=c, and consequently right-cancellable because it is symmetric, a+b = b+a.]
Define multiplication by n×m = repeat(n, repeat(m, successor), empty).
When either n or m is empty, so is n×m. When one of them is {empty}, we
obtain n×{empty} = repeat(n, successor, empty) = n or {empty}×m =
repeat(m, successor, empty) = m: {empty} serves as a multiplicative identity.
[The use of repeat(n) applied to m+...
(which is what repeat(m,
successor) means when m is a natural) enables this definition of n×... to
be extended to any context which supports a suitable addition, albeit unless the
context provides an additive identity one is constrained to positive natural
scalings: successor(n).m = repeat(n, add(m), m).]
I'll need to examine (n+m)×p and n×(p+q), among other things. repeat(n×m, successor, empty) = n×m + empty
Give empty the names 0 and zero; give {empty} the names 1 and one; this enables us to write successor much more tersely as 1+n ←n. Name their successive successors as:
and so on as far as you care to go; but only use your choice of
natural language names for the naturals beyond ten - don't be fixing 10
as a name for ten as several-digit denotations require one to chose a base;
telling me your number base is 10 is fatuous, saying it is ten is more
useful ;^)
One may interpret a list of naturals (or potentially of other kinds of
elements) as a polynomial
via a function, poly, for which poly([]) is the
mapping zero ←x while poly(:f|1+n) is the mapping x×poly((:f:n), x) +
f(n) ←x. [Note that this makes f(n) the coefficient of the order zero term
and f(0) the coefficient of the order n term; the list, written in the order
[f(0), ..., f(n)], will be the list of values of digits in a sequence of digits
making up a denotation for a number; preserving the order of digits, when
transcribing them into the list, means making the most significant digit f(0),
the least f(n). Elsewhere, where I deal with polynomials, I'll use the more
intuitive representation in which f(i) is the coefficient of the order i term,
for each i. However, the present section implements orthodoxy.]
In so far as context provides some single-character denotations, called
digits
, for some naturals and chooses to nominate a natural, b, as
number base
it is conventional to read a non-empty sequence of digits as
a natural by, first, interpreting the (textual) sequence of characters as a list
of characters (numbered from the left: 137 is read as [1, 3, 7], which maps 0 to
1, 1 to 3 and 2 to 7), then interpreting each character - as the natural it
denotes - to obtain a list, f, of naturals; the whole sequence of characters
then denotes poly(f,b). Thus, in base two, 7 = 31 = 111 = 103.
It is, of course, conventional to only use members of b as digits: and (though I have yet to show it) lists of these suffice to represent all naturals provided b is at least two. However, the definition has no need to insist on only giving meaning to canonical representations; and the present definition is compatible with using, e.g., signed trits - base 3 with digits 0, 1 and T, with T standing for -1, once we get to contexts which entertain such a thing as -1; in such terms, seven = nine-three+one = 1T1 and I was born in 10T01T01 C.E.
Written by Eddy.