Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer
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? – Dani Hobbes 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" – Arturo Magidin Mar 13 '11 at 22:51
Good, thanks for the great help! – Dani Hobbes Mar 13 '11 at 22:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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