Peano Induction confusion

Question

In a beginning Analysis book, I found this basic representation of induction:

Let $A$ be any set or collection of natural numbers $\mathbb{N}$ with the properties (1) $1 \in A$ and (2) $k + 1 \in A$ wherever $k \in A$, then $A = \mathbb{N}$.

Yes, this is informal, but I can only understand this (and any other Peano Axioms) to mean that when you get to the "last" member of $A$, say, $k_\omega$ and $k_\omega + 1$ is, by definition, also in $A$, we must conclude that $A$ can "go on indefinitely" until it too is actually all of $\mathbb{N}$. It's as if any set of natural numbers that has a proper successor function included in its definition had the ability to instantly blow itself up to be the entire set of natural numbers. How can I understand this any other way? It seems a paradox to even speak of "subset $A$" when you say it has a "machine," i.e., a successor function, that implies it never was a subset. Is this a sort of contradiction trick?

Answer 1

First of all, there's nothing here about "never was a subset"; remember that $\mathbb N$ is a subset of itself --- indeed, every set is a subset of itself.

Now for your real question, here's one way to understand induction, which some people have found useful; I hope it helps you, but if it doesn't then just wait for more people to answer. Think about a set $A$ of natural numbers which happens to contain the number $1$, but suppose it's not the whole set $\mathbb N$ of all natural numbers, so some natural number, say $z$, is not in $A$. Now imagine counting from $1$ to $z$ and checking whether the numbers you name are in $A$ or not. So you ask the questions "Is $1$ in $A$?", "Is $2$ in $A$?", "Is $3$ in $A$?", $\dots$, "Is $z-1$ in $A$?", and "Is $z$ in $A$?" The answers to these questions start with "yes" for the first question (because $1\in A$) and end with "No" for the last question (because $z$ was chosen to be outside $A$). So, at some step during the counting, the answers must have switched from "Yes" to "No". (It might have gone back and forth between yes and no several times, but that doesn't matter. All I care about is that, in order to go from "yes" at the beginning to "no" at the end, you need to switch from "yes" to "no" at least once.) Now think about that switching moment. You got a "yes" answer to some question and "no" to the next question. Those questions were about two consecutive natural numbers, say $k$ and $k+1$. So $k\in A$ but $k+1\notin A$. In other words, we have a counterexample to the implication "whenever $k\in A$ then $k+1\in A$."

Summary: If $1\in A$ but some $z\notin A$, then we cannot have the implication "whenever $k\in A$ then $k+1\in A$."

The induction principle is just this same result in contrapositive form. Assuming that "whenever $k\in A$ then $k+1\in A$." we cannot have "$1\in A$ but some $z\notin A$." So, if we also assume $1\in A$ then there cannot be any natural number $z\notin A$. That is, $A$ must contain all of the natural numbers.

Answer 2

It's not a contradiction trick. It just says that the only subset of $\mathbb{N}$ with the given properties already coincides with $\mathbb{N}$.

This is the basis of induction: you want to proof a statement $E(n)$ for every natural number. So you show $E(1)$ is true and $E(n)$ implies $E(n+1)$. From the two conditions you cited it now follows that $$\{n: E(n) \,\mbox{is true}\} = \mathbb{N}$$

Answer 3

First of all, note that "subset" doesn't mean "proper subset" - $\mathbb{N}$ is a subset of itself. So there's no contradiction there.

That said, yes, your interpretation of induction is basically correct (although I don't really understand what you mean by "last member of $A$": any such set has no last member): the only set of natural numbers which contains zero and which "has a machine" (to use your phrase) is $\mathbb{N}$ itself.

. . . but you have to be careful what you mean by "machine." For example, let $E=\{$evens$\}$. Then $E$ does have a "successor" function in a certain sense: the map $n\mapsto n+2$ takes you from one element of $E$ to the next. But this isn't the actual successor function.

Answer 4

Can you name a natural number which is not an element of $A$? And an element of $A$ which is not a natural number?

It is not the fact that the successor function is there that makes it all 'blow up', it is the fact that the set is closed under it (number (2) in the definition).

Lastly recall that we allow a set to be a subset of itself. The notion which you seem to be referring to (as of, part strictly smaller than the whole) is of 'proper subset'.

Answer 5

There is nothing mysterious about induction. The principle of induction may hold on sets other than the natural numbers, even on finite sets. It can be shown to hold on any singleton for example. If we have $n=\{ 1 \}$ and $s(1)=1$, then it is easy to prove that:

$\forall a\subset n: [1 \in a \land \forall k\in a: [s(k)\in a] \implies \forall k\in n: k\in a]$

Likewise for $n=\{ 1, 2\}$, $s(1)=2$ and $s(2)=1$. Induction would not hold, however, if $s(1)=1$ and $s(2)=2$. (Hint: The subset $a=\{1 \}$ would be a counter-example.)

If we have the function $s: n\to n$ for any non-empty, possibly finite set $n$, (say $1 \in n$), then induction would hold on subset $m\subset n$ such that:

$m=\{1, s(1), s(s(1)), s(s(s(1))), \cdots \}$

(Hint: Suppose $a\subset m$, $1 \in a$ and $\forall k\in a:[s(k)\in a]$. Suppose further that $x\in m$. Prove $x\in a$.)