Euclid proved that there are an infinite number of prime numbers.

A composite number is a number that is a product of prime numbers. Clearly, a composite number is not a prime number, so we can think of two sets - an infinite set of prime numbers, and a set containing composite numbers with no overlap between sets.

We can make a composite number by taking any two prime numbers and multiplying them together, so let's take 2 as our first number, and the (infinite) set of prime numbers as candidates for our second number, in effect multiplying each of the numbers in the infinite set of prime numbers by 2. Each entry in the infinite set of prime numbers has a corresponding entry in the set containing composite numbers, so the set containing composite numbers is infinite as well. The set of prime numbers and the set containing composite numbers can be said to have the same cardinality.

I use the term set containing composite numbers, as there are more composite numbers than there are numbers in the set. 8, for example, is a composite number that is not in our set. This proof gives a lower bound for the cardinality of the set of all composite numbers.

Really simple proofs suggested by other people:


Any integer multiplied by 2 (a prime number) has at least two prime factors, so take the set of natural numbers (infinite), and multiply each member by 2 to produce an infinite set of composite numbers


2^n is a composite number where n is an integer greater than 2. There are infinitely many integers greater than 2, so there are infinitely many composite numbers.

Personally, I think this is a nice simple problem to introduce cardinality to people who are not too clear about mathematical notation or concepts.