Advanced elimination / induction

Authors:

Yannick Forster

Théo Winterhalter

Files:
The goal of this lecture is to:
  • Understand more about universes in Rocq, i.e. about Type and Prop. This is helpful to decipher certain error messages that occasionally occur in practical developments.

  • Understand how induction principles are implemented and use this knowledge to implement induction principles for inductive types where Rocq's automated generation is too weak.

From Stdlib Require Import Arith Lia List.
Import ListNotations.

Universes

We have already seen Type and Prop. They are what we call universes: they are types of types.

You have seen that seemingly Type : Type:

Type : Type : Type

But also that Type is actually a hierarchy of universes Type@{i} in order to avoid inconsistencies with Type : Type, which becomes visible once universe printing is enabled.

Set Printing Universes.

Type@{lesson5_part1.24} : Type@{lesson5_part1.23} : Type@{lesson5_part1.23} (* {lesson5_part1.24 lesson5_part1.23} |= lesson5_part1.24 < lesson5_part1.23 *)

Below we will see more about the typing rules of Type, in particular a reminder of how the typing rule of forall works.

We use the section mechanism which allows us to declare universe levels and so on.

Section Universes.

Command Universes declares universe levels, while Constraint lets us add (in)equalities between them. Below we declare levels i and j together with constraint i < j. We can see that Type@{i} is of type Type@{j} but not the converse.

  Universes i j.
  Constraint i < j.
  
Type@{i} : Type@{j} : Type@{j} (* {} |= i < j *)
The command has indeed failed with message: The term "Type@{j}" has type "Type@{j+1}" while it is expected to have type "Type@{i}" (universe inconsistency: Cannot enforce j < i because i < j).

Here is the corresponding typing rule:

\begin{equation*} \cfrac{i < j} {\Gamma \vdash \mathsf{Type}_i : \mathsf{Type}_j} \end{equation*}

Universe of a ∀ quantifier

Let us now have a look at the type of a forall in Rocq. For this we're going to use another feature of the section mechanism: the Context command allows us to add assumptions in our context, similar to assumptions for a lemma.

  Universe k.

  Context (A : Type@{i}) (B : Type@{k}).

As you can see below, the type of a forall is the maximum of the types of the domain and codomain. See what it means for a forall containing Type.

  
A -> B : Type@{max(i,k)}
Type@{i} -> Type@{k} : Type@{max(i+1,k+1)}

