# How can I define a function to show that $\{3^n\mid n\in\mathbb{Z}\}$ is countably infinite?

I have to answer the following question for an assignment:

Is the set $A=\{3^{n}\mid n\in\mathbb{Z}\}$ finite, countably infinite, or uncountable?

I've defined what I originally thought to be a proper function rule showing a bijection from $\mathbb{N}$ to $A$, but I've since realized that I'm missing some elements in the codomain.

\begin{equation*} f:\mathbb{N}\to A:\left\{ \begin{array}{ll} n\mapsto 3^{n},&\text{if $n=2k-1$ for some $k\in\mathbb{N}$}\\ n\mapsto 3^{-n},&\text{if $n=2k$ for some $k\in\mathbb{N}$} \end{array}\right. \end{equation*}

Here, I noticed that I'm missing all the odd negative numbers and all the even positive numbers.

Is this even doable this way, or do I need to draw a diagram?

I'd much prefer to have a function definition if possible.

-
Almost tautologically $|A|=|\Bbb Z|$. – Pedro Tamaroff Mar 10 '13 at 4:23
Do you know that $\mathbb{Z}$ is countably infinite? If so it's straightforward. Let $f$ be a bijection from $\mathbb{N}$ to $\mathbb{Z}$. Then map each $n \in \mathbb{Z}$ onto $3^n$. Now compose. – anonymous Mar 10 '13 at 4:31

For every $n \in \mathbb Z$, there exists a unique $f(n) \in A$ as defined. That is, and for every number of the form $3^n$, there exists unique $n \in \mathbb Z$ such that $f(n) = 3^n$

The function is a bijection: one-to-one and onto. Hence there is a one-to-one correspondence between $A$ and $f(n) = 3^n, \;\;\forall n \in \mathbb Z$

Therefore: $\quad|A| = |\mathbb Z|$

We know $\mathbb Z$ is countably infinite, hence so must be $A$.

We can also work to find a bijection between $A$ and $\mathbb{N}$, by adjusting your attempt just a bit:

You're definition, with a few adjustments, will work nicely for defining a bijection from $\mathbb{N}$ to $A$.

Consider

$$f:\mathbb{N}\to A: \begin{cases} {n\to 3^{\Large\frac{(n-1)}{2}}};& n=2k-1,& k\in\mathbb{N} \\ \\ { n\to 3^{\Large-\frac{n}{2}}}; & n=2k,& k\in\mathbb{N} \\ \\ \end{cases}$$

Therefore $|A| = |\mathbb N|$ which means since $\mathbb N$ is countably infinite, so must be set $A$.$\quad\square$

-
But this doesn't show a bijection from $\mathbb{N}$... I'm confused. – agent154 Mar 10 '13 at 4:27
$|\mathbb N| = |\mathbb Z|$. – amWhy Mar 10 '13 at 4:30
Ohh.. ok, I think I see now - But I think for the purposes of this assignment, it'd be more work to do it this way because I'd have to show not only this, but I'd have to demonstrate that $\mathbb{Z}$ is countably infinite first. – agent154 Mar 10 '13 at 4:31
I've defined the bijection from the naturals to the set A: every natural number gets mapped to A, and every element in A has some natural number mapped to it. So it's a nice bijection. Let me know if this helps! ;-) – amWhy Mar 10 '13 at 19:27
agent154 Let me know if you're okay with this question/my answer. Any questions? Try out any integer n you please, you'll cover all the bases for you bijection from N to A! ;-) – amWhy Mar 11 '13 at 4:01

You're almost there. What if you tried \begin{equation*} f:\mathbb{N}\to A:\left\{ \begin{array}{ll} n\mapsto 3^{(n-1)/2},&\text{if $n=2k-1$ for some $k\in\mathbb{N}$}\\ n\mapsto 3^{-n/2},&\text{if $n=2k$ for some $k\in\mathbb{N}$} \end{array}\right. \end{equation*}

-
I like that - didn't think to divide the exponent by two. – agent154 Mar 10 '13 at 4:33

You have the right idea for a mapping in the other direction I think. The negatives to evens, and the positive to odds is a good idea. Consider this $f:A\to \mathbb N$ such that$$f(3^n)=\begin{cases} 2n+1, &n\geq0\\ -2n, &n<0 \end{cases}$$

-