Self-evaluation 7

Authors:

Yannick Forster

Théo Winterhalter

Files:

Exercise 1

For the following inductive type, list the

  • uniform parameters,

  • non-uniform parameters,

  • indices.

Inductive blurb (A : Type) (x : A) : list A -> bool -> Prop :=
| foo : blurb A x nil false
| bar y l : blurb A y l false -> blurb A x (x :: l) true
| baz y l : blurb A x l true -> blurb A x (y :: l) false.

Exercise 2

Give a proof term for transitivity of Leibniz equality, defined below.

Definition lbeq {A} (u v : A) :=
  forall (P : A -> Prop), P u -> P v.

Notation "u == v" := (lbeq u v) (at level 80).

Definition lb_trans {A} {u v w : A} : u == v -> v == w -> u == w :=
  REPLACE_ME.

Exercise 3

Prove the following.


list False <> list nat

list False <> list nat
Admitted.

Exercise 4

Show that PropExt implies proof irrelevance.

Definition PropExt :=
  forall (P Q : Prop), (P <-> Q) -> P = Q.

Definition ProofIrrelevance :=
  forall (P : Prop) (p q : P), p = q.


PropExt -> ProofIrrelevance

PropExt -> ProofIrrelevance
Admitted.