Too complicated,

gentlemen, too complicated! Why bring cardinality into it when you don't even really need to think?

**Definitions:** A composite number *x* is defined as a number with one or more factors not equal to *x* or 1.

**First, Really Simple Proof**

2 divides 4. (arithmetical fact)
For some real number z, if 2 divides z,
and z is not equal to 2, z is composite.
(by the definition of composite).

One such value of z is 4, by the earlier statement. Therefore at least one composite number exists.

Let y = z / 2. Since 2 divides z, 2y = z and y is an integer.

z' = 2 * (y+1) is a composite number, with two factors beside itself.

Given any even composite number, another composite number can be found. QED.

Proving cardinality has more interesting implications.

Products of two primes have the same cardinality as prime numbers, provably. Here's why:

Stack the products of known prime numbers into a grid, as follows:

p1*p1 p1*p2 p1*p3 p1*p4 ...
p2*p1 p2*p2 p2*p3 p2*p4 ...
p3*p1 p3*p2 p3*p3 p3*p4 ...
p4*p1 p4*p2 p4*p3 p4*p4 ...
. . . .
. . . .
. . . .

This proof mirrors the proof of why the sets of rational numbers, integers, and natural numbers have the same cardinality.

In order to assign a one-to-one correlation between primes and this set, we make it countable by moving over the grid in the following order:

1267
358b
49a-

Counting from 1 up to 9, then a up to b. This grid allows us to assign an integer value to each number in the grid, in a way that will never leave a number out.

Therefore, prime numbers and products of two primes have the same cardinality.

This grid can be expanded into three dimensions, with a similar pattern (although the geometry gets ugly around four dimensions) to prove that the product of *n* primes has the same cardinality as the set of primes. However, this doesn't solve the basic problem.

There's a much simpler way to solve that one, I admit with some embarrasment after coming up with the earlier proof. Composite numbers and prime numbers are positive integers, and can be written like this:

PRIME 2 3 5 7 11 13 17 ...
COMPOSITE 1 4 6 8 9 10 12 ...

The correlation can be seen visually here, making the whole process much simpler. The set of prime numbers has the same cardinality as the set of composite numbers, which is the same as that of integers, natural numbers, or rational numbers.