# Denumerable sets...

• May 2nd 2009, 09:46 PM
Danneedshelp
Denumerable sets...
Let A, B, and C be disjoint denumerable sets. Show that A∪B∪C is also denumerable.

Given: A≈N, B≈N, and C≈N. Goal:A∪B∪C≈N

Suppose A,B, and C are non-empty disjoints sets such that A≈N, B≈N, and C≈N. Then, there exists functions f:A→N, g:B→N, and h:C→N that are one-to-one and onto N.

This is where my understanding kinda falls apart...Do have to set some knda of restriction? I can't find many examples in my book of this kind of stuff. Actaully, I'm probably just not making the connection.
• May 3rd 2009, 04:47 AM
Plato
Quote:

Originally Posted by Danneedshelp
Let A, B, and C be disjoint denumerable sets. Show that A∪B∪C is also denumerable.

There are three bijections: $\alpha :A \Leftrightarrow \mathbb{N}\;,\;\beta :B \Leftrightarrow \mathbb{N}\;\& \;\chi :C \Leftrightarrow \mathbb{N}$.
Define a new function $\Phi :A \cup B \cup C \mapsto \mathbb{N}\;,\;\Phi (x) = \left\{ {\begin{array}{lr}
{2^{\alpha (x)} ,} & {x \in A} \\
{3^{\beta (x)} ,} & {x \in B} \\
{5^{\chi (x)} ,} & {x \in C} \\ \end{array} } \right.$

You must show that the function, $\Phi$, is well-defined and is an injection.
• May 3rd 2009, 11:19 AM
Danneedshelp
Suppose Φ(x)=Φ(y). We see that x and y must have same parity for or else Φ(x)≠Φ(y). So, suppose x,y∈A. Then, plugging into the definition Φ(x)=2^∝(x)=2^∝(y)=Φ(y). ln(2^∝(x))=ln(2^∝(y)) ⇒ ∝ln(2)x=∝ln(2)y ⇒ x=y. Therefore, Φ(x) is injective when x∈A.
Let y be an element of the codomain. By our definition y=2^∝(x). Solving for x we get x=ln(y)/∝ln(2) when y>0. Now, f(ln(y)/∝ln(2))=2^∝(ln(y)/∝ln(2))=y for y∈N. Thus, Φ(x) is surjective.

Then I proceed to go down the list?
• May 3rd 2009, 11:29 AM
Plato
Quote:

Originally Posted by Danneedshelp
By our definition y=2^∝(x). Solving for x we get x=ln(y)/∝ln(2) when y>0. Now, f(ln(y)/∝ln(2))=2^∝(ln(y)/∝ln(2))=y for y∈N. Thus, Φ(x) is surjective.

Absolutely not! The function $\Phi$ is of course not surjective.
But it does not have to be in order to prove the theorem.
All one has to do to prove a set is denumerable is to show that it is infinite and exhibit an injection from the set to $\mathbb{N}$.
• May 3rd 2009, 12:49 PM
HallsofIvy
Plato's method works, of course, but I had a different idea. Since A is countable, there exists a function N->A that is one-to-one and countable so each member of A can be "labeled" $a_n$. Similarly, members of B and C can be "labeled" $b_n$ and $c_n$. Now define a function from N to the union of A, B, and C by $f(3n)= a_n$, $f(3n+1)= b_n$, and $f(3n+2)= c_n$. It is easy to show that function is bijective.
• May 5th 2009, 11:26 PM
Danneedshelp
Quote:

Originally Posted by HallsofIvy
Plato's method works, of course, but I had a different idea. Since A is countable, there exists a function N->A that is one-to-one and countable so each member of A can be "labeled" $a_n$. Similarly, members of B and C can be "labeled" $b_n$ and $c_n$. Now define a function from N to the union of A, B, and C by $f(3n)= a_n$, $f(3n+1)= b_n$, and $f(3n+2)= c_n$. It is easy to show that function is bijective.

Could you maybe expand on this? I am not sure how I would write out the new function H:N⇒A∪B∪C? Would I just list them like piece wise functions?