Exercise session 3 — Proof terms and meta-theory — Solutions

Authors:

Yannick Forster

Théo Winterhalter

Files:
Set Default Goal Selector "!".

From Stdlib Require Import List.
Import ListNotations.

Exercise: N-ary functions

Define an n-ary summation function sum, such that e.g. sum 3 = fun a b c => a + b + c.

Fixpoint nary (n : nat) :=
  match n with
  | 0 => nat
  | S n => nat -> nary n
  end.

Fixpoint sum' (n : nat) (a : nat) : nary n :=
  match n with
  | 0 => a
  | S n => fun x => sum' n (a + x)
  end.

Definition sum n : nary n := sum' n 0.


sum 2 = (fun x1 x2 : nat => x1 + x2)

sum 2 = (fun x1 x2 : nat => x1 + x2)
reflexivity. Qed.

sum 3 = (fun x1 x2 x3 : nat => x1 + x2 + x3)

sum 3 = (fun x1 x2 x3 : nat => x1 + x2 + x3)
reflexivity. Qed. (* From the lecture: *) Inductive even : nat -> Prop := | evenO : even 0 | evenS : forall n, even n -> even (S (S n)). Arguments evenS {n}.

Exercise: Even

Define a proof term of the following type:

Fixpoint even_double n : even (n * 2) :=
  match n with
  | 0 => evenO
  | S n => evenS (even_double n)
  end.

Exercise: Proof terms

Prove the following statements using proof terms. If it's too hard to do directly, you can use the interactive mode together with the refine tactic.

Definition ex1 : forall (P Q : Prop), P -> Q -> P :=
  fun P Q p q => p.

Definition ex2 :
  forall (P Q R : Prop), P -> (P -> Q) -> (P -> Q -> R) -> R
:= fun P Q R p f g => g p (f p).

Exercise: Less than

We give you this type for "less than" (lt).

Inductive lt (n : nat) : nat -> Prop :=
| lt_B : lt n (S n)
| lt_S m : lt n m -> lt n (S m).

Prove the following lemma interactively using intros and apply.


forall n m : nat, lt n m -> lt n (4 + m)

forall n m : nat, lt n m -> lt n (4 + m)
n, m: nat
h: lt n m

lt n (4 + m)
n, m: nat
h: lt n m

lt n (S (S (S m)))
n, m: nat
h: lt n m

lt n (S (S m))
n, m: nat
h: lt n m

lt n (S m)
n, m: nat
h: lt n m

lt n m
apply h. Qed.

Note we make lt_S easier to use by making n, m implicit.

Arguments lt_S {n m}.

Now prove it with a proof term.

Definition lt_plus_4' n m : lt n m -> lt n (4 + m) :=
  fun h => lt_S (lt_S (lt_S (lt_S h))).

Exercise: Connectives as proof terms

Prove the following with a proof term. Hint: Use Print "\/" if needed.

Definition or_comm P Q : P \/ Q -> Q \/ P :=
  fun h =>
    match h with
    | or_introl p => or_intror p
    | or_intror q => or_introl q
    end.

Prove the following with a proof term.

Definition ex3 :
  forall X (P Q : X -> Prop),
    (forall x, P x <-> Q x) ->
    (forall x, Q x) ->
    forall x, P x
:=
  fun X P Q equiv f x =>
    match equiv x with
    | conj hpq hqp =>
        hqp (f x)
    end.

We can also write it this way:

Definition ex3_alt :
  forall X (P Q : X -> Prop),
    (forall x, P x <-> Q x) ->
    (forall x, Q x) ->
    forall x, P x
:=
  fun X P Q equiv f x =>
    let 'conj hpq hqp := equiv x in
    hqp (f x).

Prove the following with a proof term. If you have trouble with this one, try to use refine to fill the term interactively.

Definition Russell X : ~ (X <-> ~ X)
:=
  fun h =>
    let 'conj f g := h in
    let x : X := g (fun x => f x x) in
    f x x.

Exercise: Impredicative encodings

