Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

A common approach to proving a broad claim when there’s no straightforward proof is to figure out all of the entities that have the potential to produce a counterexample, break them up into a finite list of categories, and go through category by category proving, often with very different approaches depending on the category, that each category cannot contain a counterexample.

A major theorem proved in this style was the classification of finite simple groups. Not only was it done in this style, it frequently serves as a major component in other proofs of this style, since theorems about other kinds of groups can sometimes be re-expressed as claims about finite simple groups, and then checked category by category.

https://en.m.wikipedia.org/wiki/Classification_of_finite_sim...

EDIT: This is also part of why sometimes the first proof of a theorem will be very long, but someone will later use the insight of the first proof to produce a much shorter proof. The first proof will basically be a proof that the general claim breaks down into a (possibly very long) list of separately probable lemmas, followed by a proof of each of the lemmas. These may not overlap very much, leading to proofs that are very long and take a lot of background to understand. Once the result is known to be true, it may be worth the effort for the original author or someone else to refactor the “proved it can’t be disproved” proof into a much shorter direct proof.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: