While I understand the classic proof-by-contradiction which is usually given to prove that there exist infinitely many primes, I am wondering whether one could argue instead like this. I understand that there is probably something very clearly wrong that I am missing however I'm not sure exactly what.

(1) Assume there are finitely many primes.

(2) Then there would be a finite number of natural numbers; since every natural number is the product of primes, there wouldn't be enough primes to produce every natural number.

(3) Since we don't accept that there are a finite number of natural numbers, we should not accept that there are an finite number of primes.

  • 3
    $\begingroup$ There are an infinite number of powers of $2$. $\endgroup$ – Chappers Oct 1 '15 at 3:55
  • 2
    $\begingroup$ 2) would be true only if you are allowed to use each prime once. Of course, that is not the case. Regardless, if you take the definition of infinite to mean "not finite", then the classical proof is not proof by contradiction. It is a direct proof for the claim "the number of primes is not finite". $\endgroup$ – Ittay Weiss Oct 1 '15 at 3:57
  • $\begingroup$ Okay nice. Both comments are good explanations for why the proof doesn't work. Neither were considerations I'd thought of so thanks. $\endgroup$ – letsmakemuffinstogether Oct 1 '15 at 4:00

You are not limited to using each prime once in any prime factorization, so you could have a finite number of primes and still have an infinite number of natural numbers.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.