While reviewing an online textbook in abstract algebra for my website—which I'm hoping will go live by the end of the month—one of the exercises in the book inspired me to produce a simple, set theoretic proof of the infinity of primes. But it looks wrong! I can't say why exactly—but something looks off about it! If anyone can spot what's wrong with it, let me know, I'm too tired to think of it now. If it's NOT wrong, well, you get to publish that for free, go ahead, I won't fight you for credit. But boy, I'd be shocked if no one ever thought of this and it's correct!
There are countably infinite positive integers by definition. Decompose the positive integers into the following partition: the set of all primes and the set of all composite positive integers. Assume there are finitely many primes. Then there must be infinitely many composite positive integers because a union of finitely many finite sets is finite. By the fundamental theorem of arithmetic, each composite must be a unique product of primes. Since there is a finite number of primes, let's say $n$ primes, then there are at most $n!$ products of primes. Therefore, there must be at most n! composite positive integers. But that means the positive integers are a union of 2 finite sets and must be finite and this is a contradiction!
There has to be something wrong with this proof, but for the life of me I can't see what it is right now. I'm probably going to kick myself when someone points it out—it's probably something really trivial.
Any takers?
Best Answer
There is something wrong with your proof. You claim that since there are only $n$ primes, there are only $n!$ composite numbers, which is not true. Even a single prime, $2$ for example, produces infinitely many composites:
$$2,4,8,16,32,\dots, 2^n, \dots$$