Well-Ordering and Induction on the Natural Numbers I apologize in advance if this question seems overly pedantic.
On a high level, I am confused about the relationships between the principle of recursive definition, induction, and well-ordering on the natural numbers.
First, suppose that we represent the natural numbers with their set theoretic construction. Of course, this is a recursive definition; is this allowed? In other words, how are we guaranteed that this definition covers all of the natural numbers? My impression was that recursion is a property of the natural numbers, but my confusion arises from the fact that it's also necessary in their set theoretic construction.
Second, if we assume that the natural numbers are well-ordered, then we can easily prove induction on the naturals. Conversely, if we assume that the natural numbers are inductive, then we can prove that they are well-ordered. All of the proofs of well-ordering that I've seen on here rely on that. So, how do we prove that these properties are indeed true of the natural numbers? It seems like we have to assume one to generate the other. Are there any texts out there that address this issue?
I would love to find out if there's any deeper approach that answers these three problems, recursion, induction, and well-ordering, from the ground up.
Sorry again if this is diving too deep into formality. We all know how natural numbers should behave, and perhaps the questions I'm asking are more-so related to their specific representation by sets. Any help is greatly appreciated.
 A: In set theory, natural numbers are typically defined in the following way:

*

*The successor of a set $x$ is defined as $x^+=x\cup \{x\}$.

*We say that $A$ is a successor set if $0\in A$ and for all $x$, if $x\in A$ then $x^+\in A$.

*The natural numbers $\mathbb N$ are defined as the minimal successor set: they are the unique successor set with the property that if $A$ is a successor set, then $\mathbb N\subset A$.

This definition makes sense on an intuitive level, but it raises the question: how do we know a successor set exists? If we try to appeal to recursion, then we do indeed land in trouble. There is a theorem, known as the recursion theorem, which basically amounts to saying that recursive definitions make sense. However, the proof of this theorem relies heavily on the properties of natural numbers, and so trying to appeal to the recursion theorem would be circular.
Instead, we appeal to the axiom of infinity, which is the very assertion that a successor set exists. In other words, the axiom of infinity states that there exists a set containing $0$ and containing the successor of each of its elements. Note that the set $A$ postulated to exist by the axiom of infinity is not necessarily $\mathbb N$; it might be that $A$ consists all of the elements of $\mathbb N$, plus some other elements. Nevertheless, we can use the axiom of infinity, along with the other axioms of set theory, to prove that there is a set $\mathbb N$ satisfying the properties set out above. For a description of how one can do this, see Paul Halmos' Naive Set Theory, chapter 11.
It is baked into the definition of $\mathbb N$ that induction works on it. The fact that they can be well-ordered is also provable by induction. Suppose $A\subset \mathbb N$ has no least member. Let $B$ equal the set of natural numbers not in $A$. One can prove by induction that $B=\mathbb N$, and so $A=\varnothing$. Thus, the only subset of $\mathbb N$ which does not have a least member is the empty set.
