Daddy, where do numbers come from?
If you've got functions and subsets, you've got numbers! And proof by induction, too.
─Me
More precisely, if you have an injective (one-to-one) function f that is not surjective (onto) and is defined on a set S, then there exists at least one infinite subset of S that is a number-like structure, complete with the principle of mathematical induction, with f played the part of a so-called successor function.
What does a "number-like structure" look like? Graphically, something like this:
This is a chain of objects called numbers beginning with a number designated as the “1”. The 1 and each larger dot here represents a number. The three smaller dots indicates that the chain keeps going on to the right forever. In this diagram, an arrow connects every number with the next number in the chain.
This chain of arrows has no branching or merging.
No Branching No merging
No arrows point to the number 1.
All numbers must be on the chain starting at 1. There can be no individual numbers or “side structures” apart from that chain─e.g. no finite loops, no other infinite chains (as pictured) off to the side, etc.
In this diagram, the shorter side-chain above is not connected to the longer chain below.
How do we express these ideas in the language of DC Proof? We begin with a set that we will call n. In DC Proof, we write:
1 Set(n)
We also have 1 being an element of n:
2 1 e n
The arrows in the above diagrams represent a relation between the elements of the set n. When we say, as above, that this line of arrows never branches, we mean that this relation, which we will call the next, is a function mapping n to itself. In DC Proof, we write:
3 ALL(a):[a e n => next(a) e n]
Read: For all a, a is an element of n implies that next(a) is an element of n. Alternatively, we can say simply that next is function mapping n to n.
Likewise, when we say that this line of arrows never merges, we mean that if a natural number has a pre-image under next, then that pre-image is unique. A natural number can have no more than one pre-image (or predecessor) under next. The technical term for this is that the function next is one-to-one or injective. In DC Proof, we write:
4 ALL(a):ALL(b):[a e n & b e n => [next(a)=next(b) => a=b]]
To formally specify that no arrows point to the number 1, we write:
5 ALL(a):[a e n => ~next(a)=1]
Read: For all a, a is a natural number implies that next(a) is not equal 1.
To prohibit the unwanted “side-structures” mentioned above is a little trickier. But consider any subset p of the natural numbers. Suppose 1 is an element of p. Suppose further that if x is an element of p, then so is next(x). Then all natural numbers must be in p. We write:
6 ALL(a):[Set(a) & ALL(b):[b e a => b e n] & 1 e a & ALL(d):[d e a => next(d) e a]
=> ALL(c):[c e n => c e a]]]
Lines 1 through 6 (above) comprise the axioms for the natural numbers, roughly equivalent to the so-called Peano Axioms.
Just how “natural” are these axioms? So much so that the structure we refer to as the natural numbers N is embedded in every set S that has defined on it a injective (one-to-one) function f, and with at least one element (the “1”) that has no pre-image in S under f. The above “axioms” can actually be shown to hold on such a set given informally by the usual set-builder notation:
N = {1, f(1), f( f(1) ), …}
See formal proof (112 lines in the DC Proof format) at ProofByInduction.html
