6 ms·

When doing math proof exercises as an undergrad I found problems of the form "Prove X" or "Disprove X" to be much easier than "Prove or disprove X" despite no n

When doing math proof exercises as an undergrad I found problems of the form "Prove X" or "Disprove X" to be much easier than "Prove or disprove X" despite no noticeable difference in the difficulty of understanding the proof once constructed. I felt that prove/disprove was significantly more than twice as hard, actually. I thought I could trick myself into making it between 1 and 2 times as hard by attempting to force myself to believe the problem was one form or the other for set periods of time, and that did seem to help some, but not nearly to the extent I had hoped.

SilasX 11y ago
From my memory, they used this as a way to balance proof difficulty: for easier proofs, it would be a "prove of disprove", but for harder ones, they would reveal which one you can prove.
reagency 11y ago
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.
  - 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.

SilasX 11y ago

From my memory, they used this as a way to balance proof difficulty: for easier proofs, it would be a "prove of disprove", but for harder ones, they would reveal which one you can prove.

reagency 11y ago

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