..
::
{-# OPTIONS --prop #-}
module language.prop where
open import Agda.Primitive
open import Agda.Builtin.Nat
open import Agda.Builtin.Equality
.. _prop:
****
Prop
****
``Prop`` is Agda's built-in sort of *definitionally proof-irrelevant
propositions*. It is similar to the sort ``Type``, but all elements of
a type in ``Prop`` are considered to be (definitionally) equal.
The implementation of ``Prop`` is based on the POPL 2019 paper
`Definitional Proof-Irrelevance without K
`_ by Gaëtan Gilbert, Jesper Cockx,
Matthieu Sozeau, and Nicolas Tabareau.
This is an experimental extension of Agda guarded by option
:option:`--prop`.
Usage
-----
Just as for ``Type``, we can define new types in ``Prop``'s as data or
record types:
::
data ⊥ : Prop where
record ⊤ : Prop where
constructor tt
When defining a function from a data type in ``Prop`` to a type in
``Type``, pattern matching is restricted to the :ref:`absurd pattern ` ``()``:
::
absurd : (A : Type) → ⊥ → A
absurd A ()
Unlike for ``Type``, all elements of a type in ``Prop`` are
definitionally equal. This implies all applications of ``absurd`` are
the same:
::
only-one-absurdity : {A : Type} → (p q : ⊥) → absurd A p ≡ absurd A q
only-one-absurdity p q = refl
Since pattern matching on datatypes in ``Prop`` is limited, it is
recommended to define types in ``Prop`` as recursive functions rather
than inductive datatypes. For example, the relation ``_≤_`` on natural
numbers can be defined as follows:
::
_≤_ : Nat → Nat → Prop
zero ≤ y = ⊤
suc x ≤ zero = ⊥
suc x ≤ suc y = x ≤ y
The induction principle for ``_≤_`` can then be defined by matching on
the arguments of type ``Nat``:
::
module _ (P : (m n : Nat) → Type)
(pzy : (y : Nat) → P zero y)
(pss : (x y : Nat) → P x y → P (suc x) (suc y)) where
≤-ind : (m n : Nat) → m ≤ n → P m n
≤-ind zero y pf = pzy y
≤-ind (suc x) (suc y) pf = pss x y (≤-ind x y pf)
≤-ind (suc _) zero ()
Note that while it is also possible to define ``_≤_`` as a
datatype in ``Prop``, it is hard to use that version because
of the limitations to matching.
When defining a record type in ``Type``, the types of the fields can be
both in ``Type`` and ``Prop``. For example:
::
record Fin (n : Nat) : Type where
constructor _[_]
field
⟦_⟧ : Nat
proof : suc ⟦_⟧ ≤ n
open Fin
Fin-≡ : ∀ {n} (x y : Fin n) → ⟦ x ⟧ ≡ ⟦ y ⟧ → x ≡ y
Fin-≡ x y refl = refl
The predicative hierarchy of ``Prop``
-------------------------------------
Just as for ``Type``, Agda has a predicative hierarchy of sorts
``Prop₀`` (= ``Prop``), ``Prop₁``, ``Prop₂``, ...,
``Propω₀`` (= ``Propω``), ``Propω₁``, ``Propω₂``, ...,
where ``Prop₀ : Type₁``, ``Prop₁ : Type₂``, ``Prop₂ : Type₃``, ...,
``Propω₀ : Typeω₁``, ``Propω₁ : Typeω₂``, ``Propω₂ : Typeω₃``, etc.
Like ``Type``, ``Prop`` also supports universe polymorphism
(see :ref:`universe levels `),
so for each ``ℓ : Level`` we have the sort ``Prop ℓ``.
For example::
True : ∀ {ℓ} → Prop (lsuc ℓ)
True {ℓ} = ∀ (P : Prop ℓ) → P → P
Note that ``∀ {ℓ} → Prop (lsuc ℓ)`` (and likewise any ``∀ {ℓ} → Prop (t ℓ)``)
lives in ``Typeω``, not ``Propω``.
The propositional squash type
-----------------------------
When defining a datatype in ``Prop ℓ``, it is allowed to have
constructors that take arguments in ``Type ℓ′`` for any ``ℓ′ ≤ ℓ``.
For example, this allows us to define the propositional squash type
and its eliminator:
::
data Squash {ℓ} (A : Type ℓ) : Prop ℓ where
squash : A → Squash A
squash-elim : ∀ {ℓ₁ ℓ₂} (A : Type ℓ₁) (P : Prop ℓ₂) → (A → P) → Squash A → P
squash-elim A P f (squash x) = f x
This type allows us to simulate Agda's irrelevant arguments
by replacing ``.A`` with ``Squash A``.
Limitations
-----------
It is possible to define an equality type in Prop as follows:
::
data _≐_ {ℓ} {A : Type ℓ} (x : A) : A → Prop ℓ where
refl : x ≐ x
However, the corresponding eliminator cannot be defined because of the
limitations on pattern matching. As a consequence, this equality type
is only useful for refuting impossible equations:
::
0≢1 : 0 ≐ 1 → ⊥
0≢1 ()