31
$\begingroup$

I cannot figure out what is wrong:

We will attempt to show that $\mathcal{P} (\mathbb{N})$ is countable. We use the following corollary from Rudin's Principles of Mathematical Analysis, p. 29:

Suppose $A$ is at most countable, and, for every $\alpha\in A$, $B_{\alpha}$ is at most countable. Put

$$T=\bigcup_{\alpha \in A}B_{\alpha}$$

Then $T$ is at most countable.

"Proof" 1:

Let $A = \mathbb{N}$ and for every $\alpha \in A$ let $B_{\alpha}=\{S \in \mathcal{P} (\mathbb{N})| \text{the sum of the elements of } S \text{ is } \alpha \}$. $A$ is countable and for every $\alpha \in A$, $B_{\alpha}$ is finite. Therefore

$$\bigcup_{\alpha \in A}B_{\alpha}$$

is countable. But $\displaystyle \bigcup_{\alpha \in A}B_{\alpha}=\mathcal{P} (\mathbb{N})$, so $\mathcal{P} (\mathbb{N})$ is countable.


"Proof" 2:

Let $A= \mathbb{N}$ and for every $\alpha \in A$ let $B_{\alpha}=\{ S \in \mathcal{P} (\mathbb{N}): |S| = \alpha \}$. I think that I can show by induction (if requested) that for each $\alpha \in A$, $B_{\alpha}$ is countable. Thus

$$\bigcup_{\alpha \in A}B_{\alpha}$$

is countable. But again, $\bigcup_{\alpha \in A}B_{\alpha} = \mathcal{P} (\mathbb{N})$

$\endgroup$
  • 20
    $\begingroup$ In both cases, the union of the $B_{\alpha}$ is the set of finite subsets of $\mathbb{N}$ (which is indeed countable, and this is indeed a correct proof of that fact). $\endgroup$ – Qiaochu Yuan Dec 18 '17 at 1:22
  • 5
    $\begingroup$ Can the downvoter please explain? $\endgroup$ – Ovi Dec 18 '17 at 1:25
  • 5
    $\begingroup$ Yeah, I am tired of the billion questions all involving the same misunderstanding of Cantor, and further many posters (not all) cannot be reasoned with. So I downvote all such questions. Maybe you should read some of the other answers. $\endgroup$ – Rene Schipperus Dec 18 '17 at 1:28
  • 13
    $\begingroup$ @ReneSchipperus Nobody can dictate to you how to use your votes, but the Help Center says "Use your downvotes whenever you encounter an egregiously sloppy, no-effort-expended post, or an answer that is clearly and perhaps dangerously incorrect." I don't think my question falls into any of those categories. Additionally, I don't think my question is a duplicate and I fail to find another where the poster had the same misunderstanding (just an oversight rather) as me. $\endgroup$ – Ovi Dec 18 '17 at 1:47
  • 17
    $\begingroup$ Rene Schipperus. You are right. How dare anybody who doesn't understand mathematics ask a question about mathematics on a mathematics help site. I'm tired of people not as perfect as I am wasting mine but not their own time in the pointless purpose of attempting to learn something they don't understand. $\endgroup$ – fleablood Dec 18 '17 at 3:27
54
$\begingroup$

In both your "proofs", it is not true that $\displaystyle \bigcup_{\alpha \in A}B_{\alpha}=\mathcal{P} (\mathbb{N})$. Indeed, if $S\in\mathcal{P}(\mathbb{N})$ is any infinite set, then $S$ is not in any $B_\alpha$ (by either definition).

What both your arguments show correctly is that the set of all finite subsets of $\mathbb{N}$ is countable.

$\endgroup$
  • 1
    $\begingroup$ Ah got it thanks! $\endgroup$ – Ovi Dec 18 '17 at 1:24
  • 5
    $\begingroup$ @Ovi: Furthermore, this fact is important, because similarly the set of all finite sequences of naturals is countable, such as when counting the number of integer polynomials. $\endgroup$ – user21820 Dec 18 '17 at 2:33
  • 2
    $\begingroup$ @user21820 Yes, then we have shown that the set of algebraic numbers is countable. $\endgroup$ – Jeppe Stig Nielsen Dec 18 '17 at 11:09
  • 3
    $\begingroup$ @JeppeStigNielsen: Right. And similarly that there are countably many computable reals, and also countably many definable reals regardless of how powerful one's foundational system is. $\endgroup$ – user21820 Dec 18 '17 at 11:15
  • 2
    $\begingroup$ @user21820 It is consistent that all reals are definable, so it is not provable that there are only countably many definable reals. See this MathOverflow answer: mathoverflow.net/q/44129 (The other statements are correct.) $\endgroup$ – Robert Furber Dec 18 '17 at 17:41

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.