Exercise session 2 — Inductive types — Solutions

Authors:

Yannick Forster

Théo Winterhalter

Files:
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 A

l ++ [] = l
A: Type
l: list A

l ++ [] = l
A: Type

[] ++ [] = []
A: Type
a: A
l: list A
IHl: l ++ [] = l
(a :: l) ++ [] = a :: l
A: Type

[] = []
A: Type
a: A
l: list A
IHl: l ++ [] = l
a :: l ++ [] = a :: l
A: Type

[] = []
reflexivity.
A: Type
a: A
l: list A
IHl: l ++ [] = l

a :: l ++ [] = a :: l
A: Type
a: A
l: list A
IHl: l ++ [] = l

a :: l = a :: l
reflexivity. Qed.
A: Type
l1, l2, l3: list A

l1 ++ l2 ++ l3 = (l1 ++ l2) ++ l3
A: Type
l1, l2, l3: list A

l1 ++ l2 ++ l3 = (l1 ++ l2) ++ l3
A: Type
l2, l3: list A

[] ++ l2 ++ l3 = ([] ++ l2) ++ l3
A: Type
a: A
l1, l2, l3: list A
IHl: l1 ++ l2 ++ l3 = (l1 ++ l2) ++ l3
(a :: l1) ++ l2 ++ l3 = ((a :: l1) ++ l2) ++ l3
A: Type
l2, l3: list A

l2 ++ l3 = l2 ++ l3
A: Type
a: A
l1, l2, l3: list A
IHl: l1 ++ l2 ++ l3 = (l1 ++ l2) ++ l3
a :: l1 ++ l2 ++ l3 = a :: (l1 ++ l2) ++ l3
A: Type
l2, l3: list A

l2 ++ l3 = l2 ++ l3
reflexivity.
A: Type
a: A
l1, l2, l3: list A
IHl: l1 ++ l2 ++ l3 = (l1 ++ l2) ++ l3

a :: l1 ++ l2 ++ l3 = a :: (l1 ++ l2) ++ l3
A: Type
a: A
l1, l2, l3: list A
IHl: l1 ++ l2 ++ l3 = (l1 ++ l2) ++ l3

a :: (l1 ++ l2) ++ l3 = a :: (l1 ++ l2) ++ l3
reflexivity. Qed.

forall (A : Type) (l1 l2 : list A), rev (l1 ++ l2) = rev l2 ++ rev l1

forall (A : Type) (l1 l2 : list A), rev (l1 ++ l2) = rev l2 ++ rev l1
A: Type
l1, l2: list A

rev (l1 ++ l2) = rev l2 ++ rev l1
A: Type
l2: list A

rev ([] ++ l2) = rev l2 ++ rev []
A: Type
a: A
l1, l2: list A
IHl: rev (l1 ++ l2) = rev l2 ++ rev l1
rev ((a :: l1) ++ l2) = rev l2 ++ rev (a :: l1)
A: Type
l2: list A

rev l2 = rev l2 ++ []
A: Type
a: A
l1, l2: list A
IHl: rev (l1 ++ l2) = rev l2 ++ rev l1
rev (l1 ++ l2) ++ [a] = rev l2 ++ rev l1 ++ [a]
A: Type
l2: list A

rev l2 = rev l2 ++ []
A: Type
l2: list A

rev l2 = rev l2
reflexivity.
A: Type
a: A
l1, l2: list A
IHl: rev (l1 ++ l2) = rev l2 ++ rev l1

rev (l1 ++ l2) ++ [a] = rev l2 ++ rev l1 ++ [a]
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]
reflexivity. Qed.
X: Type
l: list X

rev (rev l) = l
X: Type
l: list X

rev (rev l) = l
X: Type

rev (rev []) = []
X: Type
a: X
l: list X
IHl: rev (rev l) = l
rev (rev (a :: l)) = a :: l
X: Type

[] = []
X: Type
a: X
l: list X
IHl: rev (rev l) = l
rev (rev l ++ [a]) = a :: l
X: Type

[] = []
reflexivity.
X: Type
a: X
l: list X
IHl: rev (rev l) = l

rev (rev l ++ [a]) = a :: l
X: Type
a: X
l: list X
IHl: rev (rev l) = l

rev [a] ++ l = a :: l
reflexivity. Qed.

forall (A : Type) (l : list A), fast_rev l [] = rev l

forall (A : Type) (l : list A), fast_rev l [] = rev l
A: Type
l: list A

fast_rev l [] = rev l
A: Type
l: list A

forall acc : list A, fast_rev l acc = rev l ++ acc
A: Type
l: list A
H: forall acc : list A, fast_rev l acc = rev l ++ acc
fast_rev l [] = rev l
A: Type
l: list A

forall acc : list A, fast_rev l acc = rev l ++ acc
A: Type

forall acc : list A, fast_rev [] acc = rev [] ++ acc
A: Type
a: A
l: list A
IHl: forall acc : list A, fast_rev l acc = rev l ++ acc
forall acc : list A, fast_rev (a :: l) acc = rev (a :: l) ++ acc
A: Type

forall acc : list A, acc = acc
A: Type
a: A
l: list A
IHl: forall acc : list A, fast_rev l acc = rev l ++ acc
forall acc : list A, fast_rev l (a :: acc) = (rev l ++ [a]) ++ acc
A: Type
acc: list A

