4 ms·

At undergrad, a successful technique is to assume X exists and try to construct it. As you do so, you either find one or reach a contradiction to every possible

At undergrad, a successful technique is to assume X exists and try to construct it. As you do so, you either find one or reach a contradiction to every possible class of structure. Nonconstructive proofs of existence in rare, outside of logic classes. Most branches of undergrad math aren't interested in mere existence

thaumasiotes 11y ago
The famous proof that the primes are infinite is a nonconstructive existence proof. And weirdly, it proceeds entirely by trying to construct a new prime. It just fails to do so (well, sort of) while still invalidating the idea of an upper bound.
- darkmighty 11y ago
  Might one say it's a constructive proof of the non-existence of a finite group of primes?
  - thaumasiotes 11y ago
    You can't have a constructive non-existence proof. What would it mean to construct something that doesn't exist?
- OscarCunningham 11y ago
  It is constructive, because it relies on the fact that p_1p_2...p_n + 1 has a prime factor, and to prove this you repeatedly split it into factors until you reach a prime. And so when you consider all the parts of the proof you find that you have in fact constructed another prime.
  - thaumasiotes 11y ago
    I don't understand what you're saying. You don't prove that p_1p_2...p_n + 1 has a prime factor (how would you do that?) -- you postulate it. The proof is done as soon as you observe that the number you've constructed must have a prime factor greater than p_n. It's not necessary to construct the prime factor, although I guess it's possible to do so.
    - ColinWright 11y ago
      There are several things you've said here that would worry me if said by an undergrad. You must have a new prime because the number you construct has a prime decomposition, and that prime decomposition cannot use any of the prunes you started with. And your collection so far need not contain all primes so far, so the new prime need not be bigger than the ones you already have, so you can not, as you claim, observe that the number you've constructed must have a prime factor greater than p_n. It may be that you were just being informal, but statements like this coming from an undergrad would make me start to investigate how secure their knowledge really is.
      - thaumasiotes 11y ago
        Here's the proof I learned: 1. Assume there is no prime number larger than p_n. 2. Compute the product of all the prime numbers less than or equal to p_n, plus one. Call this number c. 3. By construction, no prime number less than or equal to p_n divides c. 4. But all integers greater than one have one or more prime factors. (This is not proven.) 5. Therefore, since c has no prime factors less than or equal to p_n, it must have one which is not less than or equal to p_n, or in other words c must have a prime factor greater than p_n, which contradicts step (1). Viewing https://en.wikipedia.org/wiki/Euclid%27s_theorem https://en.wikipedia.org/wiki/Euclid%27s_theorem, I see that Euclid's original proof doesn't involve using all the primes within a certain range ("your collection so far need not contain all primes so far"), so what you've said here does apply to it. However, I also read: > Euclid is often erroneously reported to have proved this result by contradiction, beginning with the assumption that the set initially considered contains all prime numbers, or that it contains precisely the n smallest primes, rather than any arbitrary finite set of primes. So I don't feel too bad about referring to the proof I gave above as "the famous proof". I didn't call it "the proof that appears in Euclid's Elements". Since this result is by contradiction, there are several different points where you could choose to observe the contradiction. But you can certainly do it before you actually produce a new prime.
        ColinWright 11y ago
        In step 1 you haven't assumed that you know all the primes up to p_n, and then in step 2, you assume that you do have them. If you don't make step 1 more precise, saying that you know all the primes up to p_n, then when you multiply them all together and add 1, step 3 fails. The point is that the proof is fairly robust, and yet stating it all completely correctly is actually quite hard. Here is a more correct version: We know there are at least some primes. For example, 3 is prime. Take any non-empty finite collection of primes. Multiply them all together, and add 1. The result may not be prime, but it is expressible as the product of primes, and hence there is at least one prime that divides it. That prime cannot be one of the primes in our finite collection, and hence any finite collection of primes does not contain them all. The classic counter-examples used when there are proof with holes are these: Consider the set of primes { 3, 5 }. Multiply them together and add 1, and all the primes that divide the result are less than the primes you have. Starting with 2 and then repeatedly getting a new prime by multipying and adding 1 we get 3, then 7, then 43, but 2.3.7.43+1 = 13.139. Finally, taking known successive primes we get "failure" at: 2.3.5.7.11.13+1 = 59.509 And as an addendum, I've heard this before, but a few days ago Carl Pomerance told me of a joke he heard from Henrik Lenstra. Here's a proof that there are infinitely many composites: 4 is composite, 6 is composite. Suppose by way of contradiction that the set of all composites is finite. Multiply them all together and don't add 1! That's a new composite, hence contradiction. QED.
