# Proving sets A and B are countable

a) Let A and B be disjoint sets, which are both countable. Prove that $A$ U $B$ is also countable.

b) Use part (a) to show that the set of all irrational real numbers is not countable.

So for part a I understand that disjoint sets share no elements in common (other than the empty set). I tried to get a visual understanding and did: A = {1,2,3} and B = {4,5,6}.

I drew myself a diagram and realized that I can map each element in each set to a natural number, so there it has the same cardinality as the natural numbers, which implies it is countable. How can I do this as a formal proof? $A+B = N$?

• Are you using countable to mean countably infinite, or are you using it as most set theorists do to mean finite or countably infinite? – Brian M. Scott Nov 17 '13 at 21:35
• @Brian: Interestingly enough, in the course I'm teaching right now "countable" means only infinite. Somewhat surprised me to hear that, as the professor giving the course is a renowned [retired] set theorist. – Asaf Karagila Nov 17 '13 at 21:39

HINT: If $A$ and $B$ are countably infinite, there are bijections $a:A\to\Bbb N$ and $b:B\to\Bbb N$. Now modify these to get a map $a'$ that maps $A$ bijectively onto the even natural numbers and a map $b\,'$ that maps $B$ bijectively onto the odd natural numbers. Then combine $a'$ and $b\,'$ into a single bijection from $A\cup B$ to $\Bbb N$.

HINT: Can you find two disjoint subsets of $\Bbb N$ both of which are infinite?

a) $A$ and $B$ are countable means that there are injections $f:A\hookrightarrow\Bbb N,\ g:B\hookrightarrow\Bbb N$. Then you can merge these by defining $h:A\cup B\to\Bbb N$

$h(a):=2f(a)$ (always even) and $h(b):=2g(b)+1$ (always odd)

It's easy to show that $h$ is injective, and, as $A\cap B=\emptyset$, is well defined.

b) $\Bbb R=\Bbb Q\cup\{$irrationals$\}$ and $\Bbb Q$ is countable while $\Bbb R$ is not.

A set is countable if there is a bijection between it and a finite set or between it and $\mathbb{N}$.

(a) you have three cases: A and B are finite, just one of them is finite, both of them are not finite

1. let n be the cardinality of A be n and the one of B m. Then you have a bijection $f : \lbrace 0 , \ldots , n-1 \rbrace \rightarrow A$ and a bijection $g : \lbrace 0 , \ldots , m-1 \rbrace \rightarrow B$. You can patch them and build a function $h : \lbrace 0 , \ldots , n+m-1 \rbrace \rightarrow A \cup B$, defined as $h \left( x \right) = f \left( x \right)$ if $x \geq n-1$, $h \left( x \right) = g \left( x - n \right)$ otherwise. It is easy to check it is a bijection.

2. without loss of generality suppose A is finite and B not. Then you have bijections $f : \lbrace 0 , \ldots , n-1 \rbrace \rightarrow A$ and $g : \mathbb{N} \rightarrow A$. Now you can patch this way: $h : \mathbb{N} \rightarrow A \cup B$ with $h\left(x \right) = f \left( x \right)$ if $x \geq n-1$ and $h \left( x \right) = g\left( x-n \right)$ otherwise. Then you check in the same way as above.

3. now both of the sets are not finite. Now you have $f: \mathbb{N} \rightarrow A$ and $g: \mathbb{N} \rightarrow B$. Define $h: \mathbb{N} \rightarrow A \cup B$ as follows: if $x$ is even write $x=2y$ and define $h \left( 2y \right) = f \left( y \right)$, if $x$ is odd write $x=2y+1$ and define $h \left( 2y+1 \right) = g \left( y \right)$.

(b) It is known $\mathbb{Q}$ is countable and $\mathbb{R}$ is not. If the irrational numbers (i.e. $\mathbb{R} - \mathbb{Q}$) were countable, then by (a) also $\mathbb{R}$ would be countable, which is a contradiction.

$E$ =even

$O$=odd

$A$ is infinitely countable then there is a bijection $f:A\to \Bbb E$.

$B$ is infinitely countable then there is a bijection $g:B\to \Bbb O$.

Then the map $h:A\cup B\to \Bbb N$ with $h(x)=f(x),x\in A$

$h(x)=g(x),x\in B$

is a bijection.

So $Q\cup I=\Bbb R$. $\Bbb R$ is uncountable $Q$ is countable then $I$ is uncountable.

• You have a typo, $g:B\to\mathbb O$. – Martin Argerami Nov 17 '13 at 22:19
• @MartinArgerami Thanks:) – Haha Nov 17 '13 at 22:40