Thanks to impredicativity of Prop (the ability to quantify over propositions within propositions) it is possible to define most connectives using only forall and -> (no inductive definitions).

For instance, one can define False as follows:

Definition iFalse := forall (P : Prop), P.

Show that iFalse is equivalent to False.


False <-> iFalse

False <-> iFalse

False -> iFalse

iFalse -> False

False -> iFalse
contradiction.

iFalse -> False
h: iFalse

False
apply h. Qed.

Define the impredicative encoding of True and show it equivalent to True.

Definition iTrue : Prop :=
  iFalse -> iFalse.


True <-> iTrue

True <-> iTrue

True -> iTrue

iTrue -> True

True -> iTrue

iTrue
h: iFalse

iFalse
assumption.

iTrue -> True

True
constructor. Qed.

Now do the same thing for conjunction, disjunction and the existential quantifier.

If you look at the solution you should see that they are in a sense connected to the elimination rule of the corresponding connective. Note that you can get it basically by using Print and_ind.

For conjunction, the idea is that having a proof of A /\ B is the same as being able to prove any X as long as A -> B -> X holds, in other words as long as X is provable assuming A and B.

Another way of seeing it is that if you have h : iAnd P Q then apply h should be equivalent to destruct h' with h' : P /\ Q.

Definition iAnd (P Q : Prop) : Prop :=
  forall (X : Prop), (P -> Q -> X) -> X.


forall P Q : Prop, P /\ Q <-> iAnd P Q

forall P Q : Prop, P /\ Q <-> iAnd P Q
P, Q: Prop

P /\ Q <-> iAnd P Q
P, Q: Prop

P /\ Q -> iAnd P Q
P, Q: Prop
iAnd P Q -> P /\ Q
P, Q: Prop

P /\ Q -> iAnd P Q
P, Q: Prop
hP: P
hQ: Q

iAnd P Q
P, Q: Prop
hP: P
hQ: Q
X: Prop
h: P -> Q -> X

X
P, Q: Prop
hP: P
hQ: Q
X: Prop
h: P -> Q -> X

P
P, Q: Prop
hP: P
hQ: Q
X: Prop
h: P -> Q -> X
Q
all: assumption.
P, Q: Prop

iAnd P Q -> P /\ Q
P, Q: Prop
h: iAnd P Q

P /\ Q
P, Q: Prop
h: iAnd P Q

P -> Q -> P /\ Q
P, Q: Prop
h: iAnd P Q
hP: P
hQ: Q

P /\ Q
P, Q: Prop
h: iAnd P Q
hP: P
hQ: Q

P
P, Q: Prop
h: iAnd P Q
hP: P
hQ: Q
Q
all: assumption. Qed.

For disjunction it's similar, but with two branches.

Definition iOr (P Q : Prop) : Prop :=
  forall (X : Prop), (P -> X) -> (Q -> X) -> X.


forall P Q : Prop, P \/ Q <-> iOr P Q

forall P Q : Prop, P \/ Q <-> iOr P Q
P, Q: Prop

P \/ Q <-> iOr P Q
P, Q: Prop

P \/ Q -> iOr P Q
P, Q: Prop
iOr P Q -> P \/ Q
P, Q: Prop

P \/ Q -> iOr P Q
P, Q: Prop
h: P \/ Q
X: Prop
hP: P -> X
hQ: Q -> X

X
P, Q: Prop
H: P
X: Prop
hP: P -> X
hQ: Q -> X

X
P, Q: Prop
H: Q
X: Prop
hP: P -> X
hQ: Q -> X
X
P, Q: Prop
H: P
X: Prop
hP: P -> X
hQ: Q -> X

X
P, Q: Prop
H: P
X: Prop
hP: P -> X
hQ: Q -> X

P
assumption.
P, Q: Prop
H: Q
X: Prop
hP: P -> X
hQ: Q -> X

X
P, Q: Prop
H: Q
X: Prop
hP: P -> X
hQ: Q -> X

