<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-CA" link="#0563C1" vlink="#954F72" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">I’m going to discourage you from going down this road.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">Here’s an analogy: you are trying to show that the ‘bit patterns’ that represent values of two different types are the same. While this can be true, and can be a useful truth (for optimizing computations),
it isn’t necessarily a good notion of ‘equality’. Which you yourself recognize.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">Whenever I’ve been in the same situation (and it happened a lot in the early days of the work on the Pi reversible language), the eventual resolution usually involved having some type have 2 indices
instead of 1, even though the indices were provably equal. And that was indeed the crux: the indices were merely propositionally equal, not definitionally equal. [Permutations, I see you!]. Of course, your setting might be entirely different.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">In any case, if you persist down this road, I’d encourage you to see it as a “bit pattern are the same”, i.e. an issue of syntactic representation, rather than being about equality.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">Jacques<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span lang="EN-US">From:</span></b><span lang="EN-US"> Agda <agda-bounces@lists.chalmers.se>
<b>On Behalf Of </b>Matthew Daggitt<br>
<b>Sent:</b> November 7, 2020 3:26 AM<br>
<b>To:</b> Agda mailing list <agda@lists.chalmers.se><br>
<b>Subject:</b> [Agda] General notion of equality for syntactically equal objects with different types from the same datatype family?<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">Hi everyone,<o:p></o:p></p>
<div>
<p class="MsoNormal"> I'm trying to prove something a lemma that looks something like:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">```agda<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">open import Data.Fin<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">open import Data.Nat<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">open import Relation.Binary.PropositionalEquality<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">to<span style="font-family:"Cambria Math",serif">ℕ</span>-inject₁ :
<span style="font-family:"Cambria Math",serif">∀</span> {n} {i : Fin n} → to<span style="font-family:"Cambria Math",serif">ℕ</span> (inject₁ i) ≡ to<span style="font-family:"Cambria Math",serif">ℕ</span> i<br>
to<span style="font-family:"Cambria Math",serif">ℕ</span>-inject₁ = {!!}<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">```<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Note `inject₁` doesn't change the syntactic form of `i`, only it's type. In this simple case it is easy enough to prove inductively, but I've currently got a harder case where `inject₁` is more complicated. So I was thinking about using
heterogeneous equality and generalising this to something of the form:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">```<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">import Relation.Binary.HeterogeneousEquality as H using (_<span style="font-family:"Cambria Math",serif">≅</span>_)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">to<span style="font-family:"Cambria Math",serif">ℕ</span>-cong :
<span style="font-family:"Cambria Math",serif">∀</span> {m n} {i : Fin m} {j : Fin n} → i
<span style="font-family:"Cambria Math",serif">≅</span> j → to<span style="font-family:"Cambria Math",serif">ℕ</span> i ≡ to<span style="font-family:"Cambria Math",serif">ℕ</span> j<br>
to<span style="font-family:"Cambria Math",serif">ℕ</span>-cong H.refl = refl<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">inject₁-<span style="font-family:"Cambria Math",serif">≅</span> :
<span style="font-family:"Cambria Math",serif">∀</span> {n} (i : Fin n) → inject₁ i
<span style="font-family:"Cambria Math",serif">≅</span> i<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">inject₁-<span style="font-family:"Cambria Math",serif">≅</span> zero = H.refl<br>
inject₁-<span style="font-family:"Cambria Math",serif">≅</span> (suc i) = H.cong suc (inject₁-<span style="font-family:"Cambria Math",serif">≅</span> i)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">```<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">The problem is of course that the two cases of `inject₁-<span style="font-family:"Cambria Math",serif">≅</span>` don't type check as the two sides don't have the same type. Examining the first case, we want to assert that `zero : Fin n`
and `zero : Fin (suc n)` are equal. In heterogeneous equality, despite working for terms of different types, the constructor `refl` can only be applied when those two types can be proved to be propositionally equal.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I suspect I'm going to have to define a custom notion of equality over `Fin`, but I just thought I'd check that there isn't a more general notion of equality out there that I could use that I'm missing? It's probably a silly question, as
a purely syntactic notion of equality that entirely ignores the types seems very unlikely to be undefinable. But I thought perhaps the fact that they belonged to the same datatype might give some wriggle room...<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Cheers,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Matthew<o:p></o:p></p>
</div>
</div>
</div>
</div>
</body>
</html>