Exercise session 3 — Proof terms and meta-theory — Solutions
- Files:
Set Default Goal Selector "!". From Stdlib Require Import List. Import ListNotations.
Exercise: N-ary functions
Define an n-ary summation function sum, such that e.g.
sum 3 = fun a b c => a + b + c.
Fixpoint nary (n : nat) := match n with | 0 => nat | S n => nat -> nary n end. Fixpoint sum' (n : nat) (a : nat) : nary n := match n with | 0 => a | S n => fun x => sum' n (a + x) end. Definition sum n : nary n := sum' n 0.sum 2 = (fun x1 x2 : nat => x1 + x2)reflexivity. Qed.sum 2 = (fun x1 x2 : nat => x1 + x2)sum 3 = (fun x1 x2 x3 : nat => x1 + x2 + x3)reflexivity. Qed. (* From the lecture: *) Inductive even : nat -> Prop := | evenO : even 0 | evenS : forall n, even n -> even (S (S n)). Arguments evenS {n}.sum 3 = (fun x1 x2 x3 : nat => x1 + x2 + x3)
Exercise: Even
Define a proof term of the following type:
Fixpoint even_double n : even (n * 2) :=
match n with
| 0 => evenO
| S n => evenS (even_double n)
end.Exercise: Proof terms
Prove the following statements using proof terms.
If it's too hard to do directly, you can use the interactive mode together
with the refine tactic.
Definition ex1 : forall (P Q : Prop), P -> Q -> P := fun P Q p q => p. Definition ex2 : forall (P Q R : Prop), P -> (P -> Q) -> (P -> Q -> R) -> R := fun P Q R p f g => g p (f p).
Exercise: Less than
We give you this type for "less than" (lt).
Inductive lt (n : nat) : nat -> Prop :=
| lt_B : lt n (S n)
| lt_S m : lt n m -> lt n (S m).Prove the following lemma interactively using intros and apply.
forall n m : nat, lt n m -> lt n (4 + m)forall n m : nat, lt n m -> lt n (4 + m)n, m: nat
h: lt n mlt n (4 + m)n, m: nat
h: lt n mlt n (S (S (S m)))n, m: nat
h: lt n mlt n (S (S m))n, m: nat
h: lt n mlt n (S m)apply h. Qed.n, m: nat
h: lt n mlt n m
Note we make lt_S easier to use by making n, m implicit.
Arguments lt_S {n m}.Now prove it with a proof term.
Definition lt_plus_4' n m : lt n m -> lt n (4 + m) :=
fun h => lt_S (lt_S (lt_S (lt_S h))).Exercise: Connectives as proof terms
Prove the following with a proof term.
Hint: Use Print "\/" if needed.
Definition or_comm P Q : P \/ Q -> Q \/ P :=
fun h =>
match h with
| or_introl p => or_intror p
| or_intror q => or_introl q
end.Prove the following with a proof term.
Definition ex3 :
forall X (P Q : X -> Prop),
(forall x, P x <-> Q x) ->
(forall x, Q x) ->
forall x, P x
:=
fun X P Q equiv f x =>
match equiv x with
| conj hpq hqp =>
hqp (f x)
end.We can also write it this way:
Definition ex3_alt :
forall X (P Q : X -> Prop),
(forall x, P x <-> Q x) ->
(forall x, Q x) ->
forall x, P x
:=
fun X P Q equiv f x =>
let 'conj hpq hqp := equiv x in
hqp (f x).Prove the following with a proof term.
If you have trouble with this one, try to use refine to fill the term
interactively.
Definition Russell X : ~ (X <-> ~ X)
:=
fun h =>
let 'conj f g := h in
let x : X := g (fun x => f x x) in
f x x.Exercise: Impredicative encodings
Thanks to impredicativity of Prop (the ability to quantify over
propositions within propositions) it is possible to define most connectives
using only forall and -> (no inductive definitions).
For instance, one can define False as follows:
Definition iFalse := forall (P : Prop), P.Show that iFalse is equivalent to False.
False <-> iFalseFalse <-> iFalseFalse -> iFalseiFalse -> Falsecontradiction.False -> iFalseiFalse -> Falseapply h. Qed.h: iFalseFalse
Define the impredicative encoding of True and show it equivalent to
True.
Definition iTrue : Prop := iFalse -> iFalse.True <-> iTrueTrue <-> iTrueTrue -> iTrueiTrue -> TrueTrue -> iTrueiTrueassumption.h: iFalseiFalseiTrue -> Trueconstructor. Qed.True
Now do the same thing for conjunction, disjunction and the existential quantifier.
If you look at the solution you should see that they are in a sense connected
to the elimination rule of the corresponding connective.
Note that you can get it basically by using Print and_ind.
For conjunction, the idea is that having a proof of A /\ B is the same as
being able to prove any X as long as A -> B -> X holds, in other words
as long as X is provable assuming A and B.
Another way of seeing it is that if you have h : iAnd P Q then apply h
should be equivalent to destruct h' with h' : P /\ Q.
Definition iAnd (P Q : Prop) : Prop := forall (X : Prop), (P -> Q -> X) -> X.forall P Q : Prop, P /\ Q <-> iAnd P Qforall P Q : Prop, P /\ Q <-> iAnd P QP, Q: PropP /\ Q <-> iAnd P QP, Q: PropP /\ Q -> iAnd P QP, Q: PropiAnd P Q -> P /\ QP, Q: PropP /\ Q -> iAnd P QP, Q: Prop
hP: P
hQ: QiAnd P QP, Q: Prop
hP: P
hQ: Q
X: Prop
h: P -> Q -> XXall: assumption.P, Q: Prop
hP: P
hQ: Q
X: Prop
h: P -> Q -> XPP, Q: Prop
hP: P
hQ: Q
X: Prop
h: P -> Q -> XQP, Q: PropiAnd P Q -> P /\ QP, Q: Prop
h: iAnd P QP /\ QP, Q: Prop
h: iAnd P QP -> Q -> P /\ QP, Q: Prop
h: iAnd P Q
hP: P
hQ: QP /\ Qall: assumption. Qed.P, Q: Prop
h: iAnd P Q
hP: P
hQ: QPP, Q: Prop
h: iAnd P Q
hP: P
hQ: QQ
For disjunction it's similar, but with two branches.
Definition iOr (P Q : Prop) : Prop := forall (X : Prop), (P -> X) -> (Q -> X) -> X.forall P Q : Prop, P \/ Q <-> iOr P Qforall P Q : Prop, P \/ Q <-> iOr P QP, Q: PropP \/ Q <-> iOr P QP, Q: PropP \/ Q -> iOr P QP, Q: PropiOr P Q -> P \/ QP, Q: PropP \/ Q -> iOr P QP, Q: Prop
h: P \/ Q
X: Prop
hP: P -> X
hQ: Q -> XXP, Q: Prop
H: P
X: Prop
hP: P -> X
hQ: Q -> XXP, Q: Prop
H: Q
X: Prop
hP: P -> X
hQ: Q -> XXP, Q: Prop
H: P
X: Prop
hP: P -> X
hQ: Q -> XXassumption.P, Q: Prop
H: P
X: Prop
hP: P -> X
hQ: Q -> XPP, Q: Prop
H: Q
X: Prop
hP: P -> X
hQ: Q -> XXassumption.P, Q: Prop
H: Q
X: Prop
hP: P -> X
hQ: Q -> XQP, Q: PropiOr P Q -> P \/ QP, Q: Prop
h: iOr P QP \/ QP, Q: Prop
h: iOr P QP -> P \/ QP, Q: Prop
h: iOr P QQ -> P \/ QP, Q: Prop
h: iOr P QP -> P \/ QP, Q: Prop
h: iOr P Q
H: PP \/ Qassumption.P, Q: Prop
h: iOr P Q
H: PPP, Q: Prop
h: iOr P QQ -> P \/ QP, Q: Prop
h: iOr P Q
H: QP \/ Qassumption. Qed. Definition iEx (X : Type) (P : X -> Prop) : Prop := forall (Y : Prop), (forall x, P x -> Y) -> Y.P, Q: Prop
h: iOr P Q
H: QQforall (X : Type) (P : X -> Prop), (exists x : X, P x) <-> iEx X Pforall (X : Type) (P : X -> Prop), (exists x : X, P x) <-> iEx X PX: Type
P: X -> Prop(exists x : X, P x) <-> iEx X PX: Type
P: X -> Prop(exists x : X, P x) -> iEx X PX: Type
P: X -> PropiEx X P -> exists x : X, P xX: Type
P: X -> Prop(exists x : X, P x) -> iEx X PX: Type
P: X -> Prop
x: X
hx: P x
Y: Prop
h: forall x : X, P x -> YYassumption.X: Type
P: X -> Prop
x: X
hx: P x
Y: Prop
h: YYX: Type
P: X -> PropiEx X P -> exists x : X, P xX: Type
P: X -> Prop
h: iEx X Pexists x : X, P xX: Type
P: X -> Prop
h: iEx X Pforall x : X, P x -> exists x0 : X, P x0X: Type
P: X -> Prop
h: iEx X P
x: X
hx: P xexists x0 : X, P x0assumption. Qed.X: Type
P: X -> Prop
h: iEx X P
x: X
hx: P xP x
Exercise: Tactics for programs
There is also a fix tactic to introduce fix in the term.
It takes two arguments: fix f n introduces an assumption f in the context,
with the same type as the goal, and n indicates which argument (starting
from 1) is recursive.
So below fix rec 1 introduces rec : nat -> nat -> nat where the first
argument is recursive, a bit like writing rec a b {struct a}.
nat -> nat -> natnat -> nat -> natrec: nat -> nat -> natnat -> nat -> natrec: nat -> nat -> nat
n, m: natnatrec: nat -> nat -> nat
m: natnatrec: nat -> nat -> nat
n, m: natnatapply m.rec: nat -> nat -> nat
m: natnatrec: nat -> nat -> nat
n, m: natnatrec: nat -> nat -> nat
n, m: natnatrec: nat -> nat -> nat
n, m: natnatrec: nat -> nat -> nat
n, m: natnatapply n.rec: nat -> nat -> nat
n, m: natnatapply m. Defined.rec: nat -> nat -> nat
n, m: natnat
First prove the following.
Nat.add = additionreflexivity. Qed.Nat.add = addition
Now define an append function on lists (the one we write ++) using the fix
tactic.
A: Typelist A -> list A -> list AA: Typelist A -> list A -> list AA: Type
rec: list A -> list A -> list Alist A -> list A -> list AA: Type
rec: list A -> list A -> list A
n, m: list Alist AA: Type
rec: list A -> list A -> list A
m: list Alist AA: Type
rec: list A -> list A -> list A
a: A
n, m: list Alist Aexact m.A: Type
rec: list A -> list A -> list A
m: list Alist AA: Type
rec: list A -> list A -> list A
a: A
n, m: list Alist AA: Type
rec: list A -> list A -> list A
a: A
n, m: list AAA: Type
rec: list A -> list A -> list A
a: A
n, m: list Alist AA: Type
rec: list A -> list A -> list A
a: A
n, m: list Alist AA: Type
rec: list A -> list A -> list A
a: A
n, m: list Alist AA: Type
rec: list A -> list A -> list A
a: A
n, m: list Alist Aexact n.A: Type
rec: list A -> list A -> list A
a: A
n, m: list Alist Aexact m. Defined.A: Type
rec: list A -> list A -> list A
a: A
n, m: list Alist Aapp = @appendreflexivity. Qed.app = @append
Exercise: Non-termination (advanced)
There are three crucial potential breaking points of consistency of type theory:
termination of recursive functions, which needs to be ensured;
strict positivity of inductive types, which we see in the lecture right after this exercise;
having type hierarchies rather than a
Type : Typerule.
Define a function of type nat -> nat and use it to deduce False.
Note that this is surprisingly tricky.
Unset Guard Checking. Module Termination.n: natn <> S nn: natn <> S n0 <> 1n: nat
ih: n <> S nS n <> S (S n)discriminate.0 <> 1n: nat
ih: n <> S nS n <> S (S n)n: nat
ih: n <> S n
e: S n = S (S n)Falsen: nat
ih: n <> S n
e: S n = S (S n)
H0: n = S nFalseassumption. Qed. Definition idnat (x : nat) := x. Fixpoint f (x : nat) : nat := S (f (idnat x)).n: nat
ih: n <> S n
e: S n = S (S n)
H0: n = S nn = S nFalseFalsereflexivity. Qed. End Termination. Set Guard Checking.f 0 = S (f 0)
Exercise: Non-positive types (advanced)
Define an inductive type bad such that bad <-> ~ bad, use lemma
Russell from above to derive a contradiction.
Unset Positivity Checking. Module Positivity. Inductive bad := | C : (bad -> False) -> bad.bad <-> ~ badbad <-> ~ badbad -> ~ bad~ bad -> badbad -> ~ badcontradiction.h: bad
nh: bad -> FalseFalse~ bad -> badnh: ~ badbadassumption. Qed.nh: ~ badbad -> FalseFalseapply (Russell _ bad_not_bad). Qed. End Positivity. Set Positivity Checking.False
Exercise: More induction principles
Define induction principles using Fixpoint for all the following types of
trees.
Inductive btree := | bL | bN (b1 b2 : btree). Inductive ltree (L : Type) := | lL (l : L) | lN (l : L) (b1 b2 : ltree L). Inductive atree (L : Type) (B : L -> Type) := | aN (l : L) (bs : B l -> atree L B). Abbreviation altree L := (atree (L * bool) (fun p => if snd p then bool else False)). Fixpoint btree_ind' : forall (P : btree -> Prop), P bL -> (forall b1, P b1 -> forall b2, P b2 -> P (bN b1 b2)) -> forall t, P t := fun P hL hN t => match t with | bL => hL | bN b1 b2 => hN _ (btree_ind' P hL hN b1) _ (btree_ind' P hL hN b2) end. Arguments lL {L}. Arguments lN {L}. Fixpoint ltree_ind' L : forall (P : ltree L -> Prop), (forall l, P (lL l)) -> (forall l b1, P b1 -> forall b2, P b2 -> P (lN l b1 b2)) -> forall t, P t := fun P hL hN t => match t with | lL l => hL l | lN l b1 b2 => hN l _ (ltree_ind' L P hL hN b1) _ (ltree_ind' L P hL hN b2) end. Arguments aN {L B}. Fixpoint atree_ind' L B : forall (P : atree L B -> Prop), (forall l bs, (forall b, P (bs b)) -> P (aN l bs)) -> forall t, P t := fun P h t => match t with | aN l bs => h l _ (fun b => atree_ind' L B P h (bs b)) end.
Define functions to : forall {L}, ltree L -> altree L
and of : forall {L}, altree L -> ltree L such that
forall L (t : ltree L), of (to t) = t.
Fixpoint to {L} (t : ltree L) : altree L := match t with | lL l => aN (l, false) (False_rect _) | lN l b1 b2 => aN (l, true) (fun (b : bool) => if b then to b1 else to b2) end. Fixpoint of {L} (t : altree L) : ltree L := match t with | aN (l, false) bs => lL l | aN (l, true) bs => lN l (of (bs true)) (of (bs false)) end.L: Type
t: ltree Lof (to t) = tL: Type
t: ltree Lof (to t) = tL: Type
l: Lof (to (lL l)) = lL lL: Type
l: L
b1, b2: ltree L
ih1: of (to b1) = b1
ih2: of (to b2) = b2of (to (lN l b1 b2)) = lN l b1 b2L: Type
l: Lof (to (lL l)) = lL lreflexivity.L: Type
l: LlL l = lL lL: Type
l: L
b1, b2: ltree L
ih1: of (to b1) = b1
ih2: of (to b2) = b2of (to (lN l b1 b2)) = lN l b1 b2congruence. Qed.L: Type
l: L
b1, b2: ltree L
ih1: of (to b1) = b1
ih2: of (to b2) = b2lN l (of (to b1)) (of (to b2)) = lN l b1 b2
Exercise: Nested induction principles
Define an induction principle using Fixpoint for rtree.
You may use the Forall predicate to help you.
Fixpoint rtree_ind' :
forall (P : rtree -> Prop),
(forall bs, Forall P bs -> P (rN bs)) ->
forall t, P t :=
fun P h t =>
match t with
| rN bs =>
let hbs :=
fix aux bs : Forall P bs :=
match bs with
| [] => Forall_nil _
| b :: bs => Forall_cons _ (rtree_ind' P h b) (aux bs)
end
in
h _ (hbs bs)
end.Exercise: Fibonacci with recursors (advanced)
Here is the Fibonacci function.
Fixpoint fib n : nat :=
match n with
| 0 | 1 => 1
| S (S n as m) => fib m + fib n
end.Notice the as keyword to give a name to subexpression S n.
This way Rocq knows that S n is a subterm of the one we started with.
Define the Fibonacci function fib using nat_rect directly.
The idea is to recursively produce a pair (fib (n-1), fib n)
and then take the second projection snd.
Definition fib_natrec n :=
let p :=
nat_rect (fun _ => (nat * nat)%type)
(0,1)
(fun _ '(f0, f1) => (f1, f0 + f1))
n
in
snd p.Define it using course-of-values recursion, a form of strong induction shown
below.
Of course you need to prove brec first.
Fixpoint below (P : nat -> Type) (n : nat) : Type := match n with | 0 => unit | S n => P n * below P n end.Fixpoint brec' (P : nat -> Type) (F : forall n', below P n' -> P n') (n : nat) {struct n} : P n * below P n := match n with | 0 => (F 0 tt, tt) | S n => let r := brec' P F n in (F (S n) r , r) end. Definition brec {P : nat -> Type} (F : forall n, below P n -> P n) : forall n, P n := fun n => fst (brec' P F n). Definition fib_brec : nat -> nat := brec (fun n => match n with | 0 => fun _ => 1 | 1 => fun _ => 1 | S (S n) => fun r => fst r + fst (snd r) end ).
Exercise: Type : Type (advanced)
We are going to prove a theorem allowing us to prove False from
Type : Type.
Fill in the missing parts below.
Module Hierarchy. Definition embeds X Y := exists (E : X -> Y) (D : Y -> X), forall x, D (E x) = x.X: Typeembeds X XX: Typeembeds X Xreflexivity. Qed. Definition Tyi := Type. Inductive tree (A : Tyi) (D : A -> Tyi) : Tyi := | T (a : A) (f : D a -> tree A D). Arguments T { _ _}. Definition sub {A : Tyi} {D : A -> Tyi} (s t : @tree A D) : Prop := match t with | T a f => exists x, f x = s end.X: Typeforall x : X, x = xA: Tyi
D: A -> Tyiforall s : tree A D, ~ sub s sA: Tyi
D: A -> Tyiforall s : tree A D, ~ sub s sA: Tyi
D: A -> Tyi
a: A
f: D a -> tree A D
ih: forall H : D a, ~ sub (f H) (f H)~ sub (T a f) (T a f)A: Tyi
D: A -> Tyi
a: A
f: D a -> tree A D
ih: forall H : D a, ~ sub (f H) (f H)
x: D a
e: f x = T a fFalseA: Tyi
D: A -> Tyi
a: A
f: D a -> tree A D
ih: forall H : D a, ~ sub (f H) (f H)
x: D a
e: f x = T a fsub (f x) (f x)A: Tyi
D: A -> Tyi
a: A
f: D a -> tree A D
ih: forall H : D a, ~ sub (f H) (f H)
x: D a
e: f x = T a fsub (f x) (T a f)A: Tyi
D: A -> Tyi
a: A
f: D a -> tree A D
ih: forall H : D a, ~ sub (f H) (f H)
x: D a
e: f x = T a fexists x0 : D a, f x0 = f xreflexivity. Qed.A: Tyi
D: A -> Tyi
a: A
f: D a -> tree A D
ih: forall H : D a, ~ sub (f H) (f H)
x: D a
e: f x = T a ff x = f xA: Type
D: A -> Tyi
E: Tyi -> A~ embeds (tree A D) (D (E (tree A D)))A: Type
D: A -> Tyi
E: Tyi -> A~ embeds (tree A D) (D (E (tree A D)))A: Type
D: A -> Tyi
E: Tyi -> A
F: tree A D -> D (E (tree A D))
G: D (E (tree A D)) -> tree A D
h: forall x : tree A D, G (F x) = xFalseA: Type
D: A -> Tyi
E: Tyi -> A
F: tree A D -> D (E (tree A D))
G: D (E (tree A D)) -> tree A D
h: forall x : tree A D, G (F x) = xsub (T (E (tree A D)) G) (T (E (tree A D)) G)A: Type
D: A -> Tyi
E: Tyi -> A
F: tree A D -> D (E (tree A D))
G: D (E (tree A D)) -> tree A D
h: forall x : tree A D, G (F x) = xexists x : D (E (tree A D)), G x = T (E (tree A D)) Gapply h. Qed.A: Type
D: A -> Tyi
E: Tyi -> A
F: tree A D -> D (E (tree A D))
G: D (E (tree A D)) -> tree A D
h: forall x : tree A D, G (F x) = xG (F (T (E (tree A D)) G)) = T (E (tree A D)) Gforall X : Tyi, ~ embeds Tyi Xforall X : Tyi, ~ embeds Tyi XX: Tyi
E: Tyi -> X
D: X -> Tyi
h: forall x : Tyi, D (E x) = xFalseX: Tyi
E: Tyi -> X
D: X -> Tyi
h: forall x : Tyi, D (E x) = xembeds (tree X D) (D (E (tree X D)))apply embeds_refl. Qed.X: Tyi
E: Tyi -> X
D: X -> Tyi
h: forall x : Tyi, D (E x) = xembeds (tree X D) (tree X D)
We now enable the Type : Type rule.
Unset Universe Checking.FalseFalseapply embeds_refl. Qed. End Hierarchy.embeds Tyi Tyi