# Does countable induction over $\mathbb N$ require the axiom of infinity?

Consider ordinary induction over $\mathbb N$:

Proving $P(0)$

Assume $P(k)$ being true for some natural $k$

Prove $P(k+1)$

Does this require the existence of $\mathbb N$ and hence the axiom of infinity? I don't see where we would invoke the existence of $\mathbb N$; after all I can always construct arbitrary many naturals without an infinite set. The induction should hold by just repeating the argument, without any need to invoke $\mathbb N$.

We know $P(0)$ being true, and hence $P(k)$ for $k=0$. Thus $P(k+1)\Big|_{k=0} = P(1)$ must hold. Repeat this argument until you get to a desired natural, or just show you could keep going without any bound and that the proposition is valid for any natural you can construct.

I don't see how any of this would need me to invoke the existence of an infinite set.

• It doesn't. You do not need the axiom of infinity or (equivalently) that $\mathbb N$ is an actual set as opposed to a proper class. A formalization of this claim is the theorem that $\mathsf{PA}$, the first-order version of Peano arithmetic, is bi-interpretable with the theory resulting from $\mathsf{ZF}$ by replacing the axiom of infinity with its negation. Jul 14, 2018 at 12:39

In an arithmetic theory, you don't need an induction axiom to obtain a result $P(n)$ for some specific $n.$ You are correct, you can just use the idea behind induction to take you from $P(0)$ to $P(n)$ step by step, however large $n$ might be, just using simple step-by-step reasoning... no overarching principle needed. Where an induction axiom is necessary is generalizing this to all natural numbers. In logic, there is a big difference between being able to prove, for all $n,$ that "$\phi(n)$ holds," and being able to prove "for all $n,$ $\phi(n)$ holds." In the first case, the quantifier 'for all $n$' is in the metatheory, which doesn't always translate to a quantifier in the formal theory. (This may seem pedantic, but it's actually a very important subtlety that shows up in a lot of important results in logic.)

(Note also there is also a quantification over 'all properties' (more specifically all formulas) that typically happens in the metatheory, at least for first order theories.)

That's how it works in an arithmetical theory like PA, but you asked about the axiom of infinity's bearing here, so we need to see how this looks in set theory. So suppose our formal theory is ZF without the axiom of infinty where we've embedded arithmetic in the usual way where $\mathbf 0\equiv \emptyset$ and $\mathbf S(\mathbf n)\equiv \mathbf n\cup\{\mathbf n\}.$ The property of being a natural number (under this translation) is definable in set theory (it is a natural number if it an ordinal that is not greater than or equal to any limit ordinal). So one can, fairly straightforwardly, translate any first-order statement of arithmetic as a statement about sets that are natural numbers.

Notice here, we are just treating the natural numbers as a class, not necessarily a set. In fact we can prove from ZF minus infinity that any of the (translations of the) axioms of PA, including all the induction axioms, hold in this class. The induction axioms just follow from the transfinite induction theorem schema on the ordinals, which does not involve infinity at all, and just says any subclass of the ordinals has a least element. All that infinity would do is guarantee that $\mathbb N$ is a set and thus not all of ordinals. In fact, it's known that PA and ZF minus infinity (plus the negation of infinity) are, pretty much equivalent theories. Where the axiom of infinity becomes important is for second-order arithmetic (and second order induction) where we need to be able to quantify over arbitrary subsets of $\mathbb N,$ and thus take it seriously as a set.

(Infinity gives some other interesting things things here. This is an instance of the important subtlety I mentioned above. When I said 'any subclass of the ordinals' above, that quantifier was in the metatheory. When we are doing induction up to some ordinal ($\omega$ in this case) we can actually state and prove, in the theory, that every subset of $\omega$ has a least element. On a very related note, while ZF minus infinity can prove, for each instance of PA's induction schema, that $\omega$ (i.e. the class of all ordinals in this case) satisfies the instance, in ZF with infinity we can formalize and prove "$\omega$ satsifies every instance of the induction axiom." This has a lot to do with the fact that ZF can prove the consistency of PA whereas ZF with infinity replaced by its negation, being of the same strength as PA, cannot.)

• Induction up to $n+1$ is still induction. Amusingly, people use "induction" to mean "induction on $\Bbb N$", and transfinite induction to mean induction up to some ordinal (or all of them), which means that induction up to $17$ will be called transfinite induction more often than not. Jul 14, 2018 at 6:02
• @AsafKaragila True, and looking at my answer again, I'm not sure why I opened with "The principle of mathematical induction" which surely sounds more (pseudo) high-falootin and official than I intended it Jul 14, 2018 at 6:37

You just need the property which states that each subset of $\mathbb N$ has a smallest element.

for the proof of the induction, you consider the set of $k$ such that $P(k)$ is false. this set has a smallest element $m\ne 0$. this means that $P(m-1)$ is true, thus $P(m-1+1)$ is true. this is a contradiction.

• Even though, the induction principle is often stated as an axiom. Why? Jul 13, 2018 at 20:56
• It's stated as an axiom in Peano Arithmetics and set theory axioms (ZFC) don't contain them. Set theory (ZFC) just models $\mathbb{N}$ using sets. So we need to prove that our set $\mathbb{N}(=\omega)$ in ZFC is correct, that is, it follows all the axioms of PA. Jul 13, 2018 at 21:03
• @Punga So the induction principle is independent of ZFC? Jul 13, 2018 at 21:06
• @MarkusKlyver It is not independent, because it's stated in another language. In language of set theory you don't have symbols like $+, 0, -, \leq$, only $\in$, but you can still define them, which still doesn't "add" them to the formal language, but adds them to our human metalanguage. Jul 13, 2018 at 21:21
• @Punga If not, what axioms is the induction principle based on? Jul 13, 2018 at 21:56

Induction on natural numbers is stated in the set theory $ZFC$ in the following way. We have a set $\omega$ which represents $\mathbb{N}$. Now we state the principle of induction:

Let $X$ be a set. If $0\in X$ and $\forall n\in X: n+1 \in X$, then $\omega\subseteq X$.

However $ZF\setminus \{\text{axiom of infinity}\}$ itself cannot prove $\omega$ exists. That's why we need the axiom of infinity. Without it we simply cannot "talk" about $\omega$.

So no, without axiom of infinity it is not possible to even state the induction principle in $ZF\setminus\{\text{axiom of infinity}\}$, that means it cannot be proven. If we tried not to use $\omega$ we would always state it only for some finite number of naturals. (Which can be extended as much as you won't, but you will never state it for all naturals.)

What could be possible, but that would need someone more qualified than myself, is to use classes. Classes are not part of $ZFC$ (nor $ZF\setminus \{\text{axiom of infinity}\}$), but can be used as metamathematical language extention, to talk about "too big" collections of sets. So if we could define $\omega$ as a class. It could be possible to make a metatheorem about indution over the proper class of natural numbers.

• If $\omega$ were a proper class, any $X$ satisfying $\omega\subseteq X$ would have to be one too.
– J.G.
Jul 13, 2018 at 21:42
• Yes. I did not imply that would be the only change to the theorem. Jul 13, 2018 at 21:45
• But I don't have to specify that natural numbers are members of a set, as my original post tried to argue for. A proof by contradiction should yield the same result. "Assume there is a last natural $n$ such that $P(n)$ is true. But we have proven $P(k) \implies P(k+1)$, hence our assumption was wrong." Jul 13, 2018 at 21:58
• You asked about the axiom of infinity. That is of the ZFC axioms. ZFC is a set theory, to state induction you have to "talk" about the set of natural numbers. Math is not built simply on "trivial" deductions that build up complex proofs. It is built on theories of predicate logic. It has strict rules. Your statement works as informal proof using formal symbol. I recommend reading more about mathematical logic. Jul 13, 2018 at 22:15
• @Punga ZFC of course includes the axiom of infinity, so my question regards the necessity to rely on the axiom of infinity for the principle of induction. Jul 14, 2018 at 1:06