The universal quantifier is often called Π-type (because it's a product in some sense), especially when we are talking about types and not propositions. The corresponding typing rule is given below.

\begin{equation*} \cfrac{ \Gamma \vdash A : \mathsf{Type}_i \quad \Gamma, x : A \vdash B : \mathsf{Type}_j } {\Gamma \vdash \Pi (x : A). B : \mathsf{Type}_{\max(i,j)}} \end{equation*}

Cumulativity

By the way, above, we've just seen a use of so-called cumulativity which says that Type@{i} lives in Type@{j} for any j that's bigger than i. By contrast, in Agda or Lean, we have unique typing and thus Type@{i} is of type Type@{i+1} and that's it.

Cumulativity is actually more than that. It is in fact a form of subtyping that says that Type@{i} is a subtype of Type@{j} whenever i ≤ j.

See how A : Type@{i} also lives in Type@{j} but how the converse wouldn't work.

  
A : Type@{j} : Type@{j} (* {} |= i <= j *)
Context (C : Type@{j}).
The command has indeed failed with message: In environment A : Type@{i} B : Type@{k} C : Type@{j} The term "C" has type "Type@{j}" while it is expected to have type "Type@{i}" (universe inconsistency: Cannot enforce j <= i because i < j).

Prop, on the other hand, lives in Type@{i} for all i.

  
Prop : Type@{i} : Type@{i} (* {} |= Set < i *)

Here you see Rocq mentions a constraint that Set < i. There is indeed a third kind of universe which we did not mention but you have probably seen already. It's called Set. You can think of it as the lowest Type universe: Type@{0}, but in Rocq it's actually Type@{Set} because the universe levels (i, j, k etc.) are not natural numbers but abstract variables with constraints like the one we added above.

Set is the smallest Type and it is the only one which does not contain Prop. We do have cumulativity going from Prop to Set and Type however.

We give a summary below, where i is universally quantified.

Prop     : Type@{i}
Set      : Type@{i}
Prop     ≤ Type@{i}
Set      ≤ Type@{i}
Type@{i} : Type@{i+1}
Type@{i} ≤ Type@{i+1}

See how it goes in practice:

  
The command has indeed failed with message: In environment A : Type@{i} B : Type@{k} C : Type@{j} The term "Prop" has type "Type@{Set+1}" while it is expected to have type "Set" (universe inconsistency: Cannot enforce Set+1 <= Set).
The command has indeed failed with message: In environment A : Type@{i} B : Type@{k} C : Type@{j} The term "Prop" has type "Type@{Set+1}" while it is expected to have type "Set" (universe inconsistency: Cannot enforce Set+1 <= Set).
Variable (P : Prop).
P : Type@{i} : Type@{i}
P : Set : Set

We rephrase what we just said using inference rules.

\begin{equation*} \cfrac{}{\Gamma \vdash \mathsf{Prop} : \mathsf{Type}_{i}} \qquad \cfrac{}{\Gamma \vdash \mathsf{Set} : \mathsf{Type}_{i}} \qquad \cfrac{i < j}{\Gamma \vdash \mathsf{Type}_i : \mathsf{Type}_j} \end{equation*}
\begin{equation*} \cfrac{}{\Gamma \vdash \mathsf{Prop} \le \mathsf{Type}_i} \qquad \cfrac{}{\Gamma \vdash \mathsf{Set} \le \mathsf{Type}_i} \qquad \cfrac{i \le j}{\Gamma \vdash \mathsf{Type}_i \le \mathsf{Type}_j} \end{equation*}

We also have a subsumption rule below, where \(s\) and \(s'\) are two universes.

\begin{equation*} \cfrac{\Gamma \vdash A : s \quad \Gamma \vdash s \le s'}{\Gamma \vdash A : s'} \end{equation*}

Impredicativity

Prop has other particularities. When considering a forall that ends in a proposition, then the whole forall stays a proposition. This means that things like forall (n : nat), n = n or forall (P : Prop), P are propositions. This property is called impredicativity because things like forall (P : Prop), P are actually quantifying over themselves (P can be instantiated with forall (P : Prop), P).

This is another big difference with Agda which is predicative instead. To remedy this they have to also add universe levels to Prop like Prop@{i}. But in practice, most people only use Type (which they call Set) in Agda. Lean on the other hand does things the same way as Rocq. In fact, impredicativity is very strong and necessary to achieve the full power of ZFC.

In Rocq, the universe of a forall ending in a proposition is always a proposition, regardless of the size of what we quantify over. This comes from the intuition (and models) that Prop is proof-irrelevant: all propositions are morally either empty (False) or contain only one element (True) so Prop can be seen (modelled) as a set with two elements so it is always small.

The commands below illustrate all we just said.

  
The command has indeed failed with message: In environment A : Type@{i} B : Type@{k} C : Type@{j} P : Prop The term "Prop" has type "Type@{Set+1}" while it is expected to have type "Prop" (universe inconsistency: Cannot enforce Set+1 <= Prop).
forall P : Prop, P : Prop
forall n : nat, n = n : Prop
Variable (Q : A -> Prop).
forall x : A, Q x : Prop
Type@{j} -> P : Prop
Unset Printing Universes. End Universes.

Here is the inference rule for a Prop-valued Π-type.

\begin{equation*} \cfrac{ \Gamma \vdash A : \mathsf{Type}_i \quad \Gamma, x : A \vdash B : \mathsf{Prop} } {\Gamma \vdash \Pi (x : A). B : \mathsf{Prop}} \end{equation*}

Elimination restrictions

Universes are also important when defining inductive types. You may wonder when to put your type in Prop or in Type. We have seen several examples: things like disjunction and conjunction are placed in Prop, but bool is a Type for instance.

Things that weigh in a choice are intent of course, but also the fact that Prop is impredicative (as seen above), but also that Prop can be axiomatically assumed to be proof irrelevant. Proof irrelevance is expressed as follows.

Definition PI :=
  forall (P : Prop) (p q : P), p = q.

It states that any two proofs of a given proposition are always equal. In other words, PI being consistent means that proofs cannot impact computation in a meaningful way. That is, we cannot analyse a proof to build a function that is supposed to compute a Boolean.

Consider a variant of bool in Prop below.

Inductive prop_bool : Prop :=
| ptrue
| pfalse.

As long as we remain in Prop, we can do pretty much the same as before.

Definition pneg (b : prop_bool) : prop_bool :=
  match b with
  | ptrue => pfalse
  | pfalse => ptrue
  end.


forall b : prop_bool, pneg (pneg b) = b

forall b : prop_bool, pneg (pneg b) = b

pneg (pneg ptrue) = ptrue

pneg (pneg pfalse) = pfalse
all: reflexivity. Qed.

We can also map the usual Booleans into them.

Definition to_prop_bool (b : bool) : prop_bool :=
  if b then ptrue else pfalse.

But, crucially, we can't do the converse!

The command has indeed failed with message: Incorrect elimination of "b" in the inductive type "prop_bool": the return type has sort "Set" while it should be SProp or Prop. Elimination of an inductive object of sort Prop is not allowed on a predicate in sort "Set" because proofs can be eliminated only to build proofs.

Rocq complains that proofs can only be eliminated to build other proofs. The same happens in proof mode of course.


prop_bool -> bool

prop_bool -> bool
b: prop_bool

bool
The command has indeed failed with message: Incorrect elimination in the inductive type "prop_bool": the return type has sort "Set" while it should be SProp or Prop. Elimination of an inductive object of sort Prop is not allowed on a predicate in sort "Set" because proofs can be eliminated only to build proofs.
b: prop_bool

bool
Abort.

We can instead prove something weaker like this:


forall p : prop_bool, exists b : bool, to_prop_bool b = p

forall p : prop_bool, exists b : bool, to_prop_bool b = p

exists b : bool, to_prop_bool b = ptrue

exists b : bool, to_prop_bool b = pfalse

exists b : bool, to_prop_bool b = ptrue

to_prop_bool true = ptrue
reflexivity.

exists b : bool, to_prop_bool b = pfalse

to_prop_bool false = pfalse
reflexivity. Qed.

We can however not prove that there is a function inverting to_prop_bool because this would be inconsistent with PI:

f: prop_bool -> bool

(forall b : bool, f (to_prop_bool b) = b) -> ~ PI
f: prop_bool -> bool

(forall b : bool, f (to_prop_bool b) = b) -> ~ PI
f: prop_bool -> bool
H: forall b : bool, f (to_prop_bool b) = b
pi: PI

False
f: prop_bool -> bool
H: forall b : bool, f (to_prop_bool b) = b
pi: ptrue = pfalse

False
f: prop_bool -> bool
H: forall b : bool, f (to_prop_bool b) = b
pi: ptrue = pfalse
e1: f (to_prop_bool true) = true

False
f: prop_bool -> bool
H: forall b : bool, f (to_prop_bool b) = b
pi: ptrue = pfalse
e1: f (to_prop_bool true) = true
e2: f (to_prop_bool false) = false

False
f: prop_bool -> bool
H: forall b : bool, f (to_prop_bool b) = b
pi: ptrue = pfalse
e1: f ptrue = true
e2: f pfalse = false

False
f: prop_bool -> bool
H: forall b : bool, f (to_prop_bool b) = b
pi: ptrue = pfalse
e1: f pfalse = true
e2: f pfalse = false

False
congruence. Qed.
Exercise: Booleans in Prop

Define a copy of Booleans called boolp that lives in Prop. Show that you can go from bool to boolp. Can you do the converse? Why? What would a surjective function from boolp to bool mean for proof irrelevance? (We want to see a proof.)

Exercise: Surjectivity

Prove that for all p : boolp, there exists some b : bool such that its mapping to boolp is equal to p.

Exercise: Existential quantifier and Σ types

exists (x : A), P x and { x : A | P x } are two very similar types but the former lives in Prop while the latter is in Type. Show how one implies the other. Why is the other implication not provable?

Exercise: Disjunction and sum

P \/ Q and A + B are also similar types. The first you know as disjunction of propositions, the other one is relevant data that contains either a value of type A, or a value of type B.

Prove that P + Q -> P \/ Q, ideally with a proof term.

Why is the other implication not provable?

Notation "{ A } + { B }" := (sumbool A B) (* A in scope _type_scope, B in scope _type_scope *) : type_scope (default interpretation) (from Corelib.Init.Specif) Notation "A + { B }" := (sumor A B) (* A in scope _type_scope, B in scope _type_scope *) : type_scope (default interpretation) (from Corelib.Init.Specif) Notation "x + y" := (Init.Nat.add x y) (* x in scope _nat_scope, y in scope _nat_scope *) : nat_scope (default interpretation) (from Corelib.Init.Peano) Notation "x + y" := (sum x y) (* x in scope _type_scope, y in scope _type_scope *) : type_scope (from Corelib.Init.Datatypes)
Inductive sum (A B : Type) : Type := inl : A -> A + B | inr : B -> A + B. Arguments sum (A B)%_type_scope Arguments inl {A B}%_type_scope _, [_] _ _ Arguments inr {A B}%_type_scope _, _ [_] _
Exercise: Existential quantifier on Booleans

We can't show that (exists x, P x) -> { x : A | P x } in general, but we can when A is bool and when P x is of the form f x = true. Show it.

Subsingleton criterion

There are crucial exceptions to the rule that forbids elimination from Prop: If a type has at most one constructor and all the non-parameter arguments of the constructor are proofs, then such eliminations are allowed.

This property is called the (sub)singleton criterion because it essentially says that you can inspect (as in case analysis) a proof, as long as there can be at most one such proof. So a term that depends on it doesn't really depend on it in the end, but merely on the fact that there exists a proof.

It is thanks to this property that we can eliminate a proof of False to produce anything else.


False -> nat

False -> nat
bot: False

nat
destruct bot. Qed. Definition exfalso' {A : Type} (bot : False) : A := match bot with end.

It also works with True, but it's not so interesting. We leave it to you as an exercise.

Exercise: True is a singleton

Show that, for any P : True -> Type, it is enough to prove P I to prove any P p. Try to do it with a proof term and explain why it is allowed.

Another more interesting case is equality. This is what lets you use tactics such as rewrite on any type.


forall (n m : nat) (P : nat -> Type), P (n + m) -> P (m + n)

forall (n m : nat) (P : nat -> Type), P (n + m) -> P (m + n)
n, m: nat
P: nat -> Type
x: P (n + m)

P (m + n)
n, m: nat
P: nat -> Type
x: P (n + m)

P (n + m)
assumption. Qed.

The above we can do in general:


forall (A : Type) (P : A -> Type) (u v : A), u = v -> P u -> P v

forall (A : Type) (P : A -> Type) (u v : A), u = v -> P u -> P v
A: Type
P: A -> Type
u, v: A
e: u = v

P u -> P v
A: Type
P: A -> Type
u, v: A
e: u = v

P v -> P v
auto. Qed.

Disjunction for instance does not fall under the criterion:


forall P Q : Prop, P \/ Q -> bool

forall P Q : Prop, P \/ Q -> bool
P, Q: Prop
h: P \/ Q

bool
The command has indeed failed with message: Incorrect elimination in the inductive type "or": the return type has sort "Set" while it should be SProp or Prop. Elimination of an inductive object of sort Prop is not allowed on a predicate in sort "Set" because proofs can be eliminated only to build proofs.
P, Q: Prop
h: P \/ Q

bool
Abort.

We could try to cheat by boxing a proposition so it only has one constructor but it doesn't actually help.

Inductive Box (P : Prop) : Prop :=
| box (p : P).


forall P Q : Prop, Box (P \/ Q) -> bool

forall P Q : Prop, Box (P \/ Q) -> bool
P, Q: Prop
h: Box (P \/ Q)

bool
P, Q: Prop
p: P \/ Q

bool
The command has indeed failed with message: The variable h was not found in the current environment.
P, Q: Prop
p: P \/ Q

bool
Abort.
Exercise: Ex falso

Write a term that goes from False to any A : Type. Explain why this term is allowed.

Exercise: Conjunction

We have seen above that disjunction did not satisfy the subsingleton criterion. What about conjunction? State the equivalence between P * Q and P /\ Q. Either give a proof script that fails because conjunction does not satisfy the subsingleton criterion, or give a proof script that works because it does. Explain why it satisfies it or not.

Exercise: Singleton version of le

Propose a version of le that satisfies the singleton criterion (in particular, make sure it is defined in Prop). You can use the goal below with le (<=) and with your le'. It should only work with le'. Is it satisfying? If not you can try and think if you can't define one (perhaps not with the Inductive keyword) that works a bit better. Be warned: you probably won't be satisfied either.


forall n m : nat, n <= m -> nat

forall n m : nat, n <= m -> nat
n, m: nat
h: n <= m

nat
The command has indeed failed with message: Incorrect elimination in the inductive type "le": the return type has sort "Set" while it should be SProp or Prop. Elimination of an inductive object of sort Prop is not allowed on a predicate in sort "Set" because proofs can be eliminated only to build proofs.
n, m: nat
h: n <= m

nat
Abort.

Induction principles

Let us now move to induction principles. For this, we'll have a look at trees again.

We can easily define binary trees (with labels in A) as follows.

Inductive bintree A :=
| bt_leaf (a : A)
| bt_node (a : A) (l r : bintree A).

Arguments bt_leaf {A}.
Arguments bt_node {A}.

As for every inductive type, Rocq generates induction principles corresponding to the various sorts:

  • bintree_ind for Prop,

  • bintree_rect for Type,

  • bintree_rec for Set (but you can ignore it and use bintree_rect).

They only vary in the return type of the motive (the return predicate).

bintree_rect : forall (A : Type) (P : bintree A -> Type), (forall a : A, P (bt_leaf a)) -> (forall (a : A) (l : bintree A), P l -> forall r : bintree A, P r -> P (bt_node a l r)) -> forall b : bintree A, P b

Now consider the following map function on bintree.

Fixpoint bt_map {A B} (f : A -> B) (t : bintree A) : bintree B :=
  match t with
  | bt_leaf a => bt_leaf (f a)
  | bt_node a l r => bt_node (f a) (bt_map f l) (bt_map f r)
  end.

When proving properties about it, we will use the induction tactic which picks up the corresponding induction principle, below bintree_ind, and applies it for us.


forall (A : Type) (t : bintree A), bt_map (fun x : A => x) t = t

forall (A : Type) (t : bintree A), bt_map (fun x : A => x) t = t
A: Type
t: bintree A

bt_map (fun x : A => x) t = t
A: Type
a: A

bt_map (fun x : A => x) (bt_leaf a) = bt_leaf a
A: Type
a: A
l, r: bintree A
ihl: bt_map (fun x : A => x) l = l
ihr: bt_map (fun x : A => x) r = r
bt_map (fun x : A => x) (bt_node a l r) = bt_node a l r
A: Type
a: A

bt_map (fun x : A => x) (bt_leaf a) = bt_leaf a
reflexivity.
A: Type
a: A
l, r: bintree A
ihl: bt_map (fun x : A => x) l = l
ihr: bt_map (fun x : A => x) r = r

bt_map (fun x : A => x) (bt_node a l r) = bt_node a l r
A: Type
a: A
l, r: bintree A
ihl: bt_map (fun x : A => x) l = l
ihr: bt_map (fun x : A => x) r = r

bt_node a (bt_map (fun x : A => x) l) (bt_map (fun x : A => x) r) = bt_node a l r
A: Type
a: A
l, r: bintree A
ihl: bt_map (fun x : A => x) l = l
ihr: bt_map (fun x : A => x) r = r

bt_node a l r = bt_node a l r
reflexivity. Qed.

If you print the term, you will see that it indeed starts with an application of bintree_ind. No need to read the rest for now.

bt_map_id = fun (A : Type) (t : bintree A) => bintree_ind A (fun t0 : bintree A => bt_map (fun x : A => x) t0 = t0) (fun a : A => eq_refl) (fun (a : A) (l : bintree A) (ihl : bt_map (fun x : A => x) l = l) (r : bintree A) (ihr : bt_map (fun x : A => x) r = r) => eq_ind_r (fun b : bintree A => bt_node a b (bt_map (fun x : A => x) r) = bt_node a l r) (eq_ind_r (fun b : bintree A => bt_node a l b = bt_node a l r) eq_refl ihr) ihl : bt_map (fun x : A => x) (bt_node a l r) = bt_node a l r) t : forall (A : Type) (t : bintree A), bt_map (fun x : A => x) t = t Arguments bt_map_id A%_type_scope t
Exercise: Binary trees

Define an inductive type bintree' for binary trees. Write down both type and term for bintree_rect' (the induction principle with Type-valued motive) manually.

Exercise: Map on binary trees

Define a map function for it, and show mapping with the identity results in the identity on binary trees.

Exercise: Induction principle for indexed type

Define an inductive type dtree A : nat -> Type for binary trees indexed by their depth. State and prove (with a term) its Type-valued induction principle.

Nested induction principles

We have seen in week 3 that nested inductive types required special care, because by default, Rocq generates the wrong induction principle. Since Rocq 9.2 — the version we are currently using — the situation changed slightly. In fact, if you define a nested inductive type like tree you will see a bunch of warnings appearing (in fact, it's many times the same warning, who knows why 🤷).

mytree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
mytree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
mytree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
mytree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
mytree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
mytree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
mytree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
mytree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
mytree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
mytree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
mytree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
mytree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]

The warning tells you that no "scheme" for list is registered as All. Since the warning is so insistent, let us follow its advice.

Scheme All for list.

This defines a new inductive type called list_all that is a bit like Forall:

Inductive list_all@{α ; u u0} (A : Type) (PA : A -> Type@{α ; _}) : list A -> Type := nil_all : list_all A PA [] | cons_all : forall a : A, PA a -> forall l : list A, list_all A PA l -> list_all A PA (a :: l). Arguments list_all A%_type_scope PA%_function_scope l%_list_scope Arguments nil_all A%_type_scope PA%_function_scope Arguments cons_all A%_type_scope PA%_function_scope a _ l%_list_scope _

It is important to note: this is not literally Forall, in particular you will see the surprising Type@{α ; _} used in the type of PA. It also appears in the name: list_all@{α ; u u0}. Let us analyse what this all means before going forward:

u and u0 are universe level variables, as we have seen in this chapter already.

α on the other hand is a sort variable. It can be instantiated by Prop or by Type typically. So for instance Type@{Type ; i} is the same as Type@{i}, while Type@{Prop ; i} is just Prop. This feature is relatively new in Rocq, so notations and general support might be a bit rough for now; it should get better with newer releases of Rocq.

If we rephrase, list_all is like Forall but defined generically to work with Prop or Type depending on what is needed. Now that it is defined, Rocq no longer warns us about nesting list in our inductive definition:

Inductive tree A :=
| node (a : A) (children : list (tree A)).

Arguments node {A}.

If we look at the induction principle, it now uses list_all which gives us something strong enough to prove things about tree.

tree_rect : forall (A : Type) (P : tree A -> Type), (forall (a : A) (children : list (tree A)), list_all (tree A) P children -> P (node a children)) -> forall t : tree A, P t

Let's see it in action, by defining a map function and then proving things about it.

Fixpoint tree_map {A B} (f : A -> B) (t : tree A) : tree B :=
  match t with
  | node a l => node (f a) (map (tree_map f) l)
  end.

A: Type
t: tree A

tree_map (fun x : A => x) t = t
A: Type
t: tree A

tree_map (fun x : A => x) t = t
A: Type
a: A
l: list (tree A)
ih: list_all (tree A) (fun t : tree A => tree_map (fun x : A => x) t = t) l

tree_map (fun x : A => x) (node a l) = node a l
A: Type
a: A
l: list (tree A)
ih: list_all (tree A) (fun t : tree A => tree_map (fun x : A => x) t = t) l

node a (map (tree_map (fun x : A => x)) l) = node a l
A: Type
a: A
l: list (tree A)
ih: list_all (tree A) (fun t : tree A => tree_map (fun x : A => x) t = t) l

map (tree_map (fun x : A => x)) l = l
Abort.

We'll stop here, but, compared to last time, the induction principle is enough to conclude. We'll leave it as an exercise for you.

Exercise: Using list_all

Prove the following lemma.

A: Type
t: tree A

tree_map (fun x : A => x) t = t
A: Type
t: tree A

tree_map (fun x : A => x) t = t
Admitted.

Another valid approach is to define tree_map_id directly using Fixpoint. We can in fact do this directly using proof mode (with tactics). Let's see it in action.

tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
t: tree A

tree_map (fun x : A => x) t = t
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
t: tree A

tree_map (fun x : A => x) t = t
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

tree_map (fun x : A => x) (node a children) = node a children
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

node a (map (tree_map (fun x : A => x)) children) = node a children
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

map (tree_map (fun x : A => x)) children = children
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

map ?g children = children
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)
forall a0 : tree A, tree_map (fun x : A => x) a0 = ?g a0
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

map ?g children = children
apply map_id.
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

forall a0 : tree A, tree_map (fun x : A => x) a0 = (fun x : tree A => x) a0
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

forall a0 : tree A, tree_map (fun x : A => x) a0 = a0
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)
x: tree A

