[Agda] Congruence and substitutivity rules in heterogeneous equality

Liang-Ting Chen xcycl at iis.sinica.edu.tw
Wed Jul 15 09:47:38 CEST 2009


On Mon, Jul 13, 2009 at 10:06 PM, Nils Anders Danielsson
<nad at cs.nott.ac.uk>wrote:

> On 2009-07-13 13:22, Liang-Ting Chen wrote:
>
>> subst (P : A → Set) {x : A} {y : A} → x ≅ y → P x → P y
>>
>
> You could do something like the following:
>
>  ≅⇒≡₁ : ∀ {A B} {x : A} {y : B} → x ≅ y → A ≡₁ B
>  ≅⇒≡₁ refl = refl
>
>  coerce : ∀ {A B} → A ≡₁ B → A → B
>  coerce refl = id
>
>  subst : ∀ {A B} (P : A → Set) {x : A} {y : B}
>         (y≅x : y ≅ x) → P x → P (coerce (≅⇒≡₁ y≅x) y)
>  subst P refl p = p
>
> However, I suspect that you do not really want to prove
> P (coerce (≅⇒≅₁ y≅x) y), but rather something slightly different.

Thanks for it ! How about cong ?

subst looks not possible to drop the annotation before unless it is
evaluated? I noticed in RingSolver.agda
there is an interesting idiom to eliminate the use of subst by adding an
casting constructor.


>
>  Furthermore, it also breaks the heterogeneous equational reasoning for
>> the same reason.
>>
>
> In what way is this broken? The standard library requires homogeneity in
> many places, but not for equational reasoning for _≅_ (in the latest
> version).

Ooops, I got it. I checked the heterogeneous equational reasoning few months
ago,
and now it works properly now.

>
>
> --
> /NAD
>
>
> This message has been checked for viruses but the contents of an attachment
> may still contain software viruses, which could damage your computer
> system:
> you are advised to perform your own checks. Email communications with the
> University of Nottingham may be monitored as permitted by UK legislation.
>
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda
>
>


-- 
sincerely,
Liang-Ting
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://lists.chalmers.se/mailman/private/agda/attachments/20090715/d972a7e5/attachment.html


More information about the Agda mailing list