Advanced elimination / induction
- The goal of this lecture is to:
Understand more about universes in Rocq, i.e. about
TypeandProp. 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:
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.
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.
Here is the corresponding typing rule:
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.
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.
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.
Context (C : Type@{j}).
Prop, on the other hand, lives in Type@{i} for all 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:
Variable (P : Prop).
We rephrase what we just said using inference rules.
We also have a subsumption rule below, where \(s\) and \(s'\) are two universes.
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.
Variable (Q : A -> Prop).Unset Printing Universes. End Universes.
Here is the inference rule for a Prop-valued Π-type.
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) = bforall b : prop_bool, pneg (pneg b) = ball: reflexivity. Qed.pneg (pneg ptrue) = ptruepneg (pneg pfalse) = pfalse
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!
Rocq complains that proofs can only be eliminated to build other proofs. The same happens in proof mode of course.
prop_bool -> boolprop_bool -> boolb: prop_boolboolAbort.b: prop_boolbool
We can instead prove something weaker like this:
forall p : prop_bool, exists b : bool, to_prop_bool b = pforall p : prop_bool, exists b : bool, to_prop_bool b = pexists b : bool, to_prop_bool b = ptrueexists b : bool, to_prop_bool b = pfalseexists b : bool, to_prop_bool b = ptruereflexivity.to_prop_bool true = ptrueexists b : bool, to_prop_bool b = pfalsereflexivity. Qed.to_prop_bool false = pfalse
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) -> ~ PIf: prop_bool -> bool(forall b : bool, f (to_prop_bool b) = b) -> ~ PIf: prop_bool -> bool
H: forall b : bool, f (to_prop_bool b) = b
pi: PIFalsef: prop_bool -> bool
H: forall b : bool, f (to_prop_bool b) = b
pi: ptrue = pfalseFalsef: prop_bool -> bool
H: forall b : bool, f (to_prop_bool b) = b
pi: ptrue = pfalse
e1: f (to_prop_bool true) = trueFalsef: 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) = falseFalsef: prop_bool -> bool
H: forall b : bool, f (to_prop_bool b) = b
pi: ptrue = pfalse
e1: f ptrue = true
e2: f pfalse = falseFalsecongruence. Qed.f: prop_bool -> bool
H: forall b : bool, f (to_prop_bool b) = b
pi: ptrue = pfalse
e1: f pfalse = true
e2: f pfalse = falseFalse
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?
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 -> natFalse -> natdestruct bot. Qed. Definition exfalso' {A : Type} (bot : False) : A := match bot with end.bot: Falsenat
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)assumption. Qed.n, m: nat
P: nat -> Type
x: P (n + m)P (n + m)
The above we can do in general:
forall (A : Type) (P : A -> Type) (u v : A), u = v -> P u -> P vforall (A : Type) (P : A -> Type) (u v : A), u = v -> P u -> P vA: Type
P: A -> Type
u, v: A
e: u = vP u -> P vauto. Qed.A: Type
P: A -> Type
u, v: A
e: u = vP v -> P v
Disjunction for instance does not fall under the criterion:
forall P Q : Prop, P \/ Q -> boolforall P Q : Prop, P \/ Q -> boolP, Q: Prop
h: P \/ QboolAbort.P, Q: Prop
h: P \/ Qbool
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) -> boolforall P Q : Prop, Box (P \/ Q) -> boolP, Q: Prop
h: Box (P \/ Q)boolP, Q: Prop
p: P \/ QboolAbort.P, Q: Prop
p: P \/ Qbool
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 -> natforall n m : nat, n <= m -> natn, m: nat
h: n <= mnatAbort.n, m: nat
h: n <= mnat
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_indforProp,bintree_rectforType,bintree_recforSet(but you can ignore it and usebintree_rect).
They only vary in the return type of the motive (the return predicate).
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 = tforall (A : Type) (t : bintree A), bt_map (fun x : A => x) t = tA: Type
t: bintree Abt_map (fun x : A => x) t = tA: Type
a: Abt_map (fun x : A => x) (bt_leaf a) = bt_leaf aA: Type
a: A
l, r: bintree A
ihl: bt_map (fun x : A => x) l = l
ihr: bt_map (fun x : A => x) r = rbt_map (fun x : A => x) (bt_node a l r) = bt_node a l rreflexivity.A: Type
a: Abt_map (fun x : A => x) (bt_leaf a) = bt_leaf aA: Type
a: A
l, r: bintree A
ihl: bt_map (fun x : A => x) l = l
ihr: bt_map (fun x : A => x) r = rbt_map (fun x : A => x) (bt_node a l r) = bt_node a l rA: Type
a: A
l, r: bintree A
ihl: bt_map (fun x : A => x) l = l
ihr: bt_map (fun x : A => x) r = rbt_node a (bt_map (fun x : A => x) l) (bt_map (fun x : A => x) r) = bt_node a l rreflexivity. Qed.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 = rbt_node a l r = bt_node a l r
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.
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 🤷).
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:
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.
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 Atree_map (fun x : A => x) t = tA: Type
t: tree Atree_map (fun x : A => x) t = tA: Type
a: A
l: list (tree A)
ih: list_all (tree A) (fun t : tree A => tree_map (fun x : A => x) t = t) ltree_map (fun x : A => x) (node a l) = node a lA: Type
a: A
l: list (tree A)
ih: list_all (tree A) (fun t : tree A => tree_map (fun x : A => x) t = t) lnode a (map (tree_map (fun x : A => x)) l) = node a lAbort.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) lmap (tree_map (fun x : A => x)) l = l
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 Atree_map (fun x : A => x) t = tAdmitted.A: Type
t: tree Atree_map (fun x : A => x) t = t
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 Atree_map (fun x : A => x) t = ttree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
t: tree Atree_map (fun x : A => x) t = ttree_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 childrentree_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 childrentree_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 = childrentree_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 = childrentree_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 a0apply 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)map ?g children = childrentree_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) a0tree_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 = a0apply 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
children: list (tree A)
x: tree Atree_map (fun x0 : A => x0) x = xAbort.
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 Atree_map (fun x : A => x) t = ttree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
t: tree Atree_map (fun x : A => x) t = ttree_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 childrentree_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 childrentree_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 = childrentree_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 = childrentree_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 = childrentree_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 a0apply 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)map ?g children = childrentree_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) a0tree_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) a0tree_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 = a0tree_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 childrentree_map (fun x0 : A => x0) x = xapply 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
children: list (tree A)
x: tree A
h: In x childrentree_map (fun x0 : A => x0) x = xAbort.
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 Atree_map (fun x : A => x) t = ttree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
t: tree Atree_map (fun x : A => x) t = ttree_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 childrentree_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 childrentree_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 = childrentree_map_id_fix: forall (A : Type) (t : tree A), tree_map (fun x : A => x) t = t
A: Type
a: Aforall children : list (tree A), map (tree_map (fun x : A => x)) children = childrentree_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 = childrenforall children : list (tree A), map (tree_map (fun x : A => x)) children = childrentree_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 = ltree_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 = childrenmap (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 :: lreflexivity.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 = childrenmap (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 :: ltree_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 :: ltree_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 = xtree_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 = lapply 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)tree_map (fun x0 : A => x0) x = xapply aux. Qed.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
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 Atree_map (fun x : A => x) t = tAdmitted.A: Type
t: tree Atree_map (fun x : A => x) t = t
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 xX: 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 xX: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P x
x: XP xX: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P x
x: Xforall y : X, size y < size x -> P yX: 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 yX: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P x
x: Xforall (n : nat) (y : X), size y < n -> P yeauto.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 yX: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P x
x: Xforall (n : nat) (y : X), size y < n -> P yX: Type
size: X -> nat
P: X -> Type
D: forall x : X, (forall y : X, size y < size x -> P y) -> P xforall (n : nat) (y : X), size y < n -> P yX: 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 < nP yX: 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 < 0P yX: 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 yP yX: 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 yP yX: 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 yforall y0 : X, size y0 < size y -> P y0X: 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 yP xlia. Defined.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 ysize x < n
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 nAdmitted.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
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: AAcc x <-> (forall y : A, R y x -> Acc y)A: Type
R: A -> A -> Prop
x: AAcc x <-> (forall y : A, R y x -> Acc y)A: Type
R: A -> A -> Prop
x: AAcc x -> forall y : A, R y x -> Acc yA: Type
R: A -> A -> Prop
x: A(forall y : A, R y x -> Acc y) -> Acc xA: Type
R: A -> A -> Prop
x: AAcc x -> forall y : A, R y x -> Acc yexact h.A: Type
R: A -> A -> Prop
x: A
h: forall y : A, R y x -> Acc yforall y : A, R y x -> Acc yA: Type
R: A -> A -> Prop
x: A(forall y : A, R y x -> Acc y) -> Acc xA: Type
R: A -> A -> Prop
x: A
H: forall y : A, R y x -> Acc yAcc xassumption. Qed. End Well_founded. End Acc.A: Type
R: A -> A -> Prop
x: A
H: forall y : A, R y x -> Acc yforall y : A, R y x -> Acc y
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: AAcc R x -> noseq_from xAdmitted.A: Type
R: A -> A -> Prop
x: AAcc R x -> noseq_from x
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:
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: XAcc R x -> ~ (exists y : X, R x y /\ R y x)X: Type
R: X -> X -> Prop
x: XAcc 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)firstorder. Qed.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)
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: natG n -> {k : nat | least (fun k0 : nat => f k0 = true) n k}f: nat -> bool
n: natG 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 neauto.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)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 <= ileast (fun k0 : nat => f k0 = true) n kf: 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 <= in <= kf: 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 <= if 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 <= in <= kf: 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 <= if k = truef: 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 <= iforall i : nat, n <= i -> f i = true -> k <= ilia.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 <= in <= kassumption.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 <= if k = truef: 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 <= iforall i : nat, n <= i -> f i = true -> k <= if: 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 <= if i = true -> k <= if: 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 = if i = true -> k <= if: 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 = if (S m) = true -> k <= S mcongruence.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 = if i = true -> k <= if: 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 = if (S m) = true -> k <= S mlia. Defined.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 = iS n <= S mf: nat -> bool
n: natG n -> G 0f: nat -> bool
n: natG n -> G 0f: nat -> boolG 0 -> G 0f: nat -> bool
n: nat
ih: G n -> G 0G (S n) -> G 0auto.f: nat -> boolG 0 -> G 0f: nat -> bool
n: nat
ih: G n -> G 0G (S n) -> G 0f: nat -> bool
n: nat
ih: G n -> G 0
h: G (S n)G 0f: nat -> bool
n: nat
ih: G n -> G 0
h: G (S n)G nauto. Defined.f: nat -> bool
n: nat
ih: G n -> G 0
h: G (S n)f n = false -> G (S n)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 = trueG 0f: nat -> bool
n: nat
h: f n = trueG 0f: nat -> bool
n: nat
h: f n = trueG nf: nat -> bool
n: nat
h: f n = truef n = false -> G (S n)discriminate. Defined. End WO.f: nat -> bool
n: nat
h: f n = truetrue = false -> G (S n)
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 -> Propforall x : nat, P x -> acc xAdmitted.P: nat -> Prop
P_decidable: forall n : nat, {P n} + {~ P n}
R:= fun x y : nat => x = S y /\ ~ P y: nat -> nat -> Propforall x : nat, P x -> acc xP: nat -> Prop
P_decidable: forall n : nat, {P n} + {~ P n}
R:= fun x y : nat => x = S y /\ ~ P y: nat -> nat -> Propforall x n : nat, P (n + x) -> acc xAdmitted.P: nat -> Prop
P_decidable: forall n : nat, {P n} + {~ P n}
R:= fun x y : nat => x = S y /\ ~ P y: nat -> nat -> Propforall x n : nat, P (n + x) -> acc xP: 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 0Admitted.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 0P: nat -> Prop
P_decidable: forall n : nat, {P n} + {~ P n}
R:= fun x y : nat => x = S y /\ ~ P y: nat -> nat -> Propacc 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 -> Propacc 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(* 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
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}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.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}
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.
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.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 wpermutAdmitted.Reflexive wpermutSymmetric wpermutAdmitted.Symmetric wpermutTransitive wpermutAdmitted. Add Parametric Relation : (list nat) wpermut as wpermut_rel.Transitive wpermutforall (P : nat -> Prop) (l r : list nat), wpermut l r -> Forall P r -> Forall P lAdmitted.forall (P : nat -> Prop) (l r : list nat), wpermut l r -> Forall P r -> Forall P lforall (x : nat) (l r : list nat), wpermut l r -> wpermut (x :: l) (x :: r)Admitted.forall (x : nat) (l r : list nat), wpermut l r -> wpermut (x :: l) (x :: r)forall l r : list nat, wpermut (l ++ r) (r ++ l)Admitted.forall l r : list nat, wpermut (l ++ r) (r ++ l)forall (x : nat) (l : list nat), sorted (x :: l) -> sorted l /\ Forall (le x) lAdmitted.forall (x : nat) (l : list nat), sorted (x :: l) -> sorted l /\ Forall (le x) l
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: PropP -> squash Pfirstorder. Qed.P: PropP -> squash P
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 -> Aforall (A : Type) (P : A -> SProp), sig P -> Aexact x. Defined.A: Type
p: A -> SProp
x: A
p0: p xA
Gallery of inductive types and corresponding induction principles
We do not believe giving you the recipe in general is going to be useful, instead we think showing you representative examples together is going to be more helpful. So here we go.
Lists
Lists are an inductive type (Type) with one uniform parameter A : Type,
and two constructors nil and cons.
Inductive list (A : Type) : Type :=
| nil
| cons (a : A) (l : list A).As it's a type, it can be eliminated to produce both Type and Prop,
hence we have the two following induction principles.
The motive is of the form P : list A -> Type or P : list A -> Prop.
Note that A is a uniform parameter so it is quantified before the motive,
which is why it can mention it.
The conclusion will then be forall (l : list A), P l.
The induction principle has two branches, one for nil and one for cons.
Because nil : list A the corresponding branch is P nil.
Because cons : A -> list A -> list A the corresponding branch is
forall (a : A) (l : list A), P l -> P (cons a l).
To get it, you start from the type of the constructor, and for each recursive
invocation of list A you additionally get some induction hypothesis P l.
The return type list A is then replaced by P (cons a l), i.e. the
motive applied to the constructor itself.
Evenness
We have also seen the even predicate which is a proposition (Prop).
It takes no parameter, has one index n : nat and two constructors.
Inductive even : nat -> Prop :=
| evenO : even 0
| evenS (n : nat) : even n -> even (S (S n)).Since it has two constructors, it doesn't satisfy the subsingleton criterion
and thus it produces only even_ind but no even_rect.
Since the sort is Prop, the motive will not depend on the proof of
even n, only on n, so it will be P : nat -> Prop.
Otherwise the recipe is the same, you just don't need to apply P to the
constructor, only to the value of the index, so in one branch P 0 and in the
other P (S (S n)).
The conclusion will be forall n, even n -> P n.
Even if P doesn't talk about the proof of even n, it is still required.
Accessibility
Acc has three parameters: two uniform parameters A and R and one
non-uniform parameter x (it stays x in the conclusion, but in the
argument to Acc_intro it is instantiated by y). It has no index.
Because it has one constructor with only one non-parameter argument which
happens to be a proof (forall y, R y x -> Acc A R y has type Prop), it
satisfies the subsingleton criterion.
Inductive Acc' A (R : A -> A -> Prop) (x : A) := | Acc_intro' : (forall y, R y x -> Acc' A R y) -> Acc' A R x.