6 ms·

Where they disproven of massive computation failing to find a counter example or was the search space entirely exhausted? Or by actually finding the counter exa

by zaarn 7y ago

Where they disproven of massive computation failing to find a counter example or was the search space entirely exhausted? Or by actually finding the counter example? Those are different things. You can disprove by computing every possible input but you can only reasonably disprove but not actually disprove if you didn't test every input. And if you don't find ANY counter example you can't definitely disprove.

segfaultbuserr 7y ago
I've edited the comment and clarified the ambiguity.
thaumasiotes 7y ago
> And if you don't find ANY counter example you can't definitely disprove. This is... not even close to being true.
- zaarn 7y ago
  How is it untrue?
  - thaumasiotes 7y ago
    Any nonconstructive proof would fail to meet your criterion (which pretty much defines constructive mathematics). Consider the standard proof that the square root of 2 is irrational -- it takes the logical form 1. IF sqrt(2) is rational... 2. THEN it has a representation a/b where a and b are coprime integers. 3. THEN (after some algebra) a is a multiple of 2. 4. THEN (after some more algebra) b is a multiple of 2. 5. Points (3) and (4) contradict point (2), which says that a and b are coprime. 6. THEREFORE, we have disproven the idea that sqrt(2) is rational. This is a correct proof, but not a constructive proof. It's difficult to have a constructive disproof of the claim that a particular number is rational. What would you construct? But you can easily have a nonconstructive disproof of any given claim. Sticking to proof by contradiction, imagine the sequence "if this conjecture were true, there would be a unique largest prime number -> there is no largest prime number -> this conjecture is false".
    - zaarn 7y ago
      I'm aware that nonconstrutive disproof/proof exists but my comments were about constructive/example-driven proofs/disproofs, so I don't see the point really.
    - afiori 7y ago
      this is actually a constructive proof, you are proving that sqrt(2) = a/b implies false and "irrational" is defined as "not rational". A better easy non constructive proof is to show that there are two irrational numbers c and d such that c^d is rational. and either c1=d1=sqrt(2) or c2=(sqrt(2)^sqrt(2)) and d2=sqrt(2) as c2^d2 == 2 and if c2 is irrational you are done and if c2 is rational then c1^d1 is rational and you are done. The non constructivity is in that you do not know two irrational numbers c and d such that c^d is rational. In general proving "not P" by "P is absurd" is constructive and proving "P" by "not P cannot happen" is not.
    - Someone 7y ago
      ”It's difficult to have a constructive disproof of the claim that a particular number is rational. What would you construct?” Nitpick: an irrational number that is equal to the number that you want to prove not being a rational. Because the irrational aren’t closed under the ‘normal’ operations, that’s often problematic, but, as a trivial example, proving that 1/37+3√2 is not rational can easily be done that way: √2 is irrational, and the sum of a rational and an irrational is irrational, so 1/37+3√2 is irrational.
    - smallnamespace 7y ago
      Here's a constructive proof that does not rely on the law of excluded middle: https://en.m.wikipedia.org/wiki/Square_root_of_2#Constructive_proof https://en.m.wikipedia.org/wiki/Square_root_of_2#Constructiv...
  - DavidSJ 7y ago
    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.
ColinWright 7y ago
There are cases of all of the following: (a) A conjecture claims that X doesn't exist, and a proof has been found to show that X does not exist; (b) A conjecture claims that X doesn't exist, and an exhaustive search has failed to find X; (c) A conjecture claims that X does exist, and a search has found a sample X; (d) A conjecture claims that X does exist, and a proof has been given that such an X does exist but without ever demonstrating a specific example. This collection of cases seems to show that your statements are mistaken.
- a1369209993 7y ago
  I think they're saying that case d specifically is not a legitimate proof, or equivalently that instances of case that are legitimate proof can be made constructive through a trivial addition (eg https://news.ycombinator.com/item?id=20395476 https://news.ycombinator.com/item?id=20395476). I suspect they are mistaken, depending on how one defines "demonstrate" and "specific", but you haven't actually shown that.
  - ColinWright 7y ago
    It would be interesting to see how they react to this proof: https://en.wikipedia.org/wiki/Probabilistic_method#First_example https://en.wikipedia.org/wiki/Probabilistic_method#First_exa...

by zaarn 7y ago

segfaultbuserr 7y ago

I've edited the comment and clarified the ambiguity.

thaumasiotes 7y ago

> And if you don't find ANY counter example you can't definitely disprove. This is... not even close to being true.

zaarn 7y ago
How is it untrue?
- thaumasiotes 7y ago
  Any nonconstructive proof would fail to meet your criterion (which pretty much defines constructive mathematics). Consider the standard proof that the square root of 2 is irrational -- it takes the logical form 1. IF sqrt(2) is rational... 2. THEN it has a representation a/b where a and b are coprime integers. 3. THEN (after some algebra) a is a multiple of 2. 4. THEN (after some more algebra) b is a multiple of 2. 5. Points (3) and (4) contradict point (2), which says that a and b are coprime. 6. THEREFORE, we have disproven the idea that sqrt(2) is rational. This is a correct proof, but not a constructive proof. It's difficult to have a constructive disproof of the claim that a particular number is rational. What would you construct? But you can easily have a nonconstructive disproof of any given claim. Sticking to proof by contradiction, imagine the sequence "if this conjecture were true, there would be a unique largest prime number -> there is no largest prime number -> this conjecture is false".
  - zaarn 7y ago
    I'm aware that nonconstrutive disproof/proof exists but my comments were about constructive/example-driven proofs/disproofs, so I don't see the point really.
  - afiori 7y ago
    this is actually a constructive proof, you are proving that sqrt(2) = a/b implies false and "irrational" is defined as "not rational". A better easy non constructive proof is to show that there are two irrational numbers c and d such that c^d is rational. and either c1=d1=sqrt(2) or c2=(sqrt(2)^sqrt(2)) and d2=sqrt(2) as c2^d2 == 2 and if c2 is irrational you are done and if c2 is rational then c1^d1 is rational and you are done. The non constructivity is in that you do not know two irrational numbers c and d such that c^d is rational. In general proving "not P" by "P is absurd" is constructive and proving "P" by "not P cannot happen" is not.
  - Someone 7y ago
    ”It's difficult to have a constructive disproof of the claim that a particular number is rational. What would you construct?” Nitpick: an irrational number that is equal to the number that you want to prove not being a rational. Because the irrational aren’t closed under the ‘normal’ operations, that’s often problematic, but, as a trivial example, proving that 1/37+3√2 is not rational can easily be done that way: √2 is irrational, and the sum of a rational and an irrational is irrational, so 1/37+3√2 is irrational.
  - smallnamespace 7y ago
    Here's a constructive proof that does not rely on the law of excluded middle: https://en.m.wikipedia.org/wiki/Square_root_of_2#Constructive_proof https://en.m.wikipedia.org/wiki/Square_root_of_2#Constructiv...
- DavidSJ 7y ago
  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.

ColinWright 7y ago

There are cases of all of the following: (a) A conjecture claims that X doesn't exist, and a proof has been found to show that X does not exist; (b) A conjecture claims that X doesn't exist, and an exhaustive search has failed to find X; (c) A conjecture claims that X does exist, and a search has found a sample X; (d) A conjecture claims that X does exist, and a proof has been given that such an X does exist but without ever demonstrating a specific example. This collection of cases seems to show that your statements are mistaken.

a1369209993 7y ago
I think they're saying that case d specifically is not a legitimate proof, or equivalently that instances of case that are legitimate proof can be made constructive through a trivial addition (eg https://news.ycombinator.com/item?id=20395476 https://news.ycombinator.com/item?id=20395476). I suspect they are mistaken, depending on how one defines "demonstrate" and "specific", but you haven't actually shown that.
- ColinWright 7y ago
  It would be interesting to see how they react to this proof: https://en.wikipedia.org/wiki/Probabilistic_method#First_example https://en.wikipedia.org/wiki/Probabilistic_method#First_exa...