# Question about base cases in induction

So when first developing the natural numbers in basic set theory, most properties are proven by induction. This is very convenient since $\omega$ is the smallest inductive set.

I saw a proof of the following proposition.

For all $n\in\omega$ and $n\neq 0$, $n\times\omega\sim\omega$.

The induction goes as let $$K=\{n\in\omega\ |\ (n=0)\lor (n\times\omega\sim\omega)\}.$$ Base case, $0\in K$. Suppose $n\in K$. Then $$\sigma(n)\times \omega=(n\cup\{n\})\times\omega=n\times\omega\cup\{n\}\times\omega\sim\omega$$ since $n\times\omega\sim\omega$ and $\{n\}\times\omega\sim\omega$, and the union of two countable sets is countable.

What puts me off is that since the proposition is not true for $n=0$, we just throw it into the set to conclude that $K=\omega$, not $K=\omega\setminus\{0\}$. Shouldn't we start the base case at $n=1$ instead? Why is it still acceptable to begin at $0$ if the proposition is not actually true for $0$?

-

The proof is not correct as stated, precisely for the reason you point out: if $n=0$, then it is false that $n\times \omega\sim\omega$. So it's a good thing you are put off.

Rather, from $n\times\omega \cup \{n\}\times\omega$, the argument should then say something like:

$\{n\}\times\omega\sim\omega$ holds; and since $n\in K$, either $n=0$ and $n\times\omega=\emptyset$, or else $n\times\omega\sim\omega$. In either case, we have $\sigma(n)\times\omega\sim\omega$, so $\sigma(n)\in K$.

(or else the inductive step could try to handle the $\sigma(n)=1$ case as a "special case").

It's okay to begin at $0$ because the set $K$ "takes care" of the $n=0$ case explicitly. You can do this in all sorts of cases; for example, if you wanted to prove that every natural number greater than $99$ needs three or more digits to write in base $10$, you could let $K$ be $$K = \{n\in\omega\mid (n\leq 99)\lor (n\text{ requires three or more digits to write in base }10)\}$$ and use induction to show that $K=\omega$.

However, when one does this, it is very often the case that the first case in which the original statement is true has to be dealt with independently or directly, which is what happens in the argument you quote. In the one I just made up, you would have to consider the case $\sigma(n)=100$ separately from all others:

• For $n=0$ or $\sigma(n)\lt 99$ you have $\sigma(n)\in K$ by definition;

• for $\sigma(n)\gt 100$ you can use the fact that $\sigma(n)$ requires either the same number of digits of $n$ or one more, and since $n\in K$, and $\neg(n\leq 99)$, then $n$ requires at least $3$ digits, hence so does $\sigma(n)$; so $\sigma(n)\in K$.

• But if $\sigma(n)=100$, then the fact that $n\in K$ doesn't help you: you actually have to stare at $100$ and see that it takes three digits to conclude $\sigma(n)\in K$.

Essentially, you get all the "false cases" for free, so that your "true" base, the first value for which the statement holds, usually needs to be taken care of directly.

-
Thanks Arturo. I want to see if I'm correct in reading your "or else the inductive step could try to handle the σ(n)=1 case as a "special case" statement. So a good way to deal with this would be to say $0\in K$. See $1\in K$ since $1\times\omega=\{0\}\times\omega\sim\omega$. And then the induction could proceed normally? –  Hobbie Mar 13 '11 at 22:47
@Hobbie: Yes, exactly. The moral is that one should be careful with induction, and you were definitely careful here, so kudos. For a classic example of "you have to be careful with your induction" see the fake proof that "in any group of women, if at least one has blue eyes then they all have blue eyes" groups.google.com/group/sci.math/msg/00a68f5d9fcaa90d –  Arturo Magidin Mar 13 '11 at 22:51
Good, thanks for the great help! –  Hobbie Mar 13 '11 at 22:54