acc = acc
A: Type
a: A
l: list A
IHl: forall acc : list A, fast_rev l acc = rev l ++ acc
acc: list A
fast_rev l (a :: acc) = (rev l ++ [a]) ++ acc
A: Type
acc: list A

acc = acc
reflexivity.
A: Type
a: A
l: list A
IHl: forall acc : list A, fast_rev l acc = rev l ++ acc
acc: list A

fast_rev l (a :: acc) = (rev l ++ [a]) ++ acc
A: Type
a: A
l: list A
IHl: forall acc : list A, fast_rev l acc = rev l ++ acc
acc: list A

rev l ++ a :: acc = rev l ++ [a] ++ acc
reflexivity.
A: Type
l: list A
H: forall acc : list A, fast_rev l acc = rev l ++ acc

fast_rev l [] = rev l
A: Type
l: list A
H: forall acc : list A, fast_rev l acc = rev l ++ acc

rev l = rev l
reflexivity. 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.

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: nat

Nat.pow x n = iter (Nat.mul x) n 1
n, x: nat

Nat.pow x n = iter (Nat.mul x) n 1
x: nat

Nat.pow x 0 = iter (Nat.mul x) 0 1
n, x: nat
IH: Nat.pow x n = iter (Nat.mul x) n 1
Nat.pow x (S n) = iter (Nat.mul x) (S n) 1
x: nat

1 = 1
n, x: nat
IH: Nat.pow x n = iter (Nat.mul x) n 1
x * Nat.pow x n = x * iter (Nat.mul x) n 1
x: nat

1 = 1
reflexivity.
n, x: nat
IH: Nat.pow x n = iter (Nat.mul x) n 1

x * Nat.pow x n = x * iter (Nat.mul x) n 1
n, x: nat
IH: Nat.pow x n = iter (Nat.mul x) n 1

x * iter (Nat.mul x) n 1 = x * iter (Nat.mul x) n 1
reflexivity. Qed.
A: Type
f: A -> A
n: nat
x: A

iter f (S n) x = iter f n (f x)
A: Type
f: A -> A
n: nat
x: A

iter f (S n) x = iter f n (f x)
A: Type
f: A -> A
x: A

iter 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
x: A

iter f 1 x = iter f 0 (f x)
reflexivity.
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))
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))
reflexivity. Qed.

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: A

iter f n x = iter_tail f n x
A: Type
f: A -> A
n: nat
x: A

iter f n x = iter_tail f n x
A: Type
f: A -> A
n: nat

forall x : A, iter f n x = iter_tail f n x
A: Type
f: A -> A

forall x : A, iter f 0 x = iter_tail f 0 x
A: Type
f: A -> A
n: nat
IH: forall x : A, iter f n x = iter_tail f n x
forall x : A, iter f (S n) x = iter_tail f (S n) x
A: Type
f: A -> A
x: A

iter f 0 x = iter_tail f 0 x
A: Type
f: A -> A
n: nat
IH: forall x : A, iter f n x = iter_tail f n x
x: A
iter f (S n) x = iter_tail f (S n) x
A: Type
f: A -> A
x: A

iter f 0 x = iter_tail f 0 x
reflexivity.
A: Type
f: A -> A
n: nat
IH: forall x : A, iter f n x = iter_tail f n x
x: A

iter f (S n) x = iter_tail f (S n) x
A: Type
f: A -> A
n: nat
IH: forall x : A, iter f n x = iter_tail f n x
x: A

f (iter f n x) = iter_tail f n (f x)
A: Type
f: A -> A
n: nat
IH: forall x : A, iter f n x = iter_tail f n x
x: A

f (iter f n x) = iter f n (f x)
apply iter_shift. Qed. (* From the lecture: *)
tree, forest are defined
tree_ind', forest_ind' are recursively defined
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 n

forall P : nat -> Prop, (forall n : nat, (forall m : nat, m < n -> P m) -> P n) -> forall n : nat, P n
P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat

P 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: nat

forall m : nat, m <= n -> P m
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 m
P n
P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat

forall m : nat, m <= n -> P m
P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n

forall m : nat, m <= 0 -> P m
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
forall m : nat, m <= S n -> P m
P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n

forall m : nat, m <= 0 -> P m
P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
m: nat
hm: m <= 0

P m
P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
m: nat
hm: m <= 0
H: m = 0

P 0
P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
m: nat
hm: m <= 0
H: m = 0

forall m0 : nat, m0 < 0 -> P m0
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 < 0

P k
lia.

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 m

forall m : nat, m <= S n -> P m
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

P m
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

