Vtyjkyuk

We have two theorems about Cartesian product:

1. A finite Cartesian product of countable sets is countable;


2. A countable infinite Cartesian product of countable sets is not necessarily countable.

To prove the first theorem, we can show

• Firstly, we can prove $Atimes B$ is countable,


• Secondly, suppose it is true for $n-1$, i.e. $X=A_1times A_2times ldots times A_n-1$ is countable, we prove the case for $n$ by the fact $A_1times A_2times ldots times A_n-1times A_n=Xtimes A_n$ is in fact the product of two countable sets, in above we know it is still countable.

The above method to prove the first theorem is exactly the mathematical induction, which should show the theorem is true for all $ninmathbbZ_+$, so it should works for countable infinite unions.

However, we may use Cantor diagonal method to prove at least $0,1^w$ is not countable, thus the second theorem is also right. Does this means that the mathematical induction is wrong?

EDIT: After the following discussions, I have the answer:

The key point is that any element $ninmathbbZ_+$ is always a finite number, thus induction principle only guarantee the theorem is true for any $ninmathbbZ_+$, i.e. for any finite number.

When discuss a countable infinite union, it is infinite number of unions, this infinite number no more belong to $mathbbZ_+$, thus can not be guaranteed by induction principle.

The theorem that "for all finite $n$, $mathbbN^n$ is countable" is true. The "theorem" that "$mathbbN^mathbbN$ is countable" is not true. Induction on $mathbbN$ shows that something is true for arbitrary finite naturals, but not for $mathbbN$ itself.

I understand induction as justifying that "if I can build the truth of a statement out of its truth for smaller statements, then I can climb the ladder all the way to any desired endpoint": if I can show $P(n+1)$ from $P(n)$, then I can show $P(1000)$ by showing first $P(1)$, then $P(2)$, and so on.
But I can't hope to show $P(infty)$ this way, because my building procedure will never get there. To justify full transfinite induction, you need an additional induction step, one that applies at this sort of limit.

Your first proof shows that for any $ninmathbbN$, the porduct $A_1timescdotstimes A_n$ is finite but, this not say nothing about $mathbbN$ itself. In the last case you need a transfinite induction argument and as you see it is false for the first limit ordinal.