Stephen Cole Kleene was one of the greatest logicians of the twentieth century and this book is the influential textbook he wrote to teach the subject to the next generation. It was first published in 1952, some twenty years after the publication of Godel's paper on the incompleteness of arithmetic, which marked, if not the beginning of modern logic. The 1930s was a time of creativity and ferment in the subject, when the notion of computable moved from the realm of (...) philosophical speculation to the realm of science. This was accomplished by the work of Kurt Gode1, Alan Turing, and Alonzo Church, who gave three apparently different precise definitions of computable. When they all turned out to be equivalent, there was a collective realization that this was indeed the right notion. Kleene played a key role in this process. One could say that he was there at the beginning of modern logic. He showed the equivalence of lambda calculus with Turing machines and with Godel's recursion equations, and developed the modern machinery of partial recursive functions. This textbook played an invaluable part in educating the logicians of the present. It played an important role in their own logical education.". (shrink)

V. Lifschitz defined in 1979 a variant of realizability which validates Church's thesis with uniqueness condition, but not the general form of Church's thesis. In this paper we describe an extension of intuitionistic arithmetic in which the soundness of Lifschitz' realizability can be proved, and we give an axiomatic characterization of the Lifschitz-realizable formulas relative to this extension. By a "q-variant" we obtain a new derived rule. We also show how to extend Lifschitz' realizability to second-order arithmetic. Finally we describe (...) an analogous development for elementary analysis, with partial continuous application replacing partial recursive application. (shrink)

This is an introduction to, and survey of, the constructive approaches to pure mathematics. The authors emphasise the viewpoint of Errett Bishop's school, but intuitionism. Russian constructivism and recursive analysis are also treated, with comparisons between the various approaches included where appropriate. Constructive mathematics is now enjoying a revival, with interest from not only logicans but also category theorists, recursive function theorists and theoretical computer scientists. This account for non-specialists in these and other disciplines.

We give an overview of the role of equicontinuity of sequences of real-valued functions on [0,1] and related notions in classical mathematics, intuitionistic mathematics, Bishop’s constructive mathematics, and Russian recursive mathematics. We then study the logical strength of theorems concerning these notions within the programme of Constructive Reverse Mathematics. It appears that many of these theorems, like a version of Ascoli’s Lemma, are equivalent to fan-theoretic principles.

This article presents a weak system of intuitionistic second-order arithmetic, WKV, a subsystem of the one in S.C. Kleene, R.E. Vesley [The Foundations of Intuitionistic Mathematics: Especially in Relation to Recursive Functions, North-Holland Publishing Company, Amsterdam, 1965]. It is then shown that some statements of real analysis, like a version of the Heine–Borel Theorem, and some statements of logic, e.g. compactness of classical proposition calculus, are equivalent to the Fan Theorem in this system.