0
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Right, that's the set of all complex numbers. Perhaps more explanation is needed as to why the cardinality of composites isn't that of the power set of primes. $\endgroup$
    – KeithS
    Dec 4, 2014 at 17:36
  • $\begingroup$ +1 for I will also say that using $\Bbb C$ for the set of composite numbers is not a good notation. $\endgroup$ Dec 4, 2014 at 17:37
  • $\begingroup$ @Keith: You talk about products of two primes, that's $\Bbb P^2$, not $2^{\Bbb P}$. $\endgroup$
    – Asaf Karagila
    Dec 4, 2014 at 17:57
  • $\begingroup$ Two or more; 3*5*7 = 105, which is a composite number not produced by the product of two primes. A number can be produced by any subset of P with cardinality > 1. $\endgroup$
    – KeithS
    Dec 4, 2014 at 18:31
  • $\begingroup$ @Keith: Yes, but what composite number is the product of all prime numbers, which is certainly an element of $2^{\Bbb P}$? $\endgroup$
    – Asaf Karagila
    Dec 4, 2014 at 18:41

You must log in to answer this question.

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