# What's wrong with this proof of the infinity of primes?

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?

-
How many powers of $2$ are there? – Andrés E. Caicedo Aug 6 '14 at 6:08
Does anyone else find it strange that this question recieved a close vote? – 5xum Aug 6 '14 at 6:13
@ 5xum Uh,yeah,I do-I didn't think it was THAT dumb a question! – Mathemagician1234 Aug 6 '14 at 6:18
@Mathemagician1234 The question is good and the votes for closing are really incomprehensible. – egreg Aug 6 '14 at 19:36
I wonder how difficult it would be to prove that given n primes, the set of products of these primes must have an asymptotic density less than 1? – gnasher729 Aug 6 '14 at 23:03

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$$

-
There you go. There's one problem-I ruled out repeated products by the same prime without explicitly saying so. Told you it was trivial. I knew it simply couldn't be that easy. There are probably other problems with my "proof"-let's see what other people come up with. But that's good and quick. – Mathemagician1234 Aug 6 '14 at 6:09
@Mathemagician1234 There are really no other problems. If the statement "a finite number of primes can only generate a finite number of composites" would be true, then your proof would be correct. – 5xum Aug 6 '14 at 6:12
Well, if one would rule out repeated products, the number of composites that can be formed from $n$ distinct primes would only be $2^n-(n+1)$ and not $n!$. – Maarten Hilferink Aug 6 '14 at 11:37
@Maarten Hilferink Thanks for the clarification on that point-you're absolutely right. I always did suck at combinatorics............ – Mathemagician1234 Aug 6 '14 at 17:23

Note that $\{2^n\mid n\in\Bbb N^+\}$ is countably infinite, but it has only one prime number which is the unique prime divisor of all the numbers in this set.

-
Awesome, in the space of 30 seconds, a comment and two answers containing the exact same idea appeared. Nice.:) – 5xum Aug 6 '14 at 6:09
(Faster by $7$ seconds...) – Andrés E. Caicedo Aug 6 '14 at 6:09
Both you guys can also clock the time difference on the comments. :-) – Asaf Karagila Aug 6 '14 at 6:09
OK, that was funny. – Andrés E. Caicedo Aug 6 '14 at 6:10
@Asaf 5x's answer was faster by 7 seconds,but yours was more ELEGANT. So nyah.........lol – Mathemagician1234 Aug 6 '14 at 6:13

The error is in stating that there are only a finite number of possible products of primes from a list of $n$ distinct primes. You are forgetting about products with repeated prime factors.

-
Okay, I see that this is a duplicate answer. Should have read more carefully before posting, sorry. – MPW Aug 6 '14 at 6:13
3 answers basically saying the same f*** up on my part. Nice.............lol – Mathemagician1234 Aug 6 '14 at 6:14
Don't sweat it, we've all done something like this at some point. Look at it like this: you'll be aware of this pitfall in the future. :) – MPW Aug 6 '14 at 6:20
"This is only true if each prime could only be used once..." Even then, the number would not be $n!$ – leonbloy Aug 6 '14 at 20:31
@leonbloy: Yeah. I'll modify my statement. The important thing is that OP isn't allowing for repeated factors. – MPW Aug 6 '14 at 20:46

The other answers are correct, of course, but I can't help but feel they're pussyfooting around the the real issue, which is that the fundamental theorem of arithmetic is about multisets of natural numbers.

Fundamental Theorem of Arithmetic. For all $n \in \mathbb{N} \setminus \{0\}$, there is a unique finite multiset of prime numbers whose product is $n$.

Now let $P$ denote the set of all prime numbers. If we assume that $P$ is finite, call its cardinality $P$, then its true that $P$ has $2^n$ subsets. But it can still have infinitely many finite multisets. e.g.

$$\{2\}, \{2,2\}, \{2,2,2\}, \ldots$$

-
No, it is not true. $n!\ne 2^n$. (Or, more precisely, $2^n-1$, since presumably we do not want to include $1$, the empty product.) – Andrés E. Caicedo Aug 7 '14 at 0:52
(Or $2^n-n-1$ if we further require that the products result in composite numbers.) – Andrés E. Caicedo Aug 7 '14 at 0:53
@AndresCaicedo, true. So where on earth did $n!$ come from? – goblin Aug 7 '14 at 0:59
@AndresCaicedo, actually we do want to include the empty product in the fundamental theorem, since this is the prime factorization of $1$. – goblin Aug 7 '14 at 1:01
(Yes, but the phrasing of the "argument", the talk of the two finite sets indicates that the poster either forgot the existence of $1$, or is deliberately excluding it.) – Andrés E. Caicedo Aug 7 '14 at 1:05

That proof appears almost deliberately confusing.

The logical proof is very simple: There are an infinite number of numbers, therefore there are an infinite number of subsets. Any unbounded subset has an infinite quantity of members.

On the other hand, I can paraphrase an old anti-proof:

There are an infinite number of numbers. But not all numbers are primes, therefore there must be a finite number of primes. Any number divided by infinity is zero, therefore there are no prime numbers.

-
I don't think my arguement was THAT logically flawed,peter. I never assumed there were no infinite subsets of the positive integers-a bizarre thing to assume in any event! – Mathemagician1234 Aug 7 '14 at 4:30