The main result of this paper is a transfer theorem which describes the relationship between constructive validity and classical validity for a class of first-order sentences over the p-adics. The proof of one direction of the theorem uses a principle of intuitionism; the proof of the other direction is classically valid. Constructive verifications of known properties of the p-adics are indicated. In particular, the existence of cylindric algebraic decompositions for the p-adics is used.

Bar Induction occupies a central place in Brouwerian mathematics. This note is concerned with the strength of Bar Induction on the basis of Constructive Zermelo-Fraenkel Set Theory, CZF. It is shown that CZF augmented by decidable Bar Induction proves the 1-consistency of CZF. This answers a question of P. Aczel who used Bar Induction to give a proof of the Lusin Separation Theorem in the constructive set theory CZF.

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)

Context: It is often suggested that the methodology of the programme of Constructive Reverse Mathematics (CRM) can be sufficiently clarified by a thorough understanding of Brouwer’s intuitionism, Bishop’s constructive mathematics, and classical Reverse Mathematics. In this paper, the correctness of this suggestion is questioned. Method: We consider the notion of a mathematical programme in order to compare these schools of mathematics in respect of their methodologies. Results: Brouwer’s intuitionism, Bishop’s constructive mathematics, and classical Reverse Mathematics are historical influences upon the (...) origin and development of CRM, but do not give a full “methodological explanation” for it. Implications: Discussion on the methodological issues concerning CRM is needed. Constructivist content: It is shown that the characterisation and comparison of varieties of constructive mathematics should include methodological aspects (as understood from their practices). (shrink)

Brouwer’s intuitionism was a far-reaching attempt to reform the foundations of mathematics. While the mathematical community was reluctant to accept Brouwer’s work, its response to later-developed brands of intuitionism, such as those presented by Hermann Weyl and Arend Heyting, was different. The paper accounts for this difference by analyzing the intuitionistic versions of Brouwer, Weyl, and Heyting in light of a two-tiered model of the body and image of mathematical knowledge. Such a perspective provides a richer account of each story (...) and points to a possible connection between the community’s reaction and the changes each mathematician had proposed. (shrink)

Ranging from Alan Turing’s seminal 1936 paper to the latest work on Kolmogorov complexity and linear logic, this comprehensive new work clarifies the relationship between computability on the one hand and constructivity on the other. The authors argue that even though constructivists have largely shed Brouwer’s solipsistic attitude to logic, there remain points of disagreement to this day. Focusing on the growing pains computability experienced as it was forced to address the demands of rapidly expanding applications, the content maps the (...) developments following Turing’s ground-breaking linkage of computation and the machine, the resulting birth of complexity theory, the innovations of Kolmogorov complexity and resolving the dissonances between proof theoretical semantics and canonical proof feasibility. Finally, it explores one of the most fundamental questions concerning the interface between constructivity and computability: whether the theory of recursive functions is needed for a rigorous development of constructive mathematics. This volume contributes to the unity of science by overcoming disunities rather than offering an overarching framework. It posits that computability’s adoption of a classical, ontological point of view kept these imperatives separated. In studying the relationship between the two, it is a vital step forward in overcoming the disagreements and misunderstandings which stand in the way of a unifying view of logic. (shrink)

Gentzen’s approach by transfinite induction and that of intuitionist Heyting arithmetic to completeness and the self-foundation of mathematics are compared and opposed to the Gödel incompleteness results as to Peano arithmetic. Quantum mechanics involves infinity by Hilbert space, but it is finitist as any experimental science. The absence of hidden variables in it interpretable as its completeness should resurrect Hilbert’s finitism at the cost of relevant modification of the latter already hinted by intuitionism and Gentzen’s approaches for completeness. This paper (...) investigates both conditions and philosophical background necessary for that modification. The main conclusion is that the concept of infinity as underlying contemporary mathematics cannot be reduced to a single Peano arithmetic, but to at least two ones independent of each other. Intuitionism, quantum mechanics, and Gentzen’s approaches to completeness an even Hilbert’s finitism can be unified from that viewpoint. Mathematics may found itself by a way of finitism complemented by choice. The concept of information as the quantity of choices underlies that viewpoint. Quantum mechanics interpretable in terms of information and quantum information is inseparable from mathematics and its foundation. (shrink)

This dissertation examines several of the problems that Hilbert discovered in the foundations of mathematics, from a metalogical perspective. The problems manifest themselves in four different aspects of Hilbert’s views: (i) Hilbert’s axiomatic approach to the foundations of mathematics; (ii) His response to criticisms of set theory; (iii) His response to intuitionist criticisms of classical mathematics; (iv) Hilbert’s contribution to the specification of the role of logical inference in mathematical reasoning. This dissertation argues that Hilbert’s axiomatic approach was guided primarily (...) by model theoretical concerns. Accordingly, the ultimate aim of his consistency program was to prove the model-theoretical consistency of mathematical theories. It turns out that for the purpose of carrying out such consistency proofs, a suitable modification of the ordinary first-order logic is needed. To effect this modification, independence-friendly logic is needed as the appropriate conceptual framework. It is then shown how the model theoretical consistency of arithmetic can be proved by using IF logic as its basic logic. Hilbert’s other problems, manifesting themselves as aspects (ii), (iii), and (iv)—most notably the problem of the status of the axiom of choice, the problem of the role of the law of excluded middle, and the problem of giving an elementary account of quantification—can likewise be approached by using the resources of IF logic. It is shown that by means of IF logic one can carry out Hilbertian solutions to all these problems. The two major results concerning aspects (ii), (iii) and (iv) are the following: (a) The axiom of choice is a logical principle; (b) The law of excluded middle divides metamathematical methods into elementary and non-elementary ones. It is argued that these results show that IF logic helps to vindicate Hilbert’s nominalist philosophy of mathematics. On the basis of an elementary approach to logic, which enriches the expressive resources of ordinary first-order logic, this dissertation shows how the different problems that Hilbert discovered in the foundations of mathematics can be solved. (shrink)

