-1
$\begingroup$

For the former result we can prove for the base case and then use induction to prove the result. But I am unsure why this doesn't hold for the second result. I tried searching for it a bit and found out that it requires Axiom of choice. Can someone please explain me this ? It's quite confusing to me why can't we use induction always. I have already looked up proofs of these. Prove that the union of countably many countable sets is countable. and Infinite Cartesian product of countable sets is uncountable But I'm unsure why induction can't be used on both.

$\endgroup$

closed as off-topic by Andrés E. Caicedo, José Carlos Santos, Saad, Did, Xander Henderson Sep 25 '18 at 12:13

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Andrés E. Caicedo, Saad, Did, Xander Henderson
If this question can be reworded to fit the rules in the help center, please edit the question.

1
$\begingroup$

How would you use induction to prove the first statement, namely that a countable union of countable sets is itself countable? Suppose you have a collection of countable sets $\{ A_n : n \in \mathbb{N} \}$. "Applying induction" naively as desired gives us this:

The base case is $n = 1$. And indeed, $\bigcup_{i=1}^1 A_i = A_1$ is countable.

The induction hypothesis is that $\bigcup_{i=1}^{n-1} A_i$ is countable for some $n > 1$.

Assuming the induction hypothesis, we need to prove that $\bigcup_{i=1}^n A_i$ is countable. But, $$ \bigcup_{i=1}^n A_i = \bigcup_{i=1}^{n-1} \cup\ A_n $$ which is a union of two countable sets (by the induction hypothesis), and is thus countable. (Why? Prove this!)

Hence, by the Principle of Mathematical Induction. . .well, what have we shown? Only that $\bigcup_{i=1}^n A_n$ is countable for every $n \in \mathbb{N}$. This is a far cry from showing that $\bigcup_{i=1}^\infty A_n$ is countable! Do go through the steps carefully to see that we are asserting the statement and not the latter when we complete our "proof by induction".

All this is well and good, you say, but it doesn't tell me why induction doesn't help in proving what we want!

Very well. A counter question might help in understanding why it isn't so natural to expect the principle of mathematical induction to help here:

Knowing that $\bigcup_{i=1}^n A_i$ is countable for every $n \in \mathbb{N}$, why should this knowledge say anything about the size of the object $\bigcup_{i=1}^\infty A_i$?

Here's a motivating example. Let's try and solve a slightly different question using mathematical induction.

Problem. Show that $1 + 2 + \dots + n$ is finite for every $n \in \mathbb{N}$.

The template is the same. The base case is $n = 1$. And indeed, $1$ is finite. The induction hypothesis is that $1 + 2 + \dots + (n-1)$ is finite for some $n > 1$. Assuming the induction hypothesis, we need to prove that $1 + 2 + \dots + n$ is finite. But, $$ 1 + 2 + \dots + n = (1 + 2 + \dots + (n-1)) + n $$ which is a sum of two finite numbers (by the induction hypothesis), and is thus finite. Hence, by the principle of mathematical induction, $1 + 2 + \dots + n$ is finite for every $n \in \mathbb{N}$.

Great! Now, what does knowing that $1 + 2 + \dots + n$ is finite for every $n \in \mathbb{N}$ tell us about the value of $1 + 2 + 3 + \dots = \sum_{n=1}^\infty n$? This sum is defined as the limit of the partial sums, by the way, and the sequence of partial sums diverges to infinity. So, this quantity is most definitely not finite.

It is more clear why this is how things should be. What can the finiteness of the sums $1 + 2 + \dots + n$ say about the infinite sum $\sum_{n=1}^\infty n$? Nothing on its own, surely. We definitely need to do more work to talk about the value of $\sum_{n=1}^\infty n$.

Go through both proofs again if you like, and see how they really are just two applications of the same universal template that is mathematical induction. What this shows is that the template of a proof by mathematical induction cannot touch upon infinite processes at all. What it does, though, is that it proves a result for every natural number, that is, for every arbitrary finite step. So the sums in the second example could be arbitrarily large (but still only be finite sums), and the result would be true. The unions in the first example could be arbitrarily large (but still only be finite unions) and the result would be true. Moreover, this combined knowledge of a result being true for every (finite!) natural number $n$ says nothing by itself about the infinite case.

In fact, the result about unions is true for countable unions. If this was a result arising from mathematical induction alone, then you could expect to modify the underlying template to prove that $\sum_{n=1}^\infty n$ is finite as well, which is impossible. That would be another justification for why you cannot use induction to prove that a countable union of countable sets is countable.

$\endgroup$
  • $\begingroup$ Thanks I had a misconception about mathematical induction. This cleared everything. Thanks a lot $\endgroup$ – Pratik Patnaik Sep 17 '18 at 20:09

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