Skip to content
The Lumenary

Practice · Advanced undergraduate

Type theory and propositions as types

Type theory and propositions as types

Warm-upHuman

Under the propositions-as-types correspondence, what is a proof of A∧BA \wedge B?

Choose one

Type theory and propositions as types

Warm-upHuman

What is the most general simple type of λf. λg. λx. f (g x)\lambda f.\, \lambda g.\, \lambda x.\, f\,(g\, x), and hence which tautology does it prove?

Choose one

Type theory and propositions as types

CoreHuman

Which of these types are inhabited by a closed term (equivalently, are theorems of intuitionistic propositional logic)? Here p,qp, q are base types and ¬A=A→0\neg A = A \to 0. Choose all that apply.

Choose all that apply

Type theory and propositions as types

CoreHuman

In the two-state Kripke model w0≤w1w_0 \le w_1 with pp known only at w1w_1, which formulas are forced at w0w_0? (Rules: w⊩A→Bw \Vdash A \to B iff every v≥wv \ge w forcing AA forces BB; ⊥\bot is forced nowhere, ¬A=A→⊥\neg A = A \to \bot; w⊩A∨Bw \Vdash A \vee B iff w⊩Aw \Vdash A or w⊩Bw \Vdash B.) Choose all that apply.

Choose all that apply

Type theory and propositions as types

CoreHuman

Let AA be a base type. How many closed β-normal terms of type A→A→AA \to A \to A are there (counting α-equivalent terms once)?

Type theory and propositions as types

CoreHuman

In the proof of soundness for Kripke models (Theorem 3), the →\to-introduction case goes: assume ww forces all of Γ\Gamma, let v≥wv \ge w force AA; then vv forces all of Γ,A\Gamma, A, so v⊩Bv \Vdash B by induction. Which fact justifies 'vv forces all of Γ\Gamma'?

Choose one

Type theory and propositions as types

CoreHuman

With addition on N\N defined by m+zero=mm + \mathsf{zero} = m and m+succ n=succ(m+n)m + \mathsf{succ}\, n = \mathsf{succ}(m + n), why is n+0=nn + 0 = n true by computation while 0+n=n0 + n = n needs induction?

Choose one

Type theory and propositions as types

StretchFormal

The lesson's Lean file proves both peirce_classical (A B : Prop) : ((A → B) → A) → A and peirce_uninhabited : ¬ ∃ t, HasType [] t (((Ty.base 0 ⇒ Ty.base 1) ⇒ Ty.base 0) ⇒ Ty.base 0). Why is this not a contradiction?

Choose one

Type theory and propositions as types

StretchComputational

Write forces(w, f, le, val) for implicational formulas in a finite Kripke model. A formula is either an atom (a string such as 'p') or a tuple ('imp', A, B). le is a set of pairs (u, v) meaning u≤vu \le v (reflexive and transitive), and val[w] is the set of atoms known at w. Use: atoms are forced when known; ('imp', A, B) is forced at w iff every v with (w, v) in le that forces A also forces B.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.