2

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.

kevinyou81
  • 29
  • Every natural number can be reached by repeatedly adding $1$ (starting with $0$) , no matter how large it is. Of course in reality this could take longer than we can even imagine , but it would still require always only a finite number of additions since every natural number is finite. – Peter Aug 23 '22 at 11:27
  • If you are really interested in this formalism, then you should look at constructive Mathematics. For example Paul Lorenzen introduce numbers with counting by saying : __ | || ||| .... and so on. and the well ordering is then some simple application of counting. You find it in Lorenzen Metamathematik 2. ed 1980 :) – LogicTheorist Aug 23 '22 at 14:04
  • @kevinyou81.-Hi kevin. A friend of mine, who knows a lot about axiomatics and mathematical logic, tells me about your question

    «Regarding the question about induction on the natural numbers that appears in math.stackexchange, I believe that the definition of the set of natural numbers that is used in modern texts gives the answer.

    The set of natural numbers is defined as the smallest set $A$ such that the empty set belongs to $A$, and if $x$ belongs to $A$, then $x\cup{x}$ also belongs to $A$. Here minor is minor with respect to inclusion.»

     – Piquito Aug 25 '22 at 17:47
  • @Piquito Hello! yes, I stumbled on that definition while i was doing some reading. I think I figured out (im sure it's not novel) that if you assume the axiom of infinity, let I_0 be the infinite set guaranteed by it. Then, define A as the subset of the power set of I such that every element of A is infinite (or inductive). Then take the intersection over A, and you get Omega in a way that gives you induction with an easy proof. – kevinyou81 Aug 26 '22 at 19:13

1 Answers1

1

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.

Joe
  • 19,636