P (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 = n
P m
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

P (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 n

forall m0 : nat, m0 < S n -> P m0
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 n

P k
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 n

k <= n
lia.
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 = n

P m
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 = n

m <= n
lia.
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 m

P n
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 m

n <= n
lia. Qed.

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 n

forall P : nat -> Prop, (forall n : nat, (forall m : nat, m < n -> P m) -> P n) -> forall n : nat, P n
P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat

P n
P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat

forall m : nat, m <= n -> P m
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 m
P n
P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
n: nat

forall m : nat, m <= n -> P m
P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n

forall m : nat, m <= 0 -> P m
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
forall m : nat, m <= S n -> P m
P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n

forall m : nat, m <= 0 -> P m
P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
m: nat
hm: m <= 0

P m
P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
m: nat
hm: m <= 0
H: m = 0

P 0
P: nat -> Prop
h: forall n : nat, (forall m : nat, m < n -> P m) -> P n
m: nat
hm: m <= 0
H: m = 0

forall m0 : nat, m0 < 0 -> P m0
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 < 0

P k
lia.
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

forall m : nat, m <= S n -> P m
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

P m
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

P (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 = n
P m
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

P (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 n

forall m0 : nat, m0 < S n -> P m0
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 n

P k
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 n

k <= n
lia.
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 = n

P m
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 = n

m <= n
lia.
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 m

P n
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 m

n <= n
lia. Qed. End StrongInd.

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: nat

even1 n -> even2 n = true
n: nat

even1 n -> even2 n = true
n, m: nat
e: n = 2 * m

even2 n = true
m: nat

even2 (2 * m) = true

even2 (2 * 0) = true
m: nat
IH: even2 (2 * m) = true
even2 (2 * S m) = true

even2 (2 * 0) = true
reflexivity.
m: nat
IH: even2 (2 * m) = true

even2 (2 * S m) = true
m: nat
IH: even2 (2 * m) = true

even2 (S (S (2 * m))) = true
m: nat
IH: even2 (2 * m) = true

even2 (m + (m + 0)) = true
assumption. Qed.
n: nat

even2 n = true <-> even3 n
n: nat

even2 n = true <-> even3 n
n: nat
IH: forall m : nat, m < n -> even2 m = true <-> even3 m

even2 n = true <-> even3 n
IH: forall m : nat, m < 0 -> even2 m = true <-> even3 m

even2 0 = true <-> even3 0
IH: forall m : nat, m < 1 -> even2 m = true <-> even3 m
even2 1 = true <-> even3 1
n: nat
IH: forall m : nat, m < S (S n) -> even2 m = true <-> even3 m
even2 (S (S n)) = true <-> even3 (S (S n))
IH: forall m : nat, m < 0 -> even2 m = true <-> even3 m

true = true <-> True
IH: forall m : nat, m < 1 -> even2 m = true <-> even3 m
false = true <-> False
n: nat
IH: forall m : nat, m < S (S n) -> even2 m = true <-> even3 m
even2 n = true <-> even3 n
IH: forall m : nat, m < 0 -> even2 m = true <-> even3 m

true = true <-> True
IH: forall m : nat, m < 0 -> even2 m = true <-> even3 m

true = true -> True
IH: forall m : nat, m < 0 -> even2 m = true <-> even3 m
True -> true = true
IH: forall m : nat, m < 0 -> even2 m = true <-> even3 m

true = true -> True
IH: forall m : nat, m < 0 -> even2 m = true <-> even3 m

True
exact I.
IH: forall m : nat, m < 0 -> even2 m = true <-> even3 m

True -> true = true
IH: forall m : nat, m < 0 -> even2 m = true <-> even3 m

true = true
reflexivity.
IH: forall m : nat, m < 1 -> even2 m = true <-> even3 m

false = true <-> False
IH: forall m : nat, m < 1 -> even2 m = true <-> even3 m

false = true -> False
IH: forall m : nat, m < 1 -> even2 m = true <-> even3 m
False -> false = true
IH: forall m : nat, m < 1 -> even2 m = true <-> even3 m

false = true -> False
IH: forall m : nat, m < 1 -> even2 m = true <-> even3 m
h: false = true

False
discriminate.
IH: forall m : nat, m < 1 -> even2 m = true <-> even3 m

False -> false = true
IH: forall m : nat, m < 1 -> even2 m = true <-> even3 m
h: False

false = true
contradiction.
n: nat
IH: forall m : nat, m < S (S n) -> even2 m = true <-> even3 m

even2 n = true <-> even3 n
n: nat
IH: forall m : nat, m < S (S n) -> even2 m = true <-> even3 m

n < S (S n)
lia. Qed.
n: nat

even3 n -> even4 n
n: nat

even3 n -> even4 n
n: nat
IH: forall m : nat, m < n -> even3 m -> even4 m

even3 n -> even4 n
IH: forall m : nat, m < 0 -> even3 m -> even4 m

even3 0 -> even4 0
IH: forall m : nat, m < 1 -> even3 m -> even4 m
even3 1 -> even4 1
n: nat
IH: forall m : nat, m < S (S n) -> even3 m -> even4 m
even3 (S (S n)) -> even4 (S (S n))
IH: forall m : nat, m < 0 -> even3 m -> even4 m

True -> even4 0
IH: forall m : nat, m < 1 -> even3 m -> even4 m
False -> even4 1
n: nat
IH: forall m : nat, m < S (S n) -> even3 m -> even4 m
even3 n -> even4 (S (S n))
IH: forall m : nat, m < 0 -> even3 m -> even4 m
h: True

even4 0
IH: forall m : nat, m < 1 -> even3 m -> even4 m
h: False
even4 1
n: nat
IH: forall m : nat, m < S (S n) -> even3 m -> even4 m
h: even3 n
even4 (S (S n))
IH: forall m : nat, m < 0 -> even3 m -> even4 m
h: True

even4 0
constructor.
IH: forall m : nat, m < 1 -> even3 m -> even4 m
h: False

even4 1
contradiction.
n: nat
IH: forall m : nat, m < S (S n) -> even3 m -> even4 m
h: even3 n

even4 (S (S n))
n: nat
IH: forall m : nat, m < S (S n) -> even3 m -> even4 m
h: even3 n

even4 n
n: nat
IH: forall m : nat, m < S (S n) -> even3 m -> even4 m
h: even3 n

n < S (S n)
n: nat
IH: forall m : nat, m < S (S n) -> even3 m -> even4 m
h: even3 n
even3 n
n: nat
IH: forall m : nat, m < S (S n) -> even3 m -> even4 m
h: even3 n

n < S (S n)
lia.
n: nat
IH: forall m : nat, m < S (S n) -> even3 m -> even4 m
h: even3 n

even3 n
assumption. Qed.
n: nat

even4 n -> even1 n
n: nat

even4 n -> even1 n
n: nat
h: even4 n

even1 n

even1 0
n: nat
h: even4 n
m: nat
e: n = 2 * m
even1 (S (S n))

even1 0

0 = 2 * 0
reflexivity.
n: nat
h: even4 n
m: nat
e: n = 2 * m

even1 (S (S n))
n: nat
h: even4 n
m: nat
e: n = 2 * m

S (S n) = 2 * S m
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).

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: nat

le 0 n
n: nat

le 0 n

le 0 0
n: nat
IH: le 0 n
le 0 (S n)

le 0 0
constructor.
n: nat
IH: le 0 n

le 0 (S n)
n: nat
IH: le 0 n

le 0 n
assumption. Qed.
n, m: nat

le n m -> le (S n) (S m)
n, m: nat

le n m -> le (S n) (S m)
n, m: nat
h: le n m

le (S n) (S m)
n: nat

le (S n) (S n)
n, m: nat
h: le n m
IH: le (S n) (S m)
le (S n) (S (S m))
n: nat

le (S n) (S n)
constructor.
n, m: nat
h: le n m
IH: le (S n) (S m)

le (S n) (S (S m))
n, m: nat
h: le n m
IH: le (S n) (S m)

le (S n) (S m)
assumption. Qed.
n: nat

le' n n
n: nat

le' n n

le' 0 0
n: nat
IH: le' n n
le' (S n) (S n)

le' 0 0
constructor.
n: nat
IH: le' n n

le' (S n) (S n)
n: nat
IH: le' n n

le' n n
assumption. Qed.
n, m: nat

le' n m -> le' n (S m)
n, m: nat

le' n m -> le' n (S m)
n, m: nat
h: le' n m

le' n (S m)
n: nat

le' 0 (S n)
n, m: nat
h: le' n m
IH: le' n (S m)
le' (S n) (S (S m))
n: nat

le' 0 (S n)
constructor.
n, m: nat
h: le' n m
IH: le' n (S m)

le' (S n) (S (S m))
n, m: nat
h: le' n m
IH: le' n (S m)

le' n (S m)
assumption. Qed.
n, m: nat

le' n m <-> le n m
n, m: nat

le' n m <-> le n m
n, m: nat

le' n m -> le n m
n, m: nat
le n m -> le' n m
n, m: nat

le' n m -> le n m
n, m: nat
h: le' n m

le n m
n: nat

le 0 n
n, m: nat
h: le' n m
IH: le n m
le (S n) (S m)
n: nat

le 0 n
apply le_0_n.
n, m: nat
h: le' n m
IH: le n m

le (S n) (S m)
n, m: nat
h: le' n m
IH: le n m

le n m
assumption.
n, m: nat

le n m -> le' n m
n, m: nat
h: le n m

le' n m
n: nat

le' n n
n, m: nat
h: le n m
IH: le' n m
le' n (S m)
n: nat

le' n n
apply le'_refl.
n, m: nat
h: le n m
IH: le' n m

le' n (S m)
n, m: nat
h: le n m
IH: le' n m

le' n m
assumption. Qed.

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: nat

leb n m = true <-> le' n m
n, m: nat

leb n m = true <-> le' n m
n: nat

forall m : nat, leb n m = true <-> le' n m

forall m : nat, leb 0 m = true <-> le' 0 m
n: nat
IH: forall m : nat, leb n m = true <-> le' n m
forall m : nat, leb (S n) m = true <-> le' (S n) m
m: nat

leb 0 m = true <-> le' 0 m
n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: nat
leb (S n) m = true <-> le' (S n) m
m: nat

leb 0 m = true <-> le' 0 m
m: nat

leb 0 m = true -> le' 0 m
m: nat
le' 0 m -> leb 0 m = true
m: nat

leb 0 m = true -> le' 0 m
m: nat

le' 0 m
constructor.
m: nat

le' 0 m -> leb 0 m = true
m: nat

leb 0 m = true
reflexivity.
n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: nat

leb (S n) m = true <-> le' (S n) m
n: nat
IH: forall m : nat, leb n m = true <-> le' n m

leb (S n) 0 = true <-> le' (S n) 0
n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: nat
leb (S n) (S m) = true <-> le' (S n) (S m)
n: nat
IH: forall m : nat, leb n m = true <-> le' n m

leb (S n) 0 = true <-> le' (S n) 0
n: nat
IH: forall m : nat, leb n m = true <-> le' n m

leb (S n) 0 = true -> le' (S n) 0
n: nat
IH: forall m : nat, leb n m = true <-> le' n m
le' (S n) 0 -> leb (S n) 0 = true
n: nat
IH: forall m : nat, leb n m = true <-> le' n m

leb (S n) 0 = true -> le' (S n) 0
n: nat
IH: forall m : nat, leb n m = true <-> le' n m
h: leb (S n) 0 = true

le' (S n) 0
discriminate.
n: nat
IH: forall m : nat, leb n m = true <-> le' n m

le' (S n) 0 -> leb (S n) 0 = true
n: nat
IH: forall m : nat, leb n m = true <-> le' n m
h: le' (S n) 0

leb (S n) 0 = true
inversion h.
n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: nat

leb (S n) (S m) = true <-> le' (S n) (S m)
n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: nat

leb n m = true <-> le' (S n) (S m)
n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: nat

le' n m <-> le' (S n) (S m)
n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: nat

le' n m -> le' (S n) (S m)
n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: nat
le' (S n) (S m) -> le' n m
n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: nat

le' 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 m

le' (S n) (S m)
n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: nat
h: le' n m

le' n m
assumption.
n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: nat

le' (S n) (S m) -> le' n m
n: nat
IH: forall m : nat, leb n m = true <-> le' n m
m: nat
h: le' (S n) (S m)

le' n m
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 = m

le' n m
assumption. Qed.
n, m: nat

leb n m = true <-> le n m
n, m: nat

leb n m = true <-> le n m
n, m: nat

le' n m <-> le n m
apply le_equiv. Qed. (* From the lecture: *) From Stdlib Require Import Lia List.
rtree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
rtree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
rtree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
rtree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
rtree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
rtree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
rtree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
rtree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
rtree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
rtree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
rtree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
rtree is nested using list. No scheme for list is registered as All. It can be generated using command "Scheme All" e.g. "Scheme All for list.". [register-all,automation,default]
Inductive 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 r

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
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

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
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)
r: rtree A

P r
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)

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 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

Forall 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 ts
Forall 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

Forall P []
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: A
a0: rtree A
ts: list (rtree A)
IHts: Forall P ts

Forall 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 ts

P a0
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 ts
Forall P 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 ts

P a0
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 ts

forall (a1 : A) (ts0 : list (rtree A)), Forall P ts0 -> P (N A a1 ts0)
assumption.
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 ts

Forall P ts
assumption. Qed. Scheme All for list.

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.

All_ind : forall (X : Type) (P : X -> Type) (P0 : forall l : list X, All P l -> Prop), P0 [] All_nil -> (forall (x : X) (l : list X) (p : P x) (a : All P l), P0 l a -> P0 (x :: l) (All_cons x l p a)) -> forall (l : list X) (a : All P l), P0 l a
Forall_ind : forall (A : Type) (P : A -> Prop) (P0 : list A -> Prop), P0 [] -> (forall (a : A) (l : list A), P a -> Forall P l -> P0 l -> P0 (a :: l)) -> forall l : list A, Forall P l -> P0 l

Prove the following.

A: Type
P: A -> Prop
l: list A

All P l -> Forall P l
A: Type
P: A -> Prop
l: list A

All P l -> Forall P l
A: Type
P: A -> Prop
l: list A
h: All P l

Forall P l
A: Type
P: A -> Prop

Forall P []
A: Type
P: A -> Prop
x: A
l: list A
px: P x
h: All P l
IH: Forall P l
Forall P (x :: l)
A: Type
P: A -> Prop

Forall P []
constructor.
A: Type
P: A -> Prop
x: A
l: list A
px: P x
h: All P l
IH: Forall P l

Forall P (x :: l)
A: Type
P: A -> Prop
x: A
l: list A
px: P x
h: All P l
IH: Forall P l

P x
A: Type
P: A -> Prop
x: A
l: list A
px: P x
h: All P l
IH: Forall P l
Forall P l
A: Type
P: A -> Prop
x: A
l: list A
px: P x
h: All P l
IH: Forall P l

P x
assumption.
A: Type
P: A -> Prop
x: A
l: list A
px: P x
h: All P l
IH: Forall P l

Forall P l
assumption. Qed.
A: Type
P: A -> Prop
l1, l2: list A

Forall P l1 -> Forall P l2 -> Forall P (l1 ++ l2)
A: Type
P: A -> Prop
l1, l2: list A

Forall 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 l2

Forall P (l1 ++ l2)
A: Type
P: A -> Prop
l2: list A
h2: Forall P l2

Forall 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 l2

Forall 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 l2

Forall P 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)

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 a
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)
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 a
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)