Q
assumption.
P, Q: Prop

iOr P Q -> P \/ Q
P, Q: Prop
h: iOr P Q

P \/ Q
P, Q: Prop
h: iOr P Q

P -> P \/ Q
P, Q: Prop
h: iOr P Q
Q -> P \/ Q
P, Q: Prop
h: iOr P Q

P -> P \/ Q
P, Q: Prop
h: iOr P Q
H: P

P \/ Q
P, Q: Prop
h: iOr P Q
H: P

P
assumption.
P, Q: Prop
h: iOr P Q

Q -> P \/ Q
P, Q: Prop
h: iOr P Q
H: Q

P \/ Q
P, Q: Prop
h: iOr P Q
H: Q

Q
assumption. Qed. Definition iEx (X : Type) (P : X -> Prop) : Prop := forall (Y : Prop), (forall x, P x -> Y) -> Y.

forall (X : Type) (P : X -> Prop), (exists x : X, P x) <-> iEx X P

forall (X : Type) (P : X -> Prop), (exists x : X, P x) <-> iEx X P
X: Type
P: X -> Prop

(exists x : X, P x) <-> iEx X P
X: Type
P: X -> Prop

(exists x : X, P x) -> iEx X P
X: Type
P: X -> Prop
iEx X P -> exists x : X, P x
X: Type
P: X -> Prop

(exists x : X, P x) -> iEx X P
X: Type
P: X -> Prop
x: X
hx: P x
Y: Prop
h: forall x : X, P x -> Y

Y
X: Type
P: X -> Prop
x: X
hx: P x
Y: Prop
h: Y

Y
assumption.
X: Type
P: X -> Prop

iEx X P -> exists x : X, P x
X: Type
P: X -> Prop
h: iEx X P

exists x : X, P x
X: Type
P: X -> Prop
h: iEx X P

forall x : X, P x -> exists x0 : X, P x0
X: Type
P: X -> Prop
h: iEx X P
x: X
hx: P x

exists x0 : X, P x0
X: Type
P: X -> Prop
h: iEx X P
x: X
hx: P x

P x
assumption. Qed.

Exercise: Tactics for programs

There is also a fix tactic to introduce fix in the term. It takes two arguments: fix f n introduces an assumption f in the context, with the same type as the goal, and n indicates which argument (starting from 1) is recursive.

So below fix rec 1 introduces rec : nat -> nat -> nat where the first argument is recursive, a bit like writing rec a b {struct a}.


nat -> nat -> nat

nat -> nat -> nat
rec: nat -> nat -> nat

nat -> nat -> nat
rec: nat -> nat -> nat
n, m: nat

nat
rec: nat -> nat -> nat
m: nat

nat
rec: nat -> nat -> nat
n, m: nat
nat
rec: nat -> nat -> nat
m: nat

nat
apply m.
rec: nat -> nat -> nat
n, m: nat

nat
rec: nat -> nat -> nat
n, m: nat

nat
rec: nat -> nat -> nat
n, m: nat

nat
rec: nat -> nat -> nat
n, m: nat
nat
rec: nat -> nat -> nat
n, m: nat

nat
apply n.
rec: nat -> nat -> nat
n, m: nat

nat
apply m. Defined.

First prove the following.


Nat.add = addition

Nat.add = addition
reflexivity. Qed.

Now define an append function on lists (the one we write ++) using the fix tactic.

A: Type

list A -> list A -> list A
A: Type

list A -> list A -> list A
A: Type
rec: list A -> list A -> list A

list A -> list A -> list A
A: Type
rec: list A -> list A -> list A
n, m: list A

list A
A: Type
rec: list A -> list A -> list A
m: list A

list A
A: Type
rec: list A -> list A -> list A
a: A
n, m: list A
list A
A: Type
rec: list A -> list A -> list A
m: list A

list A
exact m.
A: Type
rec: list A -> list A -> list A
a: A
n, m: list A

list A
A: Type
rec: list A -> list A -> list A
a: A
n, m: list A

