Are these two definitions of the natural numbers equivalent?

Question

If we consider two definitions of the natural numbers:

Definition 1

$N$ is the set that satisfies all of:

1. There is an element $0$ in $N$.
2. For each element $n$ in $N$, there is the successor of $n$, $Sn$.
3. There is no element in $N$ whose successor is 0.
4. For each $m$ and $n$ in $N$, $Sm=Sn$ implies $m=n$.
5. For any subset $A$ of $N$, if $A$ contains $0$ and, for each $n$ in $A$, it holds that if $A$ contains $n$ then $A$ contains $Sn$, then $A=N$.

Definition 2

$N$ is the smallest set that satisfies all of:

1. There is an element $0$ in $N$.
2. For each element $n$ in $N$, there is the successor of $n$, $Sn$.
3. There is no element in $N$ whose successor is 0.
4. For each $m$ and $n$ in $N$, $Sm=Sn$ implies $m=n$.

Are these exactly equivalent? Does this get around the need for the induction axiom?

Answer 1

With just a bit of tweaking, Definition 2 can be shown to be equivalent to Definition 1:

Let $X$ be a set such that

1. There is an element $0$ in $X$.
2. For each element $n$ in $X$, there is the successor of $n$, $Sn$ in $X$.
3. There is no element in $X$ whose successor is $0$.
4. For each $m$ and $n$ in $X$, $Sm=Sn$ implies $m=n$.

Let $N$ be the smallest subset of $X$ such that

1. $0$ is in $N$.
2. For each element $n$ in $N$, $Sn$ is also in $N$.

Then this subset $N$ will be identical in structure to that given by Definition 1.

By "the smallest subset" I mean the intersection of all subsets of $X$ that meet these two requirements.

For a formal development of this idea, see "Daddy, where do numbers come from?" (February 19, 2013) and "What is a number again?" (Janunary 22, 2014) at my math blog.

Answer 2

Axioms 1-4 say that you have a set $X$, an element $0 \in X$, and an injective function $S: X \to X$ such that $0$ is not in the image of $S$. This is enough to imply that $X$ is infinite (since if $X$ is finite then any injection $S:X\to X$ is a bijection and so $0$ must be in the image of $S$). But there are many, many other examples. A few that come to mind:

• Let $X = N$ but with $S(n) = n^2+1$, say. More generally, $S$ could be any injection which doesn't map anything to 0. Here you have the right set, but the wrong successor operation.
• Let $X = N \times N$ be the set of pairs $(m,n)$ where $m \in N$ and $n \in N$, and let $S(m,n) = (m,n+1)$ (again, lots of other functions work).
• Let $X = \mathbb{R}_{\geq 0}$ be the set of nonnegative reals with $S(x) = x+1$ (or whatever). Now we actually have a set of different cardinality.

So to characterize the natural numbers, there are a lot of non-examples to rule out, and we need some kind of powerful principle encoding the information the induction principle. One way to express this formally is to follow Dan Christensen and extract a copy of $N$ from any setup satisfying 1-4.

Here's a slightly different perspective, due to Lawvere, which generalizes somewhat more readily to other settings. Let's say that an "iteration system" (I just made up that term) is a triple $(X,x_0,s)$ where $X$ is a set, $x_0$ an element $x_0 \in X$ and $s$ is a function $s: X \to X$ (this is weaker than axioms 1-4: we don't require $S$ to be injective, nor that $x_0$ be disjoint from its image). Then the natural numbers $(N,0,S)$ can be characterized by the following two properties:

• $(N,0,S)$ is an iteration system, and
• if $(X,x_0,s)$ is any other iteration system, there exists a unique function $f: N \to X$ such that $f(0) = x_0$ and for every $n \in N$, $f(S(n)) = s(f(n))$.

This can be expressed by saying that the natural numbers are a "universal iteration system".