Source author record

Alexandre Miquel

Alexandre Miquel appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.LO Logic in Computer Science

Catalog footprint

What is connected

3works

2topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Implicative algebras: a new foundation for realizability and forcing

We introduce the notion of implicative algebra, a simple algebraic structure intended to factorize the model constructions underlying forcing and realizability (both in intuitionistic and classical logic). The salient feature of this structure is that its elements can be seen both as truth values and as (generalized) realizers, thus blurring the frontier between proofs and types. We show that each implicative algebra induces a (Set-based) tripos, using a construction that is reminiscent from the construction of a realizability tripos from a partial combinatory algebra. Relating this construction with the corresponding constructions in forcing and realizability, we conclude that the class of implicative triposes encompass all forcing triposes (both intuitionistic and classical), all classical realizability triposes (in the sense of Krivine) and all intuitionistic realizability triposes built from partial combinatory algebras.

preprint2014arXiv

Ordered combinatory algebras and realizability

We consider different classes of combinatory structures related to Krivine realizability. We show, in the precise sense that they give rise to the same class of triposes, that they are equivalent for the purpose of modeling higher-order logic. We center our attentions in the role of a special kind of Ordered Combinatory Algebras-- that we call the "Krivine ordered combinatory algebras" ($\mathcal{KOCA}$s)-- that we propose as the foundational pillars for the categorical perspective of Krivine's classical realizability as presented by Streicher. Our procedure is the following: we show that each of the considered combinatory structures gives rise to an indexed preorder, and describe a way to transform the different structures into each other that preserves the associated indexed preorders up to equivalence. Since all structures give rise to the same indexed preorders, we only prove that they are triposes once: for the class of $\mathcal{KOCA}$s. We finish showing that in $\mathcal{KOCA}$s, one can define realizability in every higher-order language and in particular in higher-order arithmetic.

preprint2011arXiv

Existential witness extraction in classical realizability and via a negative translation

We show how to extract existential witnesses from classical proofs using Krivine's classical realizability---where classical proofs are interpreted as lambda-terms with the call/cc control operator. We first recall the basic framework of classical realizability (in classical second-order arithmetic) and show how to extend it with primitive numerals for faster computations. Then we show how to perform witness extraction in this framework, by discussing several techniques depending on the shape of the existential formula. In particular, we show that in the Sigma01-case, Krivine's witness extraction method reduces to Friedman's through a well-suited negative translation to intuitionistic second-order arithmetic. Finally we discuss the advantages of using call/cc rather than a negative translation, especially from the point of view of an implementation.