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

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

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 focused subgoal (unfocused: 0)
  
  ============================
   True

Coq <   thus thesis.
No more subgoals.

Coq < end proof.
No more subgoals.

Coq < Qed.
Anomaly: Cannot print a raw proof_instr. Please report.

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 focused subgoal (unfocused: 2)
  
  ============================
   True

Coq <     thus thesis.
2 subgoals
  
  ============================
   True
subgoal 2 is:
 True

Coq <   end proof.
Anomaly: Uncaught exception Invalid_argument("get_info").
Please report.

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

Coq <   proof. (* third subgoal *)
1 focused subgoal (unfocused: 0)
  
  ============================
   True

Coq <     thus thesis.
No more subgoals.

Coq <   end proof.
No more subgoals.

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 focused subgoal (unfocused: 0)
  
  ============================
   False

Coq < end proof. (* here a warning is issued *)
1 focused subgoal (unfocused: 0)
  
  ============================
   False

Coq < Qed. (* fails : the proof in incomplete *)
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 focused subgoal (unfocused: 0)
  
  ============================
   True

Coq <  escape.
1 focused subgoal (unfocused: 0-0)
  
  ============================
   True

Coq <  auto.
No more subgoals.

Coq <  return.
No more subgoals.

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 focused subgoal (unfocused: 0)
  
  a := false : bool
  b := true : bool
  H : if a then True else False
  ============================
   if b then True else False

Coq <  reconsider H as False.
1 focused subgoal (unfocused: 0)
  
  a := false : bool
  b := true : bool
  H : False
  ============================
   if b then True else False

Coq <  reconsider thesis as True.
1 focused subgoal (unfocused: 0)
  
  a := false : bool
  b := true : bool
  H : False
  ============================
   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 focused subgoal (unfocused: 0)
  
  x : nat
  H : x = 2
  ============================
   2 + x = 4

Coq <  have H’:(2+x=2+2) by H.
1 focused subgoal (unfocused: 0)
  
  x : nat
  H : x = 2
  H’ : 2 + x = 2 + 2
  ============================
   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 focused subgoal (unfocused: 0)
  
  x : nat
  H : x = 2
  ============================
   2 + x = 4

Coq <  then (2+x=2+2).
1 focused subgoal (unfocused: 0)
  
  x : nat
  H : x = 2
  _fact : 2 + x = 2 + 2
  ============================
   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 focused subgoal (unfocused: 0)
  
  x : nat
  H : x = 2
  ============================
   x + x = x * x

Coq <  have (4 = 4).
1 focused subgoal (unfocused: 0)
  
  x : nat
  H : x = 2
  _fact : 4 = 4
  ============================
   x + x = x * x

Coq <         ~= (2 * 2).
1 focused subgoal (unfocused: 0)
  
  x : nat
  H : x = 2
  _eq : 4 = 2 * 2
  ============================
   x + x = x * x

Coq <         ~= (x * x) by H.
1 focused subgoal (unfocused: 0)
  
  x : nat
  H : x = 2
  _eq0 : 4 = x * x
  ============================
   x + x = x * x

Coq <         =~ (2 + 2).
1 focused subgoal (unfocused: 0)
  
  x : nat
  H : x = 2
  _eq : 2 + 2 = x * x
  ============================
   x + x = x * x

Coq <         =~ H’:(x + x) by H.
1 focused subgoal (unfocused: 0)
  
  x : nat
  H : x = 2
  H’ : x + x = x * x
  ============================
   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 focused subgoal (unfocused: 0)
  
  x : nat
  H : x + x = x * x
  ============================
   x = 0 \/ x = 2

Coq < claim H’:((x - 2) * x = 0).
1 focused subgoal (unfocused: 1-0)
  
  x : nat
  H : x + x = x * x
  ============================
   (x - 2) * x = 0

A few steps later ...

Coq < thus thesis. 
Warning: Insufficient justification.
1 focused subgoal (unfocused: 0)
  
  x : nat
  H : x + x = x * x
  H’ : (x - 2) * x = 0
  ============================
   x = 0 \/ x = 2

Coq < end claim.
1 focused subgoal (unfocused: 0)
  
  x : nat
  H : x + x = x * x
  H’ : (x - 2) * x = 0
  ============================
   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.
1 focused subgoal (unfocused: 0)
  
  A : Prop
  B : Prop
  HA : A
  HB : B
  ============================
   A /\ B

Coq < hence B.
1 focused subgoal (unfocused: 0)
  
  A : Prop
  B : Prop
  HA : A
  HB : B
  _fact : B
  ============================
   A

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

Coq < Show.
1 focused subgoal (unfocused: 0)
  
  A : Prop
  B : Prop
  C : Prop
  HA : A
  HB : B
  HC : C
  ============================
   A /\ B /\ C

Coq < thus B by HB.
1 focused subgoal (unfocused: 0)
  
  A : Prop
  B : Prop
  C : Prop
  HA : A
  HB : B
  HC : C
  _fact : B
  ============================
   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 focused subgoal (unfocused: 0)
  
  A : Prop
  B : Prop
  C : Prop
  HA : A
  HB : B
  HC : C
  ============================
   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 focused subgoal (unfocused: 0)
  
  A : Prop
  B : Prop
  HB : B
  ============================
   A \/ B

Coq < hence B.
No more subgoals.

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

Coq < Show.
1 focused subgoal (unfocused: 0)
  
  A : Prop
  B : Prop
  C : Prop
  D : Prop
  HC : C
  HD : D
  ============================
   A /\ B \/ C /\ D

Coq < thus C by HC.
1 focused subgoal (unfocused: 0)
  
  A : Prop
  B : Prop
  C : Prop
  D : Prop
  HC : C
  HD : D
  _fact : C
  ============================
   D

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

Coq < Show.
1 focused subgoal (unfocused: 0)
  
  P : nat -> Prop
  HP : P 2
  ============================
   exists x : nat, P x

Coq < take 2.
1 focused subgoal (unfocused: 0)
  
  P : nat -> Prop
  HP : P 2
  ============================
   P 2

It is also possible to prove the existence directly.

Coq < Show.
1 focused subgoal (unfocused: 0)
  
  P : nat -> Prop
  HP : P 2
  ============================
   exists x : nat, P x

Coq < hence (P 2).
No more subgoals.

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 focused subgoal (unfocused: 0)
  
  P : nat -> Prop
  R : nat -> nat -> Prop
  HP : P 2
  HR : R 0 2
  ============================
   exists x y : nat, P y /\ R x y

Coq < thus (P 2) by HP.
1 focused subgoal (unfocused: 0)
  
  P : nat -> Prop
  R : nat -> nat -> Prop
  HP : P 2
  HR : R 0 2
  _fact : P 2
  ============================
   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 focused subgoal (unfocused: 0)
  
  A : Prop
  B : Prop
  P : nat -> Prop
  HP : forall x : nat, P x -> B
  HA : A
  ============================
   A /\ B

Coq < suffices to have x such that HP’:(P x) to show B by HP,HP’.
1 focused subgoal (unfocused: 0)
  
  A : Prop
  B : Prop
  P : nat -> Prop
  HP : forall x : nat, P x -> B
  HA : A
  _cofact : forall x : nat, P x -> B
  ============================
   A /\ (exists n : nat, P n)

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

Coq < Show.
1 focused subgoal (unfocused: 0)
  
  A : Prop
  P : nat -> Prop
  HP : P 2
  HA : A
  ============================
   A /\ (forall x : nat, x = 2 -> P x)

Coq < focus on (forall x, x = 2 -> P x).
Error: No such section variable or assumption: _claim.

Coq < let x be such that (x = 2).
Error: No product even after head-reduction.

Coq < hence thesis by HP.
No more subgoals.

Coq < end focus.
No more subgoals.

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 focused subgoal (unfocused: 0)
  
  x : nat
  H : x = 0
  ============================
   x + x = x * x

Coq < define sqr x as (x * x).
1 focused subgoal (unfocused: 0)
  
  x : nat
  H : x = 0
  sqr := fun x : nat => x * x : nat -> nat
  ============================
   x + x = x * x

Coq < reconsider thesis as (x + x = sqr x).
1 focused subgoal (unfocused: 0)
  
  x : nat
  H : x = 0
  sqr := fun x : nat => x * x : nat -> nat
  ============================
   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 focused subgoal (unfocused: 0)
  
  P : nat -> Prop
  ============================
   forall x : nat, P x -> P x

Coq < let x:nat.
1 focused subgoal (unfocused: 0)
  
  P : nat -> Prop
  x : nat
  ============================
   P x -> P x

