Induction - Countable Union of Countable Sets

Question

Stephen Abbott has a an exercise in Chapter 1 (1.2.12) that suggests that one cannot use induction to prove that a countable union of countable sets is countably infinite.

One answer is that $n={}$infinity cannot be demonstrated via induction, as inifinity is not a natural number. This seems sketchy. Rudin in chapter 2 clearly distinguishes the use of inifinity symbol for a union of sets to indicate a countably infinite union of sets and distinguishes it from the infinity used to extend the reals.

All of this also appears to ignore the fact $N$ is countably infinite by definition. Therefore any bijection with $N$ is also proved for countably infinite cases.

So why cannot induction be used to argue countable union of countable sets is countable?

Here is an example where induction is being used in the context of countably infinite sets. Using induction to prove that the infinite set of polynomials is countably infinite

Answer 1

Induction can be used to prove that the union any fixed, arbitrarily large, but finite, number of countable sets is countable.

This statement is emphatically not the same as saying that the union of countably infinitely many countable sets is countable.

---

Somewhat more formally, suppose that $A_i$ is a countable set for each $i\in\mathbb N$. You can use induction to prove that the set $$\bigcup_{i=1}^n A_i$$ is countable for any given $n\in\mathbb N$. But this does not imply that the set $$\bigcup_{i=1}^{\infty} A_i$$ is countable!

---

[Spoiler alert: using the axiom of choice, you can prove that the union of countably many countable sets is actually countable. You just cannot do that using induction alone.]

Answer 2

The formal statement of the principle of mathematical induction is to start with a statement $P(n)$ that depends on a natural number variable $n$. If:

1. $P(1)$ is true
2. $P(k+1)$ is true whenever $P(k)$ is true.

Then $P(n)$ is true for all $n$.

Let $A_1, A_2, \dots, A_n, \dots$ be an infinite sequence of countable sets. To use induction, you would need to find a statement $P(n)$ such that $$ P(n) \text{ is true }\forall n \leftrightarrow \bigcup_{n=1}^\infty A_n \text{ is countable} $$ The statement on the left is that something holds for every number $n$, while the statement on the right is about something accumulated over all $n$.

Answer 3

Probably a bit aside of the point, but if each $A_i$ is countable, this means that there is a surjective map $\phi_i: {\mathbb N} \rightarrow A_i$. Now choose your favorite surjective map: $ n\in {\mathbb N} \mapsto (a(n),b(n)) \in {\mathbb N} \times {\mathbb N}$. Then $n\in {\mathbb N} \mapsto \phi_{a(n)} (b(n)) \in \cup_i A_i$ is surjective. Why use induction?

Answer 4

You are right. Induction only gives you that for every finite case, the finite union of countable sets is countable.

However, we can prove directly the following.

Suppose that for every $n$ we are given $S_n$ and an injection $f_n\colon S_n\to\omega$. Then $\bigcup S_n$ is countable.

Now, using the axiom of countable choice, given a sequence of sets that each of them is countable, we can choose for each one an injection. So the union is countable. This is implicit in most modern books that don't fuss about using the axiom of choice, Rudin included. And seeing how at least countable choice is very natural, and working without it can be difficult, there is no reason for them to fuss about it.

However, we do know how to construct models where the axiom of choice fails so severely that there are some sequences of countable sets whose union is uncountable. In fact we can even get the real numbers to be a countable union of countable sets, despite them being uncountable. These constructions are very technical and require deep understanding of set theory. So understandably not many books go into them with details.

Answer 5

This appears to be common doubt expressed in the following places:

What are the cases of not using (countable) induction?

Why induction cannot be used for infinite sets?

Why doesn't induction extend to infinity? (re: Fourier series)

Induction essentially shows if something is true for 1 and n, it is true for n+1 - and is thus true for countably inifinite cases (bijection with N)

Stephen Abbott has a an exercise in Chapter 1 (1.2.12) that suggests that one cannot use induction to prove that a countable union of countable sets is countable. For clarity lets assume countable is countably infinite.

Rudin in chapter 2, statement after (3) clearly states that the notation for Union over the set A of all positive integers uses the infinity symbol. He states that he uses the infinity symbol for a union of sets to indicate a countably infinite union of sets and distinguishes it from the infinity used to extend the reals.

$N$ is countably infinite by definition. Therefore any bijection with $N$ is also proved for countably infinite cases.

Response 1: One answer is that n=infinity cannot be demonstrated via induction, as infinity is not a natural number - there is no n+1 = infinity. But: The infinity symbol is not used in this way as per Rudin. He is using infinity in place of N. There is a problem in semantics - see response 3.

Response 2: You don't need induction so why do you want to use it here to prove the statement. Well there is as much to learn from why not as from why.

Response 3: Induction proves for finite cases only. It only says we prove for every n in N. Whatever n you pick is by definition finite. So we have only proved finite unions of countable sets are countable. While induction proves this for countably infinite cases - each case is finite. In this sense response 1 makes sense - no case is anything but finite. Could the smarties on this thread validate this reasoning?

wow 2 downvotes but no explanation why...?

Answer 6

Induction states that what ever is true for $k=1$ and true for $\forall k:k<n$ is true for $n, \forall n\in N$.

So for the finite union of countable sets $\cup_{i=1}^n{A_i}$ you first prove for $A_1\cup A_2$.

Then for $\cup_{i=1}^n {A_i}$ you assume that the statement is true for all $k<n$.

And you partition the union to $\cup_{i=1}^k{A_i}\cup\cup_{i=k+1}^n{A_i}$

Now since both $(k<n)\land ((n-k)<n)$ induction holds and the statement is true for for $n$.

In the infinite case, however you partition the union:

$\cup_{i=1}^\infty{A_i}=\cup_{i=1}^{n}\cup\cup_{i=n+1}^\infty$

One of the partitions is always infinite so induction doesn't apply here.