4 ms·

Not all proofs are constructive. For example, Euclid’s classic proof that any finite set of primes is incomplete doesn’t actually tell you what the next one is.

zaarn 7y ago
Yes that is correct but that's not what I was talking about in earlier comments, which were exclusively about example-based proof/disproof.
- thaumasiotes 7y ago
  If you're not talking about proof/disproof, you might want to look for a different word.
  - zaarn 7y ago
    I was unware there is only one type of proof or that it is not allowed to talk only about specific types of proof.
    - ColinWright 7y ago
      You said: > Yes that is correct but that's not what I was talking about in earlier comments, which were exclusively about example-based proof/disproof.[0] In reply, thaumasiotes said: > If you're not talking about proof/disproof, you might want to look for a different word.[1] Now you say: > I was unaware there is only one type of proof or that it is not allowed to talk only about specific types of proof.[2] Based on your comment [0] above, your comments were apparently about a specific type of proof, and yet the words you used did not make that qualification clear. In particular, statement [0] says you were restricting the type of proof you were considering. Reply [1] above is suggesting that if you are only talking about a restricted type of proof then you might want to use a word other that "proof", because you are not talking about proofs in general. Your comment [2] seems to have missed the point. You yourself in [0] said you were restricting your type of proof. You're allowed to talk about anything you like, but if you use the word "proof" without qualifying it, but you intend only to be talking about a specific type of proof, don't then be surprised if people misunderstand you.
rytill 7y ago
Is that proof not constructive? While you aren’t constructing the sequence of all primes, you are constructing some infinite set of primes to prove that there are infinite primes.
- DavidSJ 7y ago
  I doesn’t construct only primes. If p1, p2, ..., pn are prime, then p1p2...pn + 1 is not divisible by any of them, but it may not be prime itself.
  - a1369209993 7y ago
    Then you haven't proved a additional prime; you still need the (trivial[0]) step of breaking down 1+Πp into its one or more prime factors. And then you've constructed a (or several) prime not in the original set. 0: Trivial in the logical sense (try every number up to √(1+Πp)), but computationally impractical, thus left as a exercise for the reader.
    - thaumasiotes 7y ago
      You don't need that; you can proceed purely through generalities. 1. 1+Πp is congruent to 1 (mod p) for every prime p. 2. This conflicts with the definition of "prime number"; all composite numbers must be congruent to 0 (mod p) for some prime p. Only the empty product can be congruent to 1 (mod p) for every p. This is already sufficient to prove that the number of primes is not finite -- we derived a contradiction from that premise without demonstrating any additional primes. (Note that -- within the proof, where we've assumed a finite list of primes -- it's easy to show that 1+Πp is itself prime (since it has no prime divisors less than itself). You can then declare a contradiction with the premise, as it isn't in the original list. However, you can only show that it's prime by using the earlier contradiction, so while this step makes the proof more intuitive, it isn't actually necessary.)

zaarn 7y ago

Yes that is correct but that's not what I was talking about in earlier comments, which were exclusively about example-based proof/disproof.

thaumasiotes 7y ago
If you're not talking about proof/disproof, you might want to look for a different word.
- zaarn 7y ago
  I was unware there is only one type of proof or that it is not allowed to talk only about specific types of proof.
  - ColinWright 7y ago
    You said: > Yes that is correct but that's not what I was talking about in earlier comments, which were exclusively about example-based proof/disproof.[0] In reply, thaumasiotes said: > If you're not talking about proof/disproof, you might want to look for a different word.[1] Now you say: > I was unaware there is only one type of proof or that it is not allowed to talk only about specific types of proof.[2] Based on your comment [0] above, your comments were apparently about a specific type of proof, and yet the words you used did not make that qualification clear. In particular, statement [0] says you were restricting the type of proof you were considering. Reply [1] above is suggesting that if you are only talking about a restricted type of proof then you might want to use a word other that "proof", because you are not talking about proofs in general. Your comment [2] seems to have missed the point. You yourself in [0] said you were restricting your type of proof. You're allowed to talk about anything you like, but if you use the word "proof" without qualifying it, but you intend only to be talking about a specific type of proof, don't then be surprised if people misunderstand you.

rytill 7y ago

Is that proof not constructive? While you aren’t constructing the sequence of all primes, you are constructing some infinite set of primes to prove that there are infinite primes.

DavidSJ 7y ago
I doesn’t construct only primes. If p1, p2, ..., pn are prime, then p1p2...pn + 1 is not divisible by any of them, but it may not be prime itself.
- a1369209993 7y ago
  Then you haven't proved a additional prime; you still need the (trivial[0]) step of breaking down 1+Πp into its one or more prime factors. And then you've constructed a (or several) prime not in the original set. 0: Trivial in the logical sense (try every number up to √(1+Πp)), but computationally impractical, thus left as a exercise for the reader.
  - thaumasiotes 7y ago
    You don't need that; you can proceed purely through generalities. 1. 1+Πp is congruent to 1 (mod p) for every prime p. 2. This conflicts with the definition of "prime number"; all composite numbers must be congruent to 0 (mod p) for some prime p. Only the empty product can be congruent to 1 (mod p) for every p. This is already sufficient to prove that the number of primes is not finite -- we derived a contradiction from that premise without demonstrating any additional primes. (Note that -- within the proof, where we've assumed a finite list of primes -- it's easy to show that 1+Πp is itself prime (since it has no prime divisors less than itself). You can then declare a contradiction with the premise, as it isn't in the original list. However, you can only show that it's prime by using the earlier contradiction, so while this step makes the proof more intuitive, it isn't actually necessary.)