1
$\begingroup$

I need to prove that for countably infinite sets $A_1,A_2,...,A_m\subset\mathbb{R}$, $\bigcup A_i$ is also countable.

My Attempt: First, consider two countable sets $A_1$ and $A_2$, and define $B_2=A_2\backslash A_1=\lbrace x\in A_2 | x\notin A_1\rbrace$. We then have two cases, one where $|B_2|$ is infinite, and one where $|B_2|$ is finite. If $|B_2|$ is inifite, then $B_2$ is countable, because there exists natural numbers $n_i$ and a function $f:\mathbb{N}\rightarrow A_2$ such that $f(n_i)=b_i$ for all $b_i\in B_2$. Then, a function $g:\mathbb{N}\rightarrow B_2$ can be defined such that $g(k)=f(n_k)$, proving that $B_2$ is countable. We now prove that the union $A_1\cup B_2=A_1\cup A_2$ is countable. Because $A_1$ and $B_2$ are countable, there exists bijective functions $f_1:\mathbb{N}\rightarrow A_2$ and $f_2:\mathbb{N}\rightarrow B_2$. Let $O_k$ be the $k$th odd natural number, and $E_k$ be the $k$th even natural number. We can simply define a new funtion $g:\mathbb{N}\rightarrow A_1\cup A_2$ where $g(O_k)=f_1(k)$ and $g(E_k)=f_2(k)$. This proves that $A_1\cup A_2$ is countable for the case $|B_2|=\infty$. Next, let $|B_2|=k$ and label each element $b_1,b_2,...,b_k$. Because $A_1$ is countable, we have the same bijective function $f_1:\mathbb{N}\rightarrow A_1$. To prove that $A_1\cup B_2$ is countable. we define a new function $g:\mathbb{N}\rightarrow A_1\cup A_2$ where $g(n)=b_n$ and $g(k+n)=a_n$ for all $a_n\in A_1$. This completes the proof.

I would like to know first if this proof is correct, and second if there is a more efficient way to write all of this.

$\endgroup$
1
$\begingroup$

With a cursory examination, it looks like the OP's proof is in the ballpark. They asked for a proof that would be more efficient, so here we will highlight the main ideas found in the OP's proof, presented as a logical progression.

In what follows we do not assume that our sets are contained in $\mathbb R$.

Proposition 1: If $A_1$ and $A_2$ are two disjoint countably infinite sets, then the union $A_1 \cup A_2$ is countably infinite.
Proof:
Let $F_1: \mathbb N \to A_1$ and $F_2: \mathbb N \to A_2$ be bijective mappings, where $\mathbb N = \{0, 1, 2, \dots, n, \dots \}$. Define $F: \mathbb N \to A_1 \cup A_2$ as follows:

$$ F(m) = \left\{\begin{array}{lr} F_1(\frac{m}{2}), & \text{for even } m \in \mathbb N\\ F_2(\frac{m+1}{2}-1), & \text{for odd } m \in \mathbb N \end{array}\right\} $$ It is easy to check that $F$ describes a bijective correspondence. $\quad \blacksquare$

The following sequence of 'add-on' propositions are not difficult to prove:

Proposition 2: Let $A_1$ and $A_2$ be any two sets. Then there exist a set $B$ satisfying the following:

$\tag 1 B \subset A_1 \text{ and } B \subset A_2$

$\tag 2 A_1 \cup A_2 \text{ is the disjoint union } (A_1 \backslash B) \cup B \cup (A_2 \backslash B)$

Proposition 3: If $A_1$ is a countably infinite set and $A_2$ is any finite set, then the union $A_1 \cup A_2$ is countably infinite..

Proposition 4: Any subset of a countably infinite set is either finite or countably infinite.
Proof (sketch)
Use the lemma found here.

Proposition 5: The union of a finite number of finite sets is finite.

We now prove the main proposition.

Proposition 6: The union of any two countably infinite sets $A_1$ and $A_2$ is countably infinite.
Proof:
By proposition 2, 4 & 5, $A_1 \cup A_2$ can be written as a disjoint union

$\tag 3 C_1 \cup B \cup C_2$

where each of the sets is either countably infinite or finite, and at least one of the sets is countably infinite.

By using the commutativity and associativity laws of the union operation and proposition 1 and/or proposition 3, we can simplify (3) in two steps so that a single countably infinite set remains that is equal to $A_1 \cup A_2$. $\quad \blacksquare$


The OP might want answer this question again at some point using the following:

