4

I have just read a topic on mathoverflow about man vs. machine in mathematics. The topic was inspired by the recent victory of Alpha Go over the World Go Champion, Lee Sedol. It reminded me of an article I read (possibly on American Mathematical Monthly) about translating Jordan Curve Theorem into machine-checkable form.

I would love to hear about why is it so hard, generally, to translate a proof of some theorem so that a machine can check it. What is fundamentally different between, says, the Four Color Theorem and Jordan Curve Theorem that makes it a lot harder for machine to deal with the later?

EDIT: I have found a wonderful related link Why is it hard to prove Jordan Curve Theorem in the case of Koch snowflake.

Community
  • 1
BigbearZzz
  • 15,084
  • The Jordan curve theorem generally has a less elementary proof, using more background results than the four color theorem. I've never examined the proof of the four color theorem, but I'd imagine the proof is completely elementary, although enormously long. – Matt Samuel Mar 13 '16 at 18:12
  • So basically Jordan Theorem need more "lemmas" so it's harder? Might there be some "genuine difficulty" about it, i.e. some idea that is hard to grasp by symbolic reasoning but not for human mind? – BigbearZzz Mar 13 '16 at 18:20

2 Answers2

5

Another example is Gonthier's recent proof of Feit–Thompson theorem. It would be too long to answer your question in detail, but this link (in French) COQ ET CARACTÈRES, Preuve formelle du théorème de Feit et Thompson, contains several relevant references.

In particular, A Special Issue on Formal Proof of the Notices of the AMS gathers four articles:

Formal Proof by Thomas Hales

Formal Proof--The Four-Color Theorem by Georges Gonthier

Formal Proof--Theory and Practice by John Harrison

Formal Proof--Getting Started by Freek Wiedijk

J.-E. Pin
  • 40,163
2

It's not so much harder as much more tedious. In a formal proof (one readable by a computer program), each step in solving an equation must be made explicit. You cannot assume, for example, that the reader (a computer in this case) knows that addition on the real numbers is commutative. You cannot even say, by the commutativity of addition, such and such. You must explicitly cite some previously proven theorem of the form $$\forall x: \forall y:[x\in \mathbb{R} \land y \in \mathbb{R} \implies x+y=y+x]$$ Then you must specify an expression for both bound variables $x$ any $y$. Then you must prove each expression is indeed a real number. Then you must apply the detachment rule. (Leaving out some details!) Then you must explicitly select the expressions in the original formula for which you want to make the substitution. Whew!

What is normally simply "known" and applied almost subconciously by an experienced human reader to fill in the gaps is a multi-step process in a formal proof. The upside, of course, is that you can be virtually certain that no errors have been made. For practical purposes, there would be no real need for any further verification by a human expert.

Dan Christensen
  • 14,529
  • Although, given how many failed attempts were made at proving the Jordan curve theorem, formal verification doesn't seem like a bad idea... somehow it is much more subtle than it appears at first glance. – Charles Mar 25 '16 at 13:23