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: enter image description here

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.

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

  • $\begingroup$ Aha! Very smart answer. Thanks so much. I get it. $\endgroup$ – Y.X. 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}$.

  • $\begingroup$ Please have a look at the edited question. I have provided the definition for a set to be infinite. $\endgroup$ – Y.X. Mar 6 '17 at 11:22
  • $\begingroup$ @Y.X. : I have added some explanation. Is it clear now? $\endgroup$ – 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.

I just made the proof up right now. If there are anu fatal errors,please point it out. I will remove/edit the answer likewise.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.