Forall P (l ++ l2)
assumption. 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.

Exercise: Labelled trees

  • Extend the type Unlabelled.tree to have labelled nodes.

  • Prove a bijection between the new type and the mutual tree from 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.

to_rtree, to_rtree_forest are recursively defined (guarded respectively on 2nd, 2nd arguments)
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 A

from_rtree (to_rtree t) = t
A: Type
t: tree A

from_rtree (to_rtree t) = t
A: Type
t: tree A

forall (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 f
A: Type
t: tree A
forall a : A, from_rtree (N A a (to_rtree_forest (nnil A))) = nnode A a (nnil A)
A: Type
t: tree A
forall 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 A

forall (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 f
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 f

from_rtree (to_rtree (nnode A a f)) = nnode A a f
exact (IH a).
A: Type
t: tree A

forall a : A, from_rtree (N A a (to_rtree_forest (nnil A))) = nnode A a (nnil A)
A: Type
t: tree A
a: A

from_rtree (N A a (to_rtree_forest (nnil A))) = nnode A a (nnil A)
reflexivity.
A: Type
t: tree A

forall 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: A

from_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 f

from_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 f

nnode 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) = f

nnode 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) = f

nnode A a (ncons A t' f) = nnode A a (ncons A t' f)
reflexivity. Qed.
A: Type
t: rtree A

