Constructive theories usually have interesting metamathematical properties where explicit witnesses can be extracted from proofs of existential sentences. For relational theories, probably the most natural of these is the existence property, EP, sometimes referred to as the set existence property. This states that whenever ϕϕ is provable, there is a formula χχ such that ϕ∧χϕ∧χ is provable. It has been known since the 80s that EP holds for some intuitionistic set theories and yet fails for IZF. Despite this, it has (...) remained open until now whether EP holds for the most well known constructive set theory, CZF. In this paper we show that EP fails for CZF. (shrink)

This article provides a survey of key papers that characterise computable functions, but also provides some novel insights as follows. It is argued that the power of algorithms is at least as strong as functions that can be proved to be totally computable in type-theoretic translations of subsystems of second-order Zermelo Fraenkel set theory. Moreover, it is claimed that typed systems of the lambda calculus give rise naturally to a functional interpretation of rich systems of types and to a hierarchy (...) of ordinal recursive functionals of arbitrary type that can be reduced by substitution to natural number functions. (shrink)

We consider formal theories synonymous with various free categories . Their Lindenbaum algebras may be described as the lattices of subobjects of a terminator. These theories have intuitionistic logic. We show that the Lindenbaum algebras of second order and higher order arithmetic , and set theory are not isomorphic to the Lindenbaum algebras of first order theories such as arithmetic . We also show that there are only five kernels of representations of the free Heyting algebra on one generator in (...) these Lindenbaum algebras. (shrink)

In this paper, we prove that Heyting's arithmetic can be interpreted in an intuitionistic version of Russell's Simple Theory of Types without extensionality.

Especially nice models of intuitionistic set theories are realizability models $V$, where $\mathcal A$ is an applicative structure or partial combinatory algebra. This paper is concerned with the preservation of various choice principles in $V$ if assumed in the underlying universe $V$, adopting Constructive Zermelo–Fraenkel as background theory for all of these investigations. Examples of choice principles are the axiom schemes of countable choice, dependent choice, relativized dependent choice and the presentation axiom. It is shown that any of these axioms (...) holds in $V$ for every applicative structure $\mathcal A$ if it holds in the background universe.1 It is also shown that a weak form of the countable axiom of choice, $\textbf{AC}^{\boldsymbol{\omega, \omega }}$, is rendered true in any $V$ regardless of whether it holds in the background universe. The paper extends work by McCarty and Rathjen. (shrink)

A variant of realizability for Heyting arithmetic which validates Church’s thesis with uniqueness condition, but not the general form of Church’s thesis, was introduced by Lifschitz (Proc Am Math Soc 73:101–106, 1979). A Lifschitz counterpart to Kleene’s realizability for functions (in Baire space) was developed by van Oosten (J Symb Log 55:805–821, 1990). In that paper he also extended Lifschitz’ realizability to second order arithmetic. The objective here is to extend it to full intuitionistic Zermelo–Fraenkel set theory, IZF. The machinery (...) would also work for extensions of IZF with large set axioms. In addition to separating Church’s thesis with uniqueness condition from its general form in intuitionistic set theory, we also obtain several interesting corollaries. The interpretation repudiates a weak form of countable choice, ACω,ω, asserting that a countable family of inhabited sets of natural numbers has a choice function. ACω,ω is validated by ordinary Kleene realizability and is of course provable in ZF. On the other hand, a pivotal consequence of ACω,ω, namely that the sets of Cauchy reals and Dedekind reals are isomorphic, remains valid in this interpretation. Another interesting aspect of this realizability is that it validates the lesser limited principle of omniscience. (shrink)

The first part of the paper introduces the varieties of modern constructive mathematics, concentrating on Bishop's constructive mathematics (BISH). it gives a sketch of both Myhill's axiomatic system for BISH and a constructive axiomatic development of the real line R. The second part of the paper focusses on the relation between constructive mathematics and programming, with emphasis on Martin-L6f 's theory of types as a formal system for BISH.

The aim of this paper is to formulate and study two weak axiom systems for the conceptual framework of constructive set theory . Arithmetical CST is just strong enough to represent the class of von Neumann natural numbers and its arithmetic so as to interpret Heyting Arithmetic. Rudimentary CST is a very weak subsystem that is just strong enough to represent a constructive version of Jensenʼs rudimentary set theoretic functions and their theory. The paper is a contribution to the study (...) of formal systems for CST that capture significant stages in the development of constructive mathematics in CST. (shrink)

Constructive and intuitionistic Zermelo-Fraenkel set theories are axiomatic theories of sets in the style of Zermelo-Fraenkel set theory (ZF) which are based on intuitionistic logic. They were introduced in the 1970's and they represent a formal context within which to codify mathematics based on intuitionistic logic. They are formulated on the basis of the standard first order language of Zermelo-Fraenkel set theory and make no direct use of inherently constructive ideas. In working in constructive and intuitionistic ZF we can thus (...) to some extent rely on our familiarity with ZF and its heuristics. -/- Notwithstanding the similarities with classical set theory, the concepts of set defined by constructive and intuitionistic set theories differ considerably from that of the classical tradition; they also differ from each other. The techniques utilised to work within them, as well as to obtain metamathematical results about them, also diverge in some respects from the classical tradition because of their commitment to intuitionistic logic. In fact, as is common in intuitionistic settings, a plethora of semantic and proof-theoretic methods are available for the study of constructive and intuitionistic set theories. -/- The entry introduces the main features of Constructive and Intuitionistic ZF and offers links to the relevant bibliography. (shrink)

Errett Bishop's work in constructive mathematics is overwhelmingly regarded as a turning point for mathematics based on intuitionistic logic. It brought new life to this form of mathematics and prompted the development of new areas of research that witness today's depth and breadth of constructive mathematics. Surprisingly, notwithstanding the extensive mathematical progress since the publication in 1967 of Errett Bishop's Foundations of Constructive Analysis, there has been no corresponding advances in the philosophy of constructive mathematics Bishop style. The aim of (...) this paper is to foster the philosophical debate about this form of mathematics. I begin by considering key elements of philosophical remarks by Bishop, especially focusing on Bishop's assessment of Brouwer. I then compare these remarks with ``traditional'' philosophical arguments for intuitionistic logic and argue that the latter are in tension with Bishop's views. ``Traditional'' arguments for intuitionistic logic turn out to be also in conflict with significant recent developments in constructive mathematics. This rises pressing questions for the philosopher of mathematics, especially with regard to the possibility of offering alternative philosophical arguments for constructive mathematics. I conclude with the suggestion to look anew at Bishop's own remarks for inspiration. (shrink)