# Prove that there are infinitely many natural numbers that are not powers of any prime.

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.

• $p q$, for $p$ and $q$ distinct primes? – Andreas Caranti Mar 6 '17 at 11:07
• If $n$ is odd, $n >1$, can $2n$ be a power of a prime? – quasi Mar 6 '17 at 11:07
• What do you mean by giving a hand??? – sgrmshrsm7 Mar 6 '17 at 11:08
• @Sagar Mishra: The phrase "give me a hand" is an idiom. It means "help me" (e.g., "help me up"). – quasi Mar 6 '17 at 11:10
• p*(p+1) for any prime? – Eric Duminil Mar 6 '17 at 12:56

$\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$. • Aha! Very smart answer. Thanks so much. I get it. – PropositionX Mar 6 '17 at 11:44 From your example, you can get$6^1$,$6^2$, etc. Thus you can set up a one-to-one correspondence$\Bbb N\to\{6^{n+1}:n\in\Bbb N\}:n\mapsto 6^{n+1}$. • Please have a look at the edited question. I have provided the definition for a set to be infinite. – PropositionX Mar 6 '17 at 11:22 • @Y.X. : I have added some explanation. Is it clear now? – John Bentin Mar 6 '17 at 12:49 If i understand your question correctly, your set is defined as :$S = n \in \mathbb N | n \ne p^q$for any prime$p$and positive integers$q$It is sufficient to prove that a subset of$S$is infinite. Consider the subset$P = n!, n \in \mathbb N, n\ge 3$clearly, it satisfies your condition that they are not the powers of a single prime. Now suppose we have a set$T = [1,2,....,n]$such that$P(T) = n$for some natural n. ($P(T)$denotes the cardinality of set$ T$). For there to exist a bijection$f: P \to T, P(T) = P(P)$. But clearly,$(n+4)! \in P$. Which means that the cardinality of$P$is at least$(n+4) -3 =n+1$. Thus there cannot exist any bijection,for any natural$n$. Thus,$P$is an infinite set. Since,$P \subset S$,$S\$ is also infinite.