Let, $\mathbb{P}$ be the set of prime numbers. We know that $\mathbb{P}$ has a bijection with set of Naturals $\mathbb{N}$. That is, $\mathbb{P} \stackrel{}{\longleftrightarrow} \mathbb{N}$.

Again, we can easily see that $2^{\mathbb{P}}$ has a bijection to set $\displaystyle W = \{ x | x = \prod_{p \in A} p, ~s.t.~ A \subseteq \mathbb{P} \}$ is a subset of set of composite numbers.

That is, $ 2^\mathbb{P} \stackrel{}{\longleftrightarrow} W \subset ( N\setminus\mathbb{P})$.

So, we reach to a strange result which shows that, set of composite numbers is uncountable!

  • 1
    $\begingroup$ What composite number $x$ do you get when $A$ is the set of all prime numbers? $\endgroup$
    – bof
    Jun 27, 2016 at 10:14
  • 1
    $\begingroup$ Well, I don't think that we consider infinity as a composite number. $\endgroup$ Jun 27, 2016 at 10:14
  • 3
    $\begingroup$ In such arguments the error usually is found in the neighborhood of words like easily, obviously, certainly etc... $\endgroup$
    – Maik Pickl
    Jun 27, 2016 at 10:17
  • 1
    $\begingroup$ The bijection is not from the set of all subsets of primes, but from the set of all finite subsets of primes. The former is uncountable, but the latter is countable. $\endgroup$
    – Aravind
    Jun 27, 2016 at 10:19
  • $\begingroup$ Thank you all I got the answer. Yes, the neighter last bijection is true, nor W is a subset of N, because it contains infinity. $\endgroup$ Jun 27, 2016 at 10:38

2 Answers 2


There are (at least) two errors. The less consequential one is that $W\not\subset(\mathbb N\setminus\mathbb P)$, since the one-element subsets of $\mathbb P$ lead to $W$ containing all prime numbers. The more consequential one is that $2^{\mathbb P}$ is only uncountable because it contains the infinite subsets of $\mathbb P$, but your definition of $W$ doesn't work for those.


Consider $A=\{p\in\mathbb{P}:p>2\}$, the set of all odd primes. What natural number is $\prod_{p\in A}p$?

If you are able to answer this question and to do the same for all subsets of $\mathbb{P}$, then you have really found an inconsistency in set theory, assuming of course that this definition of infinite products of primes gives an injection.

To be more precise:

  1. you should assign a meaning to $\prod_{p\in A}p$, for every subset $A$ of $\mathbb{P}$, as a natural number in order to have a function $f\colon 2^{\mathbb{P}}\to\mathbb{N}$;

  2. you have to show that the function $f$ is injective.

Neither step 1 nor step 2 is dealt with in your argument.

In case $A$ is a finite subset of $\mathbb{P}$, the product $\prod_{p\in A}p$ makes sense. On the other hand, $\mathbb{P}$ has plenty of infinite subsets and your attempt at an argument fails.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .