The set of natural numbers can show up in the oddest places! Suppose, for example, that f is any function defined on any non-empty set S, subject only to the following conditions:

1. f is injective  (one-to-one)
2. f is not surjective (not onto) *

Since f is not surjective, by definition, there must exist at least one element of S that has no pre-image under fEach such element can be shown to be the starting point (the 0 or 1) of its own distinct number system satisfying Peano’s Axioms for the natural numbers, with f as the required successor function.

See the formal proof (112 lines in the DC Proof format) at Constructing the Natural Numbers

Follow-up (2016-01-16)

Interestingly, if f is just an arbitrary function on S, then, for every element x in S, we can construct a subset of S on which induction will hold, using f as the successor function and x as the “first element” of that subset.

See the formal proof (89 lines in the DC Proof format) at Minimum Requirements for Induction.

Follow-up (2018-11-12):  Accessibility is a Necessary and Sufficient condition for Induction

Suppose X is a set (possibly finite), f is a function mapping X to itself and x_0 is an element of X. Then induction will hold on (X, f, x_0) if and only if there are no isolated subsets P of X that exclude x_0 and  that are not accessible by means of f from outside P.  See formal proof.

From → Uncategorized

1. If you’ll try to make the construction you mention precise, you’ll see that you rely on a pre-existing model of PA+Induction. So, basically your construction is creating an isomorphic copy of a pre-existing model of PA+induction, so it is no surprise that it satisfies PA+induction.

The standard way to obtain models of the natural numbers within set theory is by the notion of inductive set. Then the natural numbers set is the intersection of all inductive sets (suitably defined). However, this is very subtle and the resulting model of PA depends on the ambient model of ZF. The natural numbers are not so simple as your blog entry might lead one to think.

2. Here, I assume only the existence of injective, non-surjective function on a set. How is this relying on a pre-existing model of PA+Induction? The only axioms of set theory that I apply are to construct a subset (line 8) and the definition of set equality (line 130). I do not rely on any kind of ZF-like axiom of infinity.

3. well, it seems that you just rewrite the Peano axioms + induction. But, you don’t give any construction of something and then prove that it satisfies these properties. You just state these axioms (which are basically Peano + induction). You don’t actually construct any model.

• 1. The Peano axioms (including induction) that I list in my proof are not substantively different from the version(s) that are in common use today.

2. In my proof, I construct a subset n of the underlying set s, and show that n satisfies the requirements set out by Peano’s axioms (with successor function f), and that n is uniquely determined by s, f and s1. In this way, I intended to formally justify Peano’s Axioms. They are more than just the result of an exercise in pattern recognition (or “hand-waving” as you put it at MSE). They are a structure that is embedded in every infinite set. (See: http://dcproof.com/NaturalNumsEmbedded.htm )

4. I don’t see any construction of anything in your post. I see just a reformulation of (basically) Peano + Induction. I never claimed that there is anything hand-wavy about the Peano system.

• Again, I construct the subset n on lines 8 and 9 of my proof. (The link again: http://www.dcproof.com/ProofByInduction.html) The remainder of the proof demonstrates that n, together with f and s1 satisfies the requirements of Peano’s Axioms, and that n is uniquely determined by f and s1.

5. It’s a little difficult to discern what is line 8 and 9 exactly. I only see 6 numbered lines that contain something that looks like formal mathematics. The rest of the lines don’t contain any precise definitions or assertions. So, where and what is the definition of n you refer to?

• Informally:

n = {s1, f(s1), f(f(s1)),…}

OR

n is the smallest set satisfying:

1. s1 in n, and
2. if x in s and x in n then f(x) in n

Formally:

Set(n)
& ALL(a):[a in n iff a in s
& ALL(b):[Set(b) & s1 in b
& ALL(c):[c in b & c in s => f(c) in b] => a in b]]

6. ohhhh ok, I think I understand what you mean. Correct me if I’m wrong: you take f:S–>S to be an injective and non-surjective function, and s not in the image of f. Then you consider the smallest set n in S with the properties that s is in n, and if x is in n, then f(x) is in n.

So, this relies on an ambient set theory that at least has an axiom of infinity (you need to know an infinite set exists to have an f as above) and intersection of arbitrary many sets (to define n as the smallest set such that …). Assuming an empty set exists, and unions exist too, this is pretty much sufficient for the construction of inductive sets inside the model of the ambient set theory, and thus there is already in the ambient set theory a model of Peano+Induction. Your construction (if I understand it correctly) is building an isomorphic copy of that model.

• No ZF-like axiom of infinity was used in my proof. Nor is the existence of the empty set assumed.

I have proven that every infinite set has embedded in it a natural-number-like structure (with induction). The only set-theoretic axiom I use is a subset axiom (similar to specification in ZF). In this way, I think I may have formally justified Peano’s axioms. They are rightly called the “natural” numbers.

7. There are some issues here. First, you need to know that an injective non-surjective function f:S–>S exists. How do you do that? Second, to formally define the smallest set such that blah blah holds, you need to take the intersection of all sets satisfying blah blah. So you need arbitrary intersections. Third, to describe the sets that satisfy blah blah you might need some form of an axiom of specification. Next, having the empty set and unions seems a very mild assumption to me. Finally, what do you mean by justifying Peano’s axioms? There are many known models of Peano+Induction (given some form of ambient set theory, just like you are assuming). Moreover, the categoricity of Peano+Induction says indeed that all models of Peano + Induction are essentially the same, thus Peano+Induction defines “the” natural numbers (whatever that means).

• 1. Again, I have proven that for every infinite set, a natural-number-like structure is embedded in it. I don’t assume the existence of any sets in my axioms of set theory, not even the empty set. The existence of every set and every object is provisional in my system. It’s how I avoid problems like Russell’s Paradox — I can’t prove the existence of the so-called Russell set because I can’t prove the existence of any set (or object). That said, I do think it is a stretch to think every set must be finite.

2. I didn’t need an intersection axiom for this proof either. The only set-theoretic axiom I needed to construct n was my subset axiom (like specification in ZF).

3. I haven’t found it necessary in mathematical proofs to postulate the existence of the empty set.

4. By “justifying Peano’s axioms, I mean simply that I think I have gone beyond just assuming them to be true. I have, in some sense, derived them.

8. 