A set theory model of reality, representation and language based on the relation of completeness and incompleteness is explored. The problem of completeness of mathematics is linked to its counterpart in quantum mechanics. That model includes two Peano arithmetics or Turing machines independent of each other. The complex Hilbert space underlying quantum mechanics as the base of its mathematical formalism is interpreted as a generalization of Peano arithmetic: It is a doubled infinite set of doubled Peano arithmetics having a remarkable (...) symmetry to the axiom of choice. The quantity of information is interpreted as the number of elementary choices (bits). Quantum information is seen as the generalization of information to infinite sets or series. The equivalence of that model to a quantum computer is demonstrated. The condition for the Turing machines to be independent of each other is reduced to the state of Nash equilibrium between them. Two relative models of language as game in the sense of game theory and as ontology of metaphors (all mappings, which are not one-to-one, i.e. not representations of reality in a formal sense) are deduced. (shrink)

The classical forms of both modified realizability and relative realizability are naturally described in terms of the Sierpinski topos. The paper puts these two observations together and explains abstractly the existence of the geometric morphisms and logical functors connecting the various toposes at issue. This is done by advancing the theory of triposes over internal partial combinatory algebras and by employing a novel notion of elementary map.

We review and contrast three ways to make up a formal Euclidean geometry which one might call constructive, in a computational sense. The starting point is the first-order geometry created by Tarski.

In this paper it is argued that the understanding of Brouwer as replacing truth conditions with assertability or proof conditions, in particular as codified in the so-called Brouwer-Heyting-Kolmogorov Interpretation, is misleading and conflates a weak and a strong notion of truth that have to be kept apart to understand Brouwer properly: truth-as-anticipation and truth- in-content. These notions are explained, exegetical documentation provided, and semi-formal recursive definitions are given.

S. SHAPIRO (ed.), Intensional Mathematics (Studies in Logic and the Foundations of Mathematics, vol. 11 3). Amsterdam: North-Holland, 1985. v + 230 pp. $38.50/100Df.

What an intuitionist may refer to with respect to a given epistemic state depends not only on that epistemic state itself but on whether it is viewed concurrently from within, in the hindsight of some later state, or ideally from a standpoint “beyond” all epistemic states (though the latter perspective is no longer strictly intuitionistic). Each of these three perspectives has a different—and, in the last two cases, a novel—logic and semantics. This paper explains these logics and their semantics and (...) provides soundness and completeness proofs. It provides, moreover, a critique of some common versions of Kripke semantics for intuitionistic logic and suggests ways of modifying them to take account of the perspective-relativity of reference. (shrink)

ABSTRACT: It is argued that the equivalence, which is usually postulated to hold between infinite descent and transfinite induction in the foundations of arithmetic uses the law of excluded middle through the use of a double negation on the infinite set of natural numbers and therefore cannot be admitted in intuitionistic logic and mathematics, and a fortiori in more radical constructivist foundational schemes. Moreover it is shown that the infinite descent used in Dedekind-Peano arithmetic does not correspond to the infinite (...) descent of classical Fermatian arithmetic or number theory. However, from the point of view of classical logic, the principles of complete induction and transfinite induction, the least number principle and infinite descent are all equivalent. We find here a focal point for a foundational critique that aims for a a clarification of philosophical options in the foundations of logic and mathematics. (shrink)

Intuitionistically. a set has to be given by a finite construction or by a construction-project generating the elements of the set in the course of time. Quantification is only meaningful if the range of each quantifier is a well-circumscribed set. Thinking upon the meaning of quantification, one is led to insights?in particular, the so-called continuity principles?which are surprising from a classical point of view. We believe that such considerations lie at the basis of Brouwer?s reconstruction of mathematics. The predicate ?α (...) is lawless? is not acceptable, the lawless sequences do not form a well-circumscribed intuitionistic set, and quantification over lawless sequences does not make sense. (shrink)

In this paper, we deal with a relationship among the law of excluded middle, the double negation elimination and the independence of premiss rule ) for intuitionistic predicate logic. After giving a general machinery, we give, as corollaries, several examples of extensions of \ and \ which are closed under \ but do not derive the independence of premiss axiom.

Realizabilities are powerful tools for establishing consistency and independence results for theories based on intuitionistic logic. Troelstra discovered principles ECT 0 and GC 1 which precisely characterize formal number and function realizability for intuitionistic arithmetic and analysis, respectively. Building on Troelstra's results and using his methods, we introduce the notions of Church domain and domain of continuity in order to demonstrate the optimality of “almost negativity” in ECT 0 and GC 1 ; strengthen “double negation shift” DNS 0 to DNS (...) 1 and use it with GC 1 and Markov's Principle MP to characterize the classically provably realizable formulas of analysis; and show that intuitionistic analysis with GC 1 , MP and DNS 1 is consistent and satisfies Troelstra's and Church's Rules. We end with a discussion of semi-intuitionistic theories and a conjecture. (shrink)