Type theory and propositions as types
Warm-upHumanUnder the propositions-as-types correspondence, what is a proof of ?
Under the propositions-as-types correspondence, what is a proof of ?
What is the most general simple type of , and hence which tautology does it prove?
Which of these types are inhabited by a closed term (equivalently, are theorems of intuitionistic propositional logic)? Here are base types and . Choose all that apply.
In the two-state Kripke model with known only at , which formulas are forced at ? (Rules: iff every forcing forces ; is forced nowhere, ; iff or .) Choose all that apply.
Let be a base type. How many closed β-normal terms of type are there (counting α-equivalent terms once)?
In the proof of soundness for Kripke models (Theorem 3), the -introduction case goes: assume forces all of , let force ; then forces all of , so by induction. Which fact justifies ' forces all of '?
With addition on defined by and , why is true by computation while needs induction?
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?
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 (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.