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:

1Set(n)

We also have 1 being an element of *n*:

21 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:

3ALL(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:

4ALL(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:

5ALL(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:

6ALL(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