Coq < assume HP:(P x).
1 focused subgoal (unfocused: 0)
  
  P : nat -> Prop
  x : nat
  HP : P x
  ============================
   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 focused subgoal (unfocused: 0)
  
  P : nat -> Prop
  ============================
   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 focused subgoal (unfocused: 0)
  
  P : nat -> Prop
  x : nat
  HP : P x
  ============================
   P x

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

Coq < Show.
1 focused subgoal (unfocused: 0)
  
  P : nat -> Prop
  x : nat
  ============================
   P x -> P x -> P x

Coq < assume (P x). (* temporary name created *)
1 focused subgoal (unfocused: 0)
  
  P : nat -> Prop
  x : nat
  _hyp : P x
  ============================
   P x -> P x

After such that, it is also the case :

Coq < Show.
1 focused subgoal (unfocused: 0)
  
  P : nat -> Prop
  ============================
   forall x : nat, P x -> P x

Coq < let x be such that (P x). (* temporary name created *)
1 focused subgoal (unfocused: 0)
  
  P : nat -> Prop
  x : nat
  _hyp : P x
  ============================
   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 focused subgoal (unfocused: 0)
  
  P : nat -> Prop
  A : Prop
  H : exists x : nat, P x /\ A
  ============================
   A

Coq < consider x such that HP:(P x) and HA:A from H.
1 focused subgoal (unfocused: 0)
  
  P : nat -> Prop
  A : Prop
  H : exists x : nat, P x /\ A
  x : nat
  HP : P x
  HA : A
  ============================
   A

Here is an example with pairs:

Coq < Show.
1 focused subgoal (unfocused: 0)
  
  p : nat * nat
  ============================
   fst p >= snd p \/ fst p < snd p

Coq < consider x:nat,y:nat from p.
1 focused subgoal (unfocused: 0)
  
  p : nat * nat
  x : nat
  y : nat
  ============================
   fst (x, y) >= snd (x, y) \/ fst (x, y) < snd (x, y)

Coq < reconsider thesis as (x >= y \/ x < y). 
1 focused subgoal (unfocused: 0)
  
  p : nat * nat
  x : nat
  y : nat
  ============================
   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 focused subgoal (unfocused: 0)
  
  P : nat -> Prop
  HP : forall n : nat, P n -> P (n - 1)
  ============================
   (exists m : nat, P m) -> P 0

Coq < given m such that Hm:(P m).  
1 focused subgoal (unfocused: 0)
  
  P : nat -> Prop
  HP : forall n : nat, P n -> P (n - 1)
  m : nat
  Hm : P m
  ============================
   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 focused subgoal (unfocused: 0-0)
  
  A : Prop
  B : Prop
  C : Prop
  HAC : A -> C
  HBC : B -> C
  HAB : A \/ B
  ============================
   C

Coq < suppose A.
1 focused subgoal (unfocused: 1-0-0)
  
  A : Prop
  B : Prop
  C : Prop
  HAC : A -> C
  HBC : B -> C
  HAB : A \/ B
  _hyp : A
  ============================
   C

Coq <   hence thesis by HAC.
1 focused subgoal (unfocused: 0-0)
  
  A : Prop
  B : Prop
  C : Prop
  HAC : A -> C
  HBC : B -> C
  HAB : A \/ B
  subcase_ : A -> C
  ============================
   C

Coq < suppose HB:B.
1 focused subgoal (unfocused: 1-0-0)
  
  A : Prop
  B : Prop
  C : Prop
  HAC : A -> C
  HBC : B -> C
  HAB : A \/ B
  HB : B
  ============================
   C

Coq <   thus thesis by HB,HBC.
1 focused subgoal (unfocused: 0-0)
  
  A : Prop
  B : Prop
  C : Prop
  HAC : A -> C
  HBC : B -> C
  HAB : A \/ B
  subcase_ : A -> C
  subcase_0 : B -> C
  ============================
   C

Coq < end cases.
No more subgoals.

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
Warning: EM is declared as a parameter because it is at a global level
Coq < per cases of (A \~A) by EM.
1 focused subgoal (unfocused: 0-0)
  
  A : Prop
  C : Prop
  HAC : A -> C
  HNAC : ~ A -> C
  anonymous_matched : A \~ A
  ============================
   C

