<div><div><div><div><div>On Mon, May 18, 2020 at 8:19 AM David Feuer <<a href="mailto:david.feuer@gmail.com" target="_blank">david.feuer@gmail.com</a>> wrote:<br></div></div><div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto">Classically, the excluded middle is an axiom, not a theorem. </div></blockquote><div dir="auto"><br></div></div></div></div></div><div><div><div><div><div dir="auto">Untrue in general.</div></div><div></div></div><div><div></div></div></div><div><div><div></div></div></div></div><div><div><div><div><div><div class="gmail_quote"><div dir="auto"><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, May 17, 2020, 9:02 PM Kim-Ee Yeoh <<a href="mailto:ky3@atamo.com" target="_blank">ky3@atamo.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><p style="margin:0px;font-stretch:normal;font-size:12px;line-height:normal;font-family:Helvetica"><span style="font-size:12pt">Very cool to see the constructive code for the proof of double negation in intuitionistic logic.</span></p>
<p style="margin:0px;font-stretch:normal;font-size:12px;line-height:normal;font-family:Helvetica;min-height:13.8px"><span style="font-size:12pt"></span><br></p>
<p style="margin:0px;font-stretch:normal;font-size:12px;line-height:normal;font-family:Helvetica"><span style="font-size:12pt">But what about the Curry-Howard correspondence for classical logic?</span></p>
<p style="margin:0px;font-stretch:normal;font-size:12px;line-height:normal;font-family:Helvetica;min-height:13.8px"><span style="font-size:12pt"></span><br></p>
<p style="margin:0px;font-stretch:normal;font-size:12px;line-height:normal;font-family:Helvetica"><span style="font-size:12pt">What would the classical code for the classical proof of excluded middle look like?</span></p></div><div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, May 15, 2020 at 11:09 PM Chris Smith <<a href="mailto:cdsmith@gmail.com" rel="noreferrer" target="_blank">cdsmith@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">This was indeed a fun puzzle to play with. I think this becomes easier to interpret if you factor out De Morgan's Law from the form you posted at the beginning of your email.<div><br></div><div><a href="https://code.world/haskell#PYGDwpaMZ_2iSs74NnwCUrg" rel="noreferrer" target="_blank">https://code.world/haskell#PYGDwpaMZ_2iSs74NnwCUrg</a><br></div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, May 15, 2020 at 5:23 AM Ruben Astudillo <<a href="mailto:ruben.astud@gmail.com" rel="noreferrer" target="_blank">ruben.astud@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On 13-05-20 09:15, Olaf Klinke wrote:<br>
> Excersise: Prove that intuitionistically, it is absurd to deny the law<br>
> of excluded middle:<br>
><br>
> Not (Not (Either a (Not a)))<br>
<br>
It took me a while but it was good effort. I will try to explain how I<br>
derived it. We need a term for<br>
<br>
proof :: Not (Not (Either a (Not a)))<br>
proof :: (Either a (Not a) -> Void) -> Void<br>
<br>
A first approximation is<br>
<br>
-- Use the (cont :: Either a (Not a) -> Void) to construct the Void<br>
-- We need to pass it an Either a (Not a)<br>
proof :: (Either a (Not a) -> Void) -> Void<br>
proof cont = cont $ Left <no a to fill in><br>
<br>
Damn, we can't use the `Left` constructor as we are missing an `a` value<br>
to fill with. Let's try with `Right`<br>
<br>
proof :: (Either a (Not a) -> Void) -> Void<br>
proof cont = cont $ Right (\a -> cont (Left a))<br>
<br>
Mind bending. But it does make sense, on the `Right` constructor we<br>
assume we are have an `a` but we have to return a `Void`. Luckily we can<br>
construct a `Void` retaking the path we were gonna follow before filling<br>
with a `Left a`.<br>
<br>
Along the way I had other questions related to the original mail and<br>
given you seem knowledgeable I want to corroborate with you. I've seen<br>
claimed on the web that the CPS transform *is* the double negation [1]<br>
[2]. I don't think that true, it is almost true in my view. I'll<br>
explain, these are the types at hand:<br>
<br>
type DoubleNeg a = (a -> Void) -> Void<br>
type CPS a = forall r. (a -> r) -> r<br>
<br>
We want to see there is an equivalence/isomorphism between the two<br>
types. One implication is trivial<br>
<br>
proof_CPS_DoubleNeg :: forall a. CPS a -> DoubleNeg a<br>
proof_CPS_DoubleNeg cont = cont<br>
<br>
We only specialized `r ~ Void`, which mean we can transform a `CPS a`<br>
into a `DoubleNeg a`. So far so good, we are missing the other<br>
implication<br>
<br>
-- bind type variables: a, r<br>
-- cont :: (a -> Void) -> Void<br>
-- absurd :: forall b. Void -> b<br>
-- cc :: a -> r<br>
proof_DoubleNeg_CPS :: forall a. DoubleNeg a -> CPS a<br>
proof_DoubleNeg_CPS cont = \cc -> absurd $ cont (_missing . cc)<br>
<br>
Trouble, we can't fill `_missing :: r -> Void` as such function only<br>
exists when `r ~ Void` as it must be the empty function. This is why I<br>
don't think `CPS a` is the double negation.<br>
<br>
But I can see how people can get confused. Given a value `x :: a` we can<br>
embed it onto `CPS a` via `return x`. As we saw before we can pass from<br>
`CPS a` to `DoubleNeg a`. So we have *two* ways for passing from `a` to<br>
`DoubleNeg a`, the first one is directly as in the previous mail. The<br>
second one is using `proof_CPS_DoubleNeg`<br>
<br>
embed_onto_DoubleNeg :: a -> DoubleNeg<br>
embed_onto_DoubleNeg = proof_CPS_DoubleNeg . return<br>
where<br>
return :: a -> CPS a<br>
return a = ($ a)<br>
<br>
So CPS is /almost/ the double negation. It is still interesting because<br>
it's enough to embed a classical fragment of logic onto the constructive<br>
fragment (LEM, pierce etc). But calling it a double negation really<br>
tripped me off.<br>
<br>
Am I correct? Or is there other reason why CPS is called the double<br>
negation transformation?<br>
<br>
Thank for your time reading this, I know it was long.<br>
<br>
[1]: <a href="http://jelv.is/talks/curry-howard.html#slide30" rel="noreferrer noreferrer" target="_blank">http://jelv.is/talks/curry-howard.html#slide30</a><br>
[2]:<br>
<a href="https://www.quora.com/What-is-continuation-passing-style-in-functional-programming" rel="noreferrer noreferrer" target="_blank">https://www.quora.com/What-is-continuation-passing-style-in-functional-programming</a><br>
<br>
-- <br>
-- Rubén<br>
-- pgp: 4EE9 28F7 932E F4AD<br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div></div>-- <br><div dir="ltr" data-smartmail="gmail_signature">-- Kim-Ee</div>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div>
</blockquote></div></div>-- <br><div dir="ltr" data-smartmail="gmail_signature">-- Kim-Ee</div>
</div>
</div>
</div>
</div>