tree_map (fun x0 : A => x0) x = x
apply tree_map_id_fix.
The command has indeed failed with message: Recursive definition of tree_map_id_fix is ill-formed. In environment tree_map_id_fix : forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t A : Type t : tree A a : A children : list (tree A) a0 := a : A children0 := children : list (tree A) H := eq_refl : A = A H0 := eq_refl : a0 = a0 A0 := tree A : Type x := node a0 (map (tree_map (fun x : A => x)) children0) : A0 y := node a0 (map (tree_map (fun x : A => x)) children0) : A0 z := node a0 children0 : A0 H1 := f_equal (fun f : list (tree A) -> tree A => f (map (tree_map (fun x : A => x)) children0)) eq_refl : x = y A1 := list (tree A) : Type B := tree A : Type f := node a0 : A1 -> B x0 := map (tree_map (fun x : A => x)) children0 : A1 y0 := children0 : A1 A2 := list (tree A) : Type x1 := map (fun x : tree A => x) children0 : A2 P := fun l : list (tree A) => l = children0 : A2 -> Prop H2 := map_id children0 : P x1 y1 := map (tree_map (fun x : A => x)) children0 : A2 A3 := A2 : Type x2 := x1 : A3 P0 := fun y : A2 => P y : A3 -> Prop eq_refl := H2 : P0 x2 a1 := y1 : A3 A4 := A2 : Type x3 := y1 : A4 y2 := x1 : A4 x4 : tree A Recursive call to tree_map_id_fix has principal argument equal to "x4" instead of one of the following variables: "children" "children0" "y0". Recursive definition is: "fun (A : Type) (t : tree A) => match t as t0 return tree_map (fun x : A => x) t0 = t0 with | node a children => (fun (a0 : A) (children0 : list (tree A)) => (let H : map (tree_map (fun x : A => x)) children0 = children0 := eq_ind_r (fun l : list (tree A) => l = children0) (map_id children0) (map_ext (tree_map (fun x : A => x)) (fun x : tree A => x) ((fun x : tree A => tree_map_id_fix A x) : forall a1 : tree A, tree_map (fun x : A => x) a1 = (fun x : tree A => x) a1) children0) in (let H0 : a0 = a0 := eq_refl in (let H1 : A = A := eq_refl in (fun (_ : A = A) (_ : a0 = a0) (H2 : map (tree_map (fun x : A => x)) children0 = children0) => eq_trans (f_equal (fun f : list (tree A) -> tree A => f (map (tree_map (fun x : A => x)) children0)) eq_refl) (f_equal (node a0) H2)) H1) H0) H) : tree_map (fun x : A => x) (node a0 children0) = node a0 children0) a children end".
Abort.

