Hacker News Reader

Comment by segfaultbuserr | Hacker News Reader

> You'll only know for sure if you prove it false.

Yes.

Interestingly, there are disproved hypotheses, of which, before they got disproved formally, previous massive computations failed to find a single counterexample despite the search reached a huge upper bound. But from time to time, someone could get lucky enough and actually find one to disprove something entirely through computation...

The CDC 6600, R and a Conjecture by Euler

* https://criticathink.wordpress.com/2018/09/30/the-cdc-6600-r...

View on HN

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.

> And if you don't find ANY counter example you can't definitely disprove.

This is... not even close to being true.

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

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.

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

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

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.

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.

Is that proof not constructive? While you aren’t constructing the sequence of all primes, you are constructing some infinite set of primes to prove that there are infinite primes.

I doesn’t construct only primes. If p1, p2, ..., pn are prime, then p1p2...pn + 1 is not divisible by any of them, but it may not be prime itself.

Then you haven't proved a additional prime; you still need the (trivial[0]) step of breaking down 1+Πp into its one or more prime factors. And then you've constructed a (or several) prime not in the original set.

0: Trivial in the logical sense (try every number up to √(1+Πp)), but computationally impractical, thus left as a exercise for the reader.

You don't need that; you can proceed purely through generalities.

1. 1+Πp is congruent to 1 (mod p) for every prime p.

2. This conflicts with the definition of "prime number"; all composite numbers must be congruent to 0 (mod p) for some prime p. Only the empty product can be congruent to 1 (mod p) for every p.

This is already sufficient to prove that the number of primes is not finite -- we derived a contradiction from that premise without demonstrating any additional primes.

(Note that -- within the proof, where we've assumed a finite list of primes -- it's easy to show that 1+Πp is itself prime (since it has no prime divisors less than itself). You can then declare a contradiction with the premise, as it isn't in the original list. However, you can only show that it's prime by using the earlier contradiction, so while this step makes the proof more intuitive, it isn't actually necessary.)

Yes that is correct but that's not what I was talking about in earlier comments, which were exclusively about example-based proof/disproof.

If you're not talking about proof/disproof, you might want to look for a different word.

I was unware there is only one type of proof or that it is not allowed to talk only about specific types of proof.

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.

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;

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

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

I suspect they are mistaken, depending on how one defines "demonstrate" and "specific", but you haven't actually shown that.

It would be interesting to see how they react to this proof:

https://en.wikipedia.org/wiki/Probabilistic_method#First_exa...

I've edited the comment and clarified the ambiguity.

There was also a computational search for counterexamples of Fermat's last theorem (with nothing found - April 1st jokes regardless)

Reply on news.ycombinator.com