to_rtree (from_rtree t) = t
A: Type
t: rtree A

to_rtree (from_rtree t) = t
A: Type

forall t : rtree A, to_rtree (from_rtree t) = t
A: Type

forall (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 ts
A: Type
a: A
ts: list (rtree A)
IH: Forall (fun r : rtree A => to_rtree (from_rtree r) = r) ts

to_rtree (from_rtree (N A a ts)) = N A a ts
A: Type
a: A
ts: list (rtree A)
IH: Forall (fun r : rtree A => to_rtree (from_rtree r) = r) ts

N 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 ts
A: Type
a: A
ts: list (rtree A)
IH: Forall (fun r : rtree A => to_rtree (from_rtree r) = r) ts

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) = ts
A: Type
a: A

to_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) = ts
to_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 :: ts
A: Type
a: A

to_rtree_forest (nnil A) = []
reflexivity.
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) = ts

to_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 :: ts
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) = ts

to_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 :: ts
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) = ts

t :: ts = t :: ts
reflexivity. 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}.

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 A

In x l <-> In_i x l
A: Type
x: A
l: list A

In x l <-> In_i x l
A: Type
x: A
l: list A

In x l -> In_i x l
A: Type
x: A
l: list A
In_i x l -> In x l
A: Type
x: A
l: list A