Qed fails here because Rocq cannot see our fixpoint terminates. Indeed, we used a recursive call on something completely unrelated. We are only told now because Rocq only checks for termination at Qed time, and not before. There is a way to know beforehand though: the Guarded command checks that the guard condition (which verifies termination) holds up to the point where it's called.

tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
t: tree A

tree_map (fun x : A => x) t = t
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
t: tree A

tree_map (fun x : A => x) t = t
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

tree_map (fun x : A => x) (node a children) = node a children
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

node a (map (tree_map (fun x : A => x)) children) = node a children
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

map (tree_map (fun x : A => x)) children = children
The condition holds up to here.
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

map (tree_map (fun x : A => x)) children = children
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

map ?g children = children
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)
forall a0 : tree A, In a0 children -> tree_map (fun x : A => x) a0 = ?g a0
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

map ?g children = children
apply map_id.
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

forall a0 : tree A, In a0 children -> tree_map (fun x : A => x) a0 = (fun x : tree A => x) a0
The condition holds up to here.
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

forall a0 : tree A, In a0 children -> tree_map (fun x : A => x) a0 = (fun x : tree A => x) a0
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

forall a0 : tree A, In a0 children -> tree_map (fun x : A => x) a0 = a0
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)
x: tree A
h: In x children

tree_map (fun x0 : A => x0) x = x
The condition holds up to here.
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)
x: tree A
h: In x children

