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)

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

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)

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.

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.

The paper discusses different approaches to the concept of recursion and its evolution from mathematics to cognitive studies. Such approaches are observed as: self‑embedded structures, multiple hierarchical levels using the same rule, and embedding structures within structures. The paper also discusses the concept of meta‑recursion. Examining meta‑recursion may enable understanding of the ability to apply recursive processes to multilayered hierarchies, with recursive procedures acting as generators. These types of recursive processes could be the fundamental elements of (...) general cognition. The paper also briefly discusses the role of probability in current recursive approaches to cognition. It is conjenctured that the hierarchical mechanism of cognition demonstrates a kind of meta‑recursion in the sense that recursive neural loops may support some primitive recursive cognitive processes, which in turn account for recursiveness of language grammars, space orientation, social cognition, etc. The study indicates that using multiple approaches to understand the phenomenon of recursion can provide a more complete understanding of the complexity of recursion, as it plays a significant role in fields like language, mathematics, and cognitive science. (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)

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)

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.

The objective of this paper is to present the truth tables method of the propositional calculus of Tractatus Logico-Philosophicus as a result of computational procedures involving recursive operations in mathematics, since the secondary literature that is involved with such a problem fails to demonstrate such aspect of the work. The proposal is to demonstrate the base calculation of the truth operations as a consequence of the application of mathematical resources that involve the notion of recursivity, inspired both in (...) the natural numbers as well as in the factorial calculus, as well as in the procedures recommended by the combinatorial analysis and the calculation of probability. It is hoped, therefore, to present the truth operations of the propositional calculus as coming from the application of arithmetic to the logical resources. (shrink)

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.

The present volume is intended as an all-round introduction to constructivism. Here constructivism is to be understood in the wide sense, and covers in particular Brouwer's intuitionism, Bishop's constructivism and A.A. Markov's constructive recursive mathematics. The ending "-ism" has ideological overtones: "constructive mathematics is the (only) right mathematics"; we hasten, however, to declare that we do not subscribe to this ideology, and that we do not intend to present our material on such a basis.

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” , 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 focuses on recursion and reveals a host of new theoretical arguments, philosophical perspectives, formal representations, and empirical evidence from parsing, acquisition, and computer models, highlighting its central role in modern science. Noam Chomsky, whose work introduced recursion to linguistics and cognitive science, and other leading researchers in the fields of philosophy, semantics, computer science, and psycholinguistics in showing the profound reach of this concept into modern science. Recursion has been at the heart of generative grammar from the outset. (...) Recent work in minimalism has put it at center-stage with a wide range of consequences across the intellectual landscape. The contributors to this volume both advance the field and provide a cross-sectional view of the place that recursion takes in modern science. (shrink)

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)

What can computers do in principle? What are their inherent theoretical limitations? These are questions to which computer scientists must address themselves. The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function: intuitively a function whose values can be calculated in an effective or automatic way. This book is an introduction to computability theory (or recursion theory as it is traditionally known to mathematicians). Dr Cutland (...) begins with a mathematical characterisation of computable functions using a simple idealised computer (a register machine); after some comparison with other characterisations, he develops the mathematical theory, including a full discussion of non-computability and undecidability, and the theory of recursive and recursively enumerable sets. The later chapters provide an introduction to more advanced topics such as Gildel's incompleteness theorem, degrees of unsolvability, the Recursion theorems and the theory of complexity of computation. Computability is thus a branch of mathematics which is of relevance also to computer scientists and philosophers. Mathematics students with no prior knowledge of the subject and computer science students who wish to supplement their practical expertise with some theoretical background will find this book of use and interest. (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.

A real number is recursively approximable if there is a computable sequence of rational numbers converging to it. If some extra condition to the convergence is added, then the limit real number might have more effectivity. In this note we summarize some recent attempts to classify the recursively approximable real numbers by the convergence rates of the corresponding computable sequences ofr ational numbers.

Reverse mathematics is a program in mathematical logic that seeks to give precise answers to the question of which axioms are necessary in order to prove theorems of "ordinary mathematics": roughly speaking, those concerning structures that are either themselves countable, or which can be represented by countable "codes". This includes many fundamental theorems of real, complex, and functional analysis, countable algebra, countable infinitary combinatorics, descriptive set theory, and mathematical logic. This entry aims to give the reader a broad (...) introduction to the history, methodology, and results of the reverse mathematics program, with a particular focus on its connections to foundational programs such as finitism, constructivism, and predicativism. (shrink)

Alex has written an excellent thesis in the area of computable model theory. The latter is a subject that nicely combines model-theoretic ideas with delicate recursiontheoretic constructions. The results demand good knowledge of both fields. In his thesis, Alex begins by reviewing the essential model-theoretic facts, especially the Baldwin-Lachlan result about uncountably categorical theories. This he follows with a brief discussion of recursion theory, including mention of the priority method. The deepest part of the thesis concerns the study of the (...) recursive spectrum of an uncountably categorical theory, i.e. the set of n ≤ ! such that the n-th model of the theory (in the Baldwin-Lachlan sense) has a computable presentation. This is a deep and very active area of conteporary research in computable model theory which Alex discusses in considerable detail. The exposition is very good and therefore the thesis makes a nice introduction to the subject for a wide community of logicians. (Sy-David Friedman, Professor of Mathematical Logic, Director of the Kurt Godel Research Center for Mathematical Logic, University of Vienna). (shrink)

We investigate the upper semilattice Eq* of recursively enumerable equivalence relations modulo finite differences. Several natural subclasses are shown to be first-order definable in Eq*. Building on this we define a copy of the structure of recursively enumerable many-one degrees in Eq*, thereby showing that Th has the same computational complexity as the true first-order arithmetic.

We give recursion-theoretic characterizations of the counting class $\textsf {\#P}$, the class of those functions which count the number of accepting computations of non-deterministic Turing machines working in polynomial time. Moreover, we characterize in a recursion-theoretic manner all the levels $\{\textsf {\#P} _k\}_{k\in {\mathbb {N}}}$ of the counting hierarchy of functions $\textsf {FCH}$, which result from allowing queries to functions of the previous level, and $\textsf {FCH}$ itself as a whole. This is done in the style of (...) Bellantoni and Cook’s safe recursion, and it places $\textsf {\#P}$ in the context of implicit computational complexity. Namely, it relates $\textsf {\#P}$ with the implicit characterizations of $\textsf {FPTIME}$ (Bellantoni and Cook, Comput Complex 2:97–110, 1992) and $\textsf {FPSPACE}$ (Oitavem, Math Log Q 54(3):317–323, 2008), by exploiting the features of the tree-recursion scheme of $\textsf {FPSPACE}$. (shrink)