undefined | Better HN

0 pointsgus_massa4d ago0 comments

Searching for a proof and disproof are sometimes not so different. In most cases, you nibble the borders to simplify the problem.

For example, to prove something is impossible let's say you first prove that there are only 5 families, and 4 of them are impossible. So now 80% of the problem is solved! :) If you are looking for counterexamples, the search is reduced 80% too. In both cases it may be useful

In counterexamples you can make guess and leaps and if it works it's fine. This is not possible for a proof.

On the other hand, once you have found a counterexample it's usual to hide the dead ends you discarded.

0 comments

mooreat4d ago

I agree there can be some theory crafting in the search for a counterexample, but in general I think it is easier to search for.

For proving a proposition P I have to show for all x P(x), but for contradiction I only have to show that there exists an x such that not P(x).

While I agree there could be a lot of theory crafting to reduce the search space of possible x's to find not P(x), but with for all x P(x) you have to be able to produce a larger framework that explains why no counter example exists.

energy1234d ago

Timothy Gowers said a proof (rather than disproof) would have been different and more impressive because it would have required new mathematical concepts.

j / k navigate · click thread line to collapse