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.
Best Answer
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.