In x l -> In_i x l
A: Type
x: A

In x [] -> In_i x []
A: Type
x, y: A
l: list A
IH: In x l -> In_i x l
In x (y :: l) -> In_i x (y :: l)
A: Type
x: A

False -> In_i x []
A: Type
x, y: A
l: list A
IH: In x l -> In_i x l
y = x \/ In x l -> In_i x (y :: l)
A: Type
x: A
h: False

In_i x []
A: Type
x, y: A
l: list A
IH: In x l -> In_i x l
h: y = x \/ In x l
In_i x (y :: l)
A: Type
x: A
h: False

In_i x []
contradiction.
A: Type
x, y: A
l: list A
IH: In x l -> In_i x l
h: y = x \/ In x l

In_i x (y :: l)
A: Type
x, y: A
l: list A
IH: In x l -> In_i x l
e: y = x

In_i x (y :: l)
A: Type
x, y: A
l: list A
IH: In x l -> In_i x l
h: In x l
In_i x (y :: l)
A: Type
x, y: A
l: list A
IH: In x l -> In_i x l
e: y = x

In_i x (y :: l)
A: Type
x: A
l: list A
IH: In x l -> In_i x l

In_i x (x :: l)
apply In_here.
A: Type
x, y: A
l: list A
IH: In x l -> In_i x l
h: In x l

In_i x (y :: l)
A: Type
x, y: A
l: list A
IH: In x l -> In_i x l
h: In x l

In_i x l
A: Type
x, y: A
l: list A
IH: In x l -> In_i x l
h: In x l

In x l
assumption.
A: Type
x: A
l: list A

In_i x l -> In x l
A: Type
x: A
l: list A
h: In_i x l

In x l
A: Type
x: A
l: list A

In x (x :: l)
A: Type
x, y: A
l: list A
h: In_i x l
IH: In x l
In x (y :: l)
A: Type
x: A
l: list A

x = x \/ In x l
A: Type
x, y: A
l: list A
h: In_i x l
IH: In x l
y = x \/ In x l
A: Type
x: A
l: list A

x = x \/ In x l
A: Type
x: A
l: list A

x = x
reflexivity.
A: Type
x, y: A
l: list A
h: In_i x l
IH: In x l

y = x \/ In x l
A: Type
x, y: A
l: list A
h: In_i x l
IH: In x l

In x l
assumption. Qed.

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 z

forall (A : Type) (R : A -> A -> Prop) (x y z : A), rtclos' R x y -> rtclos' R y z -> rtclos' R x z
A: Type
R: A -> A -> Prop
x, y, z: A
h1: rtclos' R x y
h2: rtclos' R y z

rtclos' R x z
A: Type
R: A -> A -> Prop
z, x: A
h2: rtclos' R x z

rtclos' R x z
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 z
rtclos' R x z
A: Type
R: A -> A -> Prop
z, x: A
h2: rtclos' R x z

rtclos' R x z
assumption.
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 z

rtclos' R x z
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 z

R x w
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 z
rtclos' R w z
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 z

R x w
assumption.
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 z

rtclos' R w z
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 z

rtclos' R y z
assumption. Qed.

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

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

rtclos R x y <-> rtclos' R x y
A: Type
R: A -> A -> Prop
x, y: A

rtclos R x y -> rtclos' R x y
A: Type
R: A -> A -> Prop
x, y: A
rtclos' R x y -> rtclos R x y
A: Type
R: A -> A -> Prop
x, y: A

rtclos R x y -> rtclos' R x y
A: Type
R: A -> A -> Prop
x, y: A
h: rtclos R x y

rtclos' R x y
A: Type
R: A -> A -> Prop
x: A

rtclos' R x x
A: Type
R: A -> A -> Prop
x, y: A
r: R x y
rtclos' R x y
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 z
rtclos' R x z
A: Type
R: A -> A -> Prop
x: A

rtclos' R x x
apply refl'.
A: Type
R: A -> A -> Prop
x, y: A
r: R x y

rtclos' R x y
A: Type
R: A -> A -> Prop
x, y: A
r: R x y

R x y
A: Type
R: A -> A -> Prop
x, y: A
r: R x y
rtclos' R y y
A: Type
R: A -> A -> Prop
x, y: A
r: R x y

R x y
assumption.
A: Type
R: A -> A -> Prop
x, y: A
r: R x y

