0
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ Are you using countable to mean countably infinite, or are you using it as most set theorists do to mean finite or countably infinite? $\endgroup$ – Brian M. Scott Nov 17 '13 at 21:35
  • 1
    $\begingroup$ @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. $\endgroup$ – Asaf Karagila Nov 17 '13 at 21:39
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

$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.

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

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.