Chapter 11 The Mathematical Proof Language

# Coq Reference Manual

# 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 to go 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 DPL 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`:``]`term `justification` |
> | | | `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 an 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 undescore ’_’ 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 Languageis 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.

`Coq` `<``Theorem this_is_trivial: True.`
`1 subgoal`
``
`============================`
`True`
`Coq` `<``proof.`
`1 subgoal`
`*** Declarative Mode ***`
``
`============================`
`thesis :=`
`True`
`Coq` `<``thus thesis.`
`Subproof completed, now type "end proof".`
`Coq` `<``end proof.`
`Proof completed.`
`Coq` `<``Qed.`
`proof.`
`thus thesis.`
`end proof.`
`this_is_trivial is defined`

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.

`Coq` `<``Show.`
`3 subgoals`
``
`============================`
`True`
`subgoal 2 is:`
`True`
`subgoal 3 is:`
`True`
`Coq` `<``proof. (* first subgoal *)`
`1 subgoal`
`*** Declarative Mode ***`
``
`============================`
`thesis :=`
`True`
`Coq` `<``thus thesis.`
`Subproof completed, now type "end proof".`
`Coq` `<``end proof.`
`2 subgoals`
``
`============================`
`True`
`subgoal 2 is:`
`True`
`Coq` `<``trivial. (* second subgoal *)`
`1 subgoal`
``
`============================`
`True`
`Coq` `<``proof. (* third subgoal *)`
`1 subgoal`
`*** Declarative Mode ***`
``
`============================`
`thesis :=`
`True`
`Coq` `<``thus thesis.`
`Subproof completed, now type "end proof".`
`Coq` `<``end proof.`
`Proof completed.`

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.

`Coq` `<``Theorem this_is_not_so_trivial: False.`
`1 subgoal`
``
`============================`
`False`
`Coq` `<``proof.`
`1 subgoal`
`*** Declarative Mode ***`
``
`============================`
`thesis :=`
`False`
`Coq` `<``end proof. (* here a warning is issued *)`
`Proof completed.`
`Coq` `<``Qed. (* fails : the proof in incomplete *)`
`proof.`
`(* Some proof has been skipped here *)`
`end proof.`
`Error: Attempt to save an incomplete proof`
`Coq` `<``Admitted. (* Oops! *)`
`this_is_not_so_trivial is assumed`

### 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.

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`============================`
`thesis :=`
`True`
`Coq` `<``escape.`
`1 subgoal`
``
`============================`
`True`
`Coq` `<``auto.`
`Subgoal proved`
`Subproof completed, now type "return".`
`Coq` `<``return.`
`Subproof completed, now type "end proof".`

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 to change the type of a hypothesis or of `thesis` to a convertible one.

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`a := false : bool`
`b := true : bool`
`H : if a then True else False`
`============================`
`thesis :=`
`if b then True else False`
`Coq` `<``reconsider H as False.`
`1 subgoal`
`*** Declarative Mode ***`
``
`a := false : bool`
`b := true : bool`
`H : False`
`============================`
`thesis :=`
`if b then True else False`
`Coq` `<``reconsider thesis as True.`
`1 subgoal`
`*** Declarative Mode ***`
``
`a := false : bool`
`b := true : bool`
`H : False`
`============================`
`thesis :=`
`True`

### 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 pCic) 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.

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`x : nat`
`H : x = 2`
`============================`
`thesis :=`
`2 + x = 4`
`Coq` `<``have H’:(2+x=2+2) by H.`
`1 subgoal`
`*** Declarative Mode ***`
``
`x : nat`
`H : x = 2`
`H’ : 2 + x = 2 + 2`
`============================`
`thesis :=`
`2 + x = 4`

It is very 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 :

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`x : nat`
`H : x = 2`
`============================`
`thesis :=`
`2 + x = 4`
`Coq` `<``then (2+x=2+2).`
`1 subgoal`
`*** Declarative Mode ***`
``
`x : nat`
`H : x = 2`
`_fact : 2 + x = 2 + 2`
`============================`
`thesis :=`
`2 + x = 4`

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:

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`x : nat`
`H : x = 2`
`============================`
`thesis :=`
`x + x = x * x`
`Coq` `<``have (4 = 4).`
`1 subgoal`
`*** Declarative Mode ***`
``
`x : nat`
`H : x = 2`
`_fact : 4 = 4`
`============================`
`thesis :=`
`x + x = x * x`
`Coq` `<``` `~``= (2 * 2).`
`1 subgoal`
`*** Declarative Mode ***`
``
`x : nat`
`H : x = 2`
`_eq : 4 = 2 * 2`
`============================`
`thesis :=`
`x + x = x * x`
`Coq` `<``` `~``= (x * x) by H.`
`1 subgoal`
`*** Declarative Mode ***`
``
`x : nat`
`H : x = 2`
`_eq0 : 4 = x * x`
`============================`
`thesis :=`
`x + x = x * x`
`Coq` `<``=``~``(2 + 2).`
`1 subgoal`
`*** Declarative Mode ***`
``
`x : nat`
`H : x = 2`
`_eq : 2 + 2 = x * x`
`============================`
`thesis :=`
`x + x = x * x`
`Coq` `<``=``~``H’:(x + x) by H.`
`1 subgoal`
`*** Declarative Mode ***`
``
`x : nat`
`H : x = 2`
`H’ : x + x = x * x`
`============================`
`thesis :=`
`x + x = x * x`

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.

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`x : nat`
`H : x + x = x * x`
`============================`
`thesis :=`
`x = 0` `\``/ x = 2`
`Coq` `<``claim H’:((x - 2) * x = 0).`
`1 subgoal`
`*** Declarative Mode ***`
``
`x : nat`
`H : x + x = x * x`
`============================`
`thesis :=`
`(x - 2) * x = 0`

A few steps later ...

`Coq` `<``thus thesis.`
`Warning: Insufficient justification.`
`Subproof completed, now type "end claim".`
`Coq` `<``end claim.`
`1 subgoal`
`*** Declarative Mode ***`
``
`x : nat`
`H : x + x = x * x`
`H’ : (x - 2) * x = 0`
`============================`
`thesis :=`
`x = 0` `\``/ x = 2`

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 :

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`B : Prop`
`HA : A`
`HB : B`
`============================`
`thesis :=`
`A /``\``B`
`Coq` `<``hence B.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`B : Prop`
`HA : A`
`HB : B`
`_fact : B`
`============================`
`thesis :=`
`A`

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

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`B : Prop`
`C : Prop`
`HA : A`
`HB : B`
`HC : C`
`============================`
`thesis :=`
`A /``\``B /``\``C`
`Coq` `<``thus B by HB.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`B : Prop`
`C : Prop`
`HA : A`
`HB : B`
`HC : C`
`_fact : B`
`============================`
`thesis :=`
`A /``\``C`

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

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`B : Prop`
`C : Prop`
`HA : A`
`HB : B`
`HC : C`
`============================`
`thesis :=`
`A /``\``B`
`Coq` `<``hence C. (* fails *)`
`Error: I could not relate this statement to the thesis.`

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

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`B : Prop`
`HB : B`
`============================`
`thesis :=`
`A` `\``/ B`
`Coq` `<``hence B.`
`Subproof completed, now type "end proof".`

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

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`B : Prop`
`C : Prop`
`D : Prop`
`HC : C`
`HD : D`
`============================`
`thesis :=`
`A /``\``B` `\``/ C /``\``D`
`Coq` `<``thus C by HC.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`B : Prop`
`C : Prop`
`D : Prop`
`HC : C`
`HD : D`
`_fact : C`
`============================`
`thesis :=`
`D`

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

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`P : nat -``>``Prop`
`HP : P 2`
`============================`
`thesis :=`
`exists x : nat, P x`
`Coq` `<``take 2.`
`1 subgoal`
`*** Declarative Mode ***`
``
`P : nat -``>``Prop`
`HP : P 2`
`============================`
`thesis :=`
`P 2`

