# Cardinality

• Feb 8th 2009, 11:58 AM
vexiked
Cardinality
Can anyone tell me how I could show that the following set is countable?

Natural numbers and the integers not divisible by 3?
• Feb 8th 2009, 12:13 PM
Jhevon
Quote:

Originally Posted by vexiked
Can anyone tell me how I could show that the following set is countable?

Natural numbers and the integers not divisible by 3?

Recall the theorem that the union of countable sets is countable (in fact, the countable union of countable sets is countable).

note that the set we wish to prove is countable can be written as $\mathbb{N} \cup \{ 3k + 1 \mid k < 0,~ k \in \mathbb{Z} \} \cup \{ 3n + 2 \mid n < 0,~n \in \mathbb{Z} \}$

now show that each of these are countable, shouldn't be that hard. then apply the theorem

you can show a set is countable by showing that there exists a bijection between the set and the natural numbers.
• Feb 8th 2009, 02:53 PM
vexiked
I'm sorry but I don't follow. All I have to do is find a function that will ouput all integers not divisible by 3? Maybe an example would push me in the right direction. Thanks for the help!
• Feb 8th 2009, 02:58 PM
Jhevon
Quote:

Originally Posted by vexiked
I'm sorry but I don't follow. All I have to do is find a function that will ouput all integers not divisible by 3? Maybe an example would push me in the right direction. Thanks for the help!

for each set that you want to show is countable, find a one-to-one and onto function from the natural numbers to the set.

example, how to we know that the set of nonnegative even numbers is countable?

well, let E be the set of nonnegative even numbers.

the function $f: \mathbb{N} \mapsto E$ given by $f(x) = 2x$ for $x \in \mathbb{N}$ is one-to-one and onto.
• Feb 8th 2009, 03:23 PM
Moo
Hello,

You can consider only the negative integers not divisible by 3, because the positive ones would be in $\mathbb{N}$
So they're in the form $-3n-1$ and $-3n-2$, for any n in $\mathbb{N}$

Define the function :
$f(x)=\left\{\begin{array}{lll} 3x \text{ if } x \in \mathbb{N} \\
-x \text{ if } \exists n \in \mathbb{N} ~:~ x=-3n-1 \\
-x \text{ if } \exists n \in \mathbb{N} ~:~ x=-3n-2 \end{array} \right.$

prove that this is an injective function :P