Movatterモバイル変換

We show that Shoenfield's functional interpretation of Peano arithmetic can be factorized as a negative translation due to J. L. Krivine followed by Gödel's Dialectica interpretation. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim).

Direct download   Export citation   Bookmark   16 citations  

We show how to interpret the language of first-order set theory in an elementary topos endowed with, as extra structure, a directed structural system of inclusions . As our main result, we obtain a complete axiomatization of the intuitionistic set theory validated by all such interpretations. Since every elementary topos is equivalent to one carrying a dssi, we thus obtain a first-order set theory whose associated categories of sets are exactly the elementary toposes. In addition, we show that the full (...) axiom of Separation is validated whenever the dssi is superdirected. This gives a uniform explanation for the known facts that cocomplete and realizability toposes provide models for Intuitionistic Zermelo-Fraenkel set theory. (shrink)

Direct download(3 more)   Export citation   Bookmark   11 citations  

Direct download(5 more)   Export citation   Bookmark   6 citations  

Consistency with the formal Church’s thesis, for short CT, and the axiom of choice, for short AC, was one of the requirements asked to be satisfied by the intensional level of a two-level foundation for constructive mathematics as proposed by Maietti and Sambin From sets and types to topology and analysis: practicable foundations for constructive mathematics, Oxford University Press, Oxford, 2005). Here we show that this is the case for the intensional level of the two-level Minimalist Foundation, for short MF, (...) completed in 2009 by the second author. The intensional level of MF consists of an intensional type theory à la Martin-Löf, called mTT. The consistency of mTT with CT and AC is obtained by showing the consistency with the formal Church’s thesis of a fragment of intensional Martin-Löf’s type theory, called \, where mTT can be easily interpreted. Then to show the consistency of \ with CT we interpret it within Feferman’s predicative theory of non-iterative fixpoints \ by extending the well known Kleene’s realizability semantics of intuitionistic arithmetics so that CT is trivially validated. More in detail the fragment \ we interpret consists of first order intensional Martin-Löf’s type theory with one universe and with explicit substitution rules in place of usual equality rules preserving type constructors -rule which is not valid in our realizability semantics). A key difficulty encountered in our interpretation was to use the right interpretation of lambda abstraction in the applicative structure of natural numbers in order to model all the equality rules of \ correctly. In particular the universe of \ is modelled by means of \-fixpoints following a technique due first to Aczel and used by Feferman and Beeson. (shrink)

Direct download(2 more)   Export citation   Bookmark   2 citations  

Ishiharaʼs boundedness principleBD-N was introduced in Ishihara [5] and has turned out to be most useful for constructive analysis, see e.g. Ishihara [6]. It is equivalent to the statement that every sequentially continuous function from NN to N is continuous w.r.t. the usual metric topology on NN. We construct models for higher order arithmetic and intuitionistic set theory in which both every function from NN to N is sequentially continuous and in which the axiom of choice from NN to N (...) holds. Since the latter is known to be inconsistent with the statement that all functions from NN to N are continuous these models refute BD-N. (shrink)

Direct download(6 more)   Export citation   Bookmark   2 citations  

Direct download(6 more)   Export citation   Bookmark   1 citation  

We investigate a certain system of intuitionistic set theory from three points of view: an elementary set theory with bounded separation, a topos with distinguished inclusions, and a category of classes with a system of small maps. The three presentations are shown to be equivalent in a strong sense.

Direct download   Export citation   Bookmark   1 citation  

In this note we exhibit a continuity principle for real-valued functions on C[–1, 1] that is not validated by realizability over domains although it is validated by Kleene's functional realizability corresponding to Weihrauch's theory of type 2 effectivity.

Direct download   Export citation   Bookmark  

Direct download(3 more)   Export citation   Bookmark  

In this paper we systematically derive a predicate transformer semantics from a direct semantics for a simple probabilistic-nondeterministic programming language . This goal is achieved by exhibiting the direct semantics as isomorphic to a continuation semantics from which the predicate transformer semantics can be read off immediately. This isomorphism allows one to identify nonempty convex compact saturated sets of valuations on the set S of states with certain “good” functionals from to in a way similar to the one how H. (...) Minkowski in 1903 related nonempty convex compact subsets of to what is nowadays called Minkowski functionals. (shrink)

Direct download(4 more)   Export citation   Bookmark  

Direct download(4 more)   Export citation   Bookmark  

Direct download(4 more)   Export citation   Bookmark