For the purposes of this monograph, "by a degree" is meant a degree of recursive unsolvability. A degree [script bold]m is said to be minimal if 0 is the unique degree less than [script bold]m. Each of the six chapters of this self-contained monograph is devoted to the proof of an existence theorem for minimal degrees.

v. 1. Recursive model theory -- v. 2. Recursive algebra, analysis and combinatorics.

A metric space is said to be locally non-compact if every neighborhood contains a sequence that is eventually bounded away from every element of the space, hence contains no accumulation point. We show within recursive mathematics that a nonvoid complete metric space is locally non-compact iff it is without isolated points.The result has an interesting consequence in computable analysis: If a complete metric space has a computable witness that it is without isolated points, then every neighborhood contains a (...) computable sequence that is eventually computably bounded away from every computable element of the space. (shrink)

We examine a number of results of infinite combinatorics using the techniques of reverse mathematics. Our results are inspired by similar results in recursive combinatorics. Theorems included concern colorings of graphs and bounded graphs, Euler paths, and Hamilton paths.

We give a survey of the study of nonstandard models in recursion theory and reverse mathematics. We discuss the key notions and techniques in effective computability in nonstandard models. and their applications to problems concerning combinatorial principles in subsystems of second order arithmetic. Particular attention is given to principles related to Ramsey's Theorem for Pairs.

We give a survey of the study of nonstandard models in recursion theory and reverse mathematics. We discuss the key notions and techniques in effective computability in nonstandard models, and their applications to problems concerning combinatorial principles in subsystems of second order arithmetic. Particular attention is given to principles related to Ramsey’s Theorem for Pairs.

Gert H. Müller The growth of the number of publications in almost all scientific areas,· as in the area of (mathematical) logic, is taken as a sign of our scientifically minded culture, but it also has a terrifying aspect. In addition, given the rapidly growing sophistica tion, specialization and hence subdivision of logic, researchers, students and teachers may have a hard time getting an overview ofthe existing literature, partic ularly if they do not have an extensive library available in their (...) neighbourhood: they simply do not even know what to ask for! More specifically, if someone vaguely knows that something vaguely connected with his interests exists some where in the literature, he may not be able to find it even by searching through the publications scattered in the review journals. Answering this challenge was and is the central motivation for compiling this Bibliography. The Bibliography comprises (presently) the following six volumes (listed with the corresponding Editors): I. Classical Logic W. Rautenberg II. Non-c1assical Logics W. Rautenberg IH. Model Theory H. -D. Ebbinghaus IV. Recursion Theory P. G. Hinman V. Set Theory A. R. Blass VI. ProofTheory; Constructive Mathematics J. E. Kister; D. van Dalen & A. S. Troelstra. (shrink)

In the context of reverse mathematics, effective transfinite recursion refers to a principle that allows us to construct sequences of sets by recursion along arbitrary well orders, provided that each set is ‐definable relative to the previous stages of the recursion. It is known that this principle is provable in. In the present note, we argue that a common formulation of effective transfinite recursion is too restrictive. We then propose a more liberal formulation, which appears very natural and is (...) still provable in. (shrink)

The Dutch mathematician and philosopher L. E. J. Brouwer (1881-1966) developed a foundation for mathematics called 'intuitionism'. Intuitionism considers mathematics to consist in acts of mental construction based on internal time awareness. According to Brouwer, that awareness provides the fundamental structure to all exact thinking. In this note, it will be shown how this strand of thought leads to an intuitionistic function that is effectively computable yet non-recursive.

In mathematics, various representations of real numbers have been investigated. All these representations are mathematically equivalent because they lead to the same real structure - Dedekind-complete ordered field. Even the effective versions of these representations are equivalent in the sense that they define the same notion of computable real numbers. Although the computable real numbers can be defined in various equivalent ways, if computable is replaced by primitive recursive (p. r., for short), these definitions lead to a number (...) of different concepts, which we compare in this article. We summarize the known results and add new ones. In particular we show that there is a proper hierarchy among p. r. real numbers by nested interval representation, Cauchy representation, b -adic expansion representation, Dedekind cut representation, and continued fraction expansion representation. Our goal is to clarify systematically how the primitive recursiveness depends on the representations of the real numbers. (shrink)

This volume contains papers from the recursion theory session of the Kazan Workshop on Recursion and Complexity Theory. Recursion theory, the study of computability, is an area of mathematical logic that has traditionally been particularly strong in the United States and the former Soviet Union. This was the first workshop ever to bring together about 50 international experts in recursion theory from the United States, the former Soviet Union and Western Europe.

This volume presents the lecture notes of short courses given by three leading experts in mathematical logic at the 2012 Asian Initiative for Infinity Logic Summer School. The major topics cover set-theoretic forcing, higher recursion theory, and applications of set theory to C*-algebra. This volume offers a wide spectrum of ideas and techniques introduced in contemporary research in the field of mathematical logic to students, researchers and mathematicians.

Most of what is told in this paper has been told before by the same author, in a number of publications of various kinds, but this is the first time that all this material has been brought together and treated in a uniform way. Smaller errors in the earlier publications are corrected here without comment. It has been known since the 1920s that quadratic equations played a prominent role in Babylonian mathematics. See, most recently, Høyrup (Hist Sci 34:1–32, 1996, (...) and Lengths, widths, surfaces: a portrait of old Babylonian algebra and its kin. Springer, New York, 2002). What has not been known, however, is how quadratic equations came to play that role, since it is difficult to think of any practical use for quadratic equations in the life and work of a Babylonian scribe. One goal of the present paper is to show how the need to find solutions to quadratic equations actually arose in Mesopotamia not later than in the second half of the third millennium BC, and probably before that in connection with certain geometric division of property problems. This issue was brought up for the first time in Friberg (Cuneiform Digit Lib J 2009:3, 2009). In this connection, it is argued that the tool used for the first exact solution of a quadratic equation was either a clever use of the “conjugate rule” or a “completion of the square,” but that both methods ultimately depend on a certain division of a square, the same in both cases. Another, closely related goal of the paper is to discuss briefly certain of the most impressive achievements of anonymous Babylonian mathematicians in the first half of the second millennium BC, namely recursive geometric algorithms for the solution of various problems related to division of figures, more specifically trapezoidal fields. For an earlier, comprehensive (but less accessible) treatment of these issues, see Friberg (Amazing traces of a Babylonian origin in Greek mathematics. WorldScientific, Singapore 2007b, Ch. 11 and App. 1). (shrink)