20
$\begingroup$

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?

$\endgroup$
12
  • 24
    $\begingroup$ How many powers of $2$ are there? $\endgroup$ Aug 6, 2014 at 6:08
  • 10
    $\begingroup$ Does anyone else find it strange that this question recieved a close vote? $\endgroup$
    – 5xum
    Aug 6, 2014 at 6:13
  • $\begingroup$ @ 5xum Uh,yeah,I do-I didn't think it was THAT dumb a question! $\endgroup$ Aug 6, 2014 at 6:18
  • 1
    $\begingroup$ @Mathemagician1234 The question is good and the votes for closing are really incomprehensible. $\endgroup$
    – egreg
    Aug 6, 2014 at 19:36
  • 1
    $\begingroup$ 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? $\endgroup$
    – gnasher729
    Aug 6, 2014 at 23:03

5 Answers 5

38
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 6, 2014 at 6:09
  • 1
    $\begingroup$ @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. $\endgroup$
    – 5xum
    Aug 6, 2014 at 6:12
  • 10
    $\begingroup$ 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!$. $\endgroup$ Aug 6, 2014 at 11:37
  • $\begingroup$ @Maarten Hilferink Thanks for the clarification on that point-you're absolutely right. I always did suck at combinatorics............ $\endgroup$ Aug 6, 2014 at 17:23
22
$\begingroup$

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.

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

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.

$\endgroup$
5
  • $\begingroup$ Okay, I see that this is a duplicate answer. Should have read more carefully before posting, sorry. $\endgroup$
    – MPW
    Aug 6, 2014 at 6:13
  • $\begingroup$ 3 answers basically saying the same f*** up on my part. Nice.............lol $\endgroup$ Aug 6, 2014 at 6:14
  • 2
    $\begingroup$ 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. :) $\endgroup$
    – MPW
    Aug 6, 2014 at 6:20
  • $\begingroup$ "This is only true if each prime could only be used once..." Even then, the number would not be $n!$ $\endgroup$
    – leonbloy
    Aug 6, 2014 at 20:31
  • $\begingroup$ @leonbloy: Yeah. I'll modify my statement. The important thing is that OP isn't allowing for repeated factors. $\endgroup$
    – MPW
    Aug 6, 2014 at 20:46
3
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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.) $\endgroup$ Aug 7, 2014 at 0:52
  • $\begingroup$ (Or $2^n-n-1$ if we further require that the products result in composite numbers.) $\endgroup$ Aug 7, 2014 at 0:53
  • $\begingroup$ @AndresCaicedo, true. So where on earth did $n!$ come from? $\endgroup$ Aug 7, 2014 at 0:59
  • $\begingroup$ @AndresCaicedo, actually we do want to include the empty product in the fundamental theorem, since this is the prime factorization of $1$. $\endgroup$ Aug 7, 2014 at 1:01
  • $\begingroup$ (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.) $\endgroup$ Aug 7, 2014 at 1:05
-1
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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! $\endgroup$ Aug 7, 2014 at 4:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .