The Natural Numbers

The natural numbers provide the fundamental model of counting in mathematics. This was formalised by Peano in terms of a first natural number and a successor operation on natural numbers, which maps each natural number to another without ever repeating itself (i.e. it's monic) or producing the first. From this abstract specification alone one may build the entirety of whole-number arithmetic. I find it, however, practical to pick a specific realisation of this abstraction (due, if memory serves me right, to John von Neumann), in which each natural number is simply the set of all earlier natural numbers; thus 0 = {}, 1 = {0}, 2 = {0, 1}, 3 = {0, 1, 2}, 4 = {0, 1, 2, 3} and so on.

One may realise the naturals in various other ways, such as the mappings I have repeat produce as its outputs; and one may chose to start at 1 instead of 0; in each case, Peano's requirements for a first natural and a successor mechanism are met and one can build the usual machinery of arithmetic. I have chosen one, that suits my needs well, and I use it systematically; but bear in mind that other authors chose otherwise.

Definition

This is a strongly inductive definition: it asserts a property of a collection in terms of all its members also having that property. Accordingly, when proving that all naturals have some property, it suffices that a natural shall necessarily have that property as long as all of its members do: this is the strongly inductive mode of reasoning.

With Peano's formulation of the naturals, the corresponding mode of (weak) induction requires one to prove the first natural has the property and that, whenever a natural possesses the property, so does its successor. Since Peano gives you no way to get at a natural other than from the first by repeated application of successor, there is then no way to obtain a natural which lacks the property.

Likewise, as the strongly inductive definition gives you no way to know that something is a natural save by (inter alia) each of its members being natural, so also the matching mode of proof suffices, as a property that a natural necessarily has if all its members have it will necessarily be possesed by anything you can show to be a natural. The two modes of reasoning are in fact equivalent (for all the strong vs weak language describing them); I'll come to that below.

One way to think about the strongly inductive mode of reasoning is to observe that, if any natural will have the property if all of its members do: then, for a natural to lack the property, it must have at least one member that also lacks the property – so where do you get a first one lacking it ?

The attentive reader will notice that the definition doesn't give you any examples; fortunately, it doesn't need to, as we'll now see.

A few examples

The empty collection is finite and we can assert anything we like about each of its members: it has no member which is not a natural number, so it is a finite collection of naturals (just as it is also a finite collection of invisible pink unicorns); nor has it any member that it does not subsume, so it does indeed subsume all its members. Thus empty is a natural; when considered as a natural, it is denoted 0 and named zero.

A singleton collection – that is, one with exactly one member – is also finite. One such is {empty}, whose sole member is the empty collection: we can equally write this {0}. As empty is a natural, every member of {0} is a natural; and, as every collection subsumes empty, {0} subsumes its sole member. Consequently {0} = {empty} is a natural; when considered as a natural, it is denoted 1 and named one.

When a collection n is finite, so also is its successor collection, n&unite;{n}. When n is a natural, its successor's members are precisely the members of n – each of which is natural and subsumed by n, hence also by n&unite;{n} – and n itself, which is given to be natural, and which n&unite;{n} subsumes by virtue of n being one of the two collections united to make it. Consequently, the successor of any natural is necessarily also natural. (We could, indeed, have used this to infer that {0} is natural from the fact that 0 is natural.) By repeated application of this rule we can obtain the usual counting numbers, the first few of which are named and denoted as:

(Of course, these are all collections, so the order in which the members appear between {…} is immaterial: the last is equally 9 = {1, 2, 3, 5, 7, 4, 6, 8, 0} = {0, 1, 2, 3, 4, 5, 6, 7, 8} and similar for any other ordering.) I shall use the name ten for nine's successor; I specify elsewhere a way to denote naturals beyond nine.

We now have a first natural and a successor operation; below, I'll show these have the properties Peano requires; and, later, that we have nothing else.

Given a natural n and any i in n, we know n subsumes i and i is in n, hence n subsumes i&unite;{i}, i's successor. So every natural subsumes not only each of its members but, in fact, the successor of each of its members. If n is empty, unite(: successor :n) is unite(empty) = empty (since unite(f) relates x to y precisely if some left value of f relates x to y; and empty has no left values, so no left value of it relates x to y for any x, y). Otherwise, unite(: successor :n) subsumes n, as each i in n is in successor(i) hence in the union; but n subsumes each such successor(i), hence also the union, so n = unite(: successor :n). Thus every natural is the union of the successors of its members.

Now, for any natural n, unite(n) is a union of naturals, all of which are subsumed by n, which is finite; consequently finite n subsumes unite(n), which is thus also finite; and each of its members is in a member of n, hence in n, hence is a natural and, as one of the things united to make unite(n), subsumed by unite(n). Thus unite(n) is natural, for any natural n. For n = empty, unite(empty) = empty; for all the other examples above, you'll see that unite(n) is simply the preceding natural, so successor(unite(n)) is n; but, before I can show this is generally true, we'll need a few more details.

Endlessness

Of course, successor will only continue producing new naturals as long as no natural is a member of itself – which may appear obvious given the pattern above, but we do need to prove it. So consider any natural n, each member of which is not a member of itself; i in n implies i not in i; i in n and i not in i implies i is not n (the member i being witness to this, as it is in n but not in i); so i in n implies i is not n; so n is not a member of itself. So is not a member of itself is a property which a natural necessarily possesses provided all of its members do; which is just the requirement for strong induction given above, so I infer that every natural does, indeed, have this property: no natural is a member of itself. Consequently, in particular, every natural is distinct from its successor.

Consider two naturals n, m with equal successor, i.e. n&unite;{n} = m&unite;{m}. As n is in m&unite;{m}, either n is in m or n is m; either way, m subsumes n; by symmetry, m subsumes n; hence n = m. Thus naturals with equal successor are equal: i.e. (: successor :{naturals}) is monic. That it is a mapping follows trivially from its definition. Every collection's successor has that collection as a member, hence isn't empty, so empty is not an output of successor. Thus empty and successor = (: n&unite;{n} ←n :) satisfy, respectively, Peano's requirements for a first natural and a successor operation; repeatedly applying successor, starting with empty, yields an endless supply of distinct naturals.

Once we have the ordering of naturals properly pinned down, that'll let us prove that {naturals} is infinite (as one might intuit from that endlessness); which (bearing in mind that it is a collection of naturals, and subsumes each of its members) ensures that it isn't itself a natural – which is fortunate, as it would otherwise have been a member of itself, which we just showed a natural can't be !

If a collection, N, of naturals is closed under successor, i.e. has (N: successor |N), then its union subsumes it, since each m in N is in its own successor, which is in N, so is one of the naturals united, hence m is also in unite(N). If a collection of naturals subsumes each of its members, then it also subsumes its own union. So a collection of naturals, that both is closed under successor and subsumes each of its members, is necessarily equal to its own union. (This will make it a limit ordinal and hence either empty or infinite.)

Ordering

For naturals n, m, let n < m mean n is in m and n ≥ m mean m is in n's successor (and, for the moment, ignore any other meanings of < and ≥ with which you are familiar). I shall now prove that the union of these two relations is the all-relation on {naturals} – i.e. that, for any naturals n, m, at least one of n<m and n≥m holds true. From this, diverse useful results shall follow; in particular, that we can replace the at least with precisely.

Define d = (: {natural m: m ≥ n or m < n} ←n :{naturals}) and consider a natural n for which, for each i in n, d(i) = {naturals}, i.e. every natural is either ≥ i or < i; I shall show that this implies d(n) is also {naturals}.

In this context, consider a natural m, each member of which is in d(n); I shall show that m is also in d(n), which is just what I need, to show that d(n) is {naturals}. Now:

Each i in n has d(i) = {naturals}, so m in d(i): if m < i for any i in n then, as n subsumes this i, m < n; otherwise m ≥ i for each i in n, so m's successor subsumes n.
Each member of m is in d(n); if any is ≥ n, then n is in its successor, which m subsumes, so n is in m, hence in m's successor, so m ≥ n; otherwise, each i in m is < n, so n subsumes m.
When m's successor subsumes n subsumes m: if m subsumes n then m = n is in m's successor so m ≥ n; otherwise, n must have, as a member, the one member of m's successor that isn't in m, namely m, so m < n.

At least one of these cases must arise; and, in each case, either m < n or m ≥ n; thus m is in d(n). This being true for any natural m provided only that each of its members is in d(n), we can induce that every natural is in d(n), so d(n) = {naturals}.

Thus any natural n has d(n) = {naturals} provided each i in n has d(i) = {naturals}; which is just what we need to induce that every natural has d(n) = {naturals}. From the definition of d, we now infer that: for any naturals n, m, either m < n or m ≥ n; i.e. either m is in n or n is in m's successor. QED.

When n is in m's successor, either n is m (which m subsumes) or n is in m, which is natural, so subsumes each of its members; either way, m subsumes n. Conversely, if m subsumes n, given that we know m is not a member of itself, we know that m is not in n; hence, by the above, n is in m's successor. Thus, for naturals n, m: n is in m's successor ⇔ m ≥ n ⇔ m subsumes n (the left ⇔ by definition, the right one being what I've just shown). Although the proof depended on defining ≥ in terms of membership of a successor, it is more useful, hereafter, to understand ≥ as a synonym for subsumes. In particular, the result above now becomes: for any naturals n, m, either n is in m or n subsumes m.