It is also possible to prove the existence directly.

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`P : nat -``>``Prop`
`HP : P 2`
`============================`
`thesis :=`
`exists x : nat, P x`
`Coq` `<``hence (P 2).`
`Subproof completed, now type "end proof".`

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

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`P : nat -``>``Prop`
`R : nat -``>``nat -``>``Prop`
`HP : P 2`
`HR : R 0 2`
`============================`
`thesis :=`
`exists x : nat, exists y : nat, P y /``\``R x y`
`Coq` `<``thus (P 2) by HP.`
`1 subgoal`
`*** Declarative Mode ***`
``
`P : nat -``>``Prop`
`R : nat -``>``nat -``>``Prop`
`HP : P 2`
`HR : R 0 2`
`_fact : P 2`
`============================`
`thesis :=`
`exists n : nat, R n 2`

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

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`B : Prop`
`P : nat -``>``Prop`
`HP : forall x : nat, P x -``>``B`
`HA : A`
`============================`
`thesis :=`
`A /``\``B`
`Coq` `<``suffices to have x such that HP’:(P x) to show B by HP,HP’.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`B : Prop`
`P : nat -``>``Prop`
`HP : forall x : nat, P x -``>``B`
`HA : A`
`_cofact : forall x : nat, P x -``>``B`
`============================`
`thesis :=`
`A /``\``(exists n : nat, P n)`

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

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`P : nat -``>``Prop`
`HP : P 2`
`HA : A`
`============================`
`thesis :=`
`A /``\``(forall x : nat, x = 2 -``>``P x)`
`Coq` `<``focus on (forall x, x = 2 -``>``P x).`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`P : nat -``>``Prop`
`HP : P 2`
`HA : A`
`============================`
`thesis :=`
`forall x : nat, x = 2 -``>``P x`
`Coq` `<``let x be such that (x = 2).`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`P : nat -``>``Prop`
`HP : P 2`
`HA : A`
`x : nat`
`_hyp : x = 2`
`============================`
`thesis :=`
`P x`
`Coq` `<``hence thesis by HP.`
`Subproof completed, now type "end focus".`
`Coq` `<``end focus.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`P : nat -``>``Prop`
`HP : P 2`
`HA : A`
`_claim : forall x : nat, x = 2 -``>``P x`
`============================`
`thesis :=`
`A`

### 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.

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`x : nat`
`H : x = 0`
`============================`
`thesis :=`
`x + x = x * x`
`Coq` `<``define sqr x as (x * x).`
`1 subgoal`
`*** Declarative Mode ***`
``
`x : nat`
`H : x = 0`
`sqr := fun x : nat =``>``x * x : nat -``>``nat`
`============================`
`thesis :=`
`x + x = x * x`
`Coq` `<``reconsider thesis as (x + x = sqr x).`
`1 subgoal`
`*** Declarative Mode ***`
``
`x : nat`
`H : x = 0`
`sqr := fun x : nat =``>``x * x : nat -``>``nat`
`============================`
`thesis :=`
`x + x = sqr x`

### 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.

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`P : nat -``>``Prop`
`============================`
`thesis :=`
`forall x : nat, P x -``>``P x`
`Coq` `<``let x:nat.`
`1 subgoal`
`*** Declarative Mode ***`
``
`P : nat -``>``Prop`
`x : nat`
`============================`
`thesis :=`
`P x -``>``P x`
`Coq` `<``assume HP:(P x).`
`1 subgoal`
`*** Declarative Mode ***`
``
`P : nat -``>``Prop`
`x : nat`
`HP : P x`
`============================`
`thesis :=`
`P x`

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`.

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`P : nat -``>``Prop`
`============================`
`thesis :=`
`forall x : nat, P x -``>``P x`
`Coq` `<``let x. (* fails because x’s type is not clear *)`
`Toplevel input, characters 4-5:`
`>``let x.`
`>``` `^`
`Error: Cannot infer the type of x.`
`Coq` `<``let x be such that HP:(P x). (* here x’s type is inferred from (P x) *)`
`1 subgoal`
`*** Declarative Mode ***`
``
`P : nat -``>``Prop`
`x : nat`
`HP : P x`
`============================`
`thesis :=`
`P x`

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

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`P : nat -``>``Prop`
`x : nat`
`============================`
`thesis :=`
`P x -``>``P x -``>``P x`
`Coq` `<``assume (P x). (* temporary name created *)`
`1 subgoal`
`*** Declarative Mode ***`
``
`P : nat -``>``Prop`
`x : nat`
`_hyp : P x`
`============================`
`thesis :=`
`P x -``>``P x`

After `such that`, it is also the case :

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`P : nat -``>``Prop`
`============================`
`thesis :=`
`forall x : nat, P x -``>``P x`
`Coq` `<``let x be such that (P x). (* temporary name created *)`
`1 subgoal`
`*** Declarative Mode ***`
``
`P : nat -``>``Prop`
`x : nat`
`_hyp : P x`
`============================`
`thesis :=`
`P x`

### 11.3.10 Tuple elimination steps

In the pCic, 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...

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`P : nat -``>``Prop`
`A : Prop`
`H : exists x : nat, P x /``\``A`
`============================`
`thesis :=`
`A`
`Coq` `<``consider x such that HP:(P x) and HA:A from H.`
`1 subgoal`
`*** Declarative Mode ***`
``
`P : nat -``>``Prop`
`A : Prop`
`H : exists x : nat, P x /``\``A`
`x : nat`
`HP : P x`
`HA : A`
`============================`
`thesis :=`
`A`

Here is an example with pairs:

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`p : nat * nat`
`============================`
`thesis :=`
`fst p` `>``= snd p` `\``/ fst p` `<``snd p`
`Coq` `<``consider x:nat,y:nat from p.`
`1 subgoal`
`*** Declarative Mode ***`
``
`p : nat * nat`
`x : nat`
`y : nat`
`============================`
`thesis :=`
`fst (x, y)` `>``= snd (x, y)` `\``/ fst (x, y)` `<``snd (x, y)`
`Coq` `<``reconsider thesis as (x` `>``= y` `\``/ x` `<``y).`
`1 subgoal`
`*** Declarative Mode ***`
``
`p : nat * nat`
`x : nat`
`y : nat`
`============================`
`thesis :=`
`x` `>``= y` `\``/ x` `<``y`

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

`Coq` `<``Show.`
`1 subgoal`
`*** Declarative Mode ***`
``
`P : nat -``>``Prop`
`HP : forall n : nat, P n -``>``P (n - 1)`
`============================`
`thesis :=`
`(exists m : nat, P m) -``>``P 0`
`Coq` `<``given m such that Hm:(P m).`
`1 subgoal`
`*** Declarative Mode ***`
``
`P : nat -``>``Prop`
`HP : forall n : nat, P n -``>``P (n - 1)`
`m : nat`
`Hm : P m`
`============================`
`thesis :=`
`P 0`

### 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`.

`Coq` `<``per cases on HAB.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`B : Prop`
`C : Prop`
`HAC : A -``>``C`
`HBC : B -``>``C`
`HAB : A` `\``/ B`
`============================`
`thesis :=`
`C`
`Coq` `<``suppose A.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`B : Prop`
`C : Prop`
`HAC : A -``>``C`
`HBC : B -``>``C`
`HAB : A` `\``/ B`
`_hyp : A`
`============================`
`thesis :=`
`C`
`Coq` `<``hence thesis by HAC.`
`Subproof completed, now type "end cases" or start a new case.`
`Coq` `<``suppose HB:B.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`B : Prop`
`C : Prop`
`HAC : A -``>``C`
`HBC : B -``>``C`
`HAB : A` `\``/ B`
`HB : B`
`============================`
`thesis :=`
`C`
`Coq` `<``thus thesis by HB,HBC.`
`Subproof completed, now type "end cases" or start a new case.`
`Coq` `<``end cases.`
`Subproof completed, now type "end proof".`

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 :

`Coq` `<``Hypothesis EM : forall P:Prop, P` `\``/` `~``P.`
`EM is assumed`
`Coq` `<``per cases of (A` `\``/` `~``A) by EM.`
`1 subgoal`
`*** Declarative Mode ***`
``
`EM : forall P : Prop, P` `\``/` `~``P`
`A : Prop`
`C : Prop`
`HAC : A -``>``C`
`HNAC :` `~``A -``>``C`
`anonymous_matched : A` `\``/` `~``A`
`============================`
`thesis :=`
`C`
`Coq` `<``suppose (``~``A).`
`1 subgoal`
`*** Declarative Mode ***`
``
`EM : forall P : Prop, P` `\``/` `~``P`
`A : Prop`
`C : Prop`
`HAC : A -``>``C`
`HNAC :` `~``A -``>``C`
`anonymous_matched : A` `\``/` `~``A`
`_hyp :` `~``A`
`============================`
`thesis :=`
`C`
`Coq` `<``hence thesis by HNAC.`
`Subproof completed, now type "end cases" or start a new case.`
`Coq` `<``suppose A.`
`1 subgoal`
`*** Declarative Mode ***`
``
`EM : forall P : Prop, P` `\``/` `~``P`
`A : Prop`
`C : Prop`
`HAC : A -``>``C`
`HNAC :` `~``A -``>``C`
`anonymous_matched : A` `\``/` `~``A`
`_hyp : A`
`============================`
`thesis :=`
`C`
`Coq` `<``hence thesis by HAC.`
`Subproof completed, now type "end cases" or start a new case.`
`Coq` `<``end cases.`
`Subproof completed, now type "end proof".`

### 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.

`Coq` `<``per cases on (EM A).`
`1 subgoal`
`*** Declarative Mode ***`
``
`EM : forall P : Prop, P` `\``/` `~``P`
`A : Prop`
`C : Prop`
`HAC : A -``>``C`
`HNAC :` `~``A -``>``C`
`============================`
`thesis :=`
`C`
`Coq` `<``suppose (``~``A).`
`1 subgoal`
`*** Declarative Mode ***`
``
`EM : forall P : Prop, P` `\``/` `~``P`
`A : Prop`
`C : Prop`
`HAC : A -``>``C`
`HNAC :` `~``A -``>``C`
`_hyp :` `~``A`
`============================`
`thesis :=`
`C`

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.

`Coq` `<``per cases on x.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`B : Prop`
`x : bool`
`============================`
`thesis :=`
`(if x then A else B) -``>``A` `\``/ B`
`Coq` `<``suppose it is true.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`B : Prop`
`x : bool`
`============================`
`thesis :=`
`A -``>``A` `\``/ B`
`Coq` `<``assume A.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`B : Prop`
`x : bool`
`_hyp : A`
`============================`
`thesis :=`
`A` `\``/ B`
`Coq` `<``hence A.`
`Subproof completed, now type "end cases" or start a new case.`
`Coq` `<``suppose it is false.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`B : Prop`
`x : bool`
`============================`
`thesis :=`
`B -``>``A` `\``/ B`
`Coq` `<``assume B.`
`1 subgoal`
`*** Declarative Mode ***`
``
`A : Prop`
`B : Prop`
`x : bool`
`_hyp : B`
`============================`
`thesis :=`
`A` `\``/ B`
`Coq` `<``hence B.`
`Subproof completed, now type "end cases" or start a new case.`
`Coq` `<``end cases.`
`Subproof completed, now type "end proof".`

### 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` pattern `and` induction hypothesis. The induction hypothesis can be given explicitly or identified by the sub-object m it refers to using `thesis for` m.

`Coq` `<``per induction on n.`
`1 subgoal`
`*** Declarative Mode ***`
``
`n : nat`
`============================`
`thesis :=`
`n + 0 = n`
`Coq` `<``suppose it is 0.`
`1 subgoal`
`*** Declarative Mode ***`
``
`n : nat`
`============================`
`thesis :=`
`0 + 0 = 0`
`Coq` `<``thus (0 + 0 = 0).`
`Subproof completed, now type "end induction" or start a new case.`
`Coq` `<``suppose it is (S m) and H:thesis for m.`
`1 subgoal`
`*** Declarative Mode ***`
``
`n : nat`
`m : nat`
`H : m + 0 = m`
`============================`
`thesis :=`
`S m + 0 = S m`
`Coq` `<``then (S (m + 0) = S m).`
`1 subgoal`
`*** Declarative Mode ***`
``
`n : nat`
`m : nat`
`H : m + 0 = m`
`_fact : S (m + 0) = S m`
`============================`
`thesis :=`
`S m + 0 = S m`
`Coq` `<``thus =``~``(S m + 0).`
`Subproof completed, now type "end induction" or start a new case.`
`Coq` `<``end induction.`
`Subproof completed, now type "end proof".`

### 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 [33]. They will find in that paper a formal semantics of the proof state transition induces by mathematical commands.