There can be no doubt about the value of Frege's contributions to the philosophy of mathematics. First, he invented quantification theory and this was the first step toward making precise the notion of a purely logical deduction. Secondly, he was the first to publish a logical analysis of the ancestral R* of a relation R, which yields a definition of R* in second-order logic.1 Only a narrow and arid conception of philosophy would exclude these two achievements. Thirdly and very importantly, (...) the discussion in §§58-60 of the G r u n d l a g e n defends a conception of mathematical existence, to be found in Cantor (1883) and later in the writings of Dedekind and Hilbert, by basing it upon considerations about meaning which have general application, outside mathematics.2.. (shrink)

There is no uniquely standard concept of an effectively decidable set of real numbers or real n-tuples. Here we consider three notions: decidability up to measure zero [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382], which we abbreviate d.m.z.; recursive approximability [or r.a.; K.-I. Ko, Complexity Theory of Real Functions, Birkhäuser, Boston, 1991]; and decidability ignoring boundaries [d.i.b.; W.C. Myrvold, The decision problem for entanglement, in: R.S. (...) Cohen et al. (Eds.), Potentiality, Entanglement, and Passion-at-a-Distance: Quantum Mechanical Studies fo Abner Shimony, Vol. 2, Kluwer Academic Publishers, Great Britain, 1997, pp. 177–190]. Unlike some others in the literature, these notions apply not only to certain nice sets, but to general sets in Rn and other appropriate spaces. We consider some motivations for these concepts and the logical relations between them. It has been argued that d.m.z. is especially appropriate for physical applications, and on Rn with the standard measure, it is strictly stronger than r.a. [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382]. Here we show that this is the only implication that holds among our three decidabilities in that setting. Under arbitrary measures, even this implication fails. Yet for intervals of non-zero length, and more generally, convex sets of non-zero measure, the three concepts are equivalent. (shrink)

The behavior of some systems is non-computable in a precise new sense. One infamous problem is that of the stability of the solar system: Given the initial positions and velocities of several mutually gravitating bodies, will any eventually collide or be thrown off to infinity? Many have made vague suggestions that this and similar problems are undecidable: no finite procedure can reliably determine whether a given configuration will eventually prove unstable. But taken in the most natural way, this is trivial. (...) The state of a system corresponds to a point in a continuous space, and virtually no set of points in space is strictly decidable. A new, more pragmatic concept is therefore introduced: a set is decidable up to measure zero (d.m.z.) if there is a procedure to decide whether a point is in that set and it only fails on some points that form a set of zero volume. This is motivated by the intuitive correspondence between volume and probability: we can ignore a zero-volume set of states because the state of an arbitrary system almost certainly will not fall in that set. D.m.z. is also closer to the intuition of decidability than other notions in the literature, which are either less strict or apply only to special sets, like closed sets. Certain complicated sets are not d.m.z., most remarkably including the set of known stable orbits for planetary systems (the KAM tori). This suggests that the stability problem is indeed undecidable in the precise sense of d.m.z. Carefully extending decidability concepts from idealized models to actual systems, we see that even deterministic aspects of physical behavior can be undecidable in a clear and significant sense. (shrink)

Foundations of a General Theory of Manifolds [Cantor, 1883], which I will refer to as the Grundlagen, is Cantor’s first work on the general theory of sets. It was a separate printing, with a preface and some footnotes added, of the fifth in a series of six papers under the title of “On infinite linear point manifolds”. I want to briefly describe some of the achievements of this great work. But at the same time, I want to discuss its connection (...) with the so-called paradoxes in set theory. There seems to be some agreement now that Cantor’s own understanding of the theory of transfinite numbers in that monograph did not contain an implicit contradiction; but there is less agreement about exactly why this is so and about the content of the theory itself. For various reasons, both historical and internal, the Grundlagen seems not to have been widely read compared to later works of Cantor, and to have been even less well understood. But even some of the more recent discussions of the work, while recognizing to some degree its unique character, misunderstand it on crucial points and fail to convey its true worth. (shrink)