Theorem: If $f$ is a surjective function from $\mathbb N$ onto a set $A$, then $A$ is either finite or countably infinite.

$\endgroup$
  • 1
    $\begingroup$ I am sure that the Abbott book is referring to just the case where both sets are countably infinite. Will make edit in post. $\endgroup$ – 高田航 Apr 12 '18 at 11:42
2
$\begingroup$

Assume all the sets are infinite and disjoint. Convince yourself that this is the worst case; if their union is countable we are done.

I'll go beyond set theory using just very elementary facts about positive integers: (i) there are infinitely many prime numbers (ii) a number that is a power of one prime number can not be the power of another prime number (unique factorization theorem).

Let $p_1,p_2,p_3\ldots$ be the list of prime numbers in the increasing order.

Let $P_j = \{p_j^k\mid k \mbox{ a positive integer}\}$ consist of all powers of the $j$th prime. Clearly the sets $P_j$ are disjoint and are all countably infinite. And $\bigcup_{j=1}^\infty P_j$ is a (proper) subset of positive integers and hence is countable.

Now take your sets $A_1,A_2,\ldots, A_m$.

By countability hypothesis we can list the elements of $A_j$ as $\{a_{j1}, a_{j2},\ldots\}$ Now we can set up bijections this way: $f_j\colon A_j\to P_j$ by $f(a_{jk}) = p_j^k$ for each $j=1,2\ldots, m$.

So the union of $A_j$ has the same cardinality as the union of $P_j$'s and the latter is countable.

This proof works even in the case of countably many countable sets.

$\endgroup$
1
$\begingroup$

I'm not sure I follow your argument exactly but it does seem that you are not using the proper definition of countability. A set $S$ is countable if there is an $\textit{injection}$ $S\rightarrow\mathbb{N}$, not a $\textit{bijection}$. This is why, for example, a finite set is countable. It's also unclear to me that you aimed to prove the original claim; it seems you only proved it for two sets. Furthermore, because of this you wrote all of your functions going $\textit{from}$ $\mathbb{N}$ rather than $\textit{to}$ it, which seems more natural.

The way I would prove it is as follows: prove it for two sets, then use induction. Call the two sets $A$ and $B$. We can assume without loss of generality that they are disjoint (if not, replace them by $A$ and $B\setminus A$). Since they are both countable, we can write $$A=\{a_{1},a_{2},...\}$$ $$B=\{b_{1},b_{2},...\}$$ Note that if one or both of $A, B$ is finite, the labeling above will eventually stop i.e. you can write them all down. Clearly if $A, B$ are both finite their union is finite, hence countable. I claim that if one is countable and the other is finite, their union is countable. See if you can prove this.

The trickier case is when both are countable. You seem to have the write idea about even and odd indices. Given the labeling above, define a function $f: A\cup B\rightarrow\mathbb{N}$ by $$f(a_{k}) = 2k-1$$ $$f(b_{k}) = 2k$$ This is clearly injective, which proves that $A\cup B$ is countable. Note that injectivity relies on the assumption that $A, B$ were disjoint, which is why I made that assumption above.

The inductive hypothesis is simple: if the claim holds for $m-1$ sets then it must hold for $m$ sets because $$A_{1} \cup ... \cup A_{m} = (A_{1}\cup...A_{m-1})\cup A_{m}$$

$\endgroup$
  • $\begingroup$ In my textbook "Understanding Analysis" by Stephen Abbott, it defines countability by $f:\mathbb{N}\rightarrow A$ instead of the other way around. Also, I proved it for two sets because if $A_1\cup A_2 = B$ is countable, then the $B\cup A_3$ is simply another union of two sets, and so on. $\endgroup$ – 高田航 Apr 11 '18 at 20:55
1
$\begingroup$

The cardinality of the intersection of any two countably cardinal sets may range from zero (when the sets are disjoint) to the minimum cardinality of the two sets (when one set is a subset of the other).   Likewise we can establish the minimum and maximum cardinality for the union of any two such sets.

The union of any two countably cardinal sets must have at least a countable cardinality by definition of union.   The cardinality of the union cannot be less than something because reasons.

We can (by definition of something) map elements of one of the sets to (finite or infinite) countable many even natural numbers, and likewise the other to countable many odd natural numbers, so the union of any two countably cardinal sets must have at most the cardinality of the natural numbers; which is by definition countable.

You may now use induction to show the result of a union of finitely many such sets.

$\endgroup$

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.