- Dylan16807 11y ago
  I was going to say it's constructive but apparently the wording matters. this version is nonconstructive: assume you have all primes -> multiply, add one -> contradiction this version is constructive: you have n primes -> multiply plus one is always a new prime
  - panic 11y ago
    This constructive version doesn't work, though. The "new prime" 2×3×5×7×11×13 + 1 actually equals 59×509.
    - makomk 11y ago
      All of its prime factors are in fact new primes though - the constructive proof just requires you to use the prime factors of all the primes multiplied together, plus one.
    - Dylan16807 11y ago
      Right, sorry, I should have said it gives you a new prime (or more), not that it is a new prime.
  - thaumasiotes 11y ago
    As panic pointed out, the nonconstructive proof you outline is valid, but the constructive "proof" is fallacious. You could modify the standard proof to construct a new prime, but that wouldn't be the famous proof. The modification amounts to doing a bunch of extra work after you've already finished the proof.
    - Dylan16807 11y ago
      It's still constructive, you just have to change a word. That you insist on dismissing the method entirely baffles me. I'm sorry that I didn't remember it off the top of my head. Factoring is not a huge burden compared to the earlier steps, and also not necessary a lot of the time, especially if your goal is to keep feeding the number back into the system to create numbers made out of new primes.
pervycreeper 11y ago
>Nonconstructive proofs of existence in rare Not so sure about that. I'd also dispute that they are inherently more difficult (assume X doesn't exist... )
- mturmon 11y ago
  I have to agree with you. There are plenty of times in math classes where I've been assured that "Theorem 1 guarantees that there exists a unique solution...", but where this solution is in no sense easily known. As an example, a maximizer of some convex function over a convex set. Sure, it exists, but constructing it is another matter! As another example, solutions to differential equations of a given form. The form guarantees a solution exists, but the solution may difficult to pin down. One more example: Borel sets. Hmm, now that I'm going: the square root of 2. It is a number that satisfies a simple property, but constructing it is considerably more difficult.
mafribe 11y ago
It's a useful technique not just for undergraduates. Here are two famous computer science examples. * Dana Scott discovered the lattice based model of the λ-calculus while trying to prove that no set theoretic models exist. This put functional programming on the map. * Volker Strassen found his fast matrix multiplication while trying to show that the traditional O(n^3) is optimal. This might have been the first or one of the first non-trivial and unexpected innovations that came from the then new field of computational complexity.

thaumasiotes 11y ago

The famous proof that the primes are infinite is a nonconstructive existence proof. And weirdly, it proceeds entirely by trying to construct a new prime. It just fails to do so (well, sort of) while still invalidating the idea of an upper bound.

darkmighty 11y ago
Might one say it's a constructive proof of the non-existence of a finite group of primes?
- thaumasiotes 11y ago
  You can't have a constructive non-existence proof. What would it mean to construct something that doesn't exist?
