3.2. Propositions🔗

Propositions are meaningful statements that admit proof. Nonsensical statements are not propositions, but false statements are. All propositions are classified by Prop.

Propositions have the following properties:

Definitional proof irrelevance

Any two proofs of the same proposition are completely interchangeable.

Run-time irrelevance

Propositions are erased from compiled code.

Impredicativity

Propositions may quantify over types from any universe whatsoever.

Restricted Elimination

With the exception of subsingletons, propositions cannot be eliminated into non-proposition types.

Extensionality

Any two logically equivalent propositions can be proven to be equal with the propext axiom.

🔗
propext {a b : Prop} : (ab) → a = b

The axiom of propositional extensionality. It asserts that if propositions a and b are logically equivalent (i.e. we can prove a from b and vice versa), then a and b are equal, meaning that we can replace a with b in all contexts.

For simple expressions like a ∧ c ∨ d → e we can prove that because all the logical connectives respect logical equivalence, we can replace a with b in this expression without using propext. However, for higher order expressions like P a where P : Prop → Prop is unknown, or indeed for a = b itself, we cannot replace a with b without an axiom which says exactly this.

This is a relatively uncontroversial axiom, which is intuitionistically valid. It does however block computation when using #reduce to reduce proofs directly (which is not recommended), meaning that canonicity, the property that all closed terms of type Nat normalize to numerals, fails to hold when this (or any) axiom is used:

set_option pp.proofs true

def foo : Nat := by
  have : (True → True) ↔ True := ⟨λ _ => trivial, λ _ _ => trivial⟩
  have := propext this ▸ (2 : Nat)
  exact this

#reduce foo
-- propext { mp := fun x x => True.intro, mpr := fun x => True.intro } ▸ 2

#eval foo -- 2

#eval can evaluate it to a numeral because the compiler erases casts and does not evaluate proofs, so propext, whose return type is a proposition, can never block it.