A
A: Type
rec: list A -> list A -> list A
a: A
n, m: list A
list A
A: Type
rec: list A -> list A -> list A
a: A
n, m: list A

list A
A: Type
rec: list A -> list A -> list A
a: A
n, m: list A

list A
A: Type
rec: list A -> list A -> list A
a: A
n, m: list A
list A
A: Type
rec: list A -> list A -> list A
a: A
n, m: list A

list A
exact n.
A: Type
rec: list A -> list A -> list A
a: A
n, m: list A

list A
exact m. Defined.

app = @append

app = @append
reflexivity. Qed.

Exercise: Non-termination (advanced)

There are three crucial potential breaking points of consistency of type theory:

  • termination of recursive functions, which needs to be ensured;

  • strict positivity of inductive types, which we see in the lecture right after this exercise;

  • having type hierarchies rather than a Type : Type rule.

Define a function of type nat -> nat and use it to deduce False. Note that this is surprisingly tricky.

Unset Guard Checking.

Module Termination.

n: nat

n <> S n
n: nat

n <> S n

0 <> 1
n: nat
ih: n <> S n
S n <> S (S n)

0 <> 1
discriminate.
n: nat
ih: n <> S n

S n <> S (S n)
n: nat
ih: n <> S n
e: S n = S (S n)

False
n: nat
ih: n <> S n
e: S n = S (S n)
H0: n = S n

False
n: nat
ih: n <> S n
e: S n = S (S n)
H0: n = S n

n = S n
assumption. Qed. Definition idnat (x : nat) := x. Fixpoint f (x : nat) : nat := S (f (idnat x)).

False

False

f 0 = S (f 0)
reflexivity. Qed. End Termination. Set Guard Checking.

Exercise: Non-positive types (advanced)

Define an inductive type bad such that bad <-> ~ bad, use lemma Russell from above to derive a contradiction.

Unset Positivity Checking.

Module Positivity.

Inductive bad :=
| C : (bad -> False) -> bad.


bad <-> ~ bad

bad <-> ~ bad

bad -> ~ bad

~ bad -> bad

bad -> ~ bad
h: bad
nh: bad -> False

False
contradiction.

~ bad -> bad
nh: ~ bad

bad
nh: ~ bad

bad -> False
assumption. Qed.

False

False
apply (Russell _ bad_not_bad). Qed. End Positivity. Set Positivity Checking.

Exercise: More induction principles

Define induction principles using Fixpoint for all the following types of trees.

Inductive btree :=
| bL
| bN (b1 b2 : btree).

Inductive ltree (L : Type) :=
| lL (l : L)
| lN (l : L) (b1 b2 : ltree L).

Inductive atree (L : Type) (B : L -> Type) :=
| aN (l : L) (bs : B l -> atree L B).

Abbreviation altree L :=
  (atree (L * bool) (fun p => if snd p then bool else False)).

Fixpoint btree_ind' :
  forall (P : btree -> Prop),
    P bL ->
    (forall b1, P b1 -> forall b2, P b2 -> P (bN b1 b2)) ->
    forall t, P t :=
  fun P hL hN t =>
    match t with
    | bL => hL
    | bN b1 b2 => hN _ (btree_ind' P hL hN b1) _ (btree_ind' P hL hN b2)
    end.

Arguments lL {L}.
Arguments lN {L}.

Fixpoint ltree_ind' L :
  forall (P : ltree L -> Prop),
    (forall l, P (lL l)) ->
    (forall l b1, P b1 -> forall b2, P b2 -> P (lN l b1 b2)) ->
    forall t, P t :=
  fun P hL hN t =>
    match t with
    | lL l => hL l
    | lN l b1 b2 => hN l _ (ltree_ind' L P hL hN b1) _ (ltree_ind' L P hL hN b2)
    end.

Arguments aN {L B}.