Now, given naturals n, m, if m is in n then n subsumes m's successor and is not a member of itself, so also not a member of m's successor; thus only one of m < n and m ≥ n can hold true; since at least one does hold true, exactly one of these conditions applies, for any given pair of naturals; so < and ≥ are complementary, in the usual sense for comparisons denoted using these symbols. Furthermore, when n is in m's successor, m&unite;{m}, it either is m or is in m; and, when it is m, it isn't in m (since m is natural, so not a member of itself). We thus have, for any naturals n, m, three possibilities, exactly one of which holds true:

Thus membership constitutes a full ordering on the naturals. I'll write n < m and m > n as synonyms for n in m; with n ≥ m and m ≤ n as synonyms for n subsumes m (i.e. m is in n's successor). It is usual to read < as is less than, > as is greater than, ≥ as is greater than or equal to and ≤ as is less than or equal to; given the results just proved, the meanings of the comparisons are indeed compatible with these readings (e.g. n ≥ m ⇔ n > m or n = m). In particular, when discussing naturals, I use terms of natural language derived from less, greater and their synonyms (and those obtained by treating lower as a synonym for less, higher as a synonym for greater) in ways that presume these readings of these relations.

With ≥ meaning ({naturals}: subsume :{naturals}), we immediately know it's transitive and reflexive; every natural subsumes itself and, whenever a≥b≥c we can infer a≥c; likewise, as its reverse, ≤ is also reflexive and transitive. With < meaning is in and > being its reverse, the definition of naturals ensures that ≥ subsumes >; and the meanings of subsume and membership ensure that a≥b>c imply a>c; taken together, these ensure that a>b>c implies a>c, so > is also transitive; likewise, as its reverse, < is transitive. If we're given a>b≥c then either a>b=c or a>b>c, in each case implying a>c also; so > subsumes >&on;≥ and ≥&on;>.

