<div dir="ltr">Unprovability of void-ext has been known to be the reason why one cannot (in Coq) <div>code up natural numbers as W Types.</div><div><br></div><div>Here is a quote :</div><div><div>"This is because one cannot prove that there is only a unique function from the empty set to the set of natural numbers without using extensional equality."</div><div>from</div></div><div><div><a href="https://coq.inria.fr/cocorico/WTypeInsteadOfInductiveTypes">https://coq.inria.fr/cocorico/WTypeInsteadOfInductiveTypes</a><br></div><div><br></div><div>However, I don't know a formal (meta-theoretical) proof of unprovability of void-ext.</div><div>I'd be grateful if someone can point us to such a proof.</div></div><div><br></div></div><div class="gmail_extra"><br clear="all"><div><div class="gmail_signature"><div>-- Abhishek</div><a href="http://www.cs.cornell.edu/~aa755/" target="_blank">http://www.cs.cornell.edu/~aa755/</a></div></div>
<br><div class="gmail_quote">On Wed, Feb 18, 2015 at 11:20 AM, Dan Licata <span dir="ltr"><<a href="mailto:drl@cs.cmu.edu" target="_blank">drl@cs.cmu.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word">Can you even do this (without otherwise assuming function extensionality)?<div><br></div><div>For example, for Fin 0, isn't it the same as saying "any function from 0 to A is abort":</div><div><br></div><div><div> data Id {A : Set} (a : A) : A → Set where</div><div> refl : Id a a</div><div><br></div><div> data Void : Set where</div><div><br></div><div> abort : {A : Set} → Void → A</div><div> abort ()</div><div><br></div><div> void-ext : {A : Set} → (f : Void → A) → Id f abort</div><div> void-ext f = {!!}</div></div><div><br></div><div>(void-ext is sufficient; is it necessary?)</div><div>and if so, can you prove that? I don't see how off the top of my head. </div><span class="HOEnZb"><font color="#888888"><div><br></div><div>-Dan</div></font></span><div><div class="h5"><div><br><div><div>On Feb 18, 2015, at 10:47 AM, João Paulo Pizani Flor <<a href="mailto:J.P.PizaniFlor@uu.nl" target="_blank">J.P.PizaniFlor@uu.nl</a>> wrote:</div><br><blockquote type="cite"><div dir="ltr"><div>Not yet (couldn't find it anywhere), but I will probably need it for my Ph.D project, so maybe it will come in some time...<br><br></div>Cheers,<br><div><div class="gmail_extra"><br clear="all"><div><div><div dir="ltr"><div><div>João Pizani, M.Sc <<a href="mailto:j.p.pizaniflor@uu.nl" target="_blank">j.p.pizaniflor@uu.nl</a>><br></div>Promovendus - Departement Informatica<br></div>Faculteit Bètawetenschappen - Universiteit Utrecht<br></div></div></div>
<br><div class="gmail_quote">On Wed, Feb 18, 2015 at 3:25 PM, Jacques Carette <span dir="ltr"><<a href="mailto:carette@mcmaster.ca" target="_blank">carette@mcmaster.ca</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Does anyone have a proof in Agda that functions at type (Fin n -> Fin n) are extensional?<br>
Jacques<br>
______________________________<u></u>_________________<br>
Agda mailing list<br>
<a href="mailto:Agda@lists.chalmers.se" target="_blank">Agda@lists.chalmers.se</a><br>
<a href="https://lists.chalmers.se/mailman/listinfo/agda" target="_blank">https://lists.chalmers.se/<u></u>mailman/listinfo/agda</a><br>
</blockquote></div><br></div></div></div>
_______________________________________________<br>Agda mailing list<br><a href="mailto:Agda@lists.chalmers.se" target="_blank">Agda@lists.chalmers.se</a><br><a href="https://lists.chalmers.se/mailman/listinfo/agda" target="_blank">https://lists.chalmers.se/mailman/listinfo/agda</a><br></blockquote></div><br></div></div></div></div><br>_______________________________________________<br>
Agda mailing list<br>
<a href="mailto:Agda@lists.chalmers.se">Agda@lists.chalmers.se</a><br>
<a href="https://lists.chalmers.se/mailman/listinfo/agda" target="_blank">https://lists.chalmers.se/mailman/listinfo/agda</a><br>
<br></blockquote></div><br></div>