0

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?

Dan Christensen
  • 14,529
147pm
  • 920

5 Answers5

3

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.

Andreas Blass
  • 71,833
  • I like this explanation very much. +1. (I hope you don't mind if I steal it for future use!) – Noah Schweber Aug 17 '16 at 16:08
  • @NoahSchweber Thanks. One of the reasons I wrote this is that I want it to be "stolen". – Andreas Blass Aug 17 '16 at 16:12
  • @Noah This is sometimes called the method of minimal counterexample or "minimal criminal", i.e. if there is a counterexample, then there is a least counterexample (minimal criminal) $,1< k+1\not\in A.,$ Then $,k\in A,\Rightarrow, k+1\in A,$ contradiction. Alternatively it can be presented a la Fermat as (infinite) descent on counterexamples: All exploit that $\Bbb N$ is well-ordered (aka Least Number Principle). – Bill Dubuque Aug 17 '16 at 18:35
  • @BillDubuque I'm familiar with the name of the technique, I was pleased with Andreas' specific way of explaining it. – Noah Schweber Aug 17 '16 at 18:44
  • So, thanks everyone. This is very helpful. So we are working (sort of) with a paradox-counterexample. My difficulty with PA lies in 1) understanding how a "subset" e.g., $A = {1, 2, 3, 4, 5, 6}$ could expand to be the whole natural number set, 2) how a successor function was truly an "unit incrementer", i.e., $k+1$. What's to prohibit the successor $S$ from mapping inconsistently, say, $S(k) \mapsto k+m$ where $m > 1$, then settling back to $S(k) \mapsto k+1$? I've seen more formal definitions where that seems possible. – 147pm Aug 18 '16 at 14:39
  • @147pm It may be useful to keep in mind that sets don't "grow" or change. In particular, $A={1,2,3,4,5,6}$ does not "expand" to "become" $\mathbb N$. As for item 2 in your comment, the $S$ mentioned in the induction principle is the standard notion of successor, mapping each $k$ to $k+1$. If you vary the meaning of $S$ (or the meaning of $1$, or the meaning of $\in$, or the meaning of "if $\dots$ then $\dots$", etc.), then the induction principle's new meaning may well be false. The induction principle is to be understood as involving the standard meanings of all the words and symbols in it. – Andreas Blass Aug 18 '16 at 14:50
  • All I see with formal PA definitions is the $S$ successor has to be injective and $S(k) \neq 0$. You could define an $S$ that behaved intermittently "non-unit-incremental" could you not? It's just that formal PA definitions of $S$ don't seem to strictly imply a unit increment. But then later on subsequent applications might "plug in" a unit increment like $k+1$. – 147pm Aug 18 '16 at 15:15
  • @147pm Sure, you could do that, but you'd just get a copy of $\mathbb N$with strange names for the elements. For an easy example, suppose you worked with the usual notion of $1$, but $S(k)=k+3$. Then the "natural numbers" described by that choice of $S$ would be ${1,4,7,10,\dots}$, addition would be given by $a+b+2$, multiplication by some horrid formula that I won't compute,etc. You would reasonably rename these "natural numbers" as $1,2,3,\dots$, so that, with the new names, you could say $2+2=4$ (as opposed to $4+4=10$ with the original weird names). – Andreas Blass Aug 18 '16 at 19:46
  • Another way to say this is that the Peano axioms describe $\mathbb N$ up to isomorphism. They do not guarantee that what they call $1, S(1), S(S(1)),\dots$ are the entities that you are accustomed to calling $1,2,3,\dots$. They might be what you're used to calling $1,4,7,10\dots$, or they might be you, me, Obama, the moon, $\dots$, or any other sequence of distinct entities. But they will have operations of addition, multiplication, etc. that behave just as in ordinary arithmetic, no matter how weird the entities are (e.g., me + me = the moon, in that last example). – Andreas Blass Aug 18 '16 at 19:50
0

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}$$

Thomas
  • 22,361
0

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.

Noah Schweber
  • 245,398
0

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'.

wet
  • 605
-2

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$.)

Dan Christensen
  • 14,529