1
$\begingroup$

Does this proof look fine or contain gaps? Do you have suggestions? Many thanks for your dedicated help!

Definition: A set $A$ is countable if it is finite or if there is a bijection $c:\mathbb N \to A$; otherwise it is uncountable.

If $A$ is a countable set, and each $a \in A$ is countable, then $\bigcup_{a \in A}a$ is countable.

My attempt:

Lemma 1: $A$ is countable if and only if $A=\emptyset$ or there exists a surjection from $\mathbb N$ onto $A$.

Lemma 2: $\mathbb N$ and $\mathbb N \times \mathbb N$ are equinumerous.

WLOG, we can assume that the set $A$, and each of the sets $a \in A$, is non-empty.

By Lemma 1, there exists a surjection $c: \mathbb N \to A$, and for each $m \in \mathbb N$ there exists a surjection $f_m : \mathbb N \to c(m)$ (Note that here we use the Axiom of Countable Choice).

Let $g:\mathbb N \times \mathbb N \to \bigcup_{a \in A}a$ such that $g(m,n)=f_m(n)$: we use $m$ to select an index $c(m)$ in $A$, and use $n$ to select an element of $c(m)$. Then $g$ is a surjection from $\mathbb N \times \mathbb N$ onto $\bigcup_{a \in A}a$.

Combining the previous result with Lemma 2, there exists a surjection from $\mathbb N$ onto $\bigcup_{a \in A}a$. By Lemma 1, $\bigcup_{a \in A}a$ is countable. This completes the proof.

$\endgroup$
2
  • $\begingroup$ One thing to take home: if you use the equivalent definition "$X$ is countable if and only if there is an injection $f:X\to \Bbb N$" (equivalence is easy to prove because every surjection from a well-ordered set to a set has a natural section in assigning to $y$ the least $x$ such that $f(x)=y$), then you don't need the caveat for $X=\emptyset$. $\endgroup$
    – user562983
    Sep 12, 2018 at 16:40
  • $\begingroup$ @SaucyO'Path Yes, these two definitions are equivalent. But I find it more handy with the one in my post :) $\endgroup$
    – Akira
    Sep 12, 2018 at 16:42

1 Answer 1

Reset to default
0
$\begingroup$

I would explain a bit more about why $g$ is surjective: given $x\in\bigcup A(=\bigcup_{a \in A}a)$ then then by definition there exists $B$ s.t. $x\in B\in A$ thus there exists $m\in\Bbb N$ such that $f_m:\Bbb N\to B$, and because $f_m$ is surjective there exists $n\in\Bbb N$ such that $f_m(n)=x=g(m,n)$.

Also I would end it with finding the function that will give us the countability of $\bigcup A$: by lemma 2 there exists $h:\Bbb N\to\Bbb N\times\Bbb N$ bijective thus $H=g\circ h$(or $H(x)=g(h(x))$) is surjective from $\Bbb N$ to $\bigcup A$, and by lemma 1 $\bigcup A$ is countable.(Also, both of the lemmas require a proof and are not immediate)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .