Chapter 11  The Mathematical Proof Language

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:

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:

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 andand 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 andand 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:

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.

Coq < Theorem this_is_trivial: True.
1 subgoal
  
  ============================
   True

Coq < proof.

Coq <   thus thesis.
Subproof completed, now type "end proof".

Coq < end proof.

Coq < Qed.
     thus thesis.
Qed.
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 < Theorem T: (True /\ True) /\ True.

Coq <   split. split.

Coq <   Show.
3 subgoals
  
  ============================
   True
subgoal 2 is:
 True
subgoal 3 is:
 True

Coq <   proof. (* first subgoal *)

Coq <     thus thesis.
Subproof completed, now type "end proof".

Coq <   end proof.

Coq <   trivial. (* second subgoal *)
1 subgoal
  
  ============================
   True

Coq <   proof. (* third subgoal *)

Coq <     thus thesis.
Subproof completed, now type "end proof".

Coq <   end proof.

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.

Coq < end proof. (* here a warning is issued *)

Coq < Fail Qed. (* fails: the proof in incomplete *)
Fail Qed.
The command has indeed failed with message:
Error: Attempt to save a proof with given up goals. If this is really
what you want to do, use Admitted in place of
Qed. (in proof this_is_not_so_trivial)
No more subgoals, but there are some goals you gave up:
1 subgoal
subgoal 1 is:
 False
You need to go back and solve them.

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.
     *** Declarative Mode ***
  
  ============================
  thesis := 
   True

Coq <  escape.

Coq <  auto.
No more subgoals.

Coq <  return.

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.

Coq <  Show.
     *** 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.
     *** Declarative Mode ***
  
  a := false : bool
  b := true : bool
  H : False
  ============================
  thesis := 
   if b then True else False

Coq <  reconsider thesis as True.
     *** 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 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.

Coq <  Show.
     *** Declarative Mode ***
  
  x : nat
  H : x = 2
  ============================
  thesis := 
   2 + x = 4

Coq <  have H':(2+x=2+2) by H.
     *** Declarative Mode ***
  
  x : nat
  H : x = 2
  H' : 2 + x = 2 + 2
  ============================
  thesis := 
   2 + x = 4

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:

Coq <  Show.
     *** Declarative Mode ***
  
  x : nat
  H : x = 2
  ============================
  thesis := 
   2 + x = 4

Coq <  then (2+x=2+2).
     *** 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.
     *** Declarative Mode ***
  
  x : nat
  H : x = 2
  ============================
  thesis := 
   x + x = x * x

Coq <  have (4 = 4).
     *** Declarative Mode ***
  
  x : nat
  H : x = 2
  _fact : 4 = 4
  ============================
  thesis := 
   x + x = x * x

Coq <         ~= (2 * 2).
     *** Declarative Mode ***
  
  x : nat
  H : x = 2
  _eq : 4 = 2 * 2
  ============================
  thesis := 
   x + x = x * x

Coq <         ~= (x * x) by H.
     *** Declarative Mode ***
  
  x : nat
  H : x = 2
  _eq0 : 4 = x * x
  ============================
  thesis := 
   x + x = x * x

Coq <         =~ (2 + 2).
     *** Declarative Mode ***
  
  x : nat
  H : x = 2
  _eq : 2 + 2 = x * x
  ============================
  thesis := 
   x + x = x * x

Coq <         =~ H':(x + x) by H.
     *** 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.
     *** Declarative Mode ***
  
  x : nat
  H : x + x = x * x
  ============================
  thesis := 
   x = 0 \/ x = 2

Coq < claim H':((x - 2) * x = 0).
     *** 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 proof".

Coq < end claim.
     *** 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 stephavethen claim=/=
conclusion stepthushence focus onthus =/=
Figure 11.2: Correspondence between basic forward steps and conclusion steps

Let us begin with simple examples:

Coq < Show.
     *** Declarative Mode ***
  
  A, B : Prop
  HA : A
  HB : B
  ============================
  thesis := 
   A /\ B

Coq < hence B.
     *** Declarative Mode ***
  
  A, B : Prop
  HA : A
  HB, _fact : B
  ============================
  thesis := 
   A

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

Coq < Show.
     *** Declarative Mode ***
  
  A, B, C : Prop
  HA : A
  HB : B
  HC : C
  ============================
  thesis := 
   A /\ B /\ C

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

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

Coq < Show.
     *** Declarative Mode ***
  
  A, B, C : Prop
  HA : A
  HB : B
  HC : C
  ============================
  thesis := 
   A /\ B

Coq < Fail hence C. (* fails *)
The command has indeed failed with message:
Error: I could not relate this statement to the thesis.
     *** Declarative Mode ***
  
  A, B, C : Prop
  HA : A
  HB : B
  HC : C
  ============================
  thesis := 
   A /\ B

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

Coq < Show.
     *** Declarative Mode ***
  
  A, 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.
     *** Declarative Mode ***
  
  A, B, C, D : Prop
  HC : C
  HD : D
  ============================
  thesis := 
   A /\ B \/ C /\ D

Coq < thus C by HC.
     *** Declarative Mode ***
  
  A, B, C, 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.
     *** Declarative Mode ***
  
  P : nat -> Prop
  HP : P 2
  ============================
  thesis := 
   exists x : nat, P x

Coq < take 2.
     *** Declarative Mode ***
  
  P : nat -> Prop
  HP : P 2
  ============================
  thesis := 
   P 2

It is also possible to prove the existence directly.

Coq < Show.
     *** 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.
     *** Declarative Mode ***
  
  P : nat -> Prop
  R : nat -> nat -> Prop
  HP : P 2
  HR : R 0 2
  ============================
  thesis := 
   exists x y : nat, P y /\ R x y

Coq < thus (P 2) by HP.
     *** 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 replacing the conclusion (or part of it) by a sufficient condition.

Coq < Show.
     *** Declarative Mode ***
  
  A, 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'.
     *** Declarative Mode ***
  
  A, 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.
     *** 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).
Toplevel input, characters 0-34:
> focus on (forall x, x = 2 -> P x).
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Error: No such section variable or assumption: _claim.

Coq < let x be such that (x = 2).
Toplevel input, characters 0-27:
> let x be such that (x = 2).
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^
Error: No product even after head-reduction.

Coq < hence thesis by HP.
Subproof completed, now type "end proof".

Coq < end focus.
Toplevel input, characters 0-10:
> end focus.
> ^^^^^^^^^^
Anomaly: error with no safe_id attached:
Uncaught exception Invalid_argument("get_info").. Please report.

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.
     *** Declarative Mode ***
  
  x : nat
  H : x = 0
  ============================
  thesis := 
   x + x = x * x

Coq < define sqr x as (x * x).
     *** 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).
     *** 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.
     *** Declarative Mode ***
  
  P : nat -> Prop
  ============================
  thesis := 
   forall x : nat, P x -> P x

Coq < let x:nat.
     *** Declarative Mode ***
  
  P : nat -> Prop
  x : nat
  ============================
  thesis := 
   P x -> P x

Coq < assume HP:(P x).
     *** 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.
     *** Declarative Mode ***
  
  P : nat -> Prop
  ============================
  thesis := 
   forall x : nat, P x -> P x

Coq < Fail let x. (* fails because x's type is not clear *)
The command has indeed failed with message:
Cannot infer the type of x in environment:
P : nat -> Prop
     *** Declarative Mode ***
  
  P : nat -> Prop
  ============================
  thesis := 
   forall x : nat, P x -> P x

Coq < let x be such that HP:(P x). (* here x's type is inferred from (P x) *)
     *** 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.
     *** Declarative Mode ***
  
  P : nat -> Prop
  x : nat
  ============================
  thesis := 
   P x -> P x -> P x

Coq < assume (P x). (* temporary name created *)
     *** 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.
     *** Declarative Mode ***
  
  P : nat -> Prop
  ============================
  thesis := 
   forall x : nat, P x -> P x

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

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

Coq < Show.
     *** 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.
     *** 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.
     *** Declarative Mode ***
  
  p : nat * nat
  ============================
  thesis := 
   fst p >= snd p \/ fst p < snd p

Coq < consider x:nat,y:nat from p.
     *** Declarative Mode ***
  
  p : nat * nat
  x, y : nat
  ============================
  thesis := 
   fst (x, y) >= snd (x, y) \/ fst (x, y) < snd (x, y)

Coq < reconsider thesis as (x >= y \/ x < y). 
     *** Declarative Mode ***
  
  p : nat * nat
  x, 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.
     *** 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).  
     *** 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.
     *** Declarative Mode ***
  
  A, B, C : Prop
  HAC : A -> C
  HBC : B -> C
  HAB : A \/ B
  ============================
  thesis := 
   C

Coq < suppose A.
     *** Declarative Mode ***
  
  A, B, 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.
     *** Declarative Mode ***
  
  A, B, 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.
     *** Declarative Mode ***
  
  EM : forall P : Prop, P \~ P
  A, C : Prop
  HAC : A -> C
  HNAC : ~ A -> C
  anonymous_matched : A \~ A
  ============================
  thesis := 
   C

Coq < suppose (~A).
     *** Declarative Mode ***
  
  EM : forall P : Prop, P \~ P
  A, 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.
     *** Declarative Mode ***
  
  EM : forall P : Prop, P \~ P
  A, 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).
     *** Declarative Mode ***
  
  EM : forall P : Prop, P \~ P
  A, C : Prop
  HAC : A -> C
  HNAC : ~ A -> C
  ============================
  thesis := 
   C

Coq < suppose (~A).
     *** Declarative Mode ***
  
  EM : forall P : Prop, P \~ P
  A, 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.
     *** Declarative Mode ***
  
  A, B : Prop
  x : bool
  ============================
  thesis := 
   (if x then A else B) -> A \/ B

Coq < suppose it is true.
     *** Declarative Mode ***
  
  A, B : Prop
  x : bool
  ============================
  thesis := 
   A -> A \/ B

Coq <   assume A.
     *** Declarative Mode ***
  
  A, 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.
     *** Declarative Mode ***
  
  A, B : Prop
  x : bool
  ============================
  thesis := 
   B -> A \/ B

Coq <   assume B.
     *** Declarative Mode ***
  
  A, 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 patternand 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.
     *** Declarative Mode ***
  
  n : nat
  ============================
  thesis := 
   n + 0 = n

Coq < suppose it is 0.
     *** 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.
     *** Declarative Mode ***
  
  n, m : nat
  H : m + 0 = m
  ============================
  thesis := 
   S m + 0 = S m

Coq <   then (S (m + 0) = S m).
     *** Declarative Mode ***
  
  n, 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 [34]. They will find in that paper a formal semantics of the proof state transition induces by mathematical commands.