I am wondering whether there is a way to prove that the set consisting of all natural numbers that are not powers of any prime is infinite. For example, 6 is such a natural number. Just to make this clear, what I mean is that any numbers that are powers of 2,3,5,7… (prime numbers) are not in the defined set. So 2,4,8 ; 3,9,27 are not in the set.
For a set to be infinite, I mean the following:
I am trying to this by proving that this set is equivalent to $ \Bbb N$ but it is really hard to find an explicit bijection. Another way to do this is that I can prove the set consisting of all natural numbers that are powers of a primes is countably infinite. But it seems that the complement of a countably infinite set in $ \Bbb N$ may not be countably infinite?
Can someone please give me a hand? Thanks.
Best Answer
$\newcommand{\Set}[1]{\left\{ #1 \right\}}$$\newcommand{\N}{\mathbb{N}}$Is there any reason why you would want an explicit bijection?
Because you can prove that your set $$ X = \Set{ x \in \N : \text{$x$ is not a power of a prime}} $$ is in a bijection with the natural numbers without making the bijection explicit.
First note that $$ n \mapsto 2 \cdot (2 n + 3) $$ is an injective map from $\N$ to your set $X$. (I have taken $2 n + 3$ so that it works whether one includes zero in $\N$ ot not.)
Then $x \mapsto x$ is an injective map $X \mapsto \N$.
This guarantees that there is a bijection $\N \to X$.