# Is this proof for mathematical induction valid?

Instead of beginning from the natural numbers, we first define $$\mathbb R$$ using field axioms. Let $$\mathscr H$$ be a set of subsets of $$\mathbb R$$ defined as follows:

$$\mathscr H = \{H \subset \mathbb R : 0\in H, x\in H\implies x+1\in H\}$$

We finally define:

$$\mathbb N = \bigcap_{H\in\mathscr H}H$$

At this point, we prove induction as follows:

Theorem. If a set $$M\subset\mathbb N$$ is such that $$0\in M$$ and $$x\in M \implies x+1\in M$$, then $$M=\mathbb N$$.

Proof. Clearly $$M\in\mathscr H$$ and thus $$\mathbb N\subset M$$. Therefore, since $$M\subset\mathbb N$$ by hypothesis, $$M=\mathbb N$$ (using axiom of extensionality).

Now, I did not make this proof up, I found it in an abstract algebra introductory book. I found a comment about it that stated it is not valid, since "the principle of induction is equivalent to well-order on $$\mathbb R$$". Now, the person who said this is not a reputable source, they're just a random person on the internet, so I was wondering if what they said is right. I couldn't understand it actually, since I don't see how well-order has to do with the proof, so I hope you can enlighten me?

• That guy is wrong is several respects. To begin with, The subset $\mathbb N$ of $\mathbb R$ constructed above satisfies the theorem even if $\mathbb R$ itself isn't well-ordered (or even ordered; the construction works for any set containing a "$0$" and a "$1$" and being closed under a "$+$", and the induction principle holds in the for stated by the theorem, even if the "$\mathbb N$" obtained may not be the "usual" $\mathbb N$) Commented Apr 14 at 21:24
• Seems valid to me. The statement "the principle of induction is equivalent to well-order on R" doesn't seem to make much sense to me as wouldn't that equally apply to any definition of $\mathbb N$. ... but... we should probably get more opinions before we commit ourselves to this. Commented Apr 14 at 21:51
• "The subset N of R constructed above satisfies the theorem even if R itself isn't well-ordered (or even ordered..)" You are talking about a field with $0$ and $1$ that isn't nesc. the $\mathbb R$ we know and love, correct? Correct me if I'm wrong, butconstruction $\mathbb R$ (as we know it) from the field axioms does require it be an ordered field (which includes distribution), doesn't it? Commented Apr 14 at 21:57
• The field axioms just define what a field is. They don't define the reals, there are lots of other fields. So how are you actually defining the reals? Commented Apr 15 at 1:02
• @HagenvonEitzen he also said this: "$\mathbb N$ needs to be well-ordered, otherwise you would have non-Archimedean valuations (in particular, $\mathbb N$ has to be infinite). At first order you don't have any decent characterization of $\mathbb N$, since you're able to have (infinite) models for every (infinite) ordinal. Basically you have taken an intersection that lets in through the window what you have let out through the door (and in any case the proof you have given is not constructively - even weakly - acceptable)." Not sure what he means. Commented Apr 15 at 10:25

Let's work in Intuitionistic ZF, a constructive (as usually understood today) version of set theory. But, instead of the normal infinity axiom, suppose we have $$ℝ$$ and the other constants used in your definition.

First, let's abbreviate:

$$\mathsf{Inductive}(H) = 0 \in H ∧ (∀ s. s \in H ⇒ s+1 \in H)$$

Note that I've quantified that $$s$$, unlike your transcription. That's important.

Now, the definition of $$ℕ$$ expands to (I believe):

$$ℕ = \{r \in ℝ : ∀ H \subset ℝ. \mathsf{Inductive}(H) ⇒r \in H\}$$

This uses the separation schema. $$ℕ \subset ℝ$$ holds easily from separation.

Now, suppose we have $$M \subset ℕ$$ and $$\mathsf{Inductive}(M)$$. $$M \subset ℝ$$ holds because the subset relation is transitive.

Now, for each $$m \in ℕ$$ we have:

$$∀ H \subset ℝ. \mathsf{Inductive}(H) ⇒ m \in H$$

We can instantiate $$H$$ to $$M$$, and $$M$$ is inductive, so we have $$m \in M$$. This is the definition of $$ℕ \subset M$$.

These two subset relations give us:

$$∀m. m \in ℕ \Leftrightarrow m \in M$$

which is the premise of extensionality, so we conclude $$ℕ = M$$.

So, this definition and proof go through in a constructive set theory.

Suppose we want to prove $$∀ m \in ℕ. m = 0 ∨ ∃n. m = n+1$$, which is not justified constructively for $$ℝ$$ (because equality with $$0$$ is undecidable). First, let's form:

$$M = \{m \in ℕ : m = 0 ∨ ∃n. m = n+1\}$$

Now, let's prove that $$M$$ is inductive.

• $$0 \in M \Leftrightarrow (0 = 0 ∨ ∃n. m = n+1)$$ from separation
• the left case of the right hand side is provable via reflexivity
• Given $$s \in M$$
• $$s+1 \in M \Leftrightarrow (0 = s+1 ∨ ∃n. s+1 = n+1)$$
• The right is proved by picking $$n = s$$

So, $$M = ℕ$$. Using the separation schema we used to define $$M$$, we can then derive that $$m \in ℕ ⇒ m = 0 ∨ ∃n. m = n+1$$ which is our goal.

So, this goes to show that properties of $$ℝ$$ are not necessarily properties of $$ℕ$$ or vice versa.

Let's prove schematic induction so we don't have to keep building sets. Suppose we have a formula $$φ(n)$$ and are given $$φ(0)$$ and $$∀ n. φ(n) ⇒ φ(n+1)$$. Form the set:

$$M = \{ m \in ℕ : φ(m) \}$$

• $$0 \in M$$ because $$φ(0)$$
• given $$s \in M$$, we have $$φ(s)$$, so $$φ(s+1)$$, and therefore $$s+1 \in M$$

So, $$M$$ is inductive, and equal to $$ℕ$$, meaning that $$φ$$ holds for all $$n \in ℕ$$.

Suppose we use $$≤$$ and $$<$$ on $$ℝ$$ to induce relations on $$ℕ$$. First let's prove:

$$∀m \in ℕ. ¬m < 0$$

We can use schematic induction with $$φ(m) = ¬ m < 0$$.

• $$φ(0) = ¬ 0 < 0$$ holds via irreflexivity
• $$φ(m+1) = ¬ m+1 < 0$$. $$m+1<0 ⇒ m<0$$ by transitivity, so the contrapositive $$¬m<0 ⇒ ¬m+1<0$$ holds (constructively). But $$¬m<0$$ is the inductive hypothesis.

So, our property holds by induction. We can prove that $$∀ m \in ℕ. 0 ≤ m$$ very similarly.

Now consider $$φ(n) = ∀ m ≤ n. m < n ∨ m = n$$

• $$φ(0) = ∀ m ≤ 0. m < 0 ∨ m = 0$$. We know from the previous section that $$m = 0 ∨ ∃n. m = n+1$$. But if $$m = n+1$$ then $$n < 0$$, which is impossible. So $$m = 0$$
• $$φ(s+1) = ∀ m ≤ s+1. m < s+1 ∨ m = s+1$$. We can again split $$m$$ into cases:
• $$0 < s+1$$ holds because $$0 ≤ s$$
• $$m = n+1 ≤ s+1$$ reduces to $$n ≤ s$$, which lets us use the inductive hypothesis, giving either $$n < s ∨ n = s$$. Each respective case yields the corresponding case of $$m < s+1 ∨ m = s+1$$

Now let's prove that $$<$$ is well-founded (in the usual constructive sense).

Suppose we are given a formula $$φ(n)$$ together with $$∀n. (∀ m < n. φ(m)) ⇒ φ(n)$$.

Let's consider the formula $$ψ(n) = ∀ m ≤ n. φ(m)$$

• $$ψ(0) = ∀ m ≤ 0. φ(m)$$. It must be the case that $$m = 0$$, and $$φ(0)$$ follows from $$(∀ m<0. φ(m)) ⇒ φ(0)$$ because $$¬m<0$$.
• $$ψ(s+1) = ∀m≤s+1. φ(m)$$. The induction hypothesis is $$∀m≤s. φ(m)$$. Our previous proof gave $$m.
• when $$m < s+1$$, it's again the case that $$m ≤ s$$, so $$φ(m)$$ follows from the induction hypothesis
• when $$m = s+1$$, we can use $$(∀n < s+1. φ(n)) ⇒ φ(s+1)$$ with the induction hypothesis to prove $$φ(s+1) = φ(m)$$

So, $$∀n. ψ(n)$$ holds by induction. But $$n ≤ n$$ holds reflexively, meaning $$∀n. φ(n)$$ holds.

Thus, $$<$$ is (constructively) well-founded on $$ℕ$$ even though it isn't on $$ℝ$$.

In short, these objections do not make sense from a proof perspective. They are (constructive) derivations of the reasoning principles on $$ℕ$$ from other principles on $$ℝ$$ (and set theory). As mentioned in the comments, they don't actually depend on the whole structure of $$ℝ$$ at all (which is good, because abstract specifications of $$ℝ$$ often presuppose $$ℕ$$). You can apply them to other structures with the properties actually used above and they will still hold, although you won't necessarily get the usual $$ℕ$$.

Generally the objections seem to be erroneously conflating a lot of distinct things. Perhaps they are talking about how it is difficult to specify $$ℝ$$ such that you get something like the expected $$ℕ$$ without mentioning the latter when defining the former. But it's hard to tell because some of the objections just seem incorrect.

Incidentally, the above steps are essentially the same steps one goes through starting with the typical axiom of infinity. The difference is that instead of $$0$$, $$1$$ and $$+$$, one usually assumes a set containing the empty set and closed under some successor operation on sets. One then usually goes through the same process of intersecting all its subsets to get the minimal such set. Here $$ℝ$$ is just (supposedly) being used as the primordial infinite set. So it's unclear what objections one could have, besides skepticism that $$ℝ$$ could be characterized well enough to serve as the starting point. But I think that is not actually a problem (you don't need all facts about $$ℝ$$ to carve $$ℕ$$ out in set theory).

• What is the reason for the negative votes? Is it because I used constructive set theory to specifically address the complaint in the comments that the proofs aren't constructive? Commented Apr 15 at 17:44
• Thanks for the answer! I'm still reading it, however I have a question about the definition of $\mathbb N$ you provided in the first bit. How do you prove equivalence between that definition and the definition I used in the proof? And what are you referring to by "separation"? Also, why isn't the proof I provided constructive? Commented Apr 15 at 17:50
• What I wrote is either the definition of what you wrote (modulo the quantifier on the successor part), or it follows readily from something like the power set axiom and the definition of $\bigcap$. And I don't know why the person thinks the proof of induction isn't constructive. Part of the point of my answer is that it does work even in constructive set theory. Commented Apr 15 at 17:58
• Yeah I don't understand either to be honest. Could you explain what you mean when you say "separation schema" and "separation" or link a page about it? Commented Apr 15 at 18:05
• May I ask exactly why you state that $\neg0<0$ holds? Commented Apr 15 at 18:35