Self-evaluation 5

Authors:

Yannick Forster

Théo Winterhalter

Files:

Exercise 1

Given A : Type@{i}, B : A → Type@{j} and P : A → Prop, what is the type of the following expressions?

forall (x : A), B x
forall (x : A), P x
Type@{i} -> Type@{j}

Exercise 2

Inductive nat : Type := O | S (n : nat).
Inductive pnat : Prop := pO | pS (n : pnat).

Can you define functions of type nat -> pnat or pnat -> nat? Write a proof term or explain why not.

Exercise 3

Same question with the two following types.

Inductive unit : Type := tt.
Inductive punit : Prop := ptt.

Exercise 4

Inductive Acc {A} {R : A -> A -> Prop} (x : A) : Prop :=
  Acc_intro : (forall y, R y x -> Acc y) -> Acc x.

Give the induction principle for Acc. Can you define it for a motive in Type? Explain why.