6
$\begingroup$

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.enter image description here

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

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ A question of the form "Why can't $X$ be used to prove $Y$" is hard to answer, since it might not be obvious to others why this should appear possible. More could perhaps be said if you tell us how you'd suggest to carry out the proof by induction. $\endgroup$ – joriki Jul 27 '16 at 12:09
  • $\begingroup$ "Here is an example where induction is being used in the context of countably infinite sets." heh, heh. No, it's not! This is using induction on countably finite sets. That's why the hint "$h = n+ a_0 + [a_1] + [a_2]+...+[a_n]$ is finite" is essential. $\endgroup$ – fleablood Jul 27 '16 at 16:42
  • $\begingroup$ Rudin does avoids refering to $\infty$ as though it has any property of natural number, and successfully so in my opinion. In proving the countable union he doesn't use induction (which is extremely tempt as any union of two is uncountable so any finite union can be reduced to a single set--- but not infinite union can without circular reasoning). Instead Rudin has a direct proof. $\endgroup$ – fleablood Jul 27 '16 at 19:38
  • $\begingroup$ Short answer: induction can not work because there is no point where n finite but n + 1 = infinite. I don't see where you think Rudin implied this. $\endgroup$ – fleablood Jul 27 '16 at 19:55
4
$\begingroup$

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

|cite|improve this answer
$\endgroup$
2
$\begingroup$

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.]

|cite|improve this answer
$\endgroup$
  • $\begingroup$ To be sure this is the crux of the problem. Rudin's description appears to suggest the two are same - especially as N is countably infinite. Note for the finite case he uses small n and not N. $\endgroup$ – pythOnometrist Jul 27 '16 at 15:49
  • $\begingroup$ (as you used to represent the finite case). $\endgroup$ – pythOnometrist Jul 27 '16 at 15:55
  • 1
    $\begingroup$ @fleablood It is very subtle, but the axiom of choice is needed. Rudin’s proof of his Theorem 2.12 starts as: “Let every set $E_n$ be arranged in a sequence $\{x_{nk}\}$, $k=1,2,3,\ldots$” He chooses infinitely enumerations all at once, thus he recurs to the axiom of choice. Indeed, the negation of the axiom of choice is known to be consistent with $\mathbb R$ (which can be shown to be uncountable without the axiom of choice) being a countable union of countable sets! $\endgroup$ – triple_sec Jul 28 '16 at 5:27
  • 1
    $\begingroup$ Triple_sec. Ah. I see. Maybe. Axiom of choice is pretty damn ed subtle. $\endgroup$ – fleablood Jul 28 '16 at 17:23
  • 1
    $\begingroup$ @fleablood In fact, choice is involved. For each countable set, there exist many enumerations and we are required to pick one particular enumeration for each set. We have to do this countably infinitely times all at once. I know the possibility of doing this sounds almost trivial, but this possibility is precisely what the axiom of choice is all about! $\endgroup$ – triple_sec Jul 28 '16 at 23:41
0
$\begingroup$

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?

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Agreed - the point though is not whether this can be proved another way. The point is to clarify why induction does not apply here. $\endgroup$ – pythOnometrist Jul 27 '16 at 15:54
  • $\begingroup$ Well if not even induction is needed in the proof, I don't get the point. Logically it seems that induction suffices if I don't need it? On the other hand I would probably use induction to show that every $A_k={\mathbb Q}^k$, $k\geq 1$ is countable, and therefore that polynomials with rational coefficients (union of $A_k$) is countable. But anyway,... $\endgroup$ – H. H. Rugh Jul 27 '16 at 16:49
  • $\begingroup$ "Well if not even induction is needed in the proof, I don't get the point" Me neither, Especially as no-one did use induction. It's very tempting to try to use induction and even today I'd probably mistakenly do so if I hadn't been warned. As Uncountable U Uncountable = Uncountanble U_i Uncountable U Uncountable = Un U Un = Un is compelling that all uncountable can be reduced to two uncountable. But it doesn't work as we never ever get U_n uncountable U uncoun = U_infinity uncountable. $\endgroup$ – fleablood Jul 27 '16 at 19:53
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
-1
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I see no reason to downvote this response! $\endgroup$ – Rafael Vergnaud May 31 '18 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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