2
$\begingroup$

I would appreciate feedback on whether the specific contradiction I make is valid in my attempt to prove that there are infinitely many primes, this on a conceptual level. For context, I subsequently saw a correct proof which was very similar, but worked through this before and have some issues with my "proof" which I will describe in a bit. This is my reasoning:

  1. First, I assume that there is a finite number of primes, in order to show how a contradiction is implicated from this. If there are a finite number of primes, there must be a greatest prime number P.
  2. Consider the integer Q, which is formed by taking the product of every prime number, including P.
  3. Q+1 cannot have a prime factor, as none of the prime factors of Q can be factors of Q+1: this is because the difference between Q and Q+1 would have to be divisible by a prime factor of Q for Q+1 to be divisible by the same factor, which is not possible.
  4. Using the fact that all natural numbers greater than one are either prime or have a prime divisor, I conclude that Q+1 is prime.
  5. Q+1 is larger than P, contradicting the fact that P is the largest prime number. Therefore, the hypothesis from which this contradiction followed (that there is a finite number of primes) is false.

I am wondering if this works or if we would need to have a direct proof if we wanted to use this reasoning, which says for every prime number P, we can construct a greater prime number. This is because I am unsure whether it is correct for us to identify a greatest prime number and then construct an even greater prime number right afterwards- this feels like it was not legitimate to even say Q+1 is greater than P, as when we assumed a greatest prime number Q+1 could have been that number. This has made me wonder if the contradiction I have built is a legitimate contradiction, as P and Q could be the exact same quantity, but due to a fallacy in reasoning I have deemed them distinct.

thanks

$\endgroup$
11
  • 6
    $\begingroup$ Your argument is okay, and in essence the same given by Euclid. But you do not have to prove it by contradiction: show that given any finite collection of primes, there is a prime not in the collection, by taking their product and adding one, the argument you are using. This shows no finite set of primes contains all primes, so the set of primes is infinite. $\endgroup$ May 27, 2023 at 6:00
  • 2
    $\begingroup$ You only need that every integer $N>1$ is divisible by a prime number (it does not matter that in practice we might be unable to determine a prime factor , the existence is crucial and safe). The proof of this Lemma is easy : The set of divisors $d>1$ of $N$ is non-empty ($N$ always does the job). Hence there is a smallest such divisor. This must be a prime since otherwise we could find an even smaller such divisor. $\endgroup$
    – Peter
    May 27, 2023 at 6:10
  • 2
    $\begingroup$ And then , you take the product of a collection of primes and add $1$. The resulting integer is greater than $1$ hence must be divisible by a prime , and this prime cannot be in the collection. That's it. $\endgroup$
    – Peter
    May 27, 2023 at 6:11
  • 2
    $\begingroup$ No, the argument I outline is not a proof by contradiction. You never assume that your list is vomprehensive. The proof is "Given any finite set of primes, there is a prime not in the set". There is no reason to assume the set has "all" primes, as that assumption is never needed nor used. $\endgroup$ May 27, 2023 at 14:58
  • 2
    $\begingroup$ Adding an unnecessary contrary hypothesis just for the sake of saying at the end "which is a contradiction" is bad proof practice. It's logically valid, but it is bad practice. If you have a perfectly valid proof of "if $A$ then $B$", and you convert it into a "proof by contradiction" by saying "Assume $\mathrm{not}(B)$." then repeating the proof that "if $A$, then $B$", and then saying "but this contradicts our assumption that $\mathrm{not}(B)$, therefore $B$ holds", then you are adding unnecessary, complicating and potentially confusing arguments to a perfectly fine proof. (cont) $\endgroup$ May 27, 2023 at 19:28

2 Answers 2

2
$\begingroup$

This is because I am unsure whether it is correct for us to identify a greatest prime number P and then construct an even greater prime number Q right afterwards- this feels like it was not legitimate to even say Q is greater than P, as when we assumed a greatest prime number, Q could have been that number.

I added a few labels to your above description, but it is still confusing, but I think what you are trying to say is that you feel that a particular derivation step is being illogical or disrespecting a particular premise that you have set up, because it is apparently contradicting that premise.

You needn't worry, because in your proof I only see valid inference/derivation steps (notwithstanding the typos in your points 4 and 5 where I think Q is meant to be Q+1), and that the contradiction(s) are surfacing in spite of them, not due to them.

Also, in case relevant: given a premise A, we can make separate valid arguments; if A happens to be false, then it is natural that we may obtain some true conclusions and some false conclusions.

$\endgroup$
0
0
$\begingroup$

... use this reasoning, which says for every prime number P, we can construct a greater prime number.

It does not say that. It proves that we can construct a greater prime number if we assume that there are only a finite number of primes. You cannot extract this claim from under that assumption - its proof relies on that assumption.

$\endgroup$
1
  • $\begingroup$ It does not rely on that. Take a prime $P$. Multiply all (positive) primes up to $P$ and add $1$. The result is divisible by some prime greater than $P$. Now, I would quibble with this being a "construction" (though you can expand it into an algorithm that actually produces such a prime). But you do not need to assume that there are only finitely many primes. The argument only uses that (unnecessary) assumption to contradict it at the end of the proof by contrapositive, not in any intermediate step. $\endgroup$ May 28, 2023 at 5:50

You must log in to answer this question.

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