4 ms·

How is it untrue?

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

How is it untrue?

by zaarn 7y ago

How is it untrue?

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.