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:

Brontosaurus

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

pfft

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.

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.

Log in or register to write something here or to contact authors.