Michael Beeson's Research

Proof Checking Euclid

Joint work with Julien Narboux and Freek Wiedijk

We used computer proof-checking methods to verify the correctness of our proofs of the propositions in Euclid Book I. We used axioms as close as possible to those of Euclid, in a language closely related to that used in Tarski's formal geometry. We used proofs as close as possible to those given by Euclid, but filling Euclid's gaps and correcting errors. Euclid Book I has 48 propositions; we proved 213 theorems. The extras were partly ``Book Zero'', preliminaries of a very fundamental nature, partly propositions that Euclid omitted but were used implicitly, partly advanced theorems that we found necessary to fill Euclid's gaps, and partly just variants of Euclid's propositions. We wrote these proofs in a simple fragment of first-order logic corresponding to Euclid's logic, debugged them using a custom software tool, and then checked them in the well-known and trusted proof checkers HOL Light and Coq.

This web page provides (below) links to all the files needed to reproduce this work. The paper that describes the work can be found here:

Proof-checking Euclid

Persons wishing to download the files necessary to reproduce our work may download them all at once in the following archive:

proofs.tar.gz

The steps to reproduce our work are as follows:

(1) Unpack the archive mentioned above into a directory

CheckEuclid

(or another name of your choice). The subdirectory proofs contains .prf files. These are the formal proofs we wrote by hand. In the directory CheckEuclid are auxiliary files needed to check the proofs in HOL Light.

(2) Ensure that PHP is installed on your system, then run

 ./Checkproofs.php 

from directory CheckEuclid/proofs. This runs our custom proof-checker, or proof debugger, on all the proofs. That one PHP file contains all the source code for our custom proof-checker.

(3) Ensure the HOL Light is running on your system.

(4) Start HOL Light and load the files

proofs.ml

and

michael.ml

. That will check all the proofs in HOL Light. It will take several minutes, but you will get a lot of reassuring output as it runs.

(5) The file proofs.ml contains code designed to process HOL Light versions of our proofs. Those HOL Light versions are in michael.ml. That file was generated automatically from the proof files and the file

Axioms.php

that contains the list of our axioms for Euclid and the list of proofs to be checked. If you wish to regenerate michael.ml>, the procedure is as follows, starting from the CheckEuclid directory.

    cd proofs
    ../FreekFiles.php
    cd ..
    ./FreekFiles.pl

(6) The script CoqExport.php has already been run to produce the .v files. Those are included in GeoCoq 2.4.0 library. GeoCoq 2.4.0 compiles at least with Coq versions 8.6.1, 8.7.2 and 8.8. See instructions given here.

• The Coq version of Euclidean axioms
• Some adhoc tactics
• Book 1
• Going from Tarski's axiom to Euclid's axioms
• Going from Euclid's axioms to Tarski's axioms

(7) We also used HOL Light to verify that our axioms hold in the usual Cartesian plane. That verification required thousands of lines of HOL Light code. That code can be found in the following files. To run those proofs, load the three files in order into HOL Light. They will take some minutes but eventually you will see a list of the axioms of our theory, as objects of type thm in HOL Light.

• ETAxioms.ml
• ETAxioms2.ml
• EFAxioms.ml

(8) There is also a subdirectory dependencies that is not used in our work. This contains automatically extracted information about what lines are used to deduce other lines in our proofs. This might be useful in the future.