rtclos' R y y
apply refl'.
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 z

rtclos' R x z
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 z

rtclos' R x y
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 z
rtclos' R y z
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 z

rtclos' R x y
assumption.
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 z

rtclos' R y z
assumption.
A: Type
R: A -> A -> Prop
x, y: A

rtclos' R x y -> rtclos R x y
A: Type
R: A -> A -> Prop
x, y: A
h: rtclos' R x y

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

rtclos R x x
A: Type
R: A -> A -> Prop
x, w, y: A
r: R x w
h: rtclos' R w y
IH: rtclos R w y
rtclos R x y
A: Type
R: A -> A -> Prop
x: A

rtclos R x x
apply refl.
A: Type
R: A -> A -> Prop
x, w, y: A
r: R x w
h: rtclos' R w y
IH: rtclos R w y

rtclos R x y
A: Type
R: A -> A -> Prop
x, w, y: A
r: R x w
h: rtclos' R w y
IH: rtclos R w y

rtclos R x w
A: Type
R: A -> A -> Prop
x, w, y: A
r: R x w
h: rtclos' R w y
IH: rtclos R w y
rtclos R w y
A: Type
R: A -> A -> Prop
x, w, y: A
r: R x w
h: rtclos' R w y
IH: rtclos R w y

rtclos R x w
A: Type
R: A -> A -> Prop
x, w, y: A
r: R x w
h: rtclos' R w y
IH: rtclos R w y

R x w
assumption.
A: Type
R: A -> A -> Prop
x, w, y: A
r: R x w
h: rtclos' R w y
IH: rtclos R w y

rtclos R w y
assumption. Qed.

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 Fixpoint

  • and 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: nat

fact_iter n = fact n
n: nat

fact_iter n = fact n
n: nat

snd (iter (fun '(k, r) => (S k, S k * r)) n (0, 1)) = fact n
n: nat

iter (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 n
n: nat

iter (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))

iter (fun '(k, r) => (S k, S k * r)) 0 (0, 1) = (0, fact 0)
reflexivity.
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))
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))
reflexivity.
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 n
n: nat
h: iter (fun '(k, r) => (S k, S k * r)) n (0, 1) = (n, fact n)

snd (n, fact n) = fact n
reflexivity. Qed.

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 = 0

fib 0 = 0
reflexivity. Qed.

fib 1 = 1

fib 1 = 1
reflexivity. Qed.

forall n : nat, fib (S (S n)) = fib n + fib (S n)

forall n : nat, fib (S (S n)) = fib n + fib (S n)
n: nat

fib (S (S n)) = fib n + fib (S n)
n: nat

fst (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: nat

fst (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))
n, a, b: nat

fst (a + b, b + (a + b)) = fst (a, b) + fst (b, a + b)
reflexivity. Qed. End Fib_Iter.

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) = p

forall p : nat * nat, of_nat (to_nat p) = p

forall (n : nat) (p : nat * nat), to_nat p = n -> of_nat n = p
H: forall (n : nat) (p : nat * nat), to_nat p = n -> of_nat n = p
forall p : nat * nat, of_nat (to_nat p) = p

forall (n : nat) (p : nat * nat), to_nat p = n -> of_nat n = p

forall p : nat * nat, to_nat p = 0 -> of_nat 0 = p
n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
forall p : nat * nat, to_nat p = S n -> of_nat (S n) = p
x, y: nat
h: to_nat (x, y) = 0

of_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 n
of_nat (S n) = (x, y)
x, y: nat
h: to_nat (x, y) = 0

of_nat 0 = (x, y)
h: to_nat (0, 0) = 0

of_nat 0 = (0, 0)
y: nat
h: to_nat (0, S y) = 0
of_nat 0 = (0, S y)
x: nat
h: to_nat (S x, 0) = 0
of_nat 0 = (S x, 0)
x, y: nat
h: to_nat (S x, S y) = 0
of_nat 0 = (S x, S y)
h: 0 = 0

