[Agda] Trust me regarding Dan Licata's trick

Martin Escardo m.escardo at cs.bham.ac.uk
Tue Jun 4 23:48:43 CEST 2013


This is a suggestion/question regarding Dan Licata's trick in Agda:

http://homotopytypetheory.org/2011/04/23/running-circles-around-in-your-proof-assistant/

I am interested in applying (and perhaps improving) Dan's trick to the
following situation.

Given a type X, we want to convert it into a type ||X|| which has the
same elements as X, but all of them become equal in
||X||. Intuitively, we quotient X by the indiscrete equivalence
relation that (propositionally) equates any two elements of X. This is
called the hpropositional truncation of X.

In particular, if 0 is the type with no elements, and 1 is the type
with one element, then ||X|| is isomorphic to 1 if X is inhabited, and
isomorphic to 0 otherwise. Because we don't have excluded middle, we
can't say that ||X|| is isomorphic to either 0 or 1, of course. But we
can (constructively) say that ||X|| has at most one element, in the
sense that any two of its elements are equal.

Cutting a long story short, this can be achieved via Licata's trick as
follows, where I use the notation of the HoTT Book for this
"truncation operation" (https://github.com/HoTT/book):

data _≡_ {X : Set} : X → X → Set where
   refl : {x : X} → x ≡ x

hprop : Set → Set
hprop X = (x y : X) → x ≡ y

private
   data ∥_∥' (X : Set) : Set where
     ∣_∣' : X → ∥ X ∥'

∥_∥ : Set → Set
∥_∥ = ∥_∥'

∣_∣ : {X : Set} → X → ∥ X ∥
∣_∣ = ∣_∣'

postulate
   hprop-|| : {X : Set} → (h k : ∥ X ∥) → h ≡ k

hinhabited-elim' : {X P : Set} → hprop P → (X → P) → ∥ X ∥ → P
hinhabited-elim' _ f ∣ x ∣' = f x

hinhabited-elim : {X : Set} {P : ∥ X ∥ → Set} → ((h : ∥ X ∥) → hprop(P 
h)) → ((x : X) → P ∣ x ∣) → (h : ∥ X ∥) → P h
hinhabited-elim _ f ∣ x ∣' = f x

This is very good, but we have one postulate left (as in Dan's
technique).

Can we get rid of this postulate?

Trust me, of rather primTrustMe, that we can:

http://code.haskell.org/Agda/doc/release-notes/2-2-6.txt
http://wiki.portal.chalmers.se/agda/pmwiki.php?n=ReferenceManual.UniversePolymorphism
http://www.cse.chalmers.se/~nad/listings/lib-0.7/Relation.Binary.PropositionalEquality.TrustMe.html

Unfortunately I can't be as concise as above, because primTrustMe
requires to both have universe levels declared and equality defined in
a particular way with particular pragmas, but still the following
should be somewhat readable:

private
  postulate Level : Set
  postulate zero : Level
  postulate suc  : Level → Level

{-# BUILTIN LEVEL     Level #-}
{-# BUILTIN LEVELZERO zero  #-}
{-# BUILTIN LEVELSUC  suc   #-}

data _≡_ {ℓ} {X : Set ℓ} (x : X) : X → Set ℓ where
   refl : x ≡ x

{-# BUILTIN EQUALITY _≡_  #-}
{-# BUILTIN REFL     refl #-}

private
  primitive
    primTrustMe : ∀{ℓ} {X : Set ℓ} {x y : X} → x ≡ y

hprop : Set → Set
hprop X = (x y : X) → x ≡ y

private
   data ∥_∥' (X : Set) : Set where
     ∣_∣' : X → ∥ X ∥'

∥_∥ : Set → Set
∥_∥ = ∥_∥'

∣_∣ : {X : Set} → X → ∥ X ∥
∣_∣ = ∣_∣'

truncation-is-hprop : {X : Set} → (h k : ∥ X ∥) → h ≡ k
truncation-is-hprop h k = primTrustMe

hinhabited-elim' : {X P : Set} → hprop P → (X → P) → ∥ X ∥ → P
hinhabited-elim' _ f ∣ x ∣' = f x

hinhabited-elim : {X : Set} {P : ∥ X ∥ → Set} → ((h : ∥ X ∥) → hprop(P 
h)) → ((x : X) → P ∣ x ∣) → (h : ∥ X ∥) → P h
hinhabited-elim _ f ∣ x ∣' = f x


So indeed it seems we can do away with postulates in our application
of Dan's trick.  However, the semantics of primTrustMe is barely
hinted in the Agda documentation.

So don't trust me.

Perhaps the designers of this Agda feature can explain to what extent
I am trustworthy in the above removal of a postulate from Dan's trick.

Clearly, this primTrustMe trick can also be blindly applied to Dan's
example in the above link. But does that make sense?

Best,
Martin
PS. I also hope I've managed to send this message with the right 
character encoding so that you are able to read it.


More information about the Agda mailing list