Fixpoint atree_ind' L B :
  forall (P : atree L B -> Prop),
    (forall l bs, (forall b, P (bs b)) -> P (aN l bs)) ->
    forall t, P t :=
  fun P h t =>
    match t with
    | aN l bs => h l _ (fun b => atree_ind' L B P h (bs b))
    end.

Define functions to : forall {L}, ltree L -> altree L and of : forall {L}, altree L -> ltree L such that forall L (t : ltree L), of (to t) = t.

Fixpoint to {L} (t : ltree L) : altree L :=
  match t with
  | lL l => aN (l, false) (False_rect _)
  | lN l b1 b2 => aN (l, true) (fun (b : bool) => if b then to b1 else to b2)
  end.

Fixpoint of {L} (t : altree L) : ltree L :=
  match t with
  | aN (l, false) bs => lL l
  | aN (l, true) bs => lN l (of (bs true)) (of (bs false))
  end.

L: Type
t: ltree L

of (to t) = t
L: Type
t: ltree L

of (to t) = t
L: Type
l: L

of (to (lL l)) = lL l
L: Type
l: L
b1, b2: ltree L
ih1: of (to b1) = b1
ih2: of (to b2) = b2
of (to (lN l b1 b2)) = lN l b1 b2
L: Type
l: L

of (to (lL l)) = lL l
L: Type
l: L

lL l = lL l
reflexivity.
L: Type
l: L
b1, b2: ltree L
ih1: of (to b1) = b1
ih2: of (to b2) = b2

of (to (lN l b1 b2)) = lN l b1 b2
L: Type
l: L
b1, b2: ltree L
ih1: of (to b1) = b1
ih2: of (to b2) = b2

lN l (of (to b1)) (of (to b2)) = lN l b1 b2
congruence. Qed.

Exercise: Nested induction principles

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]

Define an induction principle using Fixpoint for rtree. You may use the Forall predicate to help you.

Fixpoint rtree_ind' :
  forall (P : rtree -> Prop),
    (forall bs, Forall P bs -> P (rN bs)) ->
    forall t, P t :=
  fun P h t =>
    match t with
    | rN bs =>
      let hbs :=
        fix aux bs : Forall P bs :=
          match bs with
          | [] => Forall_nil _
          | b :: bs => Forall_cons _ (rtree_ind' P h b) (aux bs)
          end
      in
      h _ (hbs bs)
    end.

Exercise: Fibonacci with recursors (advanced)

Here is the Fibonacci function.

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

Notice the as keyword to give a name to subexpression S n. This way Rocq knows that S n is a subterm of the one we started with.

Define the Fibonacci function fib using nat_rect directly.

The idea is to recursively produce a pair (fib (n-1), fib n) and then take the second projection snd.

Definition fib_natrec n :=
  let p :=
    nat_rect (fun _ => (nat * nat)%type)
      (0,1)
      (fun _ '(f0, f1) => (f1, f0 + f1))
      n
  in
  snd p.

Define it using course-of-values recursion, a form of strong induction shown below. Of course you need to prove brec first.

Fixpoint below (P : nat -> Type) (n : nat) : Type :=
  match n with
  | 0 => unit
  | S n => P n * below P n
  end.

= (?P 4 * (?P 3 * (?P 2 * (?P 1 * (?P 0 * unit)))))%type : Type where ?P : [ |- nat -> Type]
Fixpoint brec' (P : nat -> Type) (F : forall n', below P n' -> P n') (n : nat) {struct n} : P n * below P n := match n with | 0 => (F 0 tt, tt) | S n => let r := brec' P F n in (F (S n) r , r) end. Definition brec {P : nat -> Type} (F : forall n, below P n -> P n) : forall n, P n := fun n => fst (brec' P F n). Definition fib_brec : nat -> nat := brec (fun n => match n with | 0 => fun _ => 1 | 1 => fun _ => 1 | S (S n) => fun r => fst r + fst (snd r) end ).

Exercise: Type : Type (advanced)

We are going to prove a theorem allowing us to prove False from Type : Type. Fill in the missing parts below.

