I know that Peano's arithmetic allows induction proofs with its fifth axiom.

I also know that set theory can recreate natural numbers, for example with the Von Neumann method: $0=\left\{\right\}, 1=\left\{ 0 \right\}, 2=\left\{ 0,1 \right\}, \cdots$

But how can we allow (i.e. which axioms and which reasoning) induction proofs using set theory?

Thank you for your help.

  • $\begingroup$ Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer. For equations, please use MathJax. $\endgroup$ – dantopa Jun 10 at 22:44
  • $\begingroup$ Do you say that because I'm new the site or because my question is not properly formulated/formated? I'm sorry, I'm using the mobile app and it's difficult to do complex MathJax or in-length explanations. $\endgroup$ – JacopoStanchi Jun 10 at 22:50
  • 1
    $\begingroup$ The goal is to expose you to the agreed upon standards of the site to better understand the actions of the individual members. Some users will insist on a close adherence to standards, others are just as happy to answer the question. You seem to have solicited a rather complete answer. But other users may insist upon more context and further elaboration of efforts. So welcome, and refer to the links if you need more insight. $\endgroup$ – dantopa Jun 11 at 0:28

Let $R$ be a well-founded relation on sets of some class $M$ (that means that every non-empty subset of $M$ has an $R$-minimal element) that is set-like, i.e. for any $x \in M$ the class $\{ y \in M | y R x \}$ is a set. Then, for any formula $\phi$ in the language of set theory, we can proof the following in ZF:

$$ \forall x \in M (\forall y \in M (yRx \rightarrow \phi(y)) \rightarrow \phi(x)) \rightarrow \forall x \in M \phi(x) $$

For the proof, suppose the LHS holds but there is some element $z \in M$ for which $\phi(z)$ fails; take the $R$-least such element (exists because $R$ is well-founded, and the set $\{ x \in M | \lnot \phi(x) \}$ is a subset of $M$, and non-empty by assumption). Then $\phi(w)$ holds for all $w R z$, and thus by the LHS (which we assumed to be true) we must have $\phi(z)$, a contradiction.

Now, from this theorem (the Theorem of Transfinite Induction) we can derive ordinary induction: put $M = \omega$ (the natural numbers) and $R = \, <$ (the ordinary order relation on naturals). Note that $<$ is not only well-founded but actually well-ordered (so every non-empty subset of $\omega$ has in fact a least element). Thus, by the theorem, we have the following: take any formula $\phi$, then

$$ \forall n \in \omega (\forall m \in \omega (m < n \rightarrow \phi(m)) \rightarrow \phi(n)) \rightarrow \forall n \in \omega \phi(n) $$

This doesn't quite look like standard induction yet, but we can make a few tweaks to it by noting the following: if $n = 0$ then $m < n$ is always false and hence the implication $m < n \rightarrow \phi(m)$ is always true. So in order to verify the LHS, we only need to check that the formula $\phi(0)$ holds. This is what we usually call the base case.

If $n \neq 0$ then we are left with the standard inductive step: by renaming indices, we may assume that $\phi(m)$ holds for all $m \leq n$, and now we need to show $\phi(n+1)$. This covers all cases, and thus we are done.

As to what axioms are required, you certainly need comprehension, but perhaps someone else would like to chime in and give further details on what exactly is required.

  • 4
    $\begingroup$ The usual way of representing natural numbers as sets provides an easier proof of ordinary induction over the set $\omega$ of natural numbers. The point is that $\omega$ is usually defined as the intersection of all the sets that contain $0$ and are closed under successor. So ordinary induction is essentially built into the definition. (A formal proof would need the axiom of infinity to prove the existence of $\omega$ and the comprehension schema to prove the existence of the subset of $\omega$ consisting of the numbers with the property that one wants to prove by induction.) $\endgroup$ – Andreas Blass Jun 10 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.