coq-club AT inria.fr
Subject: The Coq mailing list
List archive
- From: Jason Gross <jasongross9 AT gmail.com>
- To: coq-club <coq-club AT inria.fr>
- Cc: mukesh tiwari <mukeshtiwari.iiitm AT gmail.com>
- Subject: Re: [Coq-Club] Intuition behind sig_forall_dec
- Date: Wed, 14 Feb 2024 11:17:10 -0800
- Authentication-results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=jasongross9 AT gmail.com; spf=Pass smtp.mailfrom=jasongross9 AT gmail.com; spf=None smtp.helo=postmaster AT mail-pl1-f174.google.com
- Ironport-data: A9a23:Mjq6Pq9amhZJbfntqnaaDrUDIHqTJUtcMsCJ2f8bNWPcYEJGY0x3y GcfXjjVPq7ZMWaheYp2aY62oEsDuJLTx4VkHFZpripEQiMRo6IpJ/zJdxaqZ3v6wu7rFR88s Z1GMrEsCOhuExcwcz/0auCJQUFUjP3OHPymYAL9EngZbRd+Tys8gg5Ulec8g4p56fC0GArlV ena+qUzA3f7nWYqWo4ow/jb8k835q2u4GlwUmEWPJingneOzxH5M7pEfcldH1OgKqFIE+izQ fr0zb3R1gs1KD9wYj8Nuu+TnnwiGtY+DyDW4pZlc/TKbix5m8AH+v1T2Mzwxqtgo27hc9hZk L2hvHErIOsjFvWkdO81C3G0H8ziVEHvFXCuzXWX6KSuI0P6n3TE6u9yD14OP9Yi1cFTDExTr s0+NxcIcUXW7w626OrTpuhEg80iKIzzONpatCg/kXfWCvEpRZ2FSKLPjTNa9G1o14YeQLCEP pZfMGUzBPjDS0Un1lM/Cpslm+GnnH7kaGxwp1ecpK5x6G/WpOB0+Oe8boSOJ4HXLSlTtlibi 2n/8WLkOB4HO/qWmWO41VCRt9aayEsXX6pJSeTgqa806LGJ/UQYDwRTXl+mq9Gim0umUpReL VYV82wgt8APGFeDS9D8W1igpCfBsEdDB5xfFOo17AzLwa3Ri+qEOoQaZhdbdN85jM1tfxMN8 lKkgojYIyNItaLAHBpx6YyohT+1PCEUK0oLaikFURYJ7rHfTGcb3kKnojFLQP7dszHlJQwc1 Qxmu8TXuln+pcsC1qH+5VSexjz1+cSPQQky6QHaGGmi62uVhbJJhaT5szA3Dt4Zc+51q2VtW lBawqByC8hQVfmweNSlGrllIV1Qz6/t3MfgqVBuBYI90D+m5mSue4tdiBknex82YppVIWCzO hSP0e+02HO1FCv6BUOQS9LhY/nGMYC5TrwJq9iNMoQUOMkuKmdrAgk0Oh7JhAgBb3TAYYlkZ M7DLpfyZZrrIatgyzWySq8c17Rtrh3SNkuCLa0XOy+PiOLEDFbMEeltGALXMogRsvnYyC2Lq I03H5XRlH1ivBjWOXW/HXg7dg1ScRDWxPne96RqSwJ0ClM2SD1wW6CNnOlJlk4Mt/09q9okN 0qVAidwoGcTT1WeQelTQik7M+u9boU1tn8hIy0nMHCh3nVpM87l774Se9FzNfMr/fBqh6w8B fQUWdSyMtIWQBT++hMZccbcqq5mf0+Vng6gBXeuTwU+WJ9CfDb33OHYUDHhzhRTMRrvh/AC+ +Wh8ij5Xas8Qx9TCZeKSfC3kHK0k3svuMNzeErqJNNsVl3m29VoIXapj9scAcIFGTPczBS0i ieUBhY5o7HWgokXqdPmu4GNn72LIcBfQHVIPjD8xqmkEAXn5Uyf+J9kfMfUWCHCRUX21b6HZ +4I/8rjMfYCoklGg7B8H5lv06g6wdnl/J1e8ShJA1TJaEaNGJp7A3zbw/RKiLJB9oVZtSSyR EiL3NtQYpeNGcH9FW8uNBgXVfuC2d4Uiwvtw6wMemui3xBO/Z2DTUl2FDuPgnYELLJKbaUU8 d14s8sSswGCmh4mN+idtR9t9kOOE2chVps2vZRLEa7pjQsWkmt5W6L+MROvwp+zaIRrCHIIc xu0n6vJgopOynXSK0QTEWf/5ssDpJAsli0T8no8CQWooPTniMUz/iVtyhUsbwEMzhx4w+N5Y WdqEEtuJJSxxTRjhekdfmWgBzB+AAa9/2rvwWAoj0zcdVGjDUbWHV0+OMGM3UEXyH1ddT5l5 4OlyH7pfDLpXcPp1A4wZBJBh9n8a+duryvutduCHcuXO7UbOx/enb6Id24EjzDFEPEBrhTLi scy9dkhdJChEzAbppMKLrWz1JMSbUuhD3NDS/Qwx5E5NzjQVx/q0AffNn3rXN1GIsHL1kqKC 8ZOAMZrfDbm3QasqgErP4I9E4VWrtUIuuVbIqjKIFQYuYSxtjBq6ZLc1hbvjV8RHulBr5wPF ZPzRRmjTEqrmnpmq03cppJlO025Q+U+Si/S4eSXyNgNRrU/6LxCUEdqybalnWSnAC0+9TKug Q7zTav3zetj9IdSo7XRAphzXwWaFf6jVcCj0hyCjNBVXNaebebMr1w0r3fkDSR3PJwQechGq rCWlO7dx2b+5bMTb2uBv5yNCaMT6d6AZ7dVOJivLV1xvyiLaOnz6TQtpkG6Lp1olotGx8+FH gGXVuq5ReQ3afx8mkJHTjd4EgkMLZj3YoPLhzKPn97VBjcziQX4fc6ar1n3ZmRlRwo0EpzZC D6snc2x59pd/b9+NDVdC95IW5ZHcULeA404fNjMtB6dPGmionWGnpDAzRMAyzX6OkOoIfbAw 6DuZ0bBLUypmaTy0ttmnZR4vUQXAFZDkOAARB8h1OAsuQ+qLlwtDLo7CooHOKF2gyap9ZDfZ RPxVkUAJxj5fwx5dUTb3Iy+cCaZX+AAA4KsbHhhtUaZcDy/C468EaNsvHUoqWt/fjz4ivqrM 5cC83n3JQK82YxtWf1V3PGgnON73bnP8xrkI6wmfxDaWH7ywInm1UCN2CJIXC3DVtnJzQDFf DdpA29DR06/RAj6FsMIl7u53v0GlGuH8tnqRX7nLBXjV0Gzw+hJyfm5MOb2ulHGRNpfP6YAH BsbWEPUi117GRUvVW8BtNcggKsyAvWOdiR/wGkPWiVK95yNBq8b0w/uUMbBoAzOOOKSLr8Fq gSR3g==
- Ironport-hdrordr: A9a23:7YWB/KP3FLaKEMBcTv6jsMiBIKoaSvp037Dk7TEJdfU1SL3hqy nKpp4mPHDP+VMssR0b6LK90ey7MBDhHP1OgLX5X43SODUO0VHAROpfBMnZowEIcBeOkdK1u5 0QFZSWy+edMbG5t6vHCcWDfOrICePozJyV
- Ironport-phdr: A9a23:K4r8qBFpgzSKPmrYXt2Cl51GfxtFhN3EVzX9CrIZgr5DOp6u447ld BSGo6k33RmQAs6CsaoMy7KP9fy6CSpYudfJmUtBWaIPfidGs/lepxYnDs+BBB+zB9/RRAt+I v5/UkR49WqwK0lfFZW2TVTTpnqv8WxaQU2nZkJ6KevvB4Hdkdm82fys9J3PeQVIgye2ba9vI BmsogjdqM0bjZF/JqszxRfFv2VEd/hLzm9sOV6fggzw68iu8JNg6Shcp+4t+8tdWqjmYqo0S qBVAzshP20p/sPnsgXNQxWS7XUGSGUWlRRIAwnB7B7kW5r6rzX3uOlg1iSEJMP6Vb87Vyis4 KdtUx/olTwINyUl/2HNi8x/l7xUrRS8rBFi2YHUYYWVNP1jfqPBeN4RWGRMUtpNWyFHH4ixa ZYEAegcMuZCt4TyqFUOohm+CweiB+3h1yFGi2Hq0qAhyestDRvL0RY8E94SsnnZqsj+OqcIU eCyyanF1THNYOlN2Tf67ojDbxEvoeuLXbJrasra1E4iFwHfgVWLrozlOTyV1v4Ks2iA9OptU fmii2Eiqw5rozivwt0ghZXOhoIQ013J8zhyz4kpK9OiUkF7fcKkH4VKtyGcL4Z7Qs0sTW9nt is4ybALup62cSgJxZkn2hPSd+CLf5WH7x/tW+icPSl0iXN5dL6jhxi+7Uytx+79W8S0zlpHr yRIn9/RvX4D0BzT79KISvp7/kq53zaAyxrc6v1AIU8ujqXXMZkhwqQ/lpYLtUTDBC72lF/4j K+Mbkkk5vWo6urmYrr4oJ+QLZV7hR3kPqs0hsyzGfo3PRUUU2eB5euwzqDj/U7hTLVLj/02k 7XZsJXDKcsBuq61GgBV0oM55Ba+CzeqysgXnX4CLF5deRKHiZLpO1DUL/ziA/e/mUygkDZtx /DcP73uGI/BImLNkLf7e7t29k1SyBIrwNxB+55ZDqsNLfHzV0PrqtDUExA0Pxapz+vlB9hw0 J4VVHyLAq+EK6PSrUGH5vgyLemNZY4api7wJ+Qj6vXzl3E2g0UdcrOs3ZYPaHC3APBmI0KBb HrpmNgBEGMKshMmTOzulVGOSDBTa2uwUq8z/D07B4WmDYDMRoCpnrONxju0HppTZmxeC1CMF 2nnd5mcVvsSdC6fJtVtnz8EWLS7VYMtyB6juBXnx7dlIefY4igYuoji1Nhx6e3TjxYy9TlsA sSfyW6NVGZ0nmUHRz8s26B/uld9x1OY3Kh3hvxXD91T5/dTXggmMp7cyvR2C9bpVQ3ZZNeGV E6mQsm6ATE2Vt893scCY1xhFNW6khDDwy2qDqcJmLyMHZw4677T33zsJ8lm0HvGz6kgj1w+Q sRVL2Gmh6h/9xLSB4HTiUmZmbyqJuwg23vG837Gxm6TtgkMWwlpFK7BQHo3Z03MrN2/6FmUH JG0DrFyEAJazsjKBbFNccah2VdPX/DlN87ZeHngs2i1DBeMgLiLady5KC0mwCzBBR1cwEgo9 nGcOF1mbs/Ai2fXDTg1UEnqf1up6u5m7nWyUk4zyQiOKUxnzbu8vBAP1rSHU/1G+LUCtW86r ilsWk6n1ofUAsGHoQV7e75HMPsy5V5G0STSsAkudoe4IfVaj0UFOx9yo1uo0hx2Dotals1/r noxywx9M6WDywJpeDaR3JS2MbrSeSHp5B76TanQ1xnF1cqOvKcC7PNts1L4oASgDVYv6V1i2 thRlmOYv9DEVVVOF532VUkz+l5xoLSyjjAVwYTS2DUsNKC1tmSHwNc1HK4+zQ7med5DMaSCH Qu0EssABsHoJvZ4016uJgkJOuxf7stWd4uvaueG1ai3Pe1hgCPujGJJ55p4216N8Cw0Q/DB3 pIMyfWVlgWdUDK0gFCku8Hx0YdKAFNaVmi20i/iC5RWfbYjVYkOAGaqZcaww5Q2hpLgXWJZ6 E/2H0kPi6rLMVKZa13w2xEV1FxC+yT233vliWYtz3dw8fbMuU6Gi/7vfxcGJGNREWxrjFO3Z JOxk8hfR0+wKQ4giBqi40/+galdvqV2aWfJEiIqN2D7KX9vVqyou/+MeclKvdkquD5QVuumZ kuBG5byphIb12XoGG4Ul1VZP3m6/470mRB3kjfXLn9oq3zWY8Zr3kb369nVRPoX1T0DDnod6 3GfFh23ON+n+s+RnpHIv7WlVm6vYZZUdDHi0YKKsCbTCXRCORSkhLjzn9TmFVN/yirnz5xxU j2Oqh/gY47t3qD8MOR9f0AuCkWuo8Z9H4h/lMM3ivRykTAYj46S+3UdlnzoYP1U3Kv/aDwGQ jtDz9PO4Qfj0VFuNTrTn9O/BijbmJI9IYDlPisfwWol4tpPCbuI4bAh/2M9uVe+oQ/LILB8k job1foy+SsfiuANthAqy3bVCbQTEE9EeC30wk7Qvpbu8eMNPTrpKOfshy8c1Zi7AbqPox9RQ iP8c5YmRmpr69lndUnLyDv1453lf9/ZaZQSsAeVmlHOlbswStp5m/wUiC5gIW+4s2cizrtxj xV12pe1po+cMDRF86ewAxoePTrwLZB2mHmlneNFk8Ca0pr6VJdoATINU4HvVun5OD0XvPXjc Q2JFXdvzxXTUaqaFgiZ5kB8qnvJGJ3+LHCbKk4SytB6TQWcLkhS00gEGS83lZkjGkW21dTsJ Q1nsysJ6Aey+X4ugqp4cgPyWWDFqEK0ZycoHdKBeQFO4FgK5l+JY5fDqLsiR2cCosLn9EvXd iSaf1gaUz1PABffQQm9Zv/2ooCRlorQTuumc6mQP/PX8bYYD7HQgsj3mop+o2TSaIPVYigkX 6V9gg0ZBTh4A5iLxG9JEnBRznOXKZbc/UfZmGU/r9jjoqu3Hlu1uM3XTeMVaIsn+gjq0/7bZ 6jJ23k/eXAAkclVjX7QlOpGgwVU0nAyMWHrSfNZ60uvBOrRgvMFVUZKLXMucpISv+RkmVASc c/D1oGvj+A+065zUgYfEwSmw5DhZNRWcTvkahWdXxfNb+7AfXqSkqSVKeuqQLlUxo24rjWWv jCWWw/mNzWHzHzyUgy3dPpLlGedNQBfv4e0dlBsD3LiRZTocE/zNtg/ljAwzbAu4xGCfWcBL ThxdV9MpbyM/GtZhPt4AWlI8ntiK6GNhS+Y6+DSLptev+FsB2x4kOdT4XJyzLUwjmkMXPtuh C7btcJjuXmjm+iLjyJjCV9A82kXwo2MukpmNOPS8ZwBEXfI8RQR7HmBXhQHo9w2b7+n86tUy 9XJiOfyMGIYq4OSrZZaXZGIbpvYbClEU1KhAjPfAQobQCT+MGjegxcYi/SO7jiOqYB8rJHwm Z0IQ7sdVVovF/pcBF42eb5KaJpxQD4glqaWycAS4n/r5hvYX8JcsYrATenDKfrqITedy7JDY lFbpNGwZZRWLYD910F4PxNim5/WHkPLQd1XiihobwtxuEEUtXYnETF11EXiZQegpnQUELTn+ 3x+whs7auMr+jD25l4xLVefvyo8nn46ntD9iCyQejr8RE9RdYRfCi6xr0xod52iHFozYgq1k khpcjzDQuAJ51OFXW9ugQ7Y/5BIHKwEJUWrSBAVzPCTIf4v1AYFwhg=
- Ironport-sdr: 65cd11c5_oDx2TvG+4FOMElmQIuaA9TvKaK7mUkgHDiHwlTnA8XC3D1j 0iIzRqa9aY0v4Z+csdbusLqnR3yn6GUL7AfqVGQ==
I realize belatedly that my explanation mostly duplicates what Hugo had already written, which I had only skimmed. Sorry about that Hugo!
On Wed, Feb 14, 2024, 10:51 Jason Gross <jasongross9 AT gmail.com> wrote:
call/cc does decide the halting problem, just as it allows implementing excluded middle. When you ask it to decide the halting problem, it takes the current continuation, and then claims that your TM never halts. In order to use that proof, you must provide evidence that your TM does halt. When you do this, instead of producing a contradiction, the program uses the continuation to effectively rewind time, and this time it says "in fact your TM does halt" and uses the evidence you gave it.In symbols, if you want A + (A -> False), you get it as (call/cc (fun cc => inr (fun a => cc (inl a)))).Best,Jason GrossOn Wed, Feb 14, 2024, 10:39 Xavier Leroy <xavier.leroy AT college-de-france.fr> wrote:On Wed, Feb 14, 2024 at 11:59 AM Hugo Herbelin <Hugo.Herbelin AT inria.fr> wrote:Hi,
The Limited Principle of Ominiscience (LPO) is indeed rather standard
in the context of the constructive study of real analysis where it
basically amounts to assuming the decidability of the disequality of
Cauchy reals [1]. The Coquelicot paper that Kile Stemen is mentioning
is, I guess, [2], section 3.2, where other applications are given.
There are computational interpretations of this axiomFor some meaning of "computational".but not purely
functional ones. The basic interpretation is as an effectful program
that duplicates its evaluation context, as would be allowed by the
call-with-current-continuation (callcc) operator, or, to some extent,
by setjmp/longjmp in C.The LPO axiom implies that the halting problem is decidable. (Just take P n = "my Turing machine has not terminated yet after n steps".) You're not saying that callcc decides the halting problem, right?Cheers,- Xavier Leroy
So, to vizualise the computation, you have to consider a program p
that uses LPO. For the purpose of a decision that p expects from LPO,
the latter first assumes that (forall n, P n) holds, which is a safe
assumption until p eventually wants to exploit this assumption by
providing some natural number n₀ for which it wants to know (P n₀). At
this time, LPO uses its assumption on the decidability of P to
determine if (P n₀) or ~(P n₀) holds. In the first case, its initial
guess that (forall n, P n) holds is satisfied (for this particular n₀)
and the evaluation of p can go on, until p wants to use the assumption
(forall n, P n) for another n, in which case the process is
repeated. In the second case, LPO changes its mind, which is possible
because it memoized the evaluation context in which it was initially
called. So, it resumes to this former point of the evaluation and now
says that {n | ~P n} holds, taking n₀ as the witness.
Note that alternative computational interpretations of LPO specific to
the form of LPO have been provided, e.g. by Aschieri, Berardi and
Birolo [3].
I can also recommend Phil Wadler's nice story rephrasing in "demonic"
terms the "magic" behind excluded-middle ([4], top of page 7). Since
LPO is the particular instantiation of excluded-middle to
∑⁰₁-formulas, this story applies to LPO too.
In any case, that's a fascinating topic...
Best,
Hugo
[1] https://ncatlab.org/nlab/show/principle+of+omniscience#the_limited_principle_of_omniscience
[2] https://www.lri.fr/~melquion/doc/14-mcs.pdf
[3] https://dmg.tuwien.ac.at/aschieri/RealizabilityforHAEM1-ExceptionsProofs.pdf
[4] https://homepages.inf.ed.ac.uk/wadler/papers/dual/dual.pdf
On Wed, Feb 14, 2024 at 10:15:05AM +0000, mukesh tiwari wrote:
> Thanks Kyle!
>
> Best,
> Mukesh
>
> On Wed, 14 Feb 2024 at 05:12, Kyle Stemen <ncyms8r3x2 AT snkmail.com> wrote:
>
> That's the limited principle of omniscience. The Coquelicot paper explains
> how it's used for classical real analysis.
>
> On Tue, Feb 13, 2024 at 7:02 AM mukesh tiwari
> mukeshtiwari.iiitm-at-gmail.com |coq-club/Example Allow| <
> dsd13c3nm2whb1t AT sneakemail.com> wrote:
>
> Hi everyone,
>
> I was looking into Coq standard library and saw this axioms
> sig_forall_dec [1] by a mere accident. I am trying to understand the
> intuition behind this axiom but my programming intuition simply cannot
> get it. I admit it is a classical axiom but I am finding it very hard
> to wrap my head around it.
>
>
> The way I see *sig_forall_dec* is a function that takes a function P
> --which returns Prop for every natural number-- and a function f
> ((forall n, {P n} + {~P n})) —which takes a natural number return P n
> or ~P n-- and it returns a proof object {n | ~P n} or returns a
> function {forall n, P n}. This whole things, to me, appears like a
> magic because we are turning a function *f* into proof object ({n | ~P
> n}) or a function for which P holds for every natural number ({forall
> n, P n}). I will appreciate if someone can shed a light on the
> intuition behind this magic. I presume it is used in reasoning of real
> numbers so what kind of proofs about real numbers require this axioms?
>
>
>
> Axiom sig_forall_dec
> : forall (P : nat -> Prop),
> (forall n, {P n} + {~P n})
> -> {n | ~P n} + {forall n, P n}.
>
>
> Best,
> Mukesh
>
> [1] https://coq.inria.fr/doc/V8.17.1/stdlib/
> Coq.Reals.ClassicalDedekindReals.html
>
- [Coq-Club] Intuition behind sig_forall_dec, mukesh tiwari, 02/13/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, Kyle Stemen, 02/14/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, mukesh tiwari, 02/14/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, Hugo Herbelin, 02/14/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, Xavier Leroy, 02/14/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, Jason Gross, 02/14/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, Jason Gross, 02/14/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, Hugo Herbelin, 02/15/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, Hugo Herbelin, 02/15/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, Xavier Leroy, 02/16/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, Hugo Herbelin, 02/16/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, Xavier Leroy, 02/17/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, Hugo Herbelin, 02/18/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, Hugo Herbelin, 02/15/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, Jason Gross, 02/14/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, Xavier Leroy, 02/14/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, Hugo Herbelin, 02/14/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, mukesh tiwari, 02/14/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, Kyle Stemen, 02/14/2024
- Re: [Coq-Club] Intuition behind sig_forall_dec, Hugo Herbelin, 02/15/2024
Archive powered by MHonArc 2.6.19+.