Infinity

It's now time to consider the (rather intimate) relationships among various properties a collection, N, of naturals may have:

We've already seen that the second implies the first. Suppose we are given the first. For each m in N, unite(N) subsumes N, so m is in unite(N), and unite(N) subsumes m, so unite(N) subsumes successor(m); for each i in unite(N), we have i in some m in N; m duly subsumes successor(i), which is thus in successor(m), which unite(N) subsumes, so successor(i) is in unite(N). So when unite(N) subsumes N, it (but not N) is necessarily closed under successor, (unite(N): successor |unite(N)); in particular, (unite(N): successor |N). This, in turn, means that unite(N) = N implies (N: successor |N), so the following two conditions are equivalent:

Consider a non-empty collection N = unite(N) of naturals. As it's non-empty, it has at least one member, i; this necessarily subsumes empty; both i and empty are naturals, with i ≥ empty, so either i = empty or empty is in i; if i is empty, then empty is in N; otherwise, N subsumes i, of which empty is a member; either way, empty is in N. We know ({naturals}: successor :{naturals}) is monic, hence so is its restriction (N: successor |N), and it doesn't have empty as a left value; so the reverse of (N: successor |N) is a mapping (N| :N) but (though monic) is not (N: |N), so serves as witness that N is infinite. Thus a collection of naturals which meets either of the equivalent conditions above is either empty or infinite. In particular, {naturals} satisfies the given requirements for N, hence is infinite.

