[Agda] Re: [Coq-Club] Re: Agda beats Coq
Arnaud Spiwack
Arnaud.Spiwack at lix.polytechnique.fr
Mon Nov 24 22:51:01 CET 2008
As hour being late, I wasn't being as clear as I should. I meant that
bisimilarity implies intentionnal equality *in Coq* (and so it does in
Agda2 if I'm not mistaken). But this doesn't close the case. (as I was
saying I personnally believe we shouldn't have this property).
Arnaud Spiwack
Arnaud Spiwack a écrit :
> As a matter of fact, the most natural bisimalirity on streams does
> imply intentionnal equality. Which can be considered quite useful, but
> I've got the feeling it's not a good idea. This is actually what makes
> that Coq conversion is not decidable or Coq doesn't have subject
> reduction (choose whichever you want). There are quite some
> metaphysical issues here. ITT, ETT, OTT, whichever intermediate
> alternative, Impredicative, Predicative, ... There is enough to fight
> over all night long.
>
>
> Arnaud Spiwack
>
> Xavier Leroy a écrit :
>> Aaron Bohannon wrote:
>>
>>
>>> [...] That is, may I safely assert that a standard definition of
>>> bisimilarity on a coinductive data type implies the default
>>> (intensional) equality ("=")? (I don't know if this question is
>>> relevant to Agda.)
>>>
>>
>> Thanks for raising this question, as I've been wondering about it for
>> a while.
>>
>> Let me take streams (infinite lists) as a concrete example of
>> coinductive datatype. My (limited) understanding is that you could
>> make a set-theoretic model of streams where a stream of A is a
>> function nat -> A, so your property would amount to function
>> extensionality, which holds in this model. However, I'm pretty sure
>> that if you assert function extensionality as an axiom in Coq, you
>> still cannot prove the extensionality property over streams stated
>> above...
>>
>> Expecting more informed replies from true logicians,
>>
>> - Xavier Leroy
>>
>> --------------------------------------------------------
>> Bug reports: http://logical.futurs.inria.fr/coq-bugs
>> Archives: http://pauillac.inria.fr/pipermail/coq-club
>> http://pauillac.inria.fr/bin/wilma/coq-club
>> Info: http://pauillac.inria.fr/mailman/listinfo/coq-club
>>
>>
>
>
More information about the Agda
mailing list