Exercise session 2 — Inductive types — Solutions
Set Default Goal Selector "!". (* From the lecture: *) From Stdlib Require Import Datatypes List. Open Scope nat. Import ListNotations. Fixpoint fast_rev {A} (l : list A) (acc : list A) := match l with | [] => acc | x :: l => fast_rev l (x :: acc) end.
Exercise: Reversal
Prove the following lemmas from the lecture again. You will need auxiliary lemmas: prove them yourself by induction and do not use lemmas from the standard library.
Module Rev.A: Type
l: list Al ++ [] = lA: Type
l: list Al ++ [] = lA: Type[] ++ [] = []A: Type
a: A
l: list A
IHl: l ++ [] = l(a :: l) ++ [] = a :: lA: Type[] = []A: Type
a: A
l: list A
IHl: l ++ [] = la :: l ++ [] = a :: lreflexivity.A: Type[] = []A: Type
a: A
l: list A
IHl: l ++ [] = la :: l ++ [] = a :: lreflexivity. Qed.A: Type
a: A
l: list A
IHl: l ++ [] = la :: l = a :: lA: Type
l1, l2, l3: list Al1 ++ l2 ++ l3 = (l1 ++ l2) ++ l3A: Type
l1, l2, l3: list Al1 ++ l2 ++ l3 = (l1 ++ l2) ++ l3A: Type
l2, l3: list A[] ++ l2 ++ l3 = ([] ++ l2) ++ l3A: Type
a: A
l1, l2, l3: list A
IHl: l1 ++ l2 ++ l3 = (l1 ++ l2) ++ l3(a :: l1) ++ l2 ++ l3 = ((a :: l1) ++ l2) ++ l3A: Type
l2, l3: list Al2 ++ l3 = l2 ++ l3A: Type
a: A
l1, l2, l3: list A
IHl: l1 ++ l2 ++ l3 = (l1 ++ l2) ++ l3a :: l1 ++ l2 ++ l3 = a :: (l1 ++ l2) ++ l3reflexivity.A: Type
l2, l3: list Al2 ++ l3 = l2 ++ l3A: Type
a: A
l1, l2, l3: list A
IHl: l1 ++ l2 ++ l3 = (l1 ++ l2) ++ l3a :: l1 ++ l2 ++ l3 = a :: (l1 ++ l2) ++ l3reflexivity. Qed.A: Type
a: A
l1, l2, l3: list A
IHl: l1 ++ l2 ++ l3 = (l1 ++ l2) ++ l3a :: (l1 ++ l2) ++ l3 = a :: (l1 ++ l2) ++ l3forall (A : Type) (l1 l2 : list A), rev (l1 ++ l2) = rev l2 ++ rev l1forall (A : Type) (l1 l2 : list A), rev (l1 ++ l2) = rev l2 ++ rev l1A: Type
l1, l2: list Arev (l1 ++ l2) = rev l2 ++ rev l1A: Type
l2: list Arev ([] ++ l2) = rev l2 ++ rev []A: Type
a: A
l1, l2: list A
IHl: rev (l1 ++ l2) = rev l2 ++ rev l1rev ((a :: l1) ++ l2) = rev l2 ++ rev (a :: l1)A: Type
l2: list Arev l2 = rev l2 ++ []A: Type
a: A
l1, l2: list A
IHl: rev (l1 ++ l2) = rev l2 ++ rev l1rev (l1 ++ l2) ++ [a] = rev l2 ++ rev l1 ++ [a]A: Type
l2: list Arev l2 = rev l2 ++ []reflexivity.A: Type
l2: list Arev l2 = rev l2A: Type
a: A
l1, l2: list A
IHl: rev (l1 ++ l2) = rev l2 ++ rev l1rev (l1 ++ l2) ++ [a] = rev l2 ++ rev l1 ++ [a]reflexivity. Qed.A: Type
a: A
l1, l2: list A
IHl: rev (l1 ++ l2) = rev l2 ++ rev l1(rev l2 ++ rev l1) ++ [a] = (rev l2 ++ rev l1) ++ [a]X: Type
l: list Xrev (rev l) = lX: Type
l: list Xrev (rev l) = lX: Typerev (rev []) = []X: Type
a: X
l: list X
IHl: rev (rev l) = lrev (rev (a :: l)) = a :: lX: Type[] = []X: Type
a: X
l: list X
IHl: rev (rev l) = lrev (rev l ++ [a]) = a :: lreflexivity.X: Type[] = []X: Type
a: X
l: list X
IHl: rev (rev l) = lrev (rev l ++ [a]) = a :: lreflexivity. Qed.X: Type
a: X
l: list X
IHl: rev (rev l) = lrev [a] ++ l = a :: lforall (A : Type) (l : list A), fast_rev l [] = rev lforall (A : Type) (l : list A), fast_rev l [] = rev lA: Type
l: list Afast_rev l [] = rev lA: Type
l: list Aforall acc : list A, fast_rev l acc = rev l ++ accA: Type
l: list A
H: forall acc : list A, fast_rev l acc = rev l ++ accfast_rev l [] = rev lA: Type
l: list Aforall acc : list A, fast_rev l acc = rev l ++ accA: Typeforall acc : list A, fast_rev [] acc = rev [] ++ accA: Type
a: A
l: list A
IHl: forall acc : list A, fast_rev l acc = rev l ++ accforall acc : list A, fast_rev (a :: l) acc = rev (a :: l) ++ accA: Typeforall acc : list A, acc = accA: Type
a: A
l: list A
IHl: forall acc : list A, fast_rev l acc = rev l ++ accforall acc : list A, fast_rev l (a :: acc) = (rev l ++ [a]) ++ accA: Type
acc: list Aacc = accA: Type
a: A
l: list A
IHl: forall acc : list A, fast_rev l acc = rev l ++ acc
acc: list Afast_rev l (a :: acc) = (rev l ++ [a]) ++ accreflexivity.A: Type
acc: list Aacc = accA: Type
a: A
l: list A
IHl: forall acc : list A, fast_rev l acc = rev l ++ acc
acc: list Afast_rev l (a :: acc) = (rev l ++ [a]) ++ accreflexivity.A: Type
a: A
l: list A
IHl: forall acc : list A, fast_rev l acc = rev l ++ acc
acc: list Arev l ++ a :: acc = rev l ++ [a] ++ accA: Type
l: list A
H: forall acc : list A, fast_rev l acc = rev l ++ accfast_rev l [] = rev lreflexivity. Qed. End Rev. (* From the lecture: *) Fixpoint iter {A : Type} (f : A -> A) (n : nat) (x : A) : A := match n with | 0 => x | S n' => f (iter f n' x) end.A: Type
l: list A
H: forall acc : list A, fast_rev l acc = rev l ++ accrev l = rev l
Exercise: Iteration
Nat.pow x n is x to the power of n.
You can use Print Nat.pow. to see the definition.
n, x: natNat.pow x n = iter (Nat.mul x) n 1n, x: natNat.pow x n = iter (Nat.mul x) n 1x: natNat.pow x 0 = iter (Nat.mul x) 0 1n, x: nat
IH: Nat.pow x n = iter (Nat.mul x) n 1Nat.pow x (S n) = iter (Nat.mul x) (S n) 1x: nat1 = 1n, x: nat
IH: Nat.pow x n = iter (Nat.mul x) n 1x * Nat.pow x n = x * iter (Nat.mul x) n 1reflexivity.x: nat1 = 1n, x: nat
IH: Nat.pow x n = iter (Nat.mul x) n 1x * Nat.pow x n = x * iter (Nat.mul x) n 1reflexivity. Qed.n, x: nat
IH: Nat.pow x n = iter (Nat.mul x) n 1x * iter (Nat.mul x) n 1 = x * iter (Nat.mul x) n 1
A: Type
f: A -> A
n: nat
x: Aiter f (S n) x = iter f n (f x)A: Type
f: A -> A
n: nat
x: Aiter f (S n) x = iter f n (f x)A: Type
f: A -> A
x: Aiter f 1 x = iter f 0 (f x)A: Type
f: A -> A
n: nat
x: A
IH: iter f (S n) x = iter f n (f x)iter f (S (S n)) x = iter f (S n) (f x)reflexivity.A: Type
f: A -> A
x: Aiter f 1 x = iter f 0 (f x)A: Type
f: A -> A
n: nat
x: A
IH: iter f (S n) x = iter f n (f x)iter f (S (S n)) x = iter f (S n) (f x)A: Type
f: A -> A
n: nat
x: A
IH: f (iter f n x) = iter f n (f x)f (f (iter f n x)) = f (iter f n (f x))reflexivity. Qed.A: Type
f: A -> A
n: nat
x: A
IH: f (iter f n x) = iter f n (f x)f (f (iter f n x)) = f (f (iter f n x))
Define a tail-recursive iteration function.
Fixpoint iter_tail {A : Type} (f : A -> A) (n : nat) (x : A) : A := match n with | 0 => x | S n => iter_tail f n (f x) end.A: Type
f: A -> A
n: nat
x: Aiter f n x = iter_tail f n xA: Type
f: A -> A
n: nat
x: Aiter f n x = iter_tail f n xA: Type
f: A -> A
n: natforall x : A, iter f n x = iter_tail f n xA: Type
f: A -> Aforall x : A, iter f 0 x = iter_tail f 0 xA: Type
f: A -> A
n: nat
IH: forall x : A, iter f n x = iter_tail f n xforall x : A, iter f (S n) x = iter_tail f (S n) xA: Type
f: A -> A
x: Aiter f 0 x = iter_tail f 0 xA: Type
f: A -> A
n: nat
IH: forall x : A, iter f n x = iter_tail f n x
x: Aiter f (S n) x = iter_tail f (S n) xreflexivity.A: Type
f: A -> A
x: Aiter f 0 x = iter_tail f 0 xA: Type
f: A -> A
n: nat
IH: forall x : A, iter f n x = iter_tail f n x
x: Aiter f (S n) x = iter_tail f (S n) xA: Type
f: A -> A
n: nat
IH: forall x : A, iter f n x = iter_tail f n x
x: Af (iter f n x) = iter_tail f n (f x)apply iter_shift. Qed. (* From the lecture: *)A: Type
f: A -> A
n: nat
IH: forall x : A, iter f n x = iter_tail f n x
x: Af (iter f n x) = iter f n (f x)Combined Scheme tree_forest_mutind from tree_ind', forest_ind'.
Exercise: Mapping over trees
Define a map function for tree.
Definition tree_map {A B} (f : A -> B) (t : tree A) : tree B := (fix map_tree (t : tree A) : tree B := match t with | nnode _ a l => nnode _ (f a) (map_forest l) end with map_forest (l : forest A) : forest B := match l with | nnil _ => nnil _ | ncons _ t tl => ncons _ (map_tree t) (map_forest tl) end for map_tree) t. (* From the lecture: *) From Stdlib Require Import Lia.forall P : nat -> Prop, (forall n : nat, (forall m : nat, m < n -> P m) -> P n) -> forall n : nat, P nforall P : nat -> Prop, (forall n : nat, (forall m : nat, m < n -> P m) -> P n) -> forall n : nat, P nP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: natP n
We'll show a stronger property by induction, that P is valid for n and
everything below.
P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: natforall m : nat, m <= n -> P mP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
hn: forall m : nat, m <= n -> P mP nP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: natforall m : nat, m <= n -> P mP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P nforall m : nat, m <= 0 -> P mP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P mforall m : nat, m <= S n -> P mP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P nforall m : nat, m <= 0 -> P mP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
m: nat
hm: m <= 0P mP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
m: nat
hm: m <= 0
H: m = 0P 0P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
m: nat
hm: m <= 0
H: m = 0forall m0 : nat, m0 < 0 -> P m0lia.P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
m: nat
hm: m <= 0
H: m = 0
k: nat
hk: k < 0P k
lia knows there can't be k < 0 so it solves the goal for us.
It is implicitly using a proof of ~ k < 0 together with False
elimination.
P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P mforall m : nat, m <= S n -> P mP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P m
m: nat
hm: m <= S nP mP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P m
m: nat
hm: m <= S n
H: m = S nP (S n)P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P m
m: nat
hm: m <= S n
m0: nat
H0: m <= n
H: m0 = nP mP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P m
m: nat
hm: m <= S n
H: m = S nP (S n)P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P m
m: nat
hm: m <= S n
H: m = S nforall m0 : nat, m0 < S n -> P m0P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P m
m: nat
hm: m <= S n
H: m = S n
k: nat
hk: k < S nP klia.P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P m
m: nat
hm: m <= S n
H: m = S n
k: nat
hk: k < S nk <= nP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P m
m: nat
hm: m <= S n
m0: nat
H0: m <= n
H: m0 = nP mlia.P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P m
m: nat
hm: m <= S n
m0: nat
H0: m <= n
H: m0 = nm <= nP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
hn: forall m : nat, m <= n -> P mP nlia. Qed.P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
hn: forall m : nat, m <= n -> P mn <= n
Exercise: Strong induction
We now allow you to use lia.
Prove strong induction yourself, without looking at the proof from the
lecture.
Module StrongInd.forall P : nat -> Prop, (forall n : nat, (forall m : nat, m < n -> P m) -> P n) -> forall n : nat, P nforall P : nat -> Prop, (forall n : nat, (forall m : nat, m < n -> P m) -> P n) -> forall n : nat, P nP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: natP nP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: natforall m : nat, m <= n -> P mP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
hn: forall m : nat, m <= n -> P mP nP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: natforall m : nat, m <= n -> P mP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P nforall m : nat, m <= 0 -> P mP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P mforall m : nat, m <= S n -> P mP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P nforall m : nat, m <= 0 -> P mP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
m: nat
hm: m <= 0P mP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
m: nat
hm: m <= 0
H: m = 0P 0P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
m: nat
hm: m <= 0
H: m = 0forall m0 : nat, m0 < 0 -> P m0lia.P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
m: nat
hm: m <= 0
H: m = 0
k: nat
hk: k < 0P kP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P mforall m : nat, m <= S n -> P mP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P m
m: nat
hm: m <= S nP mP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P m
m: nat
hm: m <= S n
H: m = S nP (S n)P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P m
m: nat
hm: m <= S n
m0: nat
H0: m <= n
H: m0 = nP mP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P m
m: nat
hm: m <= S n
H: m = S nP (S n)P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P m
m: nat
hm: m <= S n
H: m = S nforall m0 : nat, m0 < S n -> P m0P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P m
m: nat
hm: m <= S n
H: m = S n
k: nat
hk: k < S nP klia.P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P m
m: nat
hm: m <= S n
H: m = S n
k: nat
hk: k < S nk <= nP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P m
m: nat
hm: m <= S n
m0: nat
H0: m <= n
H: m0 = nP mlia.P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
ih: forall m : nat, m <= n -> P m
m: nat
hm: m <= S n
m0: nat
H0: m <= n
H: m0 = nm <= nP: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
hn: forall m : nat, m <= n -> P mP nlia. Qed. End StrongInd.P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat
hn: forall m : nat, m <= n -> P mn <= n
You can now use strong_nat_ind in the following exercises.
Import StrongInd.Exercise: Evenness
Here are two definitions of even numbers.
Definition even1 n := exists m, n = 2 * m. Fixpoint even2 (n : nat) := match n with | 0 => true | 1 => false | S (S n) => even2 n end.
Define an even predicate similar to how you would define a Boolean predicate but using propositions instead.
Fixpoint even3 (n : nat) : Prop :=
match n with
| 0 => True
| 1 => False
| S (S n) => even3 n
end.And a fourth one, as an inductive predicate.
Inductive even4 : nat -> Prop :=
| even4O : even4 0
| even4S n : even4 n -> even4 (S (S n)).Spell out the induction principle of even4 without checking it.
⚠️ Do not forget this one.
forall P : nat -> Prop,
P 0 ->
(forall n, even4 n -> P n -> P (S (S n))) ->
forall n, even4 n -> P n
.. coq::
Check even4_ind.
n: nateven1 n -> even2 n = truen: nateven1 n -> even2 n = truen, m: nat
e: n = 2 * meven2 n = truem: nateven2 (2 * m) = trueeven2 (2 * 0) = truem: nat
IH: even2 (2 * m) = trueeven2 (2 * S m) = truereflexivity.even2 (2 * 0) = truem: nat
IH: even2 (2 * m) = trueeven2 (2 * S m) = truem: nat
IH: even2 (2 * m) = trueeven2 (S (S (2 * m))) = trueassumption. Qed.m: nat
IH: even2 (2 * m) = trueeven2 (m + (m + 0)) = truen: nateven2 n = true <-> even3 nn: nateven2 n = true <-> even3 nn: nat
IH: forall m : nat, m < n -> even2 m = true <-> even3 meven2 n = true <-> even3 nIH: forall m : nat, m < 0 -> even2 m = true <-> even3 meven2 0 = true <-> even3 0IH: forall m : nat, m < 1 -> even2 m = true <-> even3 meven2 1 = true <-> even3 1n: nat
IH: forall m : nat, m < S (S n) -> even2 m = true <-> even3 meven2 (S (S n)) = true <-> even3 (S (S n))IH: forall m : nat, m < 0 -> even2 m = true <-> even3 mtrue = true <-> TrueIH: forall m : nat, m < 1 -> even2 m = true <-> even3 mfalse = true <-> Falsen: nat
IH: forall m : nat, m < S (S n) -> even2 m = true <-> even3 meven2 n = true <-> even3 nIH: forall m : nat, m < 0 -> even2 m = true <-> even3 mtrue = true <-> TrueIH: forall m : nat, m < 0 -> even2 m = true <-> even3 mtrue = true -> TrueIH: forall m : nat, m < 0 -> even2 m = true <-> even3 mTrue -> true = trueIH: forall m : nat, m < 0 -> even2 m = true <-> even3 mtrue = true -> Trueexact I.IH: forall m : nat, m < 0 -> even2 m = true <-> even3 mTrueIH: forall m : nat, m < 0 -> even2 m = true <-> even3 mTrue -> true = truereflexivity.IH: forall m : nat, m < 0 -> even2 m = true <-> even3 mtrue = trueIH: forall m : nat, m < 1 -> even2 m = true <-> even3 mfalse = true <-> FalseIH: forall m : nat, m < 1 -> even2 m = true <-> even3 mfalse = true -> FalseIH: forall m : nat, m < 1 -> even2 m = true <-> even3 mFalse -> false = trueIH: forall m : nat, m < 1 -> even2 m = true <-> even3 mfalse = true -> Falsediscriminate.IH: forall m : nat, m < 1 -> even2 m = true <-> even3 m
h: false = trueFalseIH: forall m : nat, m < 1 -> even2 m = true <-> even3 mFalse -> false = truecontradiction.IH: forall m : nat, m < 1 -> even2 m = true <-> even3 m
h: Falsefalse = truen: nat
IH: forall m : nat, m < S (S n) -> even2 m = true <-> even3 meven2 n = true <-> even3 nlia. Qed.n: nat
IH: forall m : nat, m < S (S n) -> even2 m = true <-> even3 mn < S (S n)
n: nateven3 n -> even4 nn: nateven3 n -> even4 nn: nat
IH: forall m : nat, m < n -> even3 m -> even4 meven3 n -> even4 nIH: forall m : nat, m < 0 -> even3 m -> even4 meven3 0 -> even4 0IH: forall m : nat, m < 1 -> even3 m -> even4 meven3 1 -> even4 1n: nat
IH: forall m : nat, m < S (S n) -> even3 m -> even4 meven3 (S (S n)) -> even4 (S (S n))IH: forall m : nat, m < 0 -> even3 m -> even4 mTrue -> even4 0IH: forall m : nat, m < 1 -> even3 m -> even4 mFalse -> even4 1n: nat
IH: forall m : nat, m < S (S n) -> even3 m -> even4 meven3 n -> even4 (S (S n))IH: forall m : nat, m < 0 -> even3 m -> even4 m
h: Trueeven4 0IH: forall m : nat, m < 1 -> even3 m -> even4 m
h: Falseeven4 1n: nat
IH: forall m : nat, m < S (S n) -> even3 m -> even4 m
h: even3 neven4 (S (S n))constructor.IH: forall m : nat, m < 0 -> even3 m -> even4 m
h: Trueeven4 0contradiction.IH: forall m : nat, m < 1 -> even3 m -> even4 m
h: Falseeven4 1n: nat
IH: forall m : nat, m < S (S n) -> even3 m -> even4 m
h: even3 neven4 (S (S n))n: nat
IH: forall m : nat, m < S (S n) -> even3 m -> even4 m
h: even3 neven4 nn: nat
IH: forall m : nat, m < S (S n) -> even3 m -> even4 m
h: even3 nn < S (S n)n: nat
IH: forall m : nat, m < S (S n) -> even3 m -> even4 m
h: even3 neven3 nlia.n: nat
IH: forall m : nat, m < S (S n) -> even3 m -> even4 m
h: even3 nn < S (S n)assumption. Qed.n: nat
IH: forall m : nat, m < S (S n) -> even3 m -> even4 m
h: even3 neven3 nn: nateven4 n -> even1 nn: nateven4 n -> even1 nn: nat
h: even4 neven1 neven1 0n: nat
h: even4 n
m: nat
e: n = 2 * meven1 (S (S n))even1 0reflexivity.0 = 2 * 0n: nat
h: even4 n
m: nat
e: n = 2 * meven1 (S (S n))lia. Qed. (* From the lecture: *) Inductive le : nat -> nat -> Prop := | leO n : le n n | leS n m : le n m -> le n (S m).n: nat
h: even4 n
m: nat
e: n = 2 * mS (S n) = 2 * S m
Exercise: Another definition of le
Inductive le' : nat -> nat -> Prop :=
| leO' n : le' 0 n
| leS' n m : le' n m -> le' (S n) (S m).Spell out the induction principle of le' without checking it.
Notice that it's not the same definition as le above.
⚠️ Do not forget this one.
forall P : nat -> nat -> Prop,
(forall n, P 0 n) ->
(forall n m, le' n m -> P n m -> P (S n) (S m)) ->
forall n m, le' n m -> P n m
.. coq::
Check le'_ind.
Prove the following, and the lemmas that you need, by induction.
Do not use the standard library or lia!
n: natle 0 nn: natle 0 nle 0 0n: nat
IH: le 0 nle 0 (S n)constructor.le 0 0n: nat
IH: le 0 nle 0 (S n)assumption. Qed.n: nat
IH: le 0 nle 0 nn, m: natle n m -> le (S n) (S m)n, m: natle n m -> le (S n) (S m)n, m: nat
h: le n mle (S n) (S m)n: natle (S n) (S n)n, m: nat
h: le n m
IH: le (S n) (S m)le (S n) (S (S m))constructor.n: natle (S n) (S n)n, m: nat
h: le n m
IH: le (S n) (S m)le (S n) (S (S m))assumption. Qed.n, m: nat
h: le n m
IH: le (S n) (S m)le (S n) (S m)n: natle' n nn: natle' n nle' 0 0n: nat
IH: le' n nle' (S n) (S n)constructor.le' 0 0n: nat
IH: le' n nle' (S n) (S n)assumption. Qed.n: nat
IH: le' n nle' n nn, m: natle' n m -> le' n (S m)n, m: natle' n m -> le' n (S m)n, m: nat
h: le' n mle' n (S m)n: natle' 0 (S n)n, m: nat
h: le' n m
IH: le' n (S m)le' (S n) (S (S m))constructor.n: natle' 0 (S n)n, m: nat
h: le' n m
IH: le' n (S m)le' (S n) (S (S m))assumption. Qed.n, m: nat
h: le' n m
IH: le' n (S m)le' n (S m)n, m: natle' n m <-> le n mn, m: natle' n m <-> le n mn, m: natle' n m -> le n mn, m: natle n m -> le' n mn, m: natle' n m -> le n mn, m: nat
h: le' n mle n mn: natle 0 nn, m: nat
h: le' n m
IH: le n mle (S n) (S m)apply le_0_n.n: natle 0 nn, m: nat
h: le' n m
IH: le n mle (S n) (S m)assumption.n, m: nat
h: le' n m
IH: le n mle n mn, m: natle n m -> le' n mn, m: nat
h: le n mle' n mn: natle' n nn, m: nat
h: le n m
IH: le' n mle' n (S m)apply le'_refl.n: natle' n nn, m: nat
h: le n m
IH: le' n mle' n (S m)assumption. Qed.n, m: nat
h: le n m
IH: le' n mle' n m
Exercise: Boolean comparison
Fixpoint leb (n m : nat) : bool := match n, m with | 0, _ => true | S _, 0 => false | S n, S m => leb n m end.n, m: natleb n m = true <-> le' n mn, m: natleb n m = true <-> le' n mn: natforall m : nat, leb n m = true <-> le' n mforall m : nat, leb 0 m = true <-> le' 0 mn: nat
IH: forall m : nat, leb n m = true <-> le' n mforall m : nat, leb (S n) m = true <-> le' (S n) mm: natleb 0 m = true <-> le' 0 mn: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: natleb (S n) m = true <-> le' (S n) mm: natleb 0 m = true <-> le' 0 mm: natleb 0 m = true -> le' 0 mm: natle' 0 m -> leb 0 m = truem: natleb 0 m = true -> le' 0 mconstructor.m: natle' 0 mm: natle' 0 m -> leb 0 m = truereflexivity.m: natleb 0 m = truen: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: natleb (S n) m = true <-> le' (S n) mn: nat
IH: forall m : nat, leb n m = true <-> le' n mleb (S n) 0 = true <-> le' (S n) 0n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: natleb (S n) (S m) = true <-> le' (S n) (S m)n: nat
IH: forall m : nat, leb n m = true <-> le' n mleb (S n) 0 = true <-> le' (S n) 0n: nat
IH: forall m : nat, leb n m = true <-> le' n mleb (S n) 0 = true -> le' (S n) 0n: nat
IH: forall m : nat, leb n m = true <-> le' n mle' (S n) 0 -> leb (S n) 0 = truen: nat
IH: forall m : nat, leb n m = true <-> le' n mleb (S n) 0 = true -> le' (S n) 0discriminate.n: nat
IH: forall m : nat, leb n m = true <-> le' n m
h: leb (S n) 0 = truele' (S n) 0n: nat
IH: forall m : nat, leb n m = true <-> le' n mle' (S n) 0 -> leb (S n) 0 = trueinversion h.n: nat
IH: forall m : nat, leb n m = true <-> le' n m
h: le' (S n) 0leb (S n) 0 = truen: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: natleb (S n) (S m) = true <-> le' (S n) (S m)n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: natleb n m = true <-> le' (S n) (S m)n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: natle' n m <-> le' (S n) (S m)n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: natle' n m -> le' (S n) (S m)n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: natle' (S n) (S m) -> le' n mn: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: natle' n m -> le' (S n) (S m)n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: nat
h: le' n mle' (S n) (S m)assumption.n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: nat
h: le' n mle' n mn: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: natle' (S n) (S m) -> le' n mn: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: nat
h: le' (S n) (S m)le' n massumption. Qed.n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: nat
h: le' (S n) (S m)
n0, m0: nat
H1: le' n m
H: n0 = n
H0: m0 = mle' n mn, m: natleb n m = true <-> le n mn, m: natleb n m = true <-> le n mapply le_equiv. Qed. (* From the lecture: *) From Stdlib Require Import Lia List.n, m: natle' n m <-> le n mInductive Forall {A} (P : A -> Prop) : list A -> Prop := | Forall_nil : Forall P nil | Forall_cons a l : P a -> Forall P l -> Forall P (a :: l).rtree_ind': forall (A : Type) (P : rtree A -> Prop), (forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)) -> forall r : rtree A, P rforall (A : Type) (P : rtree A -> Prop), (forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)) -> forall r : rtree A, P rrtree_ind': forall (A : Type) (P : rtree A -> Prop), (forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)) -> forall r : rtree A, P rforall (A : Type) (P : rtree A -> Prop), (forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)) -> forall r : rtree A, P rrtree_ind': forall (A : Type) (P : rtree A -> Prop), (forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)) -> forall r : rtree A, P r
A: Type
P: rtree A -> Prop
IH: forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)
r: rtree AP rrtree_ind': forall (A : Type) (P : rtree A -> Prop), (forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)) -> forall r : rtree A, P r
A: Type
P: rtree A -> Prop
IH: forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)
a: A
ts: list (rtree A)P (N A a ts)rtree_ind': forall (A : Type) (P : rtree A -> Prop), (forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)) -> forall r : rtree A, P r
A: Type
P: rtree A -> Prop
IH: forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)
a: A
ts: list (rtree A)Forall P tsrtree_ind': forall (A : Type) (P : rtree A -> Prop), (forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)) -> forall r : rtree A, P r
A: Type
P: rtree A -> Prop
IH: forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)
a: AForall P []rtree_ind': forall (A : Type) (P : rtree A -> Prop), (forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)) -> forall r : rtree A, P r
A: Type
P: rtree A -> Prop
IH: forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)
a: A
a0: rtree A
ts: list (rtree A)
IHts: Forall P tsForall P (a0 :: ts)econstructor.rtree_ind': forall (A : Type) (P : rtree A -> Prop), (forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)) -> forall r : rtree A, P r
A: Type
P: rtree A -> Prop
IH: forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)
a: AForall P []rtree_ind': forall (A : Type) (P : rtree A -> Prop), (forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)) -> forall r : rtree A, P r
A: Type
P: rtree A -> Prop
IH: forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)
a: A
a0: rtree A
ts: list (rtree A)
IHts: Forall P tsForall P (a0 :: ts)rtree_ind': forall (A : Type) (P : rtree A -> Prop), (forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)) -> forall r : rtree A, P r
A: Type
P: rtree A -> Prop
IH: forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)
a: A
a0: rtree A
ts: list (rtree A)
IHts: Forall P tsP a0rtree_ind': forall (A : Type) (P : rtree A -> Prop), (forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)) -> forall r : rtree A, P r
A: Type
P: rtree A -> Prop
IH: forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)
a: A
a0: rtree A
ts: list (rtree A)
IHts: Forall P tsForall P tsrtree_ind': forall (A : Type) (P : rtree A -> Prop), (forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)) -> forall r : rtree A, P r
A: Type
P: rtree A -> Prop
IH: forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)
a: A
a0: rtree A
ts: list (rtree A)
IHts: Forall P tsP a0assumption.rtree_ind': forall (A : Type) (P : rtree A -> Prop), (forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)) -> forall r : rtree A, P r
A: Type
P: rtree A -> Prop
IH: forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)
a: A
a0: rtree A
ts: list (rtree A)
IHts: Forall P tsforall (a1 : A) (ts0 : list (rtree A)), Forall P ts0 -> P (N A a1 ts0)assumption. Qed. Scheme All for list.rtree_ind': forall (A : Type) (P : rtree A -> Prop), (forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)) -> forall r : rtree A, P r
A: Type
P: rtree A -> Prop
IH: forall (a : A) (ts : list (rtree A)), Forall P ts -> P (N A a ts)
a: A
a0: rtree A
ts: list (rtree A)
IHts: Forall P tsForall P ts
Exercise: Unlabelled trees
Consider the following type of trees, without labels.
Can you give an element of type tree?
Module Unlabelled. Inductive tree := | N (ts : list tree). Definition ex4 : tree := N []. End Unlabelled.
Exercise: All and Forall
Here is a variant of Forall in Type. We also make the arguments of
the constructors of All and Forall implicit.
Inductive All {X} (P : X -> Type) : list X -> Type := | All_nil : All P nil | All_cons x l : P x -> All P l -> All P (x :: l). Arguments All_nil {X P}. Arguments All_cons {X P}. Arguments Forall_nil {A P}. Arguments Forall_cons {A P}.
Give the induction principles for both All and Forall. For every argument,
state whether it is a parameter, non-uniform parameter, or index.
In both cases, the type (X or A) and the predicate P are parameters and
the list is an index. Note that the induction principle of All, which lives
in Type, is dependent: the predicate also takes the proof of All P l.
Prove the following.
A: Type
P: A -> Prop
l: list AAll P l -> Forall P lA: Type
P: A -> Prop
l: list AAll P l -> Forall P lA: Type
P: A -> Prop
l: list A
h: All P lForall P lA: Type
P: A -> PropForall P []A: Type
P: A -> Prop
x: A
l: list A
px: P x
h: All P l
IH: Forall P lForall P (x :: l)constructor.A: Type
P: A -> PropForall P []A: Type
P: A -> Prop
x: A
l: list A
px: P x
h: All P l
IH: Forall P lForall P (x :: l)A: Type
P: A -> Prop
x: A
l: list A
px: P x
h: All P l
IH: Forall P lP xA: Type
P: A -> Prop
x: A
l: list A
px: P x
h: All P l
IH: Forall P lForall P lassumption.A: Type
P: A -> Prop
x: A
l: list A
px: P x
h: All P l
IH: Forall P lP xassumption. Qed.A: Type
P: A -> Prop
x: A
l: list A
px: P x
h: All P l
IH: Forall P lForall P lA: Type
P: A -> Prop
l1, l2: list AForall P l1 -> Forall P l2 -> Forall P (l1 ++ l2)A: Type
P: A -> Prop
l1, l2: list AForall P l1 -> Forall P l2 -> Forall P (l1 ++ l2)A: Type
P: A -> Prop
l1, l2: list A
h1: Forall P l1
h2: Forall P l2Forall P (l1 ++ l2)A: Type
P: A -> Prop
l2: list A
h2: Forall P l2Forall P ([] ++ l2)A: Type
P: A -> Prop
l2: list A
a: A
l: list A
pa: P a
h1: Forall P l
h2: Forall P l2
IH: Forall P (l ++ l2)Forall P ((a :: l) ++ l2)A: Type
P: A -> Prop
l2: list A
h2: Forall P l2Forall P l2A: Type
P: A -> Prop
l2: list A
a: A
l: list A
pa: P a
h1: Forall P l
h2: Forall P l2
IH: Forall P (l ++ l2)Forall P (a :: l ++ l2)assumption.A: Type
P: A -> Prop
l2: list A
h2: Forall P l2Forall P l2A: Type
P: A -> Prop
l2: list A
a: A
l: list A
pa: P a
h1: Forall P l
h2: Forall P l2
IH: Forall P (l ++ l2)Forall P (a :: l ++ l2)A: Type
P: A -> Prop
l2: list A
a: A
l: list A
pa: P a
h1: Forall P l
h2: Forall P l2
IH: Forall P (l ++ l2)P aA: Type
P: A -> Prop
l2: list A
a: A
l: list A
pa: P a
h1: Forall P l
h2: Forall P l2
IH: Forall P (l ++ l2)Forall P (l ++ l2)assumption.A: Type
P: A -> Prop
l2: list A
a: A
l: list A
pa: P a
h1: Forall P l
h2: Forall P l2
IH: Forall P (l ++ l2)P aassumption. Qed. Fixpoint All_app {A} (P : A -> Prop) (l1 l2 : list A) (h1 : All P l1) (h2 : All P l2) {struct h1} : All P (l1 ++ l2) := match h1 in @All _ _ l1 return All P (l1 ++ l2) with | All_nil => h2 | All_cons x l px hl => All_cons x (l ++ l2) px (All_app P l l2 hl h2) end.A: Type
P: A -> Prop
l2: list A
a: A
l: list A
pa: P a
h1: Forall P l
h2: Forall P l2
IH: Forall P (l ++ l2)Forall P (l ++ l2)
Exercise: Labelled trees
Extend the type
Unlabelled.treeto have labelled nodes.Prove a bijection between the new type and the mutual
treefrom the first part, i.e. define functions from one to the other and show that they invert each other.
The labelled version is exactly rtree from above.
Fixpoint from_rtree {A} (t : rtree A) : tree A := match t with | N _ a ts => nnode A a ((fix from_list (ts : list (rtree A)) : forest A := match ts with | [] => nnil A | t :: ts => ncons A (from_rtree t) (from_list ts) end) ts) end.A: Type
t: tree Afrom_rtree (to_rtree t) = tA: Type
t: tree Afrom_rtree (to_rtree t) = tA: Type
t: tree Aforall (a : A) (f : forest A), (forall a0 : A, from_rtree (N A a0 (to_rtree_forest f)) = nnode A a0 f) -> from_rtree (to_rtree (nnode A a f)) = nnode A a fA: Type
t: tree Aforall a : A, from_rtree (N A a (to_rtree_forest (nnil A))) = nnode A a (nnil A)A: Type
t: tree Aforall t0 : tree A, from_rtree (to_rtree t0) = t0 -> forall f : forest A, (forall a : A, from_rtree (N A a (to_rtree_forest f)) = nnode A a f) -> forall a : A, from_rtree (N A a (to_rtree_forest (ncons A t0 f))) = nnode A a (ncons A t0 f)A: Type
t: tree Aforall (a : A) (f : forest A), (forall a0 : A, from_rtree (N A a0 (to_rtree_forest f)) = nnode A a0 f) -> from_rtree (to_rtree (nnode A a f)) = nnode A a fexact (IH a).A: Type
t: tree A
a: A
f: forest A
IH: forall a : A, from_rtree (N A a (to_rtree_forest f)) = nnode A a ffrom_rtree (to_rtree (nnode A a f)) = nnode A a fA: Type
t: tree Aforall a : A, from_rtree (N A a (to_rtree_forest (nnil A))) = nnode A a (nnil A)reflexivity.A: Type
t: tree A
a: Afrom_rtree (N A a (to_rtree_forest (nnil A))) = nnode A a (nnil A)A: Type
t: tree Aforall t0 : tree A, from_rtree (to_rtree t0) = t0 -> forall f : forest A, (forall a : A, from_rtree (N A a (to_rtree_forest f)) = nnode A a f) -> forall a : A, from_rtree (N A a (to_rtree_forest (ncons A t0 f))) = nnode A a (ncons A t0 f)A: Type
t, t': tree A
IHt: from_rtree (to_rtree t') = t'
f: forest A
IHf: forall a : A, from_rtree (N A a (to_rtree_forest f)) = nnode A a f
a: Afrom_rtree (N A a (to_rtree_forest (ncons A t' f))) = nnode A a (ncons A t' f)A: Type
t, t': tree A
IHt: from_rtree (to_rtree t') = t'
f: forest A
a: A
IHf: from_rtree (N A a (to_rtree_forest f)) = nnode A a ffrom_rtree (N A a (to_rtree_forest (ncons A t' f))) = nnode A a (ncons A t' f)A: Type
t, t': tree A
IHt: from_rtree (to_rtree t') = t'
f: forest A
a: A
IHf: nnode A a ((fix from_list (ts : list (rtree A)) : forest A := match ts with | [] => nnil A | t :: ts0 => ncons A (from_rtree t) (from_list ts0) end) (to_rtree_forest f)) = nnode A a fnnode A a (ncons A (from_rtree (to_rtree t')) ((fix from_list (ts : list (rtree A)) : forest A := match ts with | [] => nnil A | t0 :: ts0 => ncons A (from_rtree t0) (from_list ts0) end) (to_rtree_forest f))) = nnode A a (ncons A t' f)A: Type
t, t': tree A
IHt: from_rtree (to_rtree t') = t'
f: forest A
a: A
IHf: (fix from_list (ts : list (rtree A)) : forest A := match ts with | [] => nnil A | t :: ts0 => ncons A (from_rtree t) (from_list ts0) end) (to_rtree_forest f) = fnnode A a (ncons A (from_rtree (to_rtree t')) ((fix from_list (ts : list (rtree A)) : forest A := match ts with | [] => nnil A | t0 :: ts0 => ncons A (from_rtree t0) (from_list ts0) end) (to_rtree_forest f))) = nnode A a (ncons A t' f)reflexivity. Qed.A: Type
t, t': tree A
IHt: from_rtree (to_rtree t') = t'
f: forest A
a: A
IHf: (fix from_list (ts : list (rtree A)) : forest A := match ts with | [] => nnil A | t :: ts0 => ncons A (from_rtree t) (from_list ts0) end) (to_rtree_forest f) = fnnode A a (ncons A t' f) = nnode A a (ncons A t' f)A: Type
t: rtree Ato_rtree (from_rtree t) = tA: Type
t: rtree Ato_rtree (from_rtree t) = tA: Typeforall t : rtree A, to_rtree (from_rtree t) = tA: Typeforall (a : A) (ts : list (rtree A)), Forall (fun r : rtree A => to_rtree (from_rtree r) = r) ts -> to_rtree (from_rtree (N A a ts)) = N A a tsA: Type
a: A
ts: list (rtree A)
IH: Forall (fun r : rtree A => to_rtree (from_rtree r) = r) tsto_rtree (from_rtree (N A a ts)) = N A a tsA: Type
a: A
ts: list (rtree A)
IH: Forall (fun r : rtree A => to_rtree (from_rtree r) = r) tsN A a (to_rtree_forest ((fix from_list (ts0 : list (rtree A)) : forest A := match ts0 with | [] => nnil A | t :: ts1 => ncons A (from_rtree t) (from_list ts1) end) ts)) = N A a tsA: Type
a: A
ts: list (rtree A)
IH: Forall (fun r : rtree A => to_rtree (from_rtree r) = r) tsto_rtree_forest ((fix from_list (ts0 : list (rtree A)) : forest A := match ts0 with | [] => nnil A | t :: ts1 => ncons A (from_rtree t) (from_list ts1) end) ts) = tsA: Type
a: Ato_rtree_forest (nnil A) = []A: Type
a: A
t: rtree A
ts: list (rtree A)
ht: to_rtree (from_rtree t) = t
hts: Forall (fun r : rtree A => to_rtree (from_rtree r) = r) ts
IHts: to_rtree_forest ((fix from_list (ts : list (rtree A)) : forest A := match ts with | [] => nnil A | t :: ts0 => ncons A (from_rtree t) (from_list ts0) end) ts) = tsto_rtree_forest (ncons A (from_rtree t) ((fix from_list (ts0 : list (rtree A)) : forest A := match ts0 with | [] => nnil A | t0 :: ts1 => ncons A (from_rtree t0) (from_list ts1) end) ts)) = t :: tsreflexivity.A: Type
a: Ato_rtree_forest (nnil A) = []A: Type
a: A
t: rtree A
ts: list (rtree A)
ht: to_rtree (from_rtree t) = t
hts: Forall (fun r : rtree A => to_rtree (from_rtree r) = r) ts
IHts: to_rtree_forest ((fix from_list (ts : list (rtree A)) : forest A := match ts with | [] => nnil A | t :: ts0 => ncons A (from_rtree t) (from_list ts0) end) ts) = tsto_rtree_forest (ncons A (from_rtree t) ((fix from_list (ts0 : list (rtree A)) : forest A := match ts0 with | [] => nnil A | t0 :: ts1 => ncons A (from_rtree t0) (from_list ts1) end) ts)) = t :: tsA: Type
a: A
t: rtree A
ts: list (rtree A)
ht: to_rtree (from_rtree t) = t
hts: Forall (fun r : rtree A => to_rtree (from_rtree r) = r) ts
IHts: to_rtree_forest ((fix from_list (ts : list (rtree A)) : forest A := match ts with | [] => nnil A | t :: ts0 => ncons A (from_rtree t) (from_list ts0) end) ts) = tsto_rtree (from_rtree t) :: to_rtree_forest ((fix from_list (ts0 : list (rtree A)) : forest A := match ts0 with | [] => nnil A | t0 :: ts1 => ncons A (from_rtree t0) (from_list ts1) end) ts) = t :: tsreflexivity. Qed. (* From the lecture: *) Inductive rtclos {A} (R : A -> A -> Prop) (x : A) : A -> Prop := | refl : rtclos R x x | incl y : R x y -> rtclos R x y | trans y z : rtclos R x y -> rtclos R y z -> rtclos R x z. Arguments trans {A R}.A: Type
a: A
t: rtree A
ts: list (rtree A)
ht: to_rtree (from_rtree t) = t
hts: Forall (fun r : rtree A => to_rtree (from_rtree r) = r) ts
IHts: to_rtree_forest ((fix from_list (ts : list (rtree A)) : forest A := match ts with | [] => nnil A | t :: ts0 => ncons A (from_rtree t) (from_list ts0) end) ts) = tst :: ts = t :: ts
Exercise: Membership in a list
Fixpoint In {A} (x : A) (l : list A) : Prop :=
match l with
| nil => False
| y :: m => y = x \/ In x m
end.Propose an inductive definition of membership (add the missing constructor(s)).
Inductive In_i {A} : A -> list A -> Prop := | In_here x l : In_i x (x :: l) | In_there x y l : In_i x l -> In_i x (y :: l).A: Type
x: A
l: list AIn x l <-> In_i x lA: Type
x: A
l: list AIn x l <-> In_i x lA: Type
x: A
l: list AIn x l -> In_i x lA: Type
x: A
l: list AIn_i x l -> In x lA: Type
x: A
l: list AIn x l -> In_i x lA: Type
x: AIn x [] -> In_i x []A: Type
x, y: A
l: list A
IH: In x l -> In_i x lIn x (y :: l) -> In_i x (y :: l)A: Type
x: AFalse -> In_i x []A: Type
x, y: A
l: list A
IH: In x l -> In_i x ly = x \/ In x l -> In_i x (y :: l)A: Type
x: A
h: FalseIn_i x []A: Type
x, y: A
l: list A
IH: In x l -> In_i x l
h: y = x \/ In x lIn_i x (y :: l)contradiction.A: Type
x: A
h: FalseIn_i x []A: Type
x, y: A
l: list A
IH: In x l -> In_i x l
h: y = x \/ In x lIn_i x (y :: l)A: Type
x, y: A
l: list A
IH: In x l -> In_i x l
e: y = xIn_i x (y :: l)A: Type
x, y: A
l: list A
IH: In x l -> In_i x l
h: In x lIn_i x (y :: l)A: Type
x, y: A
l: list A
IH: In x l -> In_i x l
e: y = xIn_i x (y :: l)apply In_here.A: Type
x: A
l: list A
IH: In x l -> In_i x lIn_i x (x :: l)A: Type
x, y: A
l: list A
IH: In x l -> In_i x l
h: In x lIn_i x (y :: l)A: Type
x, y: A
l: list A
IH: In x l -> In_i x l
h: In x lIn_i x lassumption.A: Type
x, y: A
l: list A
IH: In x l -> In_i x l
h: In x lIn x lA: Type
x: A
l: list AIn_i x l -> In x lA: Type
x: A
l: list A
h: In_i x lIn x lA: Type
x: A
l: list AIn x (x :: l)A: Type
x, y: A
l: list A
h: In_i x l
IH: In x lIn x (y :: l)A: Type
x: A
l: list Ax = x \/ In x lA: Type
x, y: A
l: list A
h: In_i x l
IH: In x ly = x \/ In x lA: Type
x: A
l: list Ax = x \/ In x lreflexivity.A: Type
x: A
l: list Ax = xA: Type
x, y: A
l: list A
h: In_i x l
IH: In x ly = x \/ In x lassumption. Qed.A: Type
x, y: A
l: list A
h: In_i x l
IH: In x lIn x l
Exercise: Reflexive transitive closure
Here is another definition of the reflexive transitive closure.
Inductive rtclos' {A} (R : A -> A -> Prop) : A -> A -> Prop :=
| refl' x : rtclos' R x x
| trans' x y z : R x y -> rtclos' R y z -> rtclos' R x z.
forall (A : Type) (R : A -> A -> Prop) (x y z : A), rtclos' R x y -> rtclos' R y z -> rtclos' R x zforall (A : Type) (R : A -> A -> Prop) (x y z : A), rtclos' R x y -> rtclos' R y z -> rtclos' R x zA: Type
R: A -> A -> Prop
x, y, z: A
h1: rtclos' R x y
h2: rtclos' R y zrtclos' R x zA: Type
R: A -> A -> Prop
z, x: A
h2: rtclos' R x zrtclos' R x zA: Type
R: A -> A -> Prop
z, x, w, y: A
r: R x w
h1: rtclos' R w y
h2: rtclos' R y z
IH: rtclos' R y z -> rtclos' R w zrtclos' R x zassumption.A: Type
R: A -> A -> Prop
z, x: A
h2: rtclos' R x zrtclos' R x zA: Type
R: A -> A -> Prop
z, x, w, y: A
r: R x w
h1: rtclos' R w y
h2: rtclos' R y z
IH: rtclos' R y z -> rtclos' R w zrtclos' R x zA: Type
R: A -> A -> Prop
z, x, w, y: A
r: R x w
h1: rtclos' R w y
h2: rtclos' R y z
IH: rtclos' R y z -> rtclos' R w zR x wA: Type
R: A -> A -> Prop
z, x, w, y: A
r: R x w
h1: rtclos' R w y
h2: rtclos' R y z
IH: rtclos' R y z -> rtclos' R w zrtclos' R w zassumption.A: Type
R: A -> A -> Prop
z, x, w, y: A
r: R x w
h1: rtclos' R w y
h2: rtclos' R y z
IH: rtclos' R y z -> rtclos' R w zR x wA: Type
R: A -> A -> Prop
z, x, w, y: A
r: R x w
h1: rtclos' R w y
h2: rtclos' R y z
IH: rtclos' R y z -> rtclos' R w zrtclos' R w zassumption. Qed.A: Type
R: A -> A -> Prop
z, x, w, y: A
r: R x w
h1: rtclos' R w y
h2: rtclos' R y z
IH: rtclos' R y z -> rtclos' R w zrtclos' R y zforall (A : Type) (R : A -> A -> Prop) (x y : A), rtclos R x y <-> rtclos' R x yforall (A : Type) (R : A -> A -> Prop) (x y : A), rtclos R x y <-> rtclos' R x yA: Type
R: A -> A -> Prop
x, y: Artclos R x y <-> rtclos' R x yA: Type
R: A -> A -> Prop
x, y: Artclos R x y -> rtclos' R x yA: Type
R: A -> A -> Prop
x, y: Artclos' R x y -> rtclos R x yA: Type
R: A -> A -> Prop
x, y: Artclos R x y -> rtclos' R x yA: Type
R: A -> A -> Prop
x, y: A
h: rtclos R x yrtclos' R x yA: Type
R: A -> A -> Prop
x: Artclos' R x xA: Type
R: A -> A -> Prop
x, y: A
r: R x yrtclos' R x yA: Type
R: A -> A -> Prop
x, y, z: A
h1: rtclos R x y
h2: rtclos R y z
IH1: rtclos' R x y
IH2: rtclos' R y zrtclos' R x zapply refl'.A: Type
R: A -> A -> Prop
x: Artclos' R x xA: Type
R: A -> A -> Prop
x, y: A
r: R x yrtclos' R x yA: Type
R: A -> A -> Prop
x, y: A
r: R x yR x yA: Type
R: A -> A -> Prop
x, y: A
r: R x yrtclos' R y yassumption.A: Type
R: A -> A -> Prop
x, y: A
r: R x yR x yapply refl'.A: Type
R: A -> A -> Prop
x, y: A
r: R x yrtclos' R y yA: Type
R: A -> A -> Prop
x, y, z: A
h1: rtclos R x y
h2: rtclos R y z
IH1: rtclos' R x y
IH2: rtclos' R y zrtclos' R x zA: Type
R: A -> A -> Prop
x, y, z: A
h1: rtclos R x y
h2: rtclos R y z
IH1: rtclos' R x y
IH2: rtclos' R y zrtclos' R x yA: Type
R: A -> A -> Prop
x, y, z: A
h1: rtclos R x y
h2: rtclos R y z
IH1: rtclos' R x y
IH2: rtclos' R y zrtclos' R y zassumption.A: Type
R: A -> A -> Prop
x, y, z: A
h1: rtclos R x y
h2: rtclos R y z
IH1: rtclos' R x y
IH2: rtclos' R y zrtclos' R x yassumption.A: Type
R: A -> A -> Prop
x, y, z: A
h1: rtclos R x y
h2: rtclos R y z
IH1: rtclos' R x y
IH2: rtclos' R y zrtclos' R y zA: Type
R: A -> A -> Prop
x, y: Artclos' R x y -> rtclos R x yA: Type
R: A -> A -> Prop
x, y: A
h: rtclos' R x yrtclos R x yA: Type
R: A -> A -> Prop
x: Artclos R x xA: Type
R: A -> A -> Prop
x, w, y: A
r: R x w
h: rtclos' R w y
IH: rtclos R w yrtclos R x yapply refl.A: Type
R: A -> A -> Prop
x: Artclos R x xA: Type
R: A -> A -> Prop
x, w, y: A
r: R x w
h: rtclos' R w y
IH: rtclos R w yrtclos R x yA: Type
R: A -> A -> Prop
x, w, y: A
r: R x w
h: rtclos' R w y
IH: rtclos R w yrtclos R x wA: Type
R: A -> A -> Prop
x, w, y: A
r: R x w
h: rtclos' R w y
IH: rtclos R w yrtclos R w yA: Type
R: A -> A -> Prop
x, w, y: A
r: R x w
h: rtclos' R w y
IH: rtclos R w yrtclos R x wassumption.A: Type
R: A -> A -> Prop
x, w, y: A
r: R x w
h: rtclos' R w y
IH: rtclos R w yR x wassumption. Qed.A: Type
R: A -> A -> Prop
x, w, y: A
r: R x w
h: rtclos' R w y
IH: rtclos R w yrtclos R w y
Exercise: Factorial and Fibonacci (advanced)
This and the following exercises are more advanced. Make sure you manage to do the previous exercises before. Do not hesitate to ask for help.
Define the factorial function in two ways:
once using
Fixpointand once using
iter
Prove that both yield the same value for all arguments.
⚠️ Do not forget this one. We have not stated the lemmas this time.
Fixpoint fact (n : nat) : nat := match n with | 0 => 1 | S n => S n * fact n end. Definition fact_iter (n : nat) : nat := snd (iter (fun '(k, r) => (S k, S k * r)) n (0, 1)).n: natfact_iter n = fact nn: natfact_iter n = fact nn: natsnd (iter (fun '(k, r) => (S k, S k * r)) n (0, 1)) = fact nn: natiter (fun '(k, r) => (S k, S k * r)) n (0, 1) = (n, fact n)n: nat
h: iter (fun '(k, r) => (S k, S k * r)) n (0, 1) = (n, fact n)snd (iter (fun '(k, r) => (S k, S k * r)) n (0, 1)) = fact nn: natiter (fun '(k, r) => (S k, S k * r)) n (0, 1) = (n, fact n)iter (fun '(k, r) => (S k, S k * r)) 0 (0, 1) = (0, fact 0)n: nat
IH: iter (fun '(k, r) => (S k, S k * r)) n (0, 1) = (n, fact n)iter (fun '(k, r) => (S k, S k * r)) (S n) (0, 1) = (S n, fact (S n))reflexivity.iter (fun '(k, r) => (S k, S k * r)) 0 (0, 1) = (0, fact 0)n: nat
IH: iter (fun '(k, r) => (S k, S k * r)) n (0, 1) = (n, fact n)iter (fun '(k, r) => (S k, S k * r)) (S n) (0, 1) = (S n, fact (S n))n: nat
IH: iter (fun '(k, r) => (S k, S k * r)) n (0, 1) = (n, fact n)(let '(k, r) := iter (fun '(k, r) => (S k, S k * r)) n (0, 1) in (S k, S k * r)) = (S n, fact (S n))reflexivity.n: nat
IH: iter (fun '(k, r) => (S k, S k * r)) n (0, 1) = (n, fact n)(S n, S n * fact n) = (S n, fact (S n))n: nat
h: iter (fun '(k, r) => (S k, S k * r)) n (0, 1) = (n, fact n)snd (iter (fun '(k, r) => (S k, S k * r)) n (0, 1)) = fact nreflexivity. Qed.n: nat
h: iter (fun '(k, r) => (S k, S k * r)) n (0, 1) = (n, fact n)snd (n, fact n) = fact n
Define the Fibonacci function, using only iter (no recursive definition).
As a reminder fib 0 = 0, fib 1 = 1 and fib (n+2) = fib (n+1) + fib n.
Then prove that it satisfies these equations.
Module Fib_Iter. Definition fib (n : nat) : nat := fst (iter (fun '(a, b) => (b, a + b)) n (0, 1)).fib 0 = 0reflexivity. Qed.fib 0 = 0fib 1 = 1reflexivity. Qed.fib 1 = 1forall n : nat, fib (S (S n)) = fib n + fib (S n)forall n : nat, fib (S (S n)) = fib n + fib (S n)n: natfib (S (S n)) = fib n + fib (S n)n: natfst (iter (fun '(a, b) => (b, a + b)) (S (S n)) (0, 1)) = fst (iter (fun '(a, b) => (b, a + b)) n (0, 1)) + fst (iter (fun '(a, b) => (b, a + b)) (S n) (0, 1))n: natfst (let '(a, b) := let '(a, b) := iter (fun '(a, b) => (b, a + b)) n (0, 1) in (b, a + b) in (b, a + b)) = fst (iter (fun '(a, b) => (b, a + b)) n (0, 1)) + fst (let '(a, b) := iter (fun '(a, b) => (b, a + b)) n (0, 1) in (b, a + b))reflexivity. Qed. End Fib_Iter.n, a, b: natfst (a + b, b + (a + b)) = fst (a, b) + fst (b, a + b)
Exercise: Cantor pairing (advanced)
Here is an implementation of the Cantor pairing and its inverse function,
a bijection between nat * nat and nat.
From Stdlib Require Import PeanoNat. Fixpoint to_nat' n := match n with | 0 => 0 | S i => S i + to_nat' i end.
Note that the following notation '(x, y) is performing pattern matching
implicitly.
Definition to_nat '(x, y) : nat := y + to_nat' (y + x). Fixpoint of_nat (n : nat) : nat * nat := match n with | 0 => (0,0) | S i => let '(x,y) := of_nat i in match x with | 0 => (S y, 0) | S x => (x, S y) end end.
Show that of_nat is a left inverse for to_nat.
forall p : nat * nat, of_nat (to_nat p) = pforall p : nat * nat, of_nat (to_nat p) = pforall (n : nat) (p : nat * nat), to_nat p = n -> of_nat n = pH: forall (n : nat) (p : nat * nat), to_nat p = n -> of_nat n = pforall p : nat * nat, of_nat (to_nat p) = pforall (n : nat) (p : nat * nat), to_nat p = n -> of_nat n = pforall p : nat * nat, to_nat p = 0 -> of_nat 0 = pn: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = pforall p : nat * nat, to_nat p = S n -> of_nat (S n) = px, y: nat
h: to_nat (x, y) = 0of_nat 0 = (x, y)n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x, y: nat
h: to_nat (x, y) = S nof_nat (S n) = (x, y)x, y: nat
h: to_nat (x, y) = 0of_nat 0 = (x, y)h: to_nat (0, 0) = 0of_nat 0 = (0, 0)y: nat
h: to_nat (0, S y) = 0of_nat 0 = (0, S y)x: nat
h: to_nat (S x, 0) = 0of_nat 0 = (S x, 0)x, y: nat
h: to_nat (S x, S y) = 0of_nat 0 = (S x, S y)h: 0 = 0of_nat 0 = (0, 0)y: nat
h: S (y + S (y + 0 + to_nat' (y + 0))) = 0of_nat 0 = (0, S y)x: nat
h: S (x + to_nat' x) = 0of_nat 0 = (S x, 0)x, y: nat
h: S (y + S (y + S x + to_nat' (y + S x))) = 0of_nat 0 = (S x, S y)reflexivity.h: 0 = 0of_nat 0 = (0, 0)n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x, y: nat
h: to_nat (x, y) = S nof_nat (S n) = (x, y)n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x: nat
h: to_nat (x, 0) = S nof_nat (S n) = (x, 0)n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x, y: nat
h: to_nat (x, S y) = S nof_nat (S n) = (x, S y)n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x: nat
h: to_nat (x, 0) = S nof_nat (S n) = (x, 0)n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
h: to_nat (0, 0) = S nof_nat (S n) = (0, 0)n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x: nat
h: to_nat (S x, 0) = S nof_nat (S n) = (S x, 0)n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
h: to_nat (0, 0) = S nof_nat (S n) = (0, 0)discriminate.n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
h: 0 = S nof_nat (S n) = (0, 0)n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x: nat
h: to_nat (S x, 0) = S nof_nat (S n) = (S x, 0)n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x: nat
h: to_nat (S x, 0) = S nto_nat (0, x) = nn: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x: nat
h: to_nat (S x, 0) = S n
e: to_nat (0, x) = nof_nat (S n) = (S x, 0)n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x: nat
h: to_nat (S x, 0) = S nto_nat (0, x) = nn: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x: nat
h: S (x + to_nat' x) = S nx + to_nat' (x + 0) = nlia.n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x: nat
h: S (x + to_nat' x) = S nx + to_nat' x = nn: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x: nat
h: to_nat (S x, 0) = S n
e: to_nat (0, x) = nof_nat (S n) = (S x, 0)n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x: nat
h: to_nat (S x, 0) = S n
e: to_nat (0, x) = nmatch of_nat n with | (0, y) => (S y, 0) | (S x1, y) => (x1, S y) end = (S x, 0)reflexivity.n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x: nat
h: to_nat (S x, 0) = S n
e: to_nat (0, x) = n(S x, 0) = (S x, 0)n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x, y: nat
h: to_nat (x, S y) = S nof_nat (S n) = (x, S y)n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x, y: nat
h: to_nat (x, S y) = S nto_nat (S x, y) = nn: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x, y: nat
h: to_nat (x, S y) = S n
e: to_nat (S x, y) = nof_nat (S n) = (x, S y)n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x, y: nat
h: to_nat (x, S y) = S nto_nat (S x, y) = nn: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x, y: nat
h: S (y + S (y + x + to_nat' (y + x))) = S ny + to_nat' (y + S x) = nn: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x, y: nat
h: S (y + S (y + x + to_nat' (y + x))) = S ny + to_nat' (S (y + x)) = nlia.n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x, y: nat
h: S (y + S (y + x + to_nat' (y + x))) = S ny + S (y + x + to_nat' (y + x)) = nn: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x, y: nat
h: to_nat (x, S y) = S n
e: to_nat (S x, y) = nof_nat (S n) = (x, S y)n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x, y: nat
h: to_nat (x, S y) = S n
e: to_nat (S x, y) = nmatch of_nat n with | (0, y0) => (S y0, 0) | (S x1, y0) => (x1, S y0) end = (x, S y)reflexivity.n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x, y: nat
h: to_nat (x, S y) = S n
e: to_nat (S x, y) = n(x, S y) = (x, S y)H: forall (n : nat) (p : nat * nat), to_nat p = n -> of_nat n = pforall p : nat * nat, of_nat (to_nat p) = pH: forall (n : nat) (p : nat * nat), to_nat p = n -> of_nat n = p
p: nat * natof_nat (to_nat p) = preflexivity. Qed.H: forall (n : nat) (p : nat * nat), to_nat p = n -> of_nat n = p
p: nat * natto_nat p = to_nat p
Show to_nat is injective.
forall p q : nat * nat, to_nat p = to_nat q -> p = qforall p q : nat * nat, to_nat p = to_nat q -> p = qp, q: nat * nat
h: to_nat p = to_nat qp = qreflexivity. Qed.p, q: nat * nat
h: to_nat p = to_nat qof_nat (to_nat q) = of_nat (to_nat q)
Show to_nat is a left inverse for of_nat.
forall n : nat, to_nat (of_nat n) = nforall n : nat, to_nat (of_nat n) = nto_nat (of_nat 0) = 0n: nat
IH: to_nat (of_nat n) = nto_nat (of_nat (S n)) = S nreflexivity.to_nat (of_nat 0) = 0n: nat
IH: to_nat (of_nat n) = nto_nat (of_nat (S n)) = S nn: nat
IH: to_nat (of_nat n) = nto_nat match of_nat n with | (0, y) => (S y, 0) | (S x0, y) => (x0, S y) end = S nn, x, y: nat
e: of_nat n = (x, y)
IH: to_nat (x, y) = nto_nat match x with | 0 => (S y, 0) | S x0 => (x0, S y) end = S nn, y: nat
e: of_nat n = (0, y)
IH: to_nat (0, y) = nto_nat (S y, 0) = S nn, x, y: nat
e: of_nat n = (S x, y)
IH: to_nat (S x, y) = nto_nat (x, S y) = S nn, y: nat
e: of_nat n = (0, y)
IH: to_nat (0, y) = nto_nat (S y, 0) = S nn, y: nat
e: of_nat n = (0, y)
IH: y + to_nat' (y + 0) = nS (y + to_nat' y) = S nlia.n, y: nat
e: of_nat n = (0, y)
IH: y + to_nat' y = nS (y + to_nat' y) = S nn, x, y: nat
e: of_nat n = (S x, y)
IH: to_nat (S x, y) = nto_nat (x, S y) = S nn, x, y: nat
e: of_nat n = (S x, y)
IH: y + to_nat' (y + S x) = nS (y + S (y + x + to_nat' (y + x))) = S nn, x, y: nat
e: of_nat n = (S x, y)
IH: y + to_nat' (S (y + x)) = nS (y + S (y + x + to_nat' (y + x))) = S nlia. Qed.n, x, y: nat
e: of_nat n = (S x, y)
IH: y + S (y + x + to_nat' (y + x)) = nS (y + S (y + x + to_nat' (y + x))) = S n
Show of_nat is injective.
forall n m : nat, of_nat n = of_nat m -> n = mforall n m : nat, of_nat n = of_nat m -> n = mn, m: nat
h: of_nat n = of_nat mn = mreflexivity. Qed.n, m: nat
h: of_nat n = of_nat mto_nat (of_nat m) = to_nat (of_nat m)
Exercise: Church encodings (advanced)
It is possible to encode natural numbers (and other data types) using
so-called Church encodings that you might have seen in a λ-calculus class.
Below, num is the definition of Church numerals.
Definition num := forall (X : Prop) (s : X -> X) (z : X), X. Definition zero : num := fun X s z => z. Definition succ : num -> num := fun n X s z => s (n X s z). Fixpoint from_nat n : num := match n with | 0 => zero | S n => succ (from_nat n) end. Definition add : num -> num -> num := fun n m X s z => n X s (m X s z).forall n m : nat, add (from_nat n) (from_nat m) = from_nat (n + m)forall n m : nat, add (from_nat n) (from_nat m) = from_nat (n + m)n, m: natadd (from_nat n) (from_nat m) = from_nat (n + m)m: natadd (from_nat 0) (from_nat m) = from_nat (0 + m)n, m: nat
IH: add (from_nat n) (from_nat m) = from_nat (n + m)add (from_nat (S n)) (from_nat m) = from_nat (S n + m)reflexivity.m: natadd (from_nat 0) (from_nat m) = from_nat (0 + m)n, m: nat
IH: add (from_nat n) (from_nat m) = from_nat (n + m)add (from_nat (S n)) (from_nat m) = from_nat (S n + m)n, m: nat
IH: add (from_nat n) (from_nat m) = from_nat (n + m)add (succ (from_nat n)) (from_nat m) = succ (from_nat (n + m))reflexivity. Qed. Definition mul : num -> num -> num := fun n m X s z => n X (m X s) z.n, m: nat
IH: add (from_nat n) (from_nat m) = from_nat (n + m)add (succ (from_nat n)) (from_nat m) = succ (add (from_nat n) (from_nat m))forall n m : nat, mul (from_nat n) (from_nat m) = from_nat (n * m)forall n m : nat, mul (from_nat n) (from_nat m) = from_nat (n * m)n, m: natmul (from_nat n) (from_nat m) = from_nat (n * m)m: natmul (from_nat 0) (from_nat m) = from_nat (0 * m)n, m: nat
IH: mul (from_nat n) (from_nat m) = from_nat (n * m)mul (from_nat (S n)) (from_nat m) = from_nat (S n * m)reflexivity.m: natmul (from_nat 0) (from_nat m) = from_nat (0 * m)n, m: nat
IH: mul (from_nat n) (from_nat m) = from_nat (n * m)mul (from_nat (S n)) (from_nat m) = from_nat (S n * m)n, m: nat
IH: mul (from_nat n) (from_nat m) = from_nat (n * m)mul (succ (from_nat n)) (from_nat m) = from_nat (m + n * m)reflexivity. Qed.n, m: nat
IH: mul (from_nat n) (from_nat m) = from_nat (n * m)mul (succ (from_nat n)) (from_nat m) = add (from_nat m) (mul (from_nat n) (from_nat m))
Define the power function (check out the lemma to make sure you see what it should give).
Definition exp : num -> num -> num := fun n m X => m (X -> X) (n X).n, m: natexp (from_nat n) (from_nat m) = from_nat (n ^ m)n, m: natexp (from_nat n) (from_nat m) = from_nat (n ^ m)n: natexp (from_nat n) (from_nat 0) = from_nat (n ^ 0)n, m: nat
IH: exp (from_nat n) (from_nat m) = from_nat (n ^ m)exp (from_nat n) (from_nat (S m)) = from_nat (n ^ S m)reflexivity.n: natexp (from_nat n) (from_nat 0) = from_nat (n ^ 0)n, m: nat
IH: exp (from_nat n) (from_nat m) = from_nat (n ^ m)exp (from_nat n) (from_nat (S m)) = from_nat (n ^ S m)n, m: nat
IH: exp (from_nat n) (from_nat m) = from_nat (n ^ m)exp (from_nat n) (succ (from_nat m)) = from_nat (n * n ^ m)reflexivity. Qed.n, m: nat
IH: exp (from_nat n) (from_nat m) = from_nat (n ^ m)exp (from_nat n) (succ (from_nat m)) = mul (from_nat n) (exp (from_nat n) (from_nat m))
Define a predecessor function.
Definition pred : num -> num :=
fun n X s z => n ((X -> X) -> X) (fun g h => h (g s)) (fun _ => z) (fun x => x).Two functions that give the same results are not necessarily equal in Rocq, so we need the axiom of functional extensionality.
From Stdlib Require Import FunctionalExtensionality.n: nat
X: Prop
s: X -> X
z: Xfrom_nat n ((X -> X) -> X) (fun (g : (X -> X) -> X) (h : X -> X) => h (g s)) (fun _ : X -> X => z) s = from_nat n X s zn: nat
X: Prop
s: X -> X
z: Xfrom_nat n ((X -> X) -> X) (fun (g : (X -> X) -> X) (h : X -> X) => h (g s)) (fun _ : X -> X => z) s = from_nat n X s zX: Prop
s: X -> X
z: Xfrom_nat 0 ((X -> X) -> X) (fun (g : (X -> X) -> X) (h : X -> X) => h (g s)) (fun _ : X -> X => z) s = from_nat 0 X s zn: nat
X: Prop
s: X -> X
z: X
IH: from_nat n ((X -> X) -> X) (fun (g : (X -> X) -> X) (h : X -> X) => h (g s)) (fun _ : X -> X => z) s = from_nat n X s zfrom_nat (S n) ((X -> X) -> X) (fun (g : (X -> X) -> X) (h : X -> X) => h (g s)) (fun _ : X -> X => z) s = from_nat (S n) X s zreflexivity.X: Prop
s: X -> X
z: Xfrom_nat 0 ((X -> X) -> X) (fun (g : (X -> X) -> X) (h : X -> X) => h (g s)) (fun _ : X -> X => z) s = from_nat 0 X s zn: nat
X: Prop
s: X -> X
z: X
IH: from_nat n ((X -> X) -> X) (fun (g : (X -> X) -> X) (h : X -> X) => h (g s)) (fun _ : X -> X => z) s = from_nat n X s zfrom_nat (S n) ((X -> X) -> X) (fun (g : (X -> X) -> X) (h : X -> X) => h (g s)) (fun _ : X -> X => z) s = from_nat (S n) X s zn: nat
X: Prop
s: X -> X
z: X
IH: from_nat n ((X -> X) -> X) (fun (g : (X -> X) -> X) (h : X -> X) => h (g s)) (fun _ : X -> X => z) s = from_nat n X s zsucc (from_nat n) ((X -> X) -> X) (fun (g : (X -> X) -> X) (h : X -> X) => h (g s)) (fun _ : X -> X => z) s = succ (from_nat n) X s zn: nat
X: Prop
s: X -> X
z: X
IH: from_nat n ((X -> X) -> X) (fun (g : (X -> X) -> X) (h : X -> X) => h (g s)) (fun _ : X -> X => z) s = from_nat n X s zs (from_nat n ((X -> X) -> X) (fun (g : (X -> X) -> X) (h : X -> X) => h (g s)) (fun _ : X -> X => z) s) = s (from_nat n X s z)reflexivity. Qed.n: nat
X: Prop
s: X -> X
z: X
IH: from_nat n ((X -> X) -> X) (fun (g : (X -> X) -> X) (h : X -> X) => h (g s)) (fun _ : X -> X => z) s = from_nat n X s zs (from_nat n X s z) = s (from_nat n X s z)n: natpred (from_nat n) = from_nat (Nat.pred n)n: natpred (from_nat n) = from_nat (Nat.pred n)pred (from_nat 0) = from_nat (Nat.pred 0)n: natpred (from_nat (S n)) = from_nat (Nat.pred (S n))reflexivity.pred (from_nat 0) = from_nat (Nat.pred 0)n: natpred (from_nat (S n)) = from_nat (Nat.pred (S n))n: nat(fun (X : Prop) (s : X -> X) (z : X) => from_nat (S n) ((X -> X) -> X) (fun (g : (X -> X) -> X) (h : X -> X) => h (g s)) (fun _ : X -> X => z) (fun x : X => x)) = from_nat (Nat.pred (S n))n: nat(fun (X : Prop) (s : X -> X) (z : X) => succ (from_nat n) ((X -> X) -> X) (fun (g : (X -> X) -> X) (h : X -> X) => h (g s)) (fun _ : X -> X => z) (fun x : X => x)) = from_nat nn: nat
X: Prop(fun (s : X -> X) (z : X) => succ (from_nat n) ((X -> X) -> X) (fun (g : (X -> X) -> X) (h : X -> X) => h (g s)) (fun _ : X -> X => z) (fun x : X => x)) = from_nat n Xn: nat
X: Prop
s: X -> X(fun z : X => succ (from_nat n) ((X -> X) -> X) (fun (g : (X -> X) -> X) (h : X -> X) => h (g s)) (fun _ : X -> X => z) (fun x : X => x)) = from_nat n X sapply pred_aux. Qed.n: nat
X: Prop
s: X -> X
z: Xsucc (from_nat n) ((X -> X) -> X) (fun (g : (X -> X) -> X) (h : X -> X) => h (g s)) (fun _ : X -> X => z) (fun x : X => x) = from_nat n X s z