7/2/2023 0 Comments Subsume logicThe point is to illustrate in Agda how we can get witnesses from classical proofs that use countable choice. This we can run, and it runs fast enough. Escardo-Oliva countable product of selection functions,įor giving a proof term for classical countable choice, we prove the classical infinite pigeonhole principle in Agda: every infinite boolean sequence has a constant infinite subsequence, where the existential quantification is classical (double negated).Īs a corollary, we get the finite pigeonhole principle, using Friedman's trick to make the existential quantifiers intuitionistic.Berger-Oliva modified bar recursion, or alternatively,.Berardi-Bezem-Coquand functional, or alternatively,.Computation, Constructive math, Guest post, Logic, Programming, TutorialĪs a preparation for my part of a joint tutorial Programs from proofs at MFPS 27 at the end of this month with Ulrich Berger, Monika Seisenberger, and Paulo Oliva, I've developed in Agda some things we've been doing together.Running a classical proof with choice in Agda ![]() Slides with talk notes: lc2014-slides-notes.pdf I shall discuss how one can tackle Turing reducibility constructively via Kleene's number realizability. We may also ask about a constructive treatment of other reducibilities in computability theory. Even better, under Kleene's function realizability interpretation instance reducibility corresponds to Weihrauch reducibility, while Kleene's number realizability relates it to truth-table reducibility. ![]() We may therefore define a notion of instance reducibility, which turns out to have a very rich structure. Most such reductions proceed by reducing an instance of the consequent to an instance of the antecedent. ![]() For instance, it is well known that the Limited principle of omniscience implies that equality of real numbers is decidable. This is joint work with Kazuto Yoshimura from Japan Advanced Institute for Science and Technology.Ībstract: In constructive mathematics we often consider implications between non-constructive reasoning principles. Here are the slides from my Logic Coloquium 2014 talk in Vienna. Constructive math, Logic, Synthetic computability, Talks.Reductions in computability theory from a constructive point of view
0 Comments
Leave a Reply. |