# Logical contradiction regarding cardinality of sets - help resolve

Consider the set of all natural numbers, $\mathbb{N}$. This set is composed of two subsets, the set of all primes, we'll call $\mathbb{P}$, and the set of all composite numbers (non-primes), $\mathbb{C} = \mathbb{N}-\mathbb{P}$.

A composite number is by definition the product of one or more prime numbers. There are, therefore, at least as many composites as there are unique combinations of 2 or more primes (and this is not including numbers whose factorizations include powers of primes, where multiplicity of those primes in the subset would be > 1). So, the cardinality of the set of all composite numbers must not be less than that of the power set of primes minus the cardinality of the set of primes (because the power set includes all subsets of cardinality 1), $|\mathbb{C}| >= 2^{|\mathbb{P}|} - |\mathbb{P}|$.

Now, the cardinality of the set of all primes is $\aleph_0$, because the set of all primes is a subset of the set of all natural numbers, and is itself infinite, therefore it must be at least $\aleph_0$ and cannot be more than $\aleph_0$ because it cannot be of greater cardinality than its containing set.

That would cause $|\mathbb{C}| = 2^{\aleph_0} - \aleph_0 = \beth_1 - \aleph_0 \equiv \beth_1$. But, we can say the same of the set of composite numbers that we could of primes; being a subset of natural numbers, there can be no more than $\aleph_0$ of them because there are "only" $\aleph_0$ naturals.

Only one can be right and it's obviously that the cardinality of all three sets is $\aleph_0$. So where's the fallacy in the logic behind the composites being on the order of the power set of primes?

Your mistake is by saying that $|\Bbb C|\geq 2^{|\Bbb P|}$, where it should be $|\Bbb C|\geq|\Bbb P|^2$.
I will also say that using $\Bbb C$ for the set of composite numbers is not a good notation.
• +1 for I will also say that using $\Bbb C$ for the set of composite numbers is not a good notation. Dec 4, 2014 at 17:37
• @Keith: You talk about products of two primes, that's $\Bbb P^2$, not $2^{\Bbb P}$. Dec 4, 2014 at 17:57
• @Keith: Yes, but what composite number is the product of all prime numbers, which is certainly an element of $2^{\Bbb P}$? Dec 4, 2014 at 18:41