5 ms·

Well, I guess you can prove that there are no odd numbers in set (2,4,6), so some negatives you can prove, but in general case, I do not know how to prove that

Well, I guess you can prove that there are no odd numbers in set (2,4,6), so some negatives you can prove, but in general case, I do not know how to prove that something does not exist and will not exist ever.

aatd86 3y ago
That's the absence of proof. It's a bit different from the proof of a negative. Don't worry you're not the first one mentioning it so that's something that must be some kind of colloquialism somewhere but I was asking to understand what people may have meant. To top it all, you proved a negative (by providing a counterexample) :o)
- mort96 3y ago
  No, it's absolutely a proof. Claim: There is no odd number in {2, 4, 6}. Proof: 2 is not an odd number, 4 is not an odd number, 6 is not an odd number, there are no other elements in {2, 4, 6}. Therefore, there is no odd number in {2, 4, 6}. If there was simply an absence of proof, we would be forced to conclude that we don't know whether there's an odd number in {2, 4, 6}. That's clearly not the case. The claim "S is a set with no odd number" is equivalent to the claim "S is a set where all numbers are even", which is something I assume you agree that we can prove.
  - aatd86 3y ago
    I'm not talking about the first part of the comment but the latter parts regarding the general case. (I even wrote that he proved it himself at the end)
hnben 3y ago
when proving a negativ in math, you often do a proof by contradiction precondition: Either A is true or it is false. question: is A false? solution: 1. assume that A is true 2. <math stuff> 3. find a contradiction 4. ==> A can not be true 5. ==> therefor A is false
- beefield 3y ago
  In P/NP case I would need to assume that I can solve a problem in polynomial time, and then find a contradiction. To me it is really hard to see a useful path forward from there.
  - hnben 3y ago
    > I would need to assume that I can solve a problem in polynomial time, and then find a contradiction iirc that's actually how many of these proofs work. > To me it is really hard to see a useful path forward from there. yes, CS is hard. there are resources online, that explain the general idea, e.g. [1]. But understand the specifics, you really do need a solid foundation in theoretical math and theoretical CS [1] https://www.quora.com/What-is-a-proof-by-contradiction-in-computational-complexity-theory https://www.quora.com/What-is-a-proof-by-contradiction-in-co...
  - aatd86 3y ago
    If you see a path, you'll be one million USD richer. Don't forget about us. :-)
  - tetha 3y ago
    That's what's called a "non-constructive" proof in some circles. It /doesn't/ have a useful path forward, which makes it frustrating. There are some weird sandwiches of complexity classes - like, iirc, P-SPACE, EXP, NP-SPACE - which we know to have exactly 2 subsets plus the total subset, but which constellations? Dunno. This is different from a constructive proof. "Here we have a problem, and all algorithms so far are in O(n^3). We can demonstrate the existence of a substructure in all instances of this problem which lowers the complexity to O(n^2.978)" would be a huge constructive proof in some fields. Such a breakthrough could lead to a large number of follow-up improvements. A non-constructive breakthrough is like "Yup, this is a barrier. No clue why though, but it's hard."
- perthmad 3y ago
  Proving a negation is not a proof by contradiction, that's just the proof of an (absurd) implication. Logic people actually write blog posts about this: https://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/ https://math.andrej.com/2010/03/29/proof-of-negation-and-pro...

aatd86 3y ago

That's the absence of proof. It's a bit different from the proof of a negative. Don't worry you're not the first one mentioning it so that's something that must be some kind of colloquialism somewhere but I was asking to understand what people may have meant. To top it all, you proved a negative (by providing a counterexample) :o)

mort96 3y ago
No, it's absolutely a proof. Claim: There is no odd number in {2, 4, 6}. Proof: 2 is not an odd number, 4 is not an odd number, 6 is not an odd number, there are no other elements in {2, 4, 6}. Therefore, there is no odd number in {2, 4, 6}. If there was simply an absence of proof, we would be forced to conclude that we don't know whether there's an odd number in {2, 4, 6}. That's clearly not the case. The claim "S is a set with no odd number" is equivalent to the claim "S is a set where all numbers are even", which is something I assume you agree that we can prove.
- aatd86 3y ago
  I'm not talking about the first part of the comment but the latter parts regarding the general case. (I even wrote that he proved it himself at the end)

hnben 3y ago

when proving a negativ in math, you often do a proof by contradiction precondition: Either A is true or it is false. question: is A false? solution: 1. assume that A is true 2. <math stuff> 3. find a contradiction 4. ==> A can not be true 5. ==> therefor A is false

beefield 3y ago
In P/NP case I would need to assume that I can solve a problem in polynomial time, and then find a contradiction. To me it is really hard to see a useful path forward from there.
- hnben 3y ago
  > I would need to assume that I can solve a problem in polynomial time, and then find a contradiction iirc that's actually how many of these proofs work. > To me it is really hard to see a useful path forward from there. yes, CS is hard. there are resources online, that explain the general idea, e.g. [1]. But understand the specifics, you really do need a solid foundation in theoretical math and theoretical CS [1] https://www.quora.com/What-is-a-proof-by-contradiction-in-computational-complexity-theory https://www.quora.com/What-is-a-proof-by-contradiction-in-co...
- aatd86 3y ago
  If you see a path, you'll be one million USD richer. Don't forget about us. :-)
- tetha 3y ago
  That's what's called a "non-constructive" proof in some circles. It /doesn't/ have a useful path forward, which makes it frustrating. There are some weird sandwiches of complexity classes - like, iirc, P-SPACE, EXP, NP-SPACE - which we know to have exactly 2 subsets plus the total subset, but which constellations? Dunno. This is different from a constructive proof. "Here we have a problem, and all algorithms so far are in O(n^3). We can demonstrate the existence of a substructure in all instances of this problem which lowers the complexity to O(n^2.978)" would be a huge constructive proof in some fields. Such a breakthrough could lead to a large number of follow-up improvements. A non-constructive breakthrough is like "Yup, this is a barrier. No clue why though, but it's hard."
perthmad 3y ago
Proving a negation is not a proof by contradiction, that's just the proof of an (absurd) implication. Logic people actually write blog posts about this: https://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/ https://math.andrej.com/2010/03/29/proof-of-negation-and-pro...