3.2. 命題(Propositions)🔗

命題 (propositioin)は証明を認める意味のある文です。 無意味な文は命題ではありませんが、偽の文は命題です。すべての命題は Prop によって分類されます。

命題は以下の性質を持ちます:

Definitional proof irrelevance

同じ命題の2つの証明は完全に交換可能です。

ランタイムにおける irrelevance

命題はコンパイルされたコードからは消去されます。

非可述性

命題はあらゆる宇宙からの型に対して量化することができます。

制限された除去

subsingletons を除いて、命題は非命題型に除去することができません。

外延性 (extensionality)

論理的に同等な2つの命題は、 propext 公理によって等しいことが証明できます。

🔗
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.