Any natural, n, is a collection of naturals that subsumes each of its members, hence n subsumes unite(n). It's finite so either it's empty or: unite(n) doesn't subsume it (else they'd be equal), so there is some natural i in n that is not in unite(n), which is natural and subsumes each member of n, including i; thus unite(n) ≥ i but not i < unite(n); our ordering thus tells us that i = unite(n). So every non-empty natural has its union as a member and is the successor of this member. (It'll make sense to think of m&unite;{m} as 1+m and unite(n) as n−1, but this has to wait until we investigate arithmetic.) Put another way: every natural is either empty (which is its own union and not the successor of anything) or the successor of its union, which is natural.

This means that empty is the only natural that isn't a left value of (: successor :{naturals}) and, whenever we must consider a natural, it suffices to consider just the cases where it is empty and where it is n&unite;{n} for some natural n. This ensures we can freely use the assumptions made by weak induction, as consequences of strong induction; the strongly inductive definition has given us nothing more than Peano will get out of our first natural and successor operation. This also means that (: unite :{naturals}) is a non-monic (since unite(1) = unite(0) = 0) mapping ({naturals}| :{naturals}) so (like the reverse of (: successor :{naturals}), which it subsumes) serves as a witness that {naturals} is infinite.

Once again, let N be a collection of naturals that subsumes each of its members. If it is finite, it's a natural. Otherwise, let m be the successor of one of its members; as m is a successor, it's non-empty, hence the natural of which it is the successor is unite(m). As this is a member of N, N subsumes it and hence also subsumes m. As N is infinite and m is not, N is not m, which it subsumes, so must have some member not in m; let n be any such member. As n and m are natural, with n not in m, we have n ≥ m, i.e. n subsumes m; so either m = n, a member of N, or m is in n, which N subsumes; either way, m is in N. So the successor of any member of N is also in N. Thus an infinite collection N of naturals, that subsumes each of its members, is necessarily closed under successor, (N: successor |N), hence equal to its own union, N = unite(N). Thus, given the above, the following two conditions on a collection N of naturals are equivalent:

Let N be a collection of naturals, closed under successor, with empty in N. If we are given a natural n, each member of which is given to be in N, then either n is empty (hence in N, by hypothesis) or m = unite(n) in n is in N, hence its successor is also in N (closed under successor); and n = m&unite;{m} is that successor. Either way, n is in N; every natural whose members are all in N is also in N, so strong induction says every natural is in N. Thus the only collection of naturals that has empty as a member and is closed under successor (i.e. it satisfies Peano's axioms) is {naturals} itself.

Maximal and minimal members of collections of naturals

We have already applied unite to naturals and seen some of the consequences above; I now turn to the unions and intersections of general collections of naturals. Suppose we have a collection N of naturals.

If N is non-empty, we can take its intersection. (We could indeed take the intersection of empty; but intersect(N) relates x to y precisely if every left value of N does (for a collection, the left and right values are simply members), i.e. unless some member of N doesn't, and empty has no members, so intersect(empty) is the universal all-relation, which falls well outside the present topic: the naturals.) For every i in intersect(N), we know that i is in m for all m in N; in particular, i is natural and every m in N subsumes i, hence intersect(N) subsumes i; so intersect(N) is a collection of naturals and subsumes each of its members. As N is non-empty, it has at least one member, m, which is finite; and each such subsumes intersect(N), hence intersect(N) is also finite. Consequently, intersect(N) is a natural, provided N is non-empty.

For each i in unite(N) there is some natural m in N for which i is in m; hence i is natural and subsumed by m, hence also subsumed by unite(N). So unite(N) is a collection of naturals and subsumes each of its members; if it is finite, it is a natural. In this last case, it subsumes only those naturals that are members of its successor, which is finite; but it subsumes every member of N; hence its successor subsumes N and is a natural, so finite, hence N is finite. Conversely, if N is infinite, unite(N) shall be infinite; which, applying the last section's results, implies that it is in fact {naturals}.

So intersecting a non-empty collection of naturals, or uniting a finite one, shall always yield a natural. Since the union subsumes each member of N, each of which subsumes the intersection, unite(N) and intersect(N) clearly serve as upper and lower bounds on the members of N, in some sense; I shall now show that they are, when possible, maximal and minimal members of N.

Every member of unite(N) is a member of some member of N. If unite(N) is empty, then N has no non-empty members, so N is either empty or {empty}; in the first case, N has no members, so no greatest member; in the second, it has only one member, which is thus fatuously its greatest member, and this member is indeed unite(N). Otherwise, if N is finite, unite(N) is non-empty and natural, so consider its union, m; this is in unite(N) = successor(m). Now, m in unite(N) implies m in some member of N, which is natural so duly subsumes successor(m); so some member of N subsumes unite(N); but unite(N) subsumes every member of N, so unite(N) must in fact be the member of N that has m as a member, hence unite(N) is in N; it subsumes every member of N, so is ≥ every member of N; hence it is a maximal member of N. Thus, whenever N is a non-empty finite collection of naturals, unite(N) is its largest element.

Each member of intersect(N) is a member of every member of N. If intersect(N) is empty then it doesn't have empty = 0 as a member so N must have a member which doesn't have 0 as a member; but nothing is in 0 = empty so every natural either is empty or has it as a member; so the only natural N can contain that doesn't have 0 as a member is empty and we can infer that intersect(N) = empty is a member of N; it is then trivially N's minimal member. Otherwise, for non-empty N, intersect(N) is non-empty and natural, so consider its union, m; this is in intersect(N) = successor(m), hence a member of every member of N, but its successor is not, so there is some natural in N of which successor(m) is not a member; that natural is thus ≤ successor(m) so subsumed by successor(m) = intersect(N); but every member of N subsumes intersect(N), so the given natural must in fact be intersect(N), which is thus a member of N. As m is in every member of N, every member of N subsumes successor(m) = intersect(N), making intersect(N) a minimal element of N.

Summary

albeit the latter's restriction (: :{naturals}) is of most interest here. I have shown: