Chapter 11  The Mathematical Proof Language

• 11.1  Introduction
• 11.2  Syntax
• 11.3  Language description
• 11.4  More details and Formal Semantics

11.1  Introduction

11.1.1  Foreword

In this chapter, we describe an alternative language that may be used to do proofs using the Coq proof assistant. The language described here uses the same objects (proof-terms) as Coq, but it differs in the way proofs are described. This language was created by Pierre Corbineau at the Radboud University of Nijmegen, The Netherlands.

The intent is to provide language where proofs are less formalism- and implementation-sensitive, and in the process to ease a bit the learning of computer-aided proof verification.

11.1.2  What is a declarative proof?

In vanilla Coq, proofs are written in the imperative style: the user issues commands that transform a so called proof state until it reaches a state where the proof is completed. In the process, the user mostly described the transitions of this system rather than the intermediate states it goes through.

The purpose of a declarative proof language is to take the opposite approach where intermediate states are always given by the user, but the transitions of the system are automated as much as possible.

11.1.3  Well-formedness and Completeness

The Mathematical Proof Language introduces a notion of well-formed proofs which are weaker than correct (and complete) proofs. Well-formed proofs are actually proof script where only the reasoning is incomplete. All the other aspects of the proof are correct:

• All objects referred to exist where they are used
• Conclusion steps actually prove something related to the conclusion of the theorem (the thesis.
• Hypothesis introduction steps are done when the goal is an implication with a corresponding assumption.
• Sub-objects in the elimination steps for tuples are correct sub-objects of the tuple being decomposed.
• Patterns in case analysis are type-correct, and induction is well guarded.

11.1.4  Note for tactics users

This section explain what differences the casual Coq user will experience using the Mathematical Proof Language.

1. The focusing mechanism is constrained so that only one goal at a time is visible.
2. Giving a statement that Coq cannot prove does not produce an error, only a warning: this allows going on with the proof and fill the gap later.
3. Tactics can still be used for justifications and after escape.

11.1.5  Compatibility

The Mathematical Proof Language is available for all Coq interfaces that use text-based interaction, including:

• the command-line toplevel coqtop
• the native GUI CoqIDE
• the Proof General Emacs mode
• Cezary Kaliszyk’s Web interface
• L.E. Mamane’s tmEgg TeXmacs plugin

However it is not supported by structured editors such as PCoq.

11.2  Syntax

Here is a complete formal description of the syntax for Mathematical Proof Language commands.

---

instruction	::=	proof
	|	assume statement and … and statement [[and {we have}-clause]]
	|	{let,be}-clause
	|	{given}-clause
	|	{consider}-clause from term
	|	(have | then | thus | hence]) statement justification
	|	[thus] (∼=|=∼) [ident:]termjustification
	|	suffices ({to have}-clause | statement and … and statement [and {to have}-clause])
		to show statement justification
	|	(claim | focus on) statement
	|	take term
	|	define ident[var , … , var] as term
	|	reconsider (ident| thesis) as type
	|	per (cases|induction) on term
	|	per cases of type justification
	|	suppose [ident , … , ident and]  it is pattern
		[such that statement and … and statement [and {we have}-clause]]
	|	end (proof | claim | focus | cases | induction)
	|	escape
	|	return
{α,β}-clause	::=	α var , … , var  β such that statement and … and statement
		[and {α,β}-clause]
statement	::=	[ident:] type
	|	thesis
	|	thesis for ident
var	::=	ident[: type]
justification	::=	[by (* | term , … , term)]  [using tactic]

Figure 11.1: Syntax of mathematical proof commands

---

The lexical conventions used here follows those of section 1.1.

Conventions:

• <tactic> stands for a Coq tactic.

11.2.1  Temporary names

In proof commands where an optional name is asked for, omitting the name will trigger the creation of a fresh temporary name (e.g. for a hypothesis). Temporary names always start with an underscore ‘_’ character (e.g. _hyp0). Temporary names have a lifespan of one command: they get erased after the next command. They can however be safely in the step after their creation.

11.3  Language description

11.3.1  Starting and Ending a mathematical proof

The standard way to use the Mathematical Proof Language is to first state a Lemma / Theorem / Definition and then use the proof command to switch the current subgoal to mathematical mode. After the proof is completed, the end proof command will close the mathematical proof. If any subgoal remains to be proved, they will be displayed using the usual Coq display.

The proof command only applies to one subgoal, thus if several sub-goals are already present, the proof ... end proof sequence has to be used several times.

As with all other block structures, the end proof command assumes that your proof is complete. If not, executing it will be equivalent to admitting that the statement is proved: A warning will be issued and you will not be able to run the Qed command. Instead, you can run Admitted if you wish to start another theorem and come back later.

11.3.2  Switching modes

When writing a mathematical proof, you may wish to use procedural tactics at some point. One way to do so is to write a using-phrase in a deduction step (see section 11.3.14). The other way is to use an escape...return block.

The return statement expects all subgoals to be closed, otherwise a warning is issued and the proof cannot be saved anymore.

It is possible to use the proof command inside an escape...return block, thus nesting a mathematical proof inside a procedural proof inside a mathematical proof...

11.3.3  Computation steps

The reconsider ... as command allows changing the type of a hypothesis or of thesis to a convertible one.

11.3.4  Deduction steps

The most common instruction in a mathematical proof is the deduction step: it asserts a new statement (a formula/type of the Cic) and tries to prove it using a user-provided indication: the justification. The asserted statement is then added as a hypothesis to the proof context.

It is often the case that the justifications uses the last hypothesis introduced in the context, so the then keyword can be used as a shortcut, e.g. if we want to do the same as the last example:

In this example, you can also see the creation of a temporary name _fact.

11.3.5  Iterated equalities

A common proof pattern when doing a chain of deductions is to do multiple rewriting steps over the same term, thus proving the corresponding equalities. The iterated equalities are a syntactic support for this kind of reasoning:

Notice that here we use temporary names heavily.

11.3.6  Subproofs

When an intermediate step in a proof gets too complicated or involves a well contained set of intermediate deductions, it can be useful to insert its proof as a subproof of the current proof. This is done by using the claim ... end claim pair of commands.

A few steps later...

Now the rest of the proof can happen.

11.3.7  Conclusion steps

The commands described above have a conclusion counterpart, where the new hypothesis is used to refine the conclusion.

---

X	simple	with previous step	opens sub-proof	iterated equality
intermediate step	have	then	claim	∼=/=∼
conclusion step	thus	hence	focus on	thus ∼=/=∼

Figure 11.2: Correspondence between basic forward steps and conclusion steps

---

Let us begin with simple examples:

In the next example, we have to use thus because HB is no longer the last hypothesis.

The command fails if the refinement process cannot find a place to fit the object in a proof of the conclusion.

The refinement process may induce non reversible choices, e.g. when proving a disjunction it may choose one side of the disjunction.

In this example you can see that the right branch was chosen since D remains to be proved.

Now for existential statements, we can use the take command to choose 2 as an explicit witness of existence.

It is also possible to prove the existence directly.

Here a more involved example where the choice of P 2 propagates the choice of 2 to another part of the formula.

Now, an example with the suffices command. suffices is a sort of dual for have: it allows replacing the conclusion (or part of it) by a sufficient condition.

Finally, an example where focus is handy: local assumptions.

11.3.8  Declaring an Abbreviation

In order to shorten long expressions, it is possible to use the define ... as ... command to give a name to recurring expressions.

11.3.9  Introduction steps

When the thesis consists of a hypothetical formula (implication or universal quantification (e.g. A -> B), it is possible to assume the hypothetical part A and then prove B. In the Mathematical Proof Language, this comes in two syntactic flavors that are semantically equivalent: let and assume. Their syntax is designed so that let works better for universal quantifiers and assume for implications.

In the let variant, the type of the assumed object is optional provided it can be deduced from the command. The objects introduced by let can be followed by assumptions using such that.

In the assume variant, the type of the assumed object is mandatory but the name is optional:

After such that, it is also the case:

11.3.10  Tuple elimination steps

In the Cic, many objects dealt with in simple proofs are tuples: pairs, records, existentially quantified formulas. These are so common that the Mathematical Proof Language provides a mechanism to extract members of those tuples, and also objects in tuples within tuples within tuples...

Here is an example with pairs:

It is sometimes desirable to combine assumption and tuple decomposition. This can be done using the given command.

11.3.11  Disjunctive reasoning

In some proofs (most of them usually) one has to consider several cases and prove that the thesis holds in all the cases. This is done by first specifying which object will be subject to case distinction (usually a disjunction) using per cases, and then specifying which case is being proved by using suppose.

The proof is well formed (but incomplete) even if you type end cases or the next suppose before the previous case is proved.

If the disjunction is derived from a more general principle, e.g. the excluded middle axiom), it is desirable to just specify which instance of it is being used:

11.3.12  Proofs per cases

If the case analysis is to be made on a particular object, the script is very similar: it starts with per cases on object instead.

If the object on which a case analysis occurs in the statement to be proved, the command suppose it is pattern is better suited than suppose. pattern may contain nested patterns with as clauses. A detailed description of patterns is to be found in figure 1.2. here is an example.

11.3.13  Proofs by induction

Proofs by induction are very similar to proofs per cases: they start with per induction on object and proceed with suppose it is patternand induction hypothesis. The induction hypothesis can be given explicitly or identified by the sub-object m it refers to using thesis for m.

11.3.14  Justifications

Intuitively, justifications are hints for the system to understand how to prove the statements the user types in. In the case of this language justifications are made of two components:

Justification objects: by followed by a comma-separated list of objects that will be used by a selected tactic to prove the statement. This defaults to the empty list (the statement should then be tautological). The * wildcard provides the usual tactics behavior: use all statements in local context. However, this wildcard should be avoided since it reduces the robustness of the script.

Justification tactic: using followed by a Coq tactic that is executed to prove the statement. The default is a solver for (intuitionistic) first-order with equality.

11.4  More details and Formal Semantics

I suggest the users looking for more information have a look at the paper [34]. They will find in that paper a formal semantics of the proof state transition induces by mathematical commands.