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)

In this multi-disciplinary investigation we show how an evidence-based perspective of quantification---in terms of algorithmic verifiability and algorithmic computability---admits evidence-based definitions of well-definedness and effective computability, which yield two unarguably constructive interpretations of the first-order Peano Arithmetic PA---over the structure N of the natural numbers---that are complementary, not contradictory. The first yields the weak, standard, interpretation of PA over N, which is well-defined with respect to assignments of algorithmically verifiable Tarskian truth values to the formulas of PA under the interpretation. (...) The second yields a strong, finitary, interpretation of PA over N, which is well-defined with respect to assignments of algorithmically computable Tarskian truth values to the formulas of PA under the interpretation. We situate our investigation within a broad analysis of quantification vis a vis: * Hilbert's epsilon-calculus * Goedel's omega-consistency * The Law of the Excluded Middle * Hilbert's omega-Rule * An Algorithmic omega-Rule * Gentzen's Rule of Infinite Induction * Rosser's Rule C * Markov's Principle * The Church-Turing Thesis * Aristotle's particularisation * Wittgenstein's perspective of constructive mathematics * An evidence-based perspective of quantification. By showing how these are formally inter-related, we highlight the fragility of both the persisting, theistic, classical/Platonic interpretation of quantification grounded in Hilbert's epsilon-calculus; and the persisting, atheistic, constructive/Intuitionistic interpretation of quantification rooted in Brouwer's belief that the Law of the Excluded Middle is non-finitary. We then consider some consequences for mathematics, mathematics education, philosophy, and the natural sciences, of an agnostic, evidence-based, finitary interpretation of quantification that challenges classical paradigms in all these disciplines. (shrink)

This paper proposes a formal framework for the cognitive relation understood as an ordered pair with the cognitive subject and object of cognition as its members. The cognitive subject is represented as consisting of a language, conequence relation and a stock of accepted theories, and the object as a model of those theories. This language allows a simple formulation of the realism/anti-realism controversy. In particular, Tarski’s undefinability theorem gives a philosophical argument for realism in epistemology.

This paper investigates relations between truth and consistency. The basic intuition is that truth implies consistency, but the reverse dependence fails. However, this simple account leads to some troubles, due to some metalogical results, in particular the Gödel-Malcev completeness theorem. Thus, a more advanced analysis is required. This is done by employing the concept of ω-consistency and ω-inconsistency. Both concepts motivate that the concept of the standard truth should be introduced as well. The results are illustrated by an interpretation of (...) the well-known logical square and its generalization. (shrink)

This paper investigates the determinacy of mathematics. We begin by clarifying how we are understanding the notion of determinacy before turning to the questions of whether and how famous independence results bear on issues of determinacy in mathematics. From there, we pose a metasemantic challenge for those who believe that mathematical language is determinate, motivate two important constraints on attempts to meet our challenge, and then use these constraints to develop an argument against determinacy and discuss a particularly popular approach (...) to resolving indeterminacy, before offering some brief closing reflections. We believe our discussion poses a serious challenge for most philosophical theories of mathematics, since it puts considerable pressure on all views that accept a non-trivial amount of determinacy for even basic arithmetic. (shrink)

Certain mathematical objects bear the name “pathological”. They either occur as unexpected and unwilling in mathematical research practice, or are constructed deliberately, for instance in order to delimit the scope of application of a theorem. I discuss examples of mathematical pathologies and the circumstances of their emergence. I focus my attention on the creative role of pathologies in the development of mathematics. Finally, I propose a few reflections concerning the degree of cognitive accessibility of mathematical objects. I believe that the (...) problems discussed in the paper may attract the attention of philosophers interested in concept formation and the development of mathematical ideas. (shrink)

In the paper the problem of definability and undefinability of the concept of satisfaction and truth is considered. Connections between satisfaction and truth on the one hand and consistency of certain systems of omega-logic and transfinite induction on the other are indicated.

A dialectical contradiction can be appropriately described within the framework of classical formal logic. It is in harmony with the law of noncontradiction. According to our definition, two theories make up a dialectical contradiction if each of them is consistent and their union is inconsistent. It can happen that each of these two theories has an intended model. Plenty of examples are to be found in the history of science.

Computationalism holds that our grasp of notions like ‘computable function’ can be used to account for our putative ability to refer to the standard model of arithmetic. Tennenbaum's Theorem has been repeatedly invoked in service of this claim. I will argue that not only do the relevant class of arguments fail, but that the result itself is most naturally understood as having the opposite of a reference-fixing effect — i.e., rather than securing the determinacy of number-theoretic reference, Tennenbaum's Theorem points (...) towards a sense in which portions of our computational vocabulary should be regarded as model-relative. (shrink)

One of the popular explications of the deflationary tenet of ‘thinness’ of truth is the conservativeness demand: the declaration that a deflationary truth theory should be conservative over its base. This paper contains a critical discussion and assessment of this demand. We ask and answer the question of whether conservativity forms a part of deflationary doctrines.

In an earlier paper, I claimed that one version of Putnam's model-theoretic argument against realism turned on a subtle, but philosophically significant, mathematical mistake. Recently, Luca Bellotti has criticized my argument for this claim. This paper responds to Bellotti's criticisms.

Clauses (1) and (2) guarantee the inclusion of all 'intuitive' natural numbers, and (3) guarantees the exclusion of all other objects. Thus, in particular, no nonstandard numbers, which would follow after the intuitive ones are admitted (nonstandard numbers are found in nonstandard models of Peano arithmetic, in which the standard natural numbers are followed by one or more 'copies' of integers running from minus infinity to infinity)1. What is problematic about this delimitation? I suspect that its hypothetical proponent would see (...) its weakest point in the unexplained concept of successor. However, we logicians know better (or at least some of us are convinced that we do): it is clause (3) which harbours the neuralgic spot, by dint of resisting any reasonable logical formalization to the point of appearing utterly void! There is, of course, no problem with regimenting (1) - we only need an individual constant 0 and a unary predicate constant N (the one whose meaning we are interested in) and we postulate.. (shrink)