Let $A = P \cup Q$, where $P, Q$ are disjoint [1] and $P \ne \emptyset$ is countable and $Q \ne \emptyset$ is uncountable. Then $Q \subset A$ [2].

Show that $A$ is uncountable.

Proof (by contradiction):

Suppose $A$ is countable. Then there exists a bijection $f: \mathbb{N} \to A$, by definition. I.e., $f$ associates to each element in $A$ to a unique $n\in\mathbb{N}$, as follows $f(n) = a_{n}\in A$.

If $Q$ is uncountable then no bijection exists from $\mathbb{N}$ to $Q$. So no such bijection $f$ could exist for $\mathbb{N}$ to all of $A$. This is a contradiction of our supposition.

Hence, our supposition that $A$ is countable is false, so $A$ is uncountable.

Is my proof above "correct"? I feel like it's a bit circular and am not sure that the second paragraph makes sense. This is a basic question in real analysis that I got from Introductory Real Analysis by Kolmogorov and Fomin, p19.

[1] If $P,Q$ were not disjoint, we could consider $A' = (P\setminus Q) \cup Q$ which is the same as $A$ instead. [2] If $P = \emptyset$ then $Q \subseteq A$, but this is not true by hypothesis.

  • 1
    $\begingroup$ Do you think it makes a difference if $Q\subseteq A$ or $Q\subsetneq A$? Or rather, does any detail from the assumptions relevant at all other than "Let $Q$ be an uncountable set and $Q\subseteq A$. Show that $A$ is uncountable"? $\endgroup$ – Asaf Karagila Jul 15 '16 at 5:40
  • $\begingroup$ One thing that should raise red flags is: your proof seems to use the definition "$S$ countable iff exists bijection $S\to\Bbb N$," which means finite sets are uncountable. Of course the statement is false if $Q$ could be finite, but the argument seems blind to this subtlety $\endgroup$ – Eric Stucky Jul 15 '16 at 5:45
  • 2
    $\begingroup$ @Eric: It is not uncommon to find countable to apply only to infinite sets, placing finite sets in their own, separate, part of the universe. Then uncountable means not finite and not countable. $\endgroup$ – Asaf Karagila Jul 15 '16 at 5:50
  • $\begingroup$ @AsafKaragila If $P = \emptyset$ then in fact $A = \emptyset \cup Q = Q$, and since $Q$ is uncountable then $A$ is also uncountable since it is equivalent to $A$. I wrote that in because I just wanted to avoid the trivial case. $\endgroup$ – jamesh625 Jul 15 '16 at 5:57
  • 1
    $\begingroup$ Your proof pretty much assumes what is to be, which to be fair is intuitively obvious that it's hard to imagine it not being true. Usually it's shown by induction the every subset S of N is countable. Let a0 be min of subset Let S0 = S-a0. Let ai be min of Si-1. Let Si = Si-1 - ai. By induction is 1-1 with N or finite. Then let M = {n| f (n) in Q}. M is one to one with Q and is a subset of N so is coutable. So Q is countable. A contradiction. $\endgroup$ – fleablood Jul 15 '16 at 6:07

Well,consider the following: If A is countable,then we should be able to establish a bijection between A and P,yes? Assume f:$A\rightarrow P$ is a bijection from A onto P. Then there is a bijection from $P\cup Q$ onto P. Therefore, since $P,Q\neq \emptyset$,|Q|$\leq$|P|. But then P is uncountable since Q is uncountable and we have a contradiction.

This has the advantage of not bringing $\mathbb N$ directly and only using the set relations and assumptions. That's how I'd do it.

  • $\begingroup$ "Then there is a bijection from $P\cup Q$ onto $P$." I'm assuming that this makes use of the fact that there exists a bijection between any countable set and (one of) its countable subset(s). Is that correct? $\endgroup$ – jamesh625 Jul 18 '16 at 4:00
  • $\begingroup$ @jamesh625 Bingo,on da nosie.In fact,you can use the weaker condition that 2 countably infinite sets have the same cardinality and get the same result. $\endgroup$ – Mathemagician1234 Jul 18 '16 at 4:05
  • $\begingroup$ And the trolls are at it again. Don't care,know it's right. $\endgroup$ – Mathemagician1234 Jul 28 '16 at 0:45

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.