1

Show using a proper theorem that the set {2, 3, 4, 8, 9, 16, 27, 32, 64, 81, … } is a countable set.

Im lost, this is for school, but there is a huge language barrier between students and professor. I have started it but have no idea if how i have started it is even right.

I set E = {2, 3, 4, 8, 9, 16, 27, 32, 64, 81, … n} I made a set N = {1, 2, 3, 4, 5, 6, 7, 9, 10,... n} .. to show theres a bijection

I then make a bijection... i dont even know if thats what im supposed to do bijection={(2,1),(3,2),(4,3),(8,4),(9,5),(16,6),(27,7),(32,8),(64,9),(81,10),(n,n)}

Im not exactly what to do next. Im wondering if i should make an equation to prove that its countable, and if so what would that equation be.

Any help would be appreciated thank you

Sampson
  • 9
  • 1
    Exactly what elements are in the set? Chances are that once you describe that, you have automatically built a bijection between your set and ${\mathbb N}$. – Magdiragdag Oct 29 '13 at 21:00
  • 2
    There is a theorem that says every subset of a countable set is countable, and $E \subset \mathbb {N}$ is countable. – Wmmoreno Oct 29 '13 at 21:04

2 Answers2

7

First you have to sort out exactly what the set $E$ is. It appears that $$E=\{2^n:n\in\Bbb Z^+\}\cup\{3^n:n\in\Bbb Z^+\}\;,$$ the set of positive integers that are positive powers of $2$ or of $3$. To show that $E$ is countably infinite, you need to find a bijection (one-to-one and onto map) between $E$ and $\Bbb Z^+$, the set of positive integers. The following diagram suggests one way to do it.

$$\begin{array}{rll} n:&1&2&3&4&5&6&\dots\\ e_n:&2&3&2^2&3^2&2^3&3^3&\dots \end{array}$$

In other words, this is a systematic listing of $E$ indexed by the positive integers: $e_1=2$, $e_2=3$, $e_3=2^2=4$, $e_4=3^2=9$, and so on. To finish the job, you need to express this correspondence precisely.

Can you come up with a regular rule for calculating $e_n$ if you know $n$? It’s perfectly acceptable for your rule to have two separate subrules, one for odd $n$ and one for even $n$.

Brian M. Scott
  • 616,228
1

I suppose you must write it in a more specific way. Your set consists of a mix of two sequences, one having general term $2^n$ the other $3^n$ for $n\in\mathbb N$. So maybe something like $$ f(k)=\frac{1-(-1)^k}{2}\cdot 2^{(k+1)/2}+\frac{1+(-1)^k}{2}\cdot 3^{k/2} $$ Computation of $f(k)$ for $k=1,2,...,20$ by Wolfram Alpha

And by the way: good luck finding the inverse!

String
  • 18,395