Show that the set of odd integers has the same cardinality as $\{2^n\mid n\in\mathbb N\}$

Question

How do you show that the set of odd integers $(2k + 1)$ has the same cardinality as the set of positive powers of $2$ $(2^n)?$

Answer 1

This is a bijection from the integers $\mathbb{Z}$ to the odd integers: $$ f(k) = 2k + 1. $$ This is a bijection from the nonnegative integers, $\mathbb{N}$, to the positive powers of two: $$ g(n) = 2^n. $$ So, you have to show these two functions, $f$ and $g$, are bijections. Finally, you may already know that $\mathbb{Z}$ and $\mathbb{N}$ have the same cardinality, so that means all four sets have the same cardinality.

If you don't already know $\mathbb{Z}$ and $\mathbb{N}$ have the same cardinality, you could try to make a bijection between those, too.

Answer 2

This a basic application that if $A$ and $B $ have same cardinality and $B $ and $C $ have the same cardinality then $A$ and $C $ have the same cardinality.

It should be obvious that the odd integers are one to one with the naturals. (Let $a (n=2k+1)=n$ if $n>0$ and $a (n=2k+1)=2|k|$ If $n <0$ so the positive odds numbers get mapped to the positive odds, and the odd negatives get mapped to the positive evens.)

And it should be obvious that then naturals are one to one with the powers of $2$. (Let $b (n)=2^n $. So the numbers are mapped directly to the powers).

So it should be clear that the odd integers are one to one with positive powers of $2$. (Let $c=b \circ a$ so $c (2k+1)=2^{2k+1}$ if $2k+1$ is positive and $c (2k+1)=2^{2|k|} $ if $2k+1 <0$).

This will be true ALWAYS when $a:X\rightarrow Y$ is one to one and $b:Y\rightarrow Z $ is one to one then it is ALWAYS true that $b\circ a:X\rightarrow Z $ is one to one.