Module Hierarchy.

  Definition embeds X Y :=
    exists (E : X -> Y) (D : Y -> X),
      forall x, D (E x) = x.

  
X: Type

embeds X X
X: Type

embeds X X
X: Type

forall x : X, x = x
reflexivity. Qed. Definition Tyi := Type. Inductive tree (A : Tyi) (D : A -> Tyi) : Tyi := | T (a : A) (f : D a -> tree A D). Arguments T { _ _}. Definition sub {A : Tyi} {D : A -> Tyi} (s t : @tree A D) : Prop := match t with | T a f => exists x, f x = s end.
A: Tyi
D: A -> Tyi

forall s : tree A D, ~ sub s s
A: Tyi
D: A -> Tyi

forall s : tree A D, ~ sub s s
A: Tyi
D: A -> Tyi
a: A
f: D a -> tree A D
ih: forall H : D a, ~ sub (f H) (f H)

~ sub (T a f) (T a f)
A: Tyi
D: A -> Tyi
a: A
f: D a -> tree A D
ih: forall H : D a, ~ sub (f H) (f H)
x: D a
e: f x = T a f

False
A: Tyi
D: A -> Tyi
a: A
f: D a -> tree A D
ih: forall H : D a, ~ sub (f H) (f H)
x: D a
e: f x = T a f

sub (f x) (f x)
A: Tyi
D: A -> Tyi
a: A
f: D a -> tree A D
ih: forall H : D a, ~ sub (f H) (f H)
x: D a
e: f x = T a f

sub (f x) (T a f)
A: Tyi
D: A -> Tyi
a: A
f: D a -> tree A D
ih: forall H : D a, ~ sub (f H) (f H)
x: D a
e: f x = T a f

exists x0 : D a, f x0 = f x
A: Tyi
D: A -> Tyi
a: A
f: D a -> tree A D
ih: forall H : D a, ~ sub (f H) (f H)
x: D a
e: f x = T a f

f x = f x
reflexivity. Qed.
A: Type
D: A -> Tyi
E: Tyi -> A

~ embeds (tree A D) (D (E (tree A D)))
A: Type
D: A -> Tyi
E: Tyi -> A

~ embeds (tree A D) (D (E (tree A D)))
A: Type
D: A -> Tyi
E: Tyi -> A
F: tree A D -> D (E (tree A D))
G: D (E (tree A D)) -> tree A D
h: forall x : tree A D, G (F x) = x

False
A: Type
D: A -> Tyi
E: Tyi -> A
F: tree A D -> D (E (tree A D))
G: D (E (tree A D)) -> tree A D
h: forall x : tree A D, G (F x) = x

sub (T (E (tree A D)) G) (T (E (tree A D)) G)
A: Type
D: A -> Tyi
E: Tyi -> A
F: tree A D -> D (E (tree A D))
G: D (E (tree A D)) -> tree A D
h: forall x : tree A D, G (F x) = x

exists x : D (E (tree A D)), G x = T (E (tree A D)) G
A: Type
D: A -> Tyi
E: Tyi -> A
F: tree A D -> D (E (tree A D))
G: D (E (tree A D)) -> tree A D
h: forall x : tree A D, G (F x) = x

G (F (T (E (tree A D)) G)) = T (E (tree A D)) G
apply h. Qed.

forall X : Tyi, ~ embeds Tyi X

forall X : Tyi, ~ embeds Tyi X
X: Tyi
E: Tyi -> X
D: X -> Tyi
h: forall x : Tyi, D (E x) = x

False
X: Tyi
E: Tyi -> X
D: X -> Tyi
h: forall x : Tyi, D (E x) = x

embeds (tree X D) (D (E (tree X D)))
X: Tyi
E: Tyi -> X
D: X -> Tyi
h: forall x : Tyi, D (E x) = x

embeds (tree X D) (tree X D)
apply embeds_refl. Qed.

We now enable the Type : Type rule.

  Unset Universe Checking.

  

False

False

embeds Tyi Tyi
apply embeds_refl. Qed. End Hierarchy.