Peano Induction Axiom

163 Views Asked by At

This is a typical rendition the Peano Axiom of Induction:

If subset $S \subseteq \mathbb{N}$ contains $1$ and is closed under the successor function (i.e., $n \in S$ implies $\sigma\text{n} \in S$ where $\sigma$ is the successor function) then that subset $S$ is all of $\mathbb{N}$.

How do we make the leap that $S$, which might not be all of $\mathbb{N}$ eventually does cover all of $\mathbb{N}$? I can only assume $\sigma\text{n}$ takes things outside of $S$?

3

There are 3 best solutions below

4
On

It follows from the definition of the natural numbers. $\mathbb{N}$ is defined as the smallest set containing 0 (or 1, if you insist on starting at 1) and closed under successors.

If that answer isn't satisfactory, then assume $S \subset \mathbb{N}$ is a strict subset (so $S \neq \mathbb{N}$). Let $k$ be the least element of $\mathbb{N} \setminus S$. Then either $k = 1$ or there is a natural number $n$ such that $\sigma n = k$. By the definition of $k$, $n \in S$, and since $S$ is closed under successors, $\sigma n = k \in S$, which is a contradiction.

0
On

How do we make the leap that $S$, which might not be all of $\mathbb{N}$ eventually does cover all of $\mathbb{N}$? I can only assume $\sigma n$ takes things outside of $S$?

When you say that "$S$..might not be all of $\mathbb{N}$", you are actually trying to find out whether $S$ and $\mathbb{N}$ are identical or not. In other words, you need a proof of the question whether $S=\mathbb{N}$ or not. But you can only prove the equality between two sets when you know that definition of each set. So, you need to answer first,

What is the definition of $\mathbb{N}$?

3
On

The Peano Induction Axiom can be thought of as one of the 5 essential properties of the natural numbers. See Peano's Axioms. (There are other, less widely used formulations.)

The Induction Axiom says that, if you have a subset $P$ of $\mathbb{N}$, then we can show that all elements of $\mathbb{N}$ will be in $P$ if

(a) $1 \in P$, and

(b) if $x \in P$, then the successor of $x$ will also be in $P$