Coq < suppose (~A).
1 focused subgoal (unfocused: 1-0-0)
  
  A : Prop
  C : Prop
  HAC : A -> C
  HNAC : ~ A -> C
  anonymous_matched : A \~ A
  _hyp : ~ A
  ============================
   C

Coq <   hence thesis by HNAC.
1 focused subgoal (unfocused: 0-0)
  
  A : Prop
  C : Prop
  HAC : A -> C
  HNAC : ~ A -> C
  anonymous_matched : A \~ A
  subcase_ : ~ A -> C
  ============================
   C

Coq < suppose A.
1 focused subgoal (unfocused: 1-0-0)
  
  A : Prop
  C : Prop
  HAC : A -> C
  HNAC : ~ A -> C
  anonymous_matched : A \~ A
  _hyp : A
  ============================
   C

Coq <   hence thesis by HAC.
1 focused subgoal (unfocused: 0-0)
  
  A : Prop
  C : Prop
  HAC : A -> C
  HNAC : ~ A -> C
  anonymous_matched : A \~ A
  subcase_ : ~ A -> C
  subcase_0 : A -> C
  ============================
   C

Coq < end cases.
No more subgoals.

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 focused subgoal (unfocused: 0-0)
  
  A : Prop
  C : Prop
  HAC : A -> C
  HNAC : ~ A -> C
  ============================
   C

Coq < suppose (~A).
1 focused subgoal (unfocused: 1-0-0)
  
  A : Prop
  C : Prop
  HAC : A -> C
  HNAC : ~ A -> C
  _hyp : ~ A
  ============================
   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 focused subgoal (unfocused: 0-0)
  
  A : Prop
  B : Prop
  x : bool
  ============================
   (if x then A else B) -> A \/ B

Coq < suppose it is true.
1 focused subgoal (unfocused: 1-0-0)
  
  A : Prop
  B : Prop
  x : bool
  ============================
   A -> A \/ B

Coq <   assume A.
1 focused subgoal (unfocused: 1-0-0)
  
  A : Prop
  B : Prop
  x : bool
  _hyp : A
  ============================
   A \/ B

Coq <   hence A.
1 focused subgoal (unfocused: 0-0)
  
  A : Prop
  B : Prop
  x : bool
  subcase_ : (if true then A else B) -> A \/ B
  ============================
   (if x then A else B) -> A \/ B

Coq < suppose it is false.
1 focused subgoal (unfocused: 1-0-0)
  
  A : Prop
  B : Prop
  x : bool
  ============================
   B -> A \/ B

Coq <   assume B.
1 focused subgoal (unfocused: 1-0-0)
  
  A : Prop
  B : Prop
  x : bool
  _hyp : B
  ============================
   A \/ B

Coq <   hence B.
1 focused subgoal (unfocused: 0-0)
  
  A : Prop
  B : Prop
  x : bool
  subcase_ : (if true then A else B) -> A \/ B
  subcase_0 : (if false then A else B) -> A \/ B
  ============================
   (if x then A else B) -> A \/ B

Coq < end cases.
No more subgoals.

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.
1 focused subgoal (unfocused: 0-0)
  
  n : nat
  ============================
   n + 0 = n

Coq < suppose it is 0.
1 focused subgoal (unfocused: 1-0-0)
  
  n : nat
  ============================
   0 + 0 = 0

Coq <   thus (0 + 0 = 0).
1 focused subgoal (unfocused: 0-0)
  
  n : nat
  subcase_ : 0 + 0 = 0
  ============================
   n + 0 = n

Coq < suppose it is (S m) and H:thesis for m.
1 focused subgoal (unfocused: 1-0-0)
  
  n : nat
  m : nat
  H : m + 0 = m
  ============================
   S m + 0 = S m

Coq <   then (S (m + 0) = S m).
1 focused subgoal (unfocused: 1-0-0)
  
  n : nat
  m : nat
  H : m + 0 = m
  _fact : S (m + 0) = S m
  ============================
   S m + 0 = S m

Coq <   thus =~ (S m + 0).
1 focused subgoal (unfocused: 0-0)
  
  n : nat
  subcase_ : 0 + 0 = 0
  subcase_0 : forall m : nat, m + 0 = m -> S m + 0 = S m
  ============================
   n + 0 = n

Coq < end induction.
No more subgoals.

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.