of_nat 0 = (0, 0)
y: nat
h: S (y + S (y + 0 + to_nat' (y + 0))) = 0
of_nat 0 = (0, S y)
x: nat
h: S (x + to_nat' x) = 0
of_nat 0 = (S x, 0)
x, y: nat
h: S (y + S (y + S x + to_nat' (y + S x))) = 0
of_nat 0 = (S x, S y)
h: 0 = 0

of_nat 0 = (0, 0)
reflexivity.
n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x, y: nat
h: to_nat (x, y) = S n

of_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 n

of_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 n
of_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 n

of_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 n

of_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 n
of_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 n

of_nat (S n) = (0, 0)
n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
h: 0 = S n

of_nat (S n) = (0, 0)
discriminate.
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

of_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

to_nat (0, x) = n
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
of_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

to_nat (0, x) = n
n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x: nat
h: S (x + to_nat' x) = S n

x + to_nat' (x + 0) = n
n: nat
IH: forall p : nat * nat, to_nat p = n -> of_nat n = p
x: nat
h: S (x + to_nat' x) = S n

x + to_nat' x = n
lia.
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

of_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) = n

match of_nat n with | (0, y) => (S y, 0) | (S x1, y) => (x1, S y) end = (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) = n

(S x, 0) = (S x, 0)
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

of_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

to_nat (S x, y) = n
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
of_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

to_nat (S x, y) = n
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 n

y + to_nat' (y + S x) = n
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 n

y + to_nat' (S (y + x)) = n
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 n

y + S (y + x + to_nat' (y + x)) = n
lia.
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

of_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) = n

match of_nat n with | (0, y0) => (S y0, 0) | (S x1, y0) => (x1, S y0) end = (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) = n

(x, S y) = (x, S y)
reflexivity.
H: forall (n : nat) (p : nat * nat), to_nat p = n -> of_nat n = p

forall p : nat * nat, of_nat (to_nat p) = p
H: forall (n : nat) (p : nat * nat), to_nat p = n -> of_nat n = p
p: nat * nat

of_nat (to_nat p) = p
H: forall (n : nat) (p : nat * nat), to_nat p = n -> of_nat n = p
p: nat * nat

to_nat p = to_nat p
reflexivity. Qed.

Show to_nat is injective.


forall p q : nat * nat, to_nat p = to_nat q -> p = q

forall p q : nat * nat, to_nat p = to_nat q -> p = q
p, q: nat * nat
h: to_nat p = to_nat q

p = q
p, q: nat * nat
h: to_nat p = to_nat q

of_nat (to_nat q) = of_nat (to_nat q)
reflexivity. Qed.

Show to_nat is a left inverse for of_nat.


forall n : nat, to_nat (of_nat n) = n

forall n : nat, to_nat (of_nat n) = n

to_nat (of_nat 0) = 0
n: nat
IH: to_nat (of_nat n) = n
to_nat (of_nat (S n)) = S n

to_nat (of_nat 0) = 0
reflexivity.
n: nat
IH: to_nat (of_nat n) = n

to_nat (of_nat (S n)) = S n
n: nat
IH: to_nat (of_nat n) = n

to_nat match of_nat n with | (0, y) => (S y, 0) | (S x0, y) => (x0, S y) end = S n
n, x, y: nat
e: of_nat n = (x, y)
IH: to_nat (x, y) = n

to_nat match x with | 0 => (S y, 0) | S x0 => (x0, S y) end = S n
n, y: nat
e: of_nat n = (0, y)
IH: to_nat (0, y) = n

to_nat (S y, 0) = S n
n, x, y: nat
e: of_nat n = (S x, y)
IH: to_nat (S x, y) = n
to_nat (x, S y) = S n
n, y: nat
e: of_nat n = (0, y)
IH: to_nat (0, y) = n

to_nat (S y, 0) = S n
n, y: nat
e: of_nat n = (0, y)
IH: y + to_nat' (y + 0) = n

S (y + to_nat' y) = S n
n, y: nat
e: of_nat n = (0, y)
IH: y + to_nat' y = n

S (y + to_nat' y) = S n
lia.
n, x, y: nat
e: of_nat n = (S x, y)
IH: to_nat (S x, y) = n

to_nat (x, S y) = S n
n, x, y: nat
e: of_nat n = (S x, y)
IH: y + to_nat' (y + S x) = n

S (y + S (y + x + to_nat' (y + x))) = S n
n, x, y: nat
e: of_nat n = (S x, y)
IH: y + to_nat' (S (y + x)) = n

S (y + S (y + x + to_nat' (y + x))) = S n
n, x, y: nat
e: of_nat n = (S x, y)
IH: y + S (y + x + to_nat' (y + x)) = n

S (y + S (y + x + to_nat' (y + x))) = S n
lia. Qed.

Show of_nat is injective.


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

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

n = m
n, m: nat
h: of_nat n = of_nat m

to_nat (of_nat m) = to_nat (of_nat m)
reflexivity. Qed.

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).

= fun (X : Prop) (s : X -> X) (z : X) => s (s (s (s (s z)))) : num

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: nat

add (from_nat n) (from_nat m) = from_nat (n + m)
m: nat

add (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)
m: nat

add (from_nat 0) (from_nat m) = from_nat (0 + m)
reflexivity.
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))
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))
reflexivity. Qed. Definition mul : num -> num -> num := fun n m X s z => n X (m X s) z.

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: nat

mul (from_nat n) (from_nat m) = from_nat (n * m)
m: nat

mul (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)
m: nat

mul (from_nat 0) (from_nat m) = from_nat (0 * m)
reflexivity.
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)
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))
reflexivity. Qed.

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: nat

exp (from_nat n) (from_nat m) = from_nat (n ^ m)
n, m: nat

exp (from_nat n) (from_nat m) = from_nat (n ^ m)
n: nat

exp (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: nat

exp (from_nat n) (from_nat 0) = from_nat (n ^ 0)
reflexivity.
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)
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))
reflexivity. Qed.

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: X

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 z
n: nat
X: Prop
s: X -> X
z: X

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 z
X: Prop
s: X -> X
z: X

from_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 z
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 z
from_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 z
X: Prop
s: X -> X
z: X

from_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 z
reflexivity.
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 z

from_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 z
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 z

succ (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 z
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 z

s (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)
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 z

s (from_nat n X s z) = s (from_nat n X s z)
reflexivity. Qed.
n: nat

pred (from_nat n) = from_nat (Nat.pred n)
n: nat

pred (from_nat n) = from_nat (Nat.pred n)

pred (from_nat 0) = from_nat (Nat.pred 0)
n: nat
pred (from_nat (S n)) = from_nat (Nat.pred (S n))

pred (from_nat 0) = from_nat (Nat.pred 0)
reflexivity.
n: nat

pred (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 n
n: 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 X
n: 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 s
n: nat
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 n X s z
apply pred_aux. Qed.