# Chapter 11  The C-zar 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 a 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.

While not being a purely declarative language, the C-zar mathematical proof language aims at providing a solution for users who wish to edit Coq proofs following the declarative philosophy.

### 11.1.3  Well-formedness and Completeness

The C-zar 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 C-zar 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 C-zar 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 C-zar 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 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 underscore ’_’ character (e.g. _hyp0). Temporary names have a lifespan of one command: they get erased after the next command. They can however be used 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 C-zar 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.
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 C-zar 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 C-zar 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 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 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

The users looking for more information should have a look at the paper [33]. This paper features a formal semantics of proof state transitions corresponding to the mathematical commands.