Computational complexity theory is a subfield of computer science originating in computability theory and the study of algorithms for solving practical mathematical problems. Amongst its aims is classifying problems by their degree of difficulty — i.e., how hard they are to solve computationally. This paper highlights the significance of complexity theory relative to questions traditionally asked by philosophers of mathematics while also attempting to isolate some new ones — e.g., about the notion of feasibility in mathematics, the $\mathbf{P} \neq \mathbf{NP}$ (...) problem and why it has proven hard to resolve, and the role of non-classical modes of computation and proof. (shrink)

Dummett's objections to the coherence of the strict finitist philosophy of mathematics are thus, at the present time at least, ill-taken. We have so far no definitive treatment of Sorites paradoxes; so no conclusive ground for dismissing Dummett's response — the response of simply writing off a large class of familiar, confidently handled expressions as semantically incoherent. I believe that cannot be the right response, if only because it threatens to open an unacceptable gulf between the insight into his own (...) understanding available to a philosophically reflective speaker and the conclusions available to one confined to observing the former's linguistic practice; for an observer of our linguistic practice could never justifiably arrive at the conclusion that ‘red’, ‘child’, etc., are governed by inconsistent rules. But the Sorites is not the subject of this paper. The points I hope to have made plausible are: that a generalized intuitionist position cannot be so much as formulated and that even a most local intuitionism, argued for the special case of arithmetic, is hard pressed effectively to stabilize and defend itself; that strict finitism remains the natural outcome of the anti-realism which Dummett has propounded by way of support for the intuitionist philosophy of mathematics; that it is powerfully buttressed by the ideas of the latter Wittgenstein on rule-following; and that there is no extant compelling reason to suppose that its involvement with predicates of surveyability calls its coherence into question. The correct philosophical assessment of strict finitism, and its proper mathematical exegesis, remain absolutely open, almost virgin issues. This is not a situation which philosophers of mathematics should tolerate very much longer. (shrink)

Reverse mathematics is a program in the foundations of mathematics founded by Friedman and developed extensively by Simpson and others. The aim of RM is to find the minimal axioms needed to prove a theorem of ordinary, that is, non-set-theoretic, mathematics. As suggested by the title, this paper deals with two RM-phenomena, namely, splittings and disjunctions. As to splittings, there are some examples in RM of theorems A, B, C such that A↔, that is, A can be split into two (...) independent parts B and C. As to disjunctions, there are examples in RM of theorems D, E, F such that D↔, that is, D can be written as the disjunction of two independent parts E and F. By contrast, we show in this paper that there is a plethora of splittings and disjunctions in Kohlenbach’s higher-order RM. (shrink)

Reverse mathematics is a program in the foundations of mathematics founded by Friedman and developed extensively by Simpson and others. The aim of RM is to find the minimal axioms needed to prove a theorem of ordinary, that is, non-set-theoretic, mathematics. As suggested by the title, this paper deals with the study of the topological notions of dimension and paracompactness, inside Kohlenbach’s higher-order RM. As to splittings, there are some examples in RM of theorems A, B, C such that A (...) ↔, that is, A can be split into two independent parts B and C, and the aforementioned topological notions give rise to a number of splittings involving highly natural A, B, C. Nonetheless, the higher-order picture is markedly different from the second-one: in terms of comprehension axioms, the proof in higher-order RM of, for example, the paracompactness of the unit interval requires full second-order arithmetic, while the second-order/countable version of paracompactness of the unit interval is provable in the base theory RCA 0. We obtain similarly “exceptional” results for the Urysohn identity, the Lindelöf lemma, and partitions of unity. We show that our results exhibit a certain robustness, in that they do not depend on the exact definition of cover, even in the absence of the axiom of choice. (shrink)

Patrick Grim has put forward a set theoretical argument purporting to prove that omniscience is an inconsistent concept and a model theoretical argument for the claim that we cannot even consistently define omniscience. The former relies on the fact that the class of all truths seems to be an inconsistent multiplicity (or a proper class, a class that is not a set); the latter is based on the difficulty of quantifying over classes that are not sets. We first address the (...) set theoretical argument and make explicit some ways in which it depends on mathematical Platonism. Then we sketch a non Platonistic account of inconsistent multiplicities, based on the notion of indefinite extensibility, and show how Grim’s set theoretical argument could fail to be conclusive in such a context. Finally, we confront Grim’s model theoretical argument suggesting a way to define a being as omniscient without quantifying over any inconsistent multiplicity. (shrink)

In his Tractatus Logico-Philosophicus Ludwig Wittgenstein (1889–1951) presents the concept of order in terms of a notational iteration that is completely logical but not part of logic. Logic for him is not the foundation of mathematical concepts but rather a purely formal way of reflecting the world that at the minimum adds absolutely no content. Order for him is not based on the concepts of logic but is instead revealed through an ideal notational series. He states that logic is “transcendental”. (...) As such it requires an ideal that his philosophical method eventually forces him to reject. I argue that Wittgenstein’s philosophy is more dialectical than transcendental. (shrink)

In this paper some of the history of the development of arithmetic in set theory is traced, particularly with reference to the problem of avoiding the assumption of an infinite set. Although the standard method of singling out a sequence of sets to be the natural numbers goes back to Zermelo, its development was more tortuous than is generally believed. We consider the development in the light of three desiderata for a solution and argue that they can probably not all (...) be satisfied simultaneously. (shrink)

It is a well-known fact of mathematical logic, by now developed in considerable detail, that formalized mathematical theories can be ordered by relative interpretability, and the "strength" of a theory is indicated by where it stands in this ordering. Mutual interpretability is an equivalence relation, and what I call an ordering is a partial ordering modulo this equivalence. Of the theories that have been studied, the natural theories belong to a linearly ordered subset of this ordering.