The natural numbers are a mathematical tool describing counting in its most
basic form: I here develop a particular description (from naïve set
þeory) of one realisation of that tool. The fundamental idea is that
there's a succession of numbers, each having a successor (one bigger
than it)
distinct from it and from all its predecessors. Modern mathematics credits
this formalisation of counting to Guiseppe Peano.
There are two common definitions of the natural numbers: the difference
comes down to which number is taken as the beginning, 1 or 0. In either case,
we can construct the integers (positive, zero and negative) from the natural
numbers: relative to these we describe our two candidates for the name natural
numbers
as the positive integers and the non-negative integers, respectively.
Both of these sets shall be subjects of discussion and one of them has an uglier
name than the other. If I had no other way to chose between the two, I'd let
that be reason enough to refer to the non-negative integers as the natural
numbers. As it happens, I prefer to count from 0, following Conway.
Informally, then, the natural numbers form the set N = {0, 1, 2, …} of
values obtained by applying a successor operation (N|1+:N) arbitrarily often to
0 and giving conventional names to the results thereof. For the moment, read
1+
as a single symbol, or even as successor
, and do not interpret it in
terms of addition. If we are to be truly formal, though, we are going to have
to say what 0, 1, 2 and so on are: we actually do this inductively, but in
effect define each natural number, n, to be the set of natural numbers preceding
it, {0, …, n-1}. 0 is then just the empty set, 1 is the set {0}. Notably, n
has n elements and the union of n with {n} is 1+n. It is from this last that we
formalise the matter.
The advantage of using conventional names for the numbers may better be appreciated, I feel, when you consider that
In general, writing each natural number takes twice as many of each
kind of brace as its predecessor: the number of commas increases as double and
add one
at each step after 1, so it's one less than half the number of opening
braces. Writing out n requires 2n (the nth power of 2, power(n,2))
of each kind of brace and (for n>0) power(n-1, 2) - 1 (one less than half as
many) commas.
We define the natural numbers to be the trajectory generated by the successor functor, in the category Set, when applied arbitrarily often to the empty set. The successor functor, 1+, transforms a function (A|f:B) to (1+A|1+f:1+B) with 1+A defined to be the union of A with {A} (which necessarily differs from A since Set forbids A to be an element of A), 1+B likewise defined as B's union with {B} and 1+f defined to agree with f on A and map A to B, so (1+f)(A) = B while, for any a in A, (1+f)(a)=f(a). Our interest is here focussed on its former action, on sets.
The definition gives us 0={}, 1={0}={{}}, 2={0,1}, …, n={0,…,n-1}, …
as the natural numbers. I shall regularly employ this representation, notably
saying for i in n
by preference to for i satisfying 0 <= i < n
or for
i=0, …, n-1
: those who start their natural numbers from 1 would usually give
these as for i = 1 to n
.
We describe a natural number as positive iff it is the successor of some
natural number: equivalently, iff it is non-empty or iff it is not 0. It is
worth note that, in the category Set, the empty set (or, rather, its identity)
is initial and 1 is terminal. Notice that we obtain 1={0} isomorphic to any
other set with precisely one element, whence any set A's successor, {A}+A, is
isomorphic to 1+A, whence our use of 1+
as the functor's name is consistent
with the meaning of + in the context of direct sums. Likewise, ({A}| A->B:
{B}) is isomorphic to the identity function on 1, making 1+f above consistent
with its meaning in terms of direct sums.
Given the natural numbers, we define a very powerful mathematical tool: Induction. This says that if we
then we have proved it true for every natural number greater than or equal to the one given natural number. It should not be hard to see that almost any proof relating to the natural numbers will require induction.
It takes some effort to prove that, for any pair of natural numbers: there is a unique member of the natural numbers isomorphic to their direct sum, thus defining an addition on the natural numbers; and there is a unique member of the natural numbers isomorphic to their Cartesian product, thus defining a multiplication on them. Further effort reveals that both are associative and Abelian, with multiplication distributing over addition, which is cancellable. We can also show that multiplication by positives is cancellable.
Once we have defined addition on the natural numbers and shown it to be associative, Abelian and cancellable, we can use a standard difference construction to complete the additive structure, yielding the integers. Equally, applying the same construction to the restriction of multiplication to the positive integers, we can obtain the positive rationals, complete with their additive structure, which is cancellable and associative still, so we can apply the (additive) difference construction here to obtain the rationals. We have, then:
It is worthy of note that there are no more
rationals, or integers, than
there are natural numbers, although every natural number is an integer, every
integer is a rational and there are plenty of non-integer rationals and negative
integers, so there would certainly seem to be more rationals than
integers than natural numbers. To see that there are no more integers than natural
numbers, consider the function from natural numbers to integers which maps any odd
natural number, 2i+1 (for natural i), to -(1+i) and every even natural number, 2i
(for natural i) to i. For every integer there is some natural number which this
function maps to the given integer: thus there are no more integers than there
are natural numbers.
The case that there are no more
rationals than naturals is addressed in
much the same way, only this time (perhaps perversely) we shall visit each
non-zero rational a large number of times (we visit zero just once): we
construct a function from the natural numbers to the rationals for which each
rational appears as the image of at least one natural number. This
then shows that there are no more rationals than naturals.
The idea is to draw a zig-zag path, in one quadrant of a lattice, which visits every lattice point in the quadrant as it steadily works its way out: the lattice point (n,m) represents the rational n/m, and we proceed from (1,1) to (2,1), (1,2), (3,1), (2,2), (1,3), (4,1), (3,2), (2,3), (1,4), (5,1) and so on. We begin by visiting 0 and, as when we traversed the integers, visit each value's negative just before visiting the value itself. This will be clearest, however, if I actually define a function, f, from the positive integers to the positive rationals and extend this to a function from the integers to the rationals using f(0)=0 and f(-x)=-f(x). Composing this extended f with the earlier function from the naturals yielding all the integers, we obtain the required function from the natural numbers to the rationals. As long as my basic f delivers every positive rational, its extension to the integers delivers every rational: we are composing it with a function which yields every integer, so the composite, from naturals to rationals, yields every rational, as required.
The required function from the positive integers to the positive rationals obliges us to find, for each positive integer n, two natural numbers, p and q, satisfying: 2.n=2.p+ (1+p+q).(p+q). We then set f(n)=(1+p)/(1+q).
To see that we can solve for p and q, and that the solution is unique,
consider the triangle
function (natural| m-> (1+m).m/2: natural). That any
natural m has (1+m).m/2 well-defined follows because one of m and (1+m) is even
[Proof: by induction - true for m = 0; whenever true for m, we have either m
even, whence 2+m even, or 1+m even; whence one of (1+m) and (2+m) is even]. Let
k = (|i->(1+i).i/2: 1+n) be the set of naturals on which the triangle
function does not exceed n. Now, triangle(1)=1 is in 1+n (as n is positive), so
k is not empty; and the triangle function is monotonically increasing, so any m
in k is also a subset of k; the union of k's elements is the largest natural
number m for which n is at least (1+m).m/2, and k is just 1+m. This implies
n< (2+m).(1+m)/2= (1+m) + (1+m).m/2, so we have n=p+ (1+m).m/2 for some p in
(1+m), with p and m uniquely determined by these relationships. Now p in 1+m =
{0, …, m} implies some q in 1+m for which p+q=m. Substituting for m we now
obtain what we asked for. Uniqueness of (p,q) follows from that of (p,m).
To confirm that every positive rational is visited, observe that every positive rational is of form (1+p)/(1+q) for some natural numbers p and q. The only pair of natural numbers, (p,q), not produced above is p=0=q, corresponding to n=0, which we skip (as we restrict to positive n): but this is just the rational 1/1, which does arise since p=1=q arises, for n=4, and yields f(4)=2/2=1. Indeed, in general, p=q yields n=2.p.(1+p) with f(n)= (1+p)/(1+p) =1.
The Successor Functor, 1+, introduced above is worthy of further study. Although we only needed its action on sets, rather than on functions, it is in fact defined, as above, by its action on functions as 1+(A|f:B)= ({A}+A| (:A->B:)+f: {B}+B), using the notation of disjoint sums with (:A->B:) denoting the only possible function ({A}|:{B}) - a set, such as {B}, with only one element is terminal in Set.
There is a natural transformation between the identity functor on Set and 1+, transforming any (A|f:B) to (A|f:1+B), the same function interpreted in terms of a set of which B appears as a subset. This maps any identity function e in Set to the corresponding embedding of (|e) in 1+(e|), so I'll call it the successor-embedding transformation. Furthermore, this transformation is natural not only between the identity and successor but also between any functor obtained by repeating successor arbitrarily often and that obtained by repeating it just once more. Equally, repeated self-composition of the successor-embedding transformation yields transformations between the identity and each result of repeated self-composition of the successor functor.
Starting with the empty identity and applying the successor functor and the successor-embedding transformation, we obtain the identities on each of the natural numbers and the natural embeddings of each in any of its successors. These form a subcategory of Set (or, indeed, of the subset embedding category of the set of natural numbers).
Maintained by Eddy.