Predicate to prove a set is countably infinite

Question

Hi I have this question and have been struggling to find an answer.

Prove that the set of numbers which are powers of 2 (i.e. $\{1, 2, 4, 8, 16, 32, \ldots\}$) is a countably infinite set.

Not sure if I've been over thinking it but I've been trying it for the last week and haven't got anywhere with it.

Answer 1

Hint: $f:\mathbb N \rightarrow A, f(n)=2^n$ is a bijection, where $A=\{1,2,4,8,..\}$

Assuming $\mathbb N$ contains zero.

Answer 2

Define $f: \mathbb{N} \to \mathbb{N}: n \mapsto 2^n$. This is a bijection $\mathbb{N} \to \{2^n: n \in \mathbb{N}\}$. Thus the cardinality of the set of numbers of powers of two is the same as that of the natural numbers. That is, both are countably infinite.

In general, to show that some set is countable, construct an injection to $\mathbb{N}$. Of course an bijection works to.

Answer 3

This question has two parts:

1. Is the set infinite?
2. Is the set countable?

Number 1. you can do by contradiction, much like how Euclid proved that there are infinitely many primes. For 2., the definition of countable is that there exists a one-to-one function from your set to the integers. Inclusion is such a function in this case.