OscarCunningham 11y ago
It is constructive, because it relies on the fact that p_1p_2...p_n + 1 has a prime factor, and to prove this you repeatedly split it into factors until you reach a prime. And so when you consider all the parts of the proof you find that you have in fact constructed another prime.
- thaumasiotes 11y ago
  I don't understand what you're saying. You don't prove that p_1p_2...p_n + 1 has a prime factor (how would you do that?) -- you postulate it. The proof is done as soon as you observe that the number you've constructed must have a prime factor greater than p_n. It's not necessary to construct the prime factor, although I guess it's possible to do so.
  - ColinWright 11y ago
    There are several things you've said here that would worry me if said by an undergrad. You must have a new prime because the number you construct has a prime decomposition, and that prime decomposition cannot use any of the prunes you started with. And your collection so far need not contain all primes so far, so the new prime need not be bigger than the ones you already have, so you can not, as you claim, observe that the number you've constructed must have a prime factor greater than p_n. It may be that you were just being informal, but statements like this coming from an undergrad would make me start to investigate how secure their knowledge really is.
    - thaumasiotes 11y ago
      Here's the proof I learned: 1. Assume there is no prime number larger than p_n. 2. Compute the product of all the prime numbers less than or equal to p_n, plus one. Call this number c. 3. By construction, no prime number less than or equal to p_n divides c. 4. But all integers greater than one have one or more prime factors. (This is not proven.) 5. Therefore, since c has no prime factors less than or equal to p_n, it must have one which is not less than or equal to p_n, or in other words c must have a prime factor greater than p_n, which contradicts step (1). Viewing https://en.wikipedia.org/wiki/Euclid%27s_theorem https://en.wikipedia.org/wiki/Euclid%27s_theorem, I see that Euclid's original proof doesn't involve using all the primes within a certain range ("your collection so far need not contain all primes so far"), so what you've said here does apply to it. However, I also read: > Euclid is often erroneously reported to have proved this result by contradiction, beginning with the assumption that the set initially considered contains all prime numbers, or that it contains precisely the n smallest primes, rather than any arbitrary finite set of primes. So I don't feel too bad about referring to the proof I gave above as "the famous proof". I didn't call it "the proof that appears in Euclid's Elements". Since this result is by contradiction, there are several different points where you could choose to observe the contradiction. But you can certainly do it before you actually produce a new prime.
      - ColinWright 11y ago
        In step 1 you haven't assumed that you know all the primes up to p_n, and then in step 2, you assume that you do have them. If you don't make step 1 more precise, saying that you know all the primes up to p_n, then when you multiply them all together and add 1, step 3 fails. The point is that the proof is fairly robust, and yet stating it all completely correctly is actually quite hard. Here is a more correct version: We know there are at least some primes. For example, 3 is prime. Take any non-empty finite collection of primes. Multiply them all together, and add 1. The result may not be prime, but it is expressible as the product of primes, and hence there is at least one prime that divides it. That prime cannot be one of the primes in our finite collection, and hence any finite collection of primes does not contain them all. The classic counter-examples used when there are proof with holes are these: Consider the set of primes { 3, 5 }. Multiply them together and add 1, and all the primes that divide the result are less than the primes you have. Starting with 2 and then repeatedly getting a new prime by multipying and adding 1 we get 3, then 7, then 43, but 2.3.7.43+1 = 13.139. Finally, taking known successive primes we get "failure" at: 2.3.5.7.11.13+1 = 59.509 And as an addendum, I've heard this before, but a few days ago Carl Pomerance told me of a joke he heard from Henrik Lenstra. Here's a proof that there are infinitely many composites: 4 is composite, 6 is composite. Suppose by way of contradiction that the set of all composites is finite. Multiply them all together and don't add 1! That's a new composite, hence contradiction. QED.
Dylan16807 11y ago
I was going to say it's constructive but apparently the wording matters. this version is nonconstructive: assume you have all primes -> multiply, add one -> contradiction this version is constructive: you have n primes -> multiply plus one is always a new prime
- panic 11y ago
  This constructive version doesn't work, though. The "new prime" 2×3×5×7×11×13 + 1 actually equals 59×509.
  - makomk 11y ago
    All of its prime factors are in fact new primes though - the constructive proof just requires you to use the prime factors of all the primes multiplied together, plus one.
  - Dylan16807 11y ago
    Right, sorry, I should have said it gives you a new prime (or more), not that it is a new prime.
- thaumasiotes 11y ago
  As panic pointed out, the nonconstructive proof you outline is valid, but the constructive "proof" is fallacious. You could modify the standard proof to construct a new prime, but that wouldn't be the famous proof. The modification amounts to doing a bunch of extra work after you've already finished the proof.
  - Dylan16807 11y ago
    It's still constructive, you just have to change a word. That you insist on dismissing the method entirely baffles me. I'm sorry that I didn't remember it off the top of my head. Factoring is not a huge burden compared to the earlier steps, and also not necessary a lot of the time, especially if your goal is to keep feeding the number back into the system to create numbers made out of new primes.

pervycreeper 11y ago

>Nonconstructive proofs of existence in rare Not so sure about that. I'd also dispute that they are inherently more difficult (assume X doesn't exist... )

mturmon 11y ago
I have to agree with you. There are plenty of times in math classes where I've been assured that "Theorem 1 guarantees that there exists a unique solution...", but where this solution is in no sense easily known. As an example, a maximizer of some convex function over a convex set. Sure, it exists, but constructing it is another matter! As another example, solutions to differential equations of a given form. The form guarantees a solution exists, but the solution may difficult to pin down. One more example: Borel sets. Hmm, now that I'm going: the square root of 2. It is a number that satisfies a simple property, but constructing it is considerably more difficult.

mafribe 11y ago

It's a useful technique not just for undergraduates. Here are two famous computer science examples. * Dana Scott discovered the lattice based model of the λ-calculus while trying to prove that no set theoretic models exist. This put functional programming on the map. * Volker Strassen found his fast matrix multiplication while trying to show that the traditional O(n^3) is optimal. This might have been the first or one of the first non-trivial and unexpected innovations that came from the then new field of computational complexity.