[Agda] question about a form of irrelevance elimination
Martin Escardo
m.escardo at cs.bham.ac.uk
Tue Jul 14 14:46:04 CEST 2015
On 14/07/15 10:07, Neelakantan Krishnaswami wrote:
> Dear Andy,
>
> It looks like the escape property you describe is equivalent to the
> universal property of truncation in HoTT. Adding it means that
> irrelevance is basically the same as quotienting by the full relation.
> (See Kraus et al's "Notions of Anonymous Existence in Martin-Loef Type
> Theory".)
>
> However, this has the effect that irrelevant arguments cannot be
> erased at runtime; you still need to pass them around in case you
> use an irrelevant argument to construct an escaping value.
See
http://wiki.portal.chalmers.se/agda/agda.php?n=ReferenceManual.Irrelevance#Nomoreerasing
"No more erasing
Irrelevant things are no longer erased internally. This means that
they are printed as ordinary terms, not as “_” as before.
"
Nevertheless, I think you still don't get propositional truncations with
irrelevant fields.
> So, it's consistent to add, but if you care about running dependently
> typed programs (as opposed to typechecking them), you might not want to
> add it. :)
I am a bit nervous about the computational consistency of this
postulate. I think this may imply excluded middle (but I am not sure).
Martin
>
> Best,
> Neel
>
>
> On 14/07/15 09:48, Andrew Pitts wrote:
>> Since version 2.2.8, Agda supports irrelevancy annotations
>> (http://wiki.portal.chalmers.se/agda/agda.php?n=ReferenceManual.Irrelevance).
>>
>> Among other things this allows one to define a form of truncation:
>>
>> record ! {ℓ : Level}(A : Set ℓ) : Set ℓ where
>> constructor ![_]
>> field
>> .prf : A
>> open ! public
>>
>> Since the elements of ! A are definitionally irrelevant, they are also
>> propositionally irrelevant, i.e. ! A is a proposition in the sense of
>> Homotopy Type Theory:
>>
>> isProp : {ℓ : Level}(A : Set ℓ) → Set ℓ
>> isProp A = (x y : A) → x ≡ y
>> !isprop : {ℓ : Level}{A : Set ℓ} → isProp (! A)
>> !isprop _ _ = refl
>>
>> I would like to be able to escape from an irrelevant context in the
>> case of propositions:
>>
>> postulate
>> !elim : {ℓ : Level}{A : Set ℓ}.(_ : isProp A) → (! A) → A
>>
>> Does adding such a postulate destroy logical consistency?
>>
>> Andy Pitts
>> _______________________________________________
>> Agda mailing list
>> Agda at lists.chalmers.se
>> https://lists.chalmers.se/mailman/listinfo/agda
>>
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda
--
Martin Escardo
http://www.cs.bham.ac.uk/~mhe
More information about the Agda
mailing list