tree_map (fun x0 : A => x0) x = x
apply tree_map_id_fix.
The command has indeed failed with message: Recursive definition of tree_map_id_fix is ill-formed. As a fixpoint decreasing on the 2nd argument of tree_map_id_fix: Recursive call to tree_map_id_fix has principal argument equal to "x4" instead of one of the following variables: "children" "children" "y". Recursive definition is: "fun (A : Type) (t : tree A) => match t as t0 return tree_map (fun x : A => x) t0 = t0 with | node a children => (fun (a0 : A) (children0 : list (tree A)) => (let H : map (tree_map (fun x : A => x)) children0 = children0 := eq_ind_r (fun l : list (tree A) => l = children0) (map_id children0) (map_ext_in (tree_map (fun x : A => x)) (fun x : tree A => x) children0 ((fun (x : tree A) (_ : In x children0) => tree_map_id_fix A x) : forall a1 : tree A, In a1 children0 -> tree_map (fun x : A => x) a1 = (fun x : tree A => x) a1)) in (let H0 : a0 = a0 := eq_refl in (let H1 : A = A := eq_refl in (fun (_ : A = A) (_ : a0 = a0) (H2 : map (tree_map (fun x : A => x)) children0 = children0) => eq_trans (f_equal (fun f : list (tree A) -> tree A => f (map (tree_map (fun x : A => x)) children0)) eq_refl) (f_equal (node a0) H2)) H1) H0) H) : tree_map (fun x : A => x) (node a0 children0) = node a0 children0) a children end".
The command has indeed failed with message: Recursive definition of tree_map_id_fix is ill-formed. In environment tree_map_id_fix : forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t A : Type t : tree A a : A children : list (tree A) a0 := a : A children0 := children : list (tree A) H := eq_refl : A = A H0 := eq_refl : a0 = a0 A0 := tree A : Type x := node a0 (map (tree_map (fun x : A => x)) children0) : A0 y := node a0 (map (tree_map (fun x : A => x)) children0) : A0 z := node a0 children0 : A0 H1 := f_equal (fun f : list (tree A) -> tree A => f (map (tree_map (fun x : A => x)) children0)) eq_refl : x = y A1 := list (tree A) : Type B := tree A : Type f := node a0 : A1 -> B x0 := map (tree_map (fun x : A => x)) children0 : A1 y0 := children0 : A1 A2 := list (tree A) : Type x1 := map (fun x : tree A => x) children0 : A2 P := fun l : list (tree A) => l = children0 : A2 -> Prop H2 := map_id children0 : P x1 y1 := map (tree_map (fun x : A => x)) children0 : A2 A3 := A2 : Type x2 := x1 : A3 P0 := fun y : A2 => P y : A3 -> Prop eq_refl := H2 : P0 x2 a1 := y1 : A3 A4 := A2 : Type x3 := y1 : A4 y2 := x1 : A4 x4 : tree A h : In x4 children0 Recursive call to tree_map_id_fix has principal argument equal to "x4" instead of one of the following variables: "children" "children0" "y0". Recursive definition is: "fun (A : Type) (t : tree A) => match t as t0 return tree_map (fun x : A => x) t0 = t0 with | node a children => (fun (a0 : A) (children0 : list (tree A)) => (let H : map (tree_map (fun x : A => x)) children0 = children0 := eq_ind_r (fun l : list (tree A) => l = children0) (map_id children0) (map_ext_in (tree_map (fun x : A => x)) (fun x : tree A => x) children0 ((fun (x : tree A) (_ : In x children0) => tree_map_id_fix A x) : forall a1 : tree A, In a1 children0 -> tree_map (fun x : A => x) a1 = (fun x : tree A => x) a1)) in (let H0 : a0 = a0 := eq_refl in (let H1 : A = A := eq_refl in (fun (_ : A = A) (_ : a0 = a0) (H2 : map (tree_map (fun x : A => x)) children0 = children0) => eq_trans (f_equal (fun f : list (tree A) -> tree A => f (map (tree_map (fun x : A => x)) children0)) eq_refl) (f_equal (node a0) H2)) H1) H0) H) : tree_map (fun x : A => x) (node a0 children0) = node a0 children0) a children end".
Abort.

This time it should actually work because morally we only use recursive calls on elements inside the list, but Rocq doesn't know it.

We in fact need to be able to recurse on the list, so the same way we nested inductive types, we need to nest fixpoints. For this we can use the fix tactic which introduces a fixed point. We need to revert the argument on which we want to recurse (to put it back into the goal) and then fix aux 1 will introduce a new hypothesis named aux corresponding to potential recursive calls.

tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
t: tree A

tree_map (fun x : A => x) t = t
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
t: tree A

tree_map (fun x : A => x) t = t
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

tree_map (fun x : A => x) (node a children) = node a children
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

node a (map (tree_map (fun x : A => x)) children) = node a children
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
children: list (tree A)

map (tree_map (fun x : A => x)) children = children
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A

forall children : list (tree A), map (tree_map (fun x : A => x)) children = children
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
aux: forall children : list (tree A), map (tree_map (fun x : A => x)) children = children

forall children : list (tree A), map (tree_map (fun x : A => x)) children = children
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
aux: forall children : list (tree A), map (tree_map (fun x : A => x)) children = children
l: list (tree A)

map (tree_map (fun x : A => x)) l = l
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
aux: forall children : list (tree A), map (tree_map (fun x : A => x)) children = children

map (tree_map (fun x : A => x)) [] = []
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
aux: forall children : list (tree A), map (tree_map (fun x : A => x)) children = children
x: tree A
l: list (tree A)
map (tree_map (fun x0 : A => x0)) (x :: l) = x :: l
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
aux: forall children : list (tree A), map (tree_map (fun x : A => x)) children = children

map (tree_map (fun x : A => x)) [] = []
reflexivity.
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
aux: forall children : list (tree A), map (tree_map (fun x : A => x)) children = children
x: tree A
l: list (tree A)

map (tree_map (fun x0 : A => x0)) (x :: l) = x :: l
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
aux: forall children : list (tree A), map (tree_map (fun x : A => x)) children = children
x: tree A
l: list (tree A)

tree_map (fun x0 : A => x0) x :: map (tree_map (fun x0 : A => x0)) l = x :: l
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
aux: forall children : list (tree A), map (tree_map (fun x : A => x)) children = children
x: tree A
l: list (tree A)

tree_map (fun x0 : A => x0) x = x
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
aux: forall children : list (tree A), map (tree_map (fun x : A => x)) children = children
x: tree A
l: list (tree A)
map (tree_map (fun x0 : A => x0)) l = l
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
aux: forall children : list (tree A), map (tree_map (fun x : A => x)) children = children
x: tree A
l: list (tree A)

tree_map (fun x0 : A => x0) x = x
apply tree_map_id_fix.
tree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: A
aux: forall children : list (tree A), map (tree_map (fun x : A => x)) children = children
x: tree A
l: list (tree A)

map (tree_map (fun x0 : A => x0)) l = l
apply aux. Qed.

This was rather painful because we had to manually ensure that Rocq recognises the proof as structurally recursive.

The version from earlier using list_all wasn't so bad right? 😸

Exercise: Nested induction principle by hand

You already had an exercise about defining a nice induction principle for tree using Forall (which is the special case of list_all for Prop-valued predicates). To switch things up we'll be using a different method, using In.

State and prove the induction principle for tree called tree_ind_in. You will likely have to use the fix tactic, and probably the revert tactic to generalise the goal (revert x is basically the opposite of intro x).

You can add using tree_ind_in to an induction command to instruct Rocq to use your custom induction principle instead. Use it to prove the following.

A: Type
t: tree A

tree_map (fun x : A => x) t = t
A: Type
t: tree A

tree_map (fun x : A => x) t = t
Admitted.

Size recursion

In pen-and-paper proofs, you often see people perform induction on the size of objects, or alternatively with a measure. We can do this generically for any type X which has a size : X -> nat function.

X: Type
size: X -> nat
P: X -> Type

(forall x : X, (forall y : X, size y < size x -> P y) -> P x) -> forall x : X, P x
X: Type
size: X -> nat
P: X -> Type

(forall x : X, (forall y : X, size y < size x -> P y) -> P x) -> forall x : X, P x
X: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P x
x: X

P x
X: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P x
x: X

forall y : X, size y < size x -> P y
X: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P x
x: X

(forall (n : nat) (y : X), size y < n -> P y) -> forall y : X, size y < size x -> P y
X: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P x
x: X
forall (n : nat) (y : X), size y < n -> P y
X: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P x
x: X

(forall (n : nat) (y : X), size y < n -> P y) -> forall y : X, size y < size x -> P y
eauto.
X: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P x
x: X

forall (n : nat) (y : X), size y < n -> P y
X: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P x

forall (n : nat) (y : X), size y < n -> P y
X: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P x
n: nat
y: X
E: size y < n

P y
X: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P x
y: X
E: size y < 0

P y
X: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P x
n: nat
y: X
E: size y < S n
ih: forall y : X, size y < n -> P y
P y
X: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P x
n: nat
y: X
E: size y < S n
ih: forall y : X, size y < n -> P y

P y
X: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P x
n: nat
y: X
E: size y < S n
ih: forall y : X, size y < n -> P y

forall y0 : X, size y0 < size y -> P y0
X: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P x
n: nat
y: X
E: size y < S n
ih: forall y : X, size y < n -> P y
x: X
F: size x < size y

P x
X: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P x
n: nat
y: X
E: size y < S n
ih: forall y : X, size y < n -> P y
x: X
F: size x < size y

size x < n
lia. Defined.
Exercise: Strong induction on natural numbers

We have seen strong induction on nat already, but show it again and use it to prove the following lemma that corresponds to induction on natural numbers with access to the two previous cases.


forall P : nat -> Prop, P 0 -> P 1 -> (forall n : nat, P n -> P (S n) -> P (S (S n))) -> forall n : nat, P n

forall P : nat -> Prop, P 0 -> P 1 -> (forall n : nat, P n -> P (S n) -> P (S (S n))) -> forall n : nat, P n
Admitted.
Exercise: Fibonacci

Use the induction tactic with nat_ind_2 to prove that the Fibonacci sequence is always above its index (n <= fib n).

Fixpoint fib n :=
  match n with
  | 0 => 1
  | 1 => 1
  | S (S n as m) => fib n + fib m
  end.

Well-founded induction

The last topic is about doing induction / recursion along any well-founded order. We define well-foundedness of an order on a point as the so-called accessibility predicate.

We do it inside a module to avoid overriding the definition from the standard library.

Module Acc.

Section Well_founded.

We work with a type and a relation on it.

  Context {A : Type}.
  Context (R : A -> A -> Prop).

A point x is accessible when all its predecessors in the relation are accessible as well.

  Inductive Acc (x : A) : Prop :=
    Acc_intro : (forall y, R y x -> Acc y) -> Acc x.

Since the inductive type has exactly one constructor, we can show this is a (logical) equivalence.

  
A: Type
R: A -> A -> Prop
x: A

Acc x <-> (forall y : A, R y x -> Acc y)
A: Type
R: A -> A -> Prop
x: A

Acc x <-> (forall y : A, R y x -> Acc y)
A: Type
R: A -> A -> Prop
x: A

Acc x -> forall y : A, R y x -> Acc y
A: Type
R: A -> A -> Prop
x: A
(forall y : A, R y x -> Acc y) -> Acc x
A: Type
R: A -> A -> Prop
x: A

Acc x -> forall y : A, R y x -> Acc y
A: Type
R: A -> A -> Prop
x: A
h: forall y : A, R y x -> Acc y

forall y : A, R y x -> Acc y
exact h.
A: Type
R: A -> A -> Prop
x: A

(forall y : A, R y x -> Acc y) -> Acc x
A: Type
R: A -> A -> Prop
x: A
H: forall y : A, R y x -> Acc y

Acc x
A: Type
R: A -> A -> Prop
x: A
H: forall y : A, R y x -> Acc y

forall y : A, R y x -> Acc y
assumption. Qed. End Well_founded. End Acc.
Exercise: No infinite decreasing sequence

You might be surprised that our definition of well-foundedness isn't talking about the absence of infinite decreasing sequences. While that is the usual definition, in our setting such a definition doesn't let us construct terms in general, so it is better to have a positive outlook on well-foundedness.

We can still connect the two though! Prove the following lemmas.

Section Sequences.

  Context (A : Type) (R : A -> A -> Prop).

  Definition noseq_from x :=
    ~ (exists (u : nat -> A), u 0 = x /\ forall n, R (u (S n)) (u n)).

  
A: Type
R: A -> A -> Prop
x: A

Acc R x -> noseq_from x
A: Type
R: A -> A -> Prop
x: A

Acc R x -> noseq_from x
Admitted.
End Sequences.

Now behold the return of the subsingleton criterion! Acc indeed verifies it: it has exactly one constructor Acc_intro which itself has two arguments, x : A and h : forall y, R y x -> Acc y. The first one is a (non-uniform) parameter so it doesn't count, and the second one is a proof (because, remember, ∀ quantifiers ending in Prop land in Prop as well).

This means that we get an induction principle with a motive in Type:

Acc_rect : forall (A : Type) (R : A -> A -> Prop) (P : A -> Type), (forall x : A, (forall y : A, R y x -> Acc R y) -> (forall y : A, R y x -> P y) -> P x) -> forall x : A, Acc R x -> P x

It says that when proving P x for accessible x, one can assume P y for any R-smaller y.

We can prove that accessible points are not contained in loops:

X: Type
R: X -> X -> Prop
x: X

Acc R x -> ~ (exists y : X, R x y /\ R y x)
X: Type
R: X -> X -> Prop
x: X

Acc R x -> ~ (exists y : X, R x y /\ R y x)
X: Type
R: X -> X -> Prop
x: X
H: Acc R x

~ (exists y : X, R x y /\ R y x)
X: Type
R: X -> X -> Prop
x: X
H: forall y : X, R y x -> Acc R y
ih: forall y : X, R y x -> ~ (exists y0 : X, R y y0 /\ R y0 y)

~ (exists y : X, R x y /\ R y x)
firstorder. Qed.

To conclude this lecture, we give a proof that one can use recursion on proofs to write a function that extracts the witness from a proof of exists n, f n = true. This proof can be given in different ways. We show the easiest approach here, and leave a variant using Acc as an exercise.

From Stdlib Require Import Lia.

We start by giving a predicate least P n k that says that k is the least natural number above n that verifies predicate P.

Definition least P n k :=
  n <= k /\
  P k /\
  forall i, n <= i -> P i -> k <= i.

Section WO.

  Context (f : nat -> bool).

The key is in the definition of a guardedness predicate which is in Prop (so we can eliminate exist into it) and which verifies the subsingleton criterion (so we can eliminate it into Type).

  Inductive G (n : nat) : Prop :=
  | GI : (f n = false -> G (S n)) -> G n.

  
f: nat -> bool
n: nat

G n -> {k : nat | least (fun k0 : nat => f k0 = true) n k}
f: nat -> bool
n: nat

G n -> {k : nat | least (fun k0 : nat => f k0 = true) n k}
f: nat -> bool
n: nat
ih: f n = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}

{k : nat | least (fun k0 : nat => f k0 = true) n k}
f: nat -> bool
n: nat
e: f n = true
ih: true = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}

{k : nat | least (fun k0 : nat => f k0 = true) n k}
f: nat -> bool
n: nat
e: f n = false
ih: false = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}
{k : nat | least (fun k0 : nat => f k0 = true) n k}
f: nat -> bool
n: nat
e: f n = true
ih: true = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}

{k : nat | least (fun k0 : nat => f k0 = true) n k}
f: nat -> bool
n: nat
e: f n = true
ih: true = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}

least (fun k : nat => f k = true) n n
f: nat -> bool
n: nat
e: f n = true
ih: true = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}

n <= n /\ f n = true /\ (forall i : nat, n <= i -> f i = true -> n <= i)
eauto.
f: nat -> bool
n: nat
e: f n = false
ih: false = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}

{k : nat | least (fun k0 : nat => f k0 = true) n k}
f: nat -> bool
n: nat
e: f n = false
ih: false = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}
k: nat
hle: S n <= k
hk: f k = true
hleast: forall i : nat, S n <= i -> f i = true -> k <= i

{k0 : nat | least (fun k1 : nat => f k1 = true) n k0}
f: nat -> bool
n: nat
e: f n = false
ih: false = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}
k: nat
hle: S n <= k
hk: f k = true
hleast: forall i : nat, S n <= i -> f i = true -> k <= i

least (fun k0 : nat => f k0 = true) n k
f: nat -> bool
n: nat
e: f n = false
ih: false = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}
k: nat
hle: S n <= k
hk: f k = true
hleast: forall i : nat, S n <= i -> f i = true -> k <= i

n <= k
f: nat -> bool
n: nat
e: f n = false
ih: false = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}
k: nat
hle: S n <= k
hk: f k = true
hleast: forall i : nat, S n <= i -> f i = true -> k <= i
f k = true /\ (forall i : nat, n <= i -> f i = true -> k <= i)
f: nat -> bool
n: nat
e: f n = false
ih: false = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}
k: nat
hle: S n <= k
hk: f k = true
hleast: forall i : nat, S n <= i -> f i = true -> k <= i

n <= k
f: nat -> bool
n: nat
e: f n = false
ih: false = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}
k: nat
hle: S n <= k
hk: f k = true
hleast: forall i : nat, S n <= i -> f i = true -> k <= i
f k = true
f: nat -> bool
n: nat
e: f n = false
ih: false = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}
k: nat
hle: S n <= k
hk: f k = true
hleast: forall i : nat, S n <= i -> f i = true -> k <= i
forall i : nat, n <= i -> f i = true -> k <= i
f: nat -> bool
n: nat
e: f n = false
ih: false = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}
k: nat
hle: S n <= k
hk: f k = true
hleast: forall i : nat, S n <= i -> f i = true -> k <= i

n <= k
lia.
f: nat -> bool
n: nat
e: f n = false
ih: false = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}
k: nat
hle: S n <= k
hk: f k = true
hleast: forall i : nat, S n <= i -> f i = true -> k <= i

f k = true
assumption.
f: nat -> bool
n: nat
e: f n = false
ih: false = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}
k: nat
hle: S n <= k
hk: f k = true
hleast: forall i : nat, S n <= i -> f i = true -> k <= i

forall i : nat, n <= i -> f i = true -> k <= i
f: nat -> bool
n: nat
e: f n = false
ih: false = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}
k: nat
hle: S n <= k
hk: f k = true
hleast: forall i : nat, S n <= i -> f i = true -> k <= i
i: nat
hi: n <= i

f i = true -> k <= i
f: nat -> bool
n: nat
e: f n = false
ih: false = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}
k: nat
hle: S n <= k
hk: f k = true
hleast: forall i : nat, S n <= i -> f i = true -> k <= i
i: nat
hi: n <= i
H: n = i

f i = true -> k <= i
f: nat -> bool
n: nat
e: f n = false
ih: false = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}
k: nat
hle: S n <= k
hk: f k = true
hleast: forall i : nat, S n <= i -> f i = true -> k <= i
i: nat
hi: n <= i
m: nat
H: n <= m
H0: S m = i
f (S m) = true -> k <= S m
f: nat -> bool
n: nat
e: f n = false
ih: false = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}
k: nat
hle: S n <= k
hk: f k = true
hleast: forall i : nat, S n <= i -> f i = true -> k <= i
i: nat
hi: n <= i
H: n = i

f i = true -> k <= i
congruence.
f: nat -> bool
n: nat
e: f n = false
ih: false = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}
k: nat
hle: S n <= k
hk: f k = true
hleast: forall i : nat, S n <= i -> f i = true -> k <= i
i: nat
hi: n <= i
m: nat
H: n <= m
H0: S m = i

f (S m) = true -> k <= S m
f: nat -> bool
n: nat
e: f n = false
ih: false = false -> {k : nat | least (fun k0 : nat => f k0 = true) (S n) k}
k: nat
hle: S n <= k
hk: f k = true
hleast: forall i : nat, S n <= i -> f i = true -> k <= i
i: nat
hi: n <= i
m: nat
H: n <= m
H0: S m = i

S n <= S m
lia. Defined.
f: nat -> bool
n: nat

G n -> G 0
f: nat -> bool
n: nat

G n -> G 0
f: nat -> bool

G 0 -> G 0
f: nat -> bool
n: nat
ih: G n -> G 0
G (S n) -> G 0
f: nat -> bool

G 0 -> G 0
auto.
f: nat -> bool
n: nat
ih: G n -> G 0

G (S n) -> G 0
f: nat -> bool
n: nat
ih: G n -> G 0
h: G (S n)

G 0
f: nat -> bool
n: nat
ih: G n -> G 0
h: G (S n)

G n
f: nat -> bool
n: nat
ih: G n -> G 0
h: G (S n)

f n = false -> G (S n)
auto. Defined.
f: nat -> bool

(exists n : nat, f n = true) -> {n : nat | least (fun n0 : nat => f n0 = true) 0 n}
f: nat -> bool

(exists n : nat, f n = true) -> {n : nat | least (fun n0 : nat => f n0 = true) 0 n}
f: nat -> bool
h: exists n : nat, f n = true

{n : nat | least (fun n0 : nat => f n0 = true) 0 n}
f: nat -> bool
h: exists n : nat, f n = true

G 0
f: nat -> bool
n: nat
h: f n = true

G 0
f: nat -> bool
n: nat
h: f n = true

G n
f: nat -> bool
n: nat
h: f n = true

f n = false -> G (S n)
f: nat -> bool
n: nat
h: f n = true

true = false -> G (S n)
discriminate. Defined. End WO.
linear_search : forall f : nat -> bool, (exists n : nat, f n = true) -> {n : nat | least (fun n0 : nat => f n0 = true) 0 n} linear_search is not universe polymorphic Arguments linear_search f%_function_scope _ linear_search is transparent Expands to: Constant lesson5_part1.linear_search Declared in toplevel input, characters 6684-6697
Exercise: Search using Acc

We are going to show that for any decidable predicate P with exists n, P n we can compute a natural number n for which P holds, i.e. deduce { n | P n }.

Prove the admitted lemmas below.

Section ConstructiveIndefiniteGroundDescription_Acc.

  Context (P : nat -> Prop).

  Hypothesis P_decidable : forall n : nat, {P n} + {~ P n}.

  Let R (x y : nat) : Prop := x = S y /\ ~ P y.

  Local Abbreviation acc x := (Acc R x).

  
P: nat -> Prop
P_decidable: forall n : nat, {P n} + {~ P n}
R:= fun x y : nat => x = S y /\ ~ P y: nat -> nat -> Prop

forall x : nat, P x -> acc x
P: nat -> Prop
P_decidable: forall n : nat, {P n} + {~ P n}
R:= fun x y : nat => x = S y /\ ~ P y: nat -> nat -> Prop

forall x : nat, P x -> acc x
Admitted.
P: nat -> Prop
P_decidable: forall n : nat, {P n} + {~ P n}
R:= fun x y : nat => x = S y /\ ~ P y: nat -> nat -> Prop

forall x n : nat, P (n + x) -> acc x
P: nat -> Prop
P_decidable: forall n : nat, {P n} + {~ P n}
R:= fun x y : nat => x = S y /\ ~ P y: nat -> nat -> Prop

forall x n : nat, P (n + x) -> acc x
Admitted.
P: nat -> Prop
P_decidable: forall n : nat, {P n} + {~ P n}
R:= fun x y : nat => x = S y /\ ~ P y: nat -> nat -> Prop

(exists n : nat, P n) -> acc 0
P: nat -> Prop
P_decidable: forall n : nat, {P n} + {~ P n}
R:= fun x y : nat => x = S y /\ ~ P y: nat -> nat -> Prop

(exists n : nat, P n) -> acc 0
Admitted.
P: nat -> Prop
P_decidable: forall n : nat, {P n} + {~ P n}
R:= fun x y : nat => x = S y /\ ~ P y: nat -> nat -> Prop

acc 0 -> {n : nat | P n}
P: nat -> Prop
P_decidable: forall n : nat, {P n} + {~ P n}
R:= fun x y : nat => x = S y /\ ~ P y: nat -> nat -> Prop

acc 0 -> {n : nat | P n}
P: nat -> Prop
P_decidable: forall n : nat, {P n} + {~ P n}
R:= fun x y : nat => x = S y /\ ~ P y: nat -> nat -> Prop
Acc_0: acc 0

{n : nat | P n}
P: nat -> Prop
P_decidable: forall n : nat, {P n} + {~ P n}
R:= fun x y : nat => x = S y /\ ~ P y: nat -> nat -> Prop
Acc_0: acc 0

(fun _ : nat => {n : nat | P n}) 0
P: nat -> Prop
P_decidable: forall n : nat, {P n} + {~ P n}
R:= fun x y : nat => x = S y /\ ~ P y: nat -> nat -> Prop
x: nat
H: forall y : nat, R y x -> acc y
IH: forall y : nat, R y x -> {n : nat | P n}

{n : nat | P n}
(* now use decidability of P *) Admitted.
P: nat -> Prop
P_decidable: forall n : nat, {P n} + {~ P n}
R:= fun x y : nat => x = S y /\ ~ P y: nat -> nat -> Prop

(exists n : nat, P n) -> {n : nat | P n}
P: nat -> Prop
P_decidable: forall n : nat, {P n} + {~ P n}
R:= fun x y : nat => x = S y /\ ~ P y: nat -> nat -> Prop

(exists n : nat, P n) -> {n : nat | P n}
Admitted. End ConstructiveIndefiniteGroundDescription_Acc.
Exercise: Defining functions by well-founded recursion

We have seen well-founded induction, but sometimes we also want to define functions by well-founded recursion. The standard library comes with a helpful function for doing that called Fix_F. It performs induction on accessibility like we have been doing.

Fix_F : forall [A : Type] [R : A -> A -> Prop] (P : A -> Type), (forall x : A, (forall y : A, R y x -> P y) -> P x) -> forall [x : A], Acc R x -> P x Fix_F is not universe polymorphic Arguments Fix_F [A]%_type_scope [R]%_function_scope (P F)%_function_scope [x] a Fix_F is transparent Expands to: Constant Corelib.Init.Wf.Fix_F Declared in library Corelib.Init.Wf, line 83, characters 11-16

Implement a merge function on lists such that if l and r are individually sorted, then merge l r should be sorted too. This function is the main ingredient for the merge sort algorithm.

We give you the version one would write in OCaml and you have to adapt it into a function accepted by Rocq. We're using lists of natural numbers to make it simpler but it could be generalised of course.

Next, prove a specification for merge that ensures it preserves sortedness and that the result is a permutation of the original lists. You can use a weak version of permutation that doesn't account for multiplicity.

We give you some lemmas about sorted and wpermut that you may or may not use. This is so you don't waste too much time on those. We expect you to begin by admitting them, but you should be able to prove them.

From Stdlib Require Import RelationClasses.

The command has indeed failed with message: Cannot guess decreasing argument of fix.
Inductive sorted : list nat -> Prop := | sorted_nil : sorted [] | sorted_cons : forall x l, sorted l -> Forall (le x) l -> sorted (x :: l). Definition wpermut (l r : list nat) : Prop := forall x, In x l <-> In x r.

Reflexive wpermut

Reflexive wpermut
Admitted.

Symmetric wpermut

Symmetric wpermut
Admitted.

Transitive wpermut

Transitive wpermut
Admitted. Add Parametric Relation : (list nat) wpermut as wpermut_rel.

forall (P : nat -> Prop) (l r : list nat), wpermut l r -> Forall P r -> Forall P l

forall (P : nat -> Prop) (l r : list nat), wpermut l r -> Forall P r -> Forall P l
Admitted.

forall (x : nat) (l r : list nat), wpermut l r -> wpermut (x :: l) (x :: r)

forall (x : nat) (l r : list nat), wpermut l r -> wpermut (x :: l) (x :: r)
Admitted.

forall l r : list nat, wpermut (l ++ r) (r ++ l)

forall l r : list nat, wpermut (l ++ r) (r ++ l)
Admitted.

forall (x : nat) (l : list nat), sorted (x :: l) -> sorted l /\ Forall (le x) l

forall (x : nat) (l : list nat), sorted (x :: l) -> sorted l /\ Forall (le x) l
Admitted.
Exercise: Hilbert's epsilon (advanced)

We're going to show the Bishop-Diaconescu-Myhill-Goodman theorem. It shows that the axiom of choice implies excluded middle with sufficient extensionality.

There are several versions of the axiom of choice. One is Hilbert's epsilon operator which takes a property on a type, and returns an element of that type that verifies the property if such an element exists. To avoid inconsistencies, we have to restrict this operator to inhabited types.

Section Hilbert.

inhabited A is just a proposition from which you cannot extract the witness.

  Context (epsilon : forall A, inhabited A -> (A -> Prop) -> A).

If there is an element verifying the property, then the one epsilon gave us also verifies it.

  Context (epsilon_spec :
    forall A i P,
      (exists x, P x) ->
      P (epsilon A i P)).

We also need some extensionality to tell us that the choice does not depend on how the property was formulated.

  Context (epsilon_ext :
    forall A i P Q,
      (forall x, P x <-> Q x) ->
      epsilon A i P = epsilon A i Q
  ).

Prove the excluded middle.

End Hilbert.
Exercise: From relation to function (advanced)

Another version of the axiom of choice says that from an entire relation, one can extract a function. It's a form of inversion of quantifiers.

Definition fun_choice :=
  forall A B (R : A -> B -> Prop),
    (forall x, exists y, R x y) ->
    exists (f : A -> B),
      forall x, R x (f x).

Show that fun_choice implies LEM as well. You may use proposition and function extensionality.

The proof should share some ideas with the one above and could involve some function of type { p : bool -> Prop | p = B \/ p = C } -> bool with carefully chosen B and C.

Definition FunExt :=
  forall A B (f g : A -> B),
    (forall x, f x = g x) ->
    f = g.

Definition PropExt :=
  forall (P Q : Prop), P <-> Q -> P = Q.
Exercise: Choice and proof irrelevance (advanced)

PI (forall P : Prop, forall h1 h2 : P, h1 = h2) suffices to prove that choice implies ELEM := forall A : Type, forall a b : A, a = b \/ ~ (a = b).

Prove this, and then deduce that PropExt suffices for Diaconescu's theorem, i.e. that FunExt is not actually needed.

Exercise: Choice in SProp (advanced)

Read the documentation of SProp and see whether you can prove that choice for SProp implies ELEM for SProp (without any additional assumption).

To make our life easier, we define how to squash a proposition into a strict proposition.

Definition squash (P : Prop) : SProp :=
  forall S : SProp, (P -> S) -> S.

P: Prop

P -> squash P
P: Prop

P -> squash P
firstorder. Qed.

The statement.

Definition fun_choice_SProp :=
  forall A B (R : A -> B -> Prop),
    (forall x, squash (exists y, R x y)) ->
    squash (exists (f : A -> B),
    forall x, R x (f x)).

Auxiliary definition for the proof.

Inductive sig {A : Type} (P : A -> SProp) : Type :=  exist : forall x : A, P x -> sig P.


forall (A : Type) (P : A -> SProp), sig P -> A

forall (A : Type) (P : A -> SProp), sig P -> A
A: Type
p: A -> SProp
x: A
p0: p x

A
exact x. Defined.