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)

We describe a fairly general procedure for preserving I3 embeddings j: Vλ → Vλ via λ-stage reverse Easton iterated forcings. We use this method to prove that, assuming the consistency of an I3 embedding, V = HOD is consistent with the theory ZFC + WA where WA is an axiom schema in the language {∈, j} asserting a strong but not inconsistent form of “there is an elementary embedding V → V”. This improves upon an earlier result in which consistency (...) was established assuming an I1 embedding. (shrink)

We describe a fairly general procedure for preserving I3 embeddings j: V λ → V λ via λ-stage reverse Easton iterated forcings. We use this method to prove that, assuming the consistency of an I3 embedding, V = HOD is consistent with the theory ZFC + WA where WA is an axiom schema in the language {∈, j} asserting a strong but not inconsistent form of “there is an elementary embedding V → V”. This improves upon an earlier result in (...) which consistency was established assuming an I1 embedding. (shrink)

I provide and defend two natural accounts of fundamentality for facts that do justice to the idea that the “degree of fundamentality” enjoyed by a fact is a matter of how far, from a ground-theoretic perspective, the fact is from the ungrounded facts.

The implicit commitment thesis is the claim that believing in a mathematical theory S carries an implicit commitment to further sentences not deductively entailed by the theory, such as the consistency sentence Con(S). I provide a new argument for this thesis based on the notion of mathematical certainty. I also reply to a recent argument by Walter Dean against the implicit commitment thesis, showing that my formulation of the thesis avoids the difficulties he raises.

In the the passage just quoted from theDialogues concerning Natural Religion, David Hume developed a thought-experiment that contravened his better-known views about chance expressed in hisTreatise and firstEnquiry.For among other consequences of the eternal-recurrence hypothesis Philo proposes in this passage, it may turn out that what the vulgar call cause is nothing but a secret and concealed chance.

The basic purpose of this essay, the first of an intended pair, is to interpret standard von Neumann quantum theory in a framework of iterated measure algebraic truth for mathematical (and thus mathematical-physical) assertions — a framework, that is, in which the truth-values for such assertions are elements of iterated boolean measure-algebras (cf. Sections 2.2.9, 5.2.1–5.2.6 and 5.3 below).The essay itself employs constructions of Takeuti's boolean-valued analysis (whose origins lay in work of Scott, Solovay, Krauss and others) to provide a (...) metamathematical interpretation of ideas sometimes considered disparate, heuristic, or simply ill-defined: the collapse of the wave function, for example; Everett's many worlds'-construal of quantum measurement; and a natural product space of contextual (nonlocal) hidden variables. (shrink)

Cantor’s abstractionist account of cardinal numbers has been criticized by Frege as a psychological theory of numbers which leads to contradiction. The aim of the paper is to meet these objections by proposing a reassessment of Cantor’s proposal based upon the set theoretic framework of Bourbaki—called BK—which is a First-order set theory extended with Hilbert’s \-operator. Moreover, it is argued that the BK system and the \-operator provide a faithful reconstruction of Cantor’s insights on cardinal numbers. I will introduce first (...) the axiomatic setting of BK and the definition of cardinal numbers by means of the \-operator. Then, after presenting Cantor’s abstractionist theory, I will point out two assumptions concerning the definition of cardinal numbers that are deeply rooted in Cantor’s work. I will claim that these assumptions are supported as well by the BK definition of cardinal numbers, which will be compared to those of Zermelo–von Neumann and Frege–Russell. On the basis of these similarities, I will make use of the BK framework in meeting Frege’s objections to Cantor’s proposal. A key ingredient in the defence of Cantorian abstraction will be played by the role of representative sets, which are arbitrarily denoted by the \-operator in the BK definition of cardinal numbers. (shrink)

Digital physics claims that the entire universe is, at the very bottom, made out of bits; as a result, all physical processes are intrinsically computational. For that reason, many digital physicists go further and affirm that the universe is indeed a giant computer. The aim of this article is to make explicit the ontological assumptions underlying such a view. Our main concern is to clarify what kind of properties the universe must instantiate in order to perform computations. We analyse the (...) logical form of the two models of computation traditionally adopted in digital physics, namely, cellular automata and Turing machines. These models are computationally equivalent, but we show that they support different ontological commitments about the fundamental properties of the universe. In fact, cellular automata are compatible with a rather traditional form of physicalism, whereas Turing machines support a dualistic ontology, which could be understood as a realism about the laws of nature or, alternatively, as a kind of panpsychism. (shrink)

In this paper, I will attempt to develop and defend a common form of intuitive resistance to the companions in guilt argument. I will argue that one can reasonably believe there are promising solutions to the access problem for mathematical realism that don’t translate to moral realism. In particular, I will suggest that the structuralist project of accounting for mathematical knowledge in terms of some form of logical knowledge offers significant hope of success while no analogous approach offers such hope (...) for moral realism. (shrink)

A pervasive thought in contemporary philosophy of mathematics is that in order to justify reflection principles, one must hold universism: the view that there is a single universe of pure sets. I challenge this kind of reasoning by contrasting universism with a Zermelian form of multiversism. I argue that if extant justifications of reflection principles using notions of richness are acceptable for the universist, then the Zermelian can use similar justifications. However, I note that for some forms of richness argument, (...) the status of reflection principles as axioms is left open for the Zermelian. (shrink)

Much of the discussion of set-theoretic independence, and whether or not we could legitimately expand our foundational theory, concerns how we could possibly come to know the truth value of independent sentences. This paper pursues a slightly different tack, examining how we are ignorant of issues surrounding their truth. We argue that a study of how we are ignorant reveals a need for an understanding of set-theoretic explanation and motivates a pluralism concerning the adoption of foundational theory.

A central area of current philosophical debate in the foundations of mathematics concerns whether or not there is a single, maximal, universe of set theory. Universists maintain that there is such a universe, while Multiversists argue that there are many universes, no one of which is ontologically privileged. Often forcing constructions that add subsets to models are cited as evidence in favour of the latter. This paper informs this debate by analysing ways the Universist might interpret this discourse that seems (...) to necessitate the addition of subsets to V. We argue that despite the prima facie incoherence of such talk for the Universist, she nonetheless has reason to try and provide interpretation of this discourse. We analyse extant interpretations of such talk, and analyse various tradeoffs in naturality that might be made. We conclude that the Universist has promising options for interpreting different forcing constructions. (shrink)

We explore Shelah's model‐theoretic dividing line methodology. In particular, we discuss how problems in model theory motivated new techniques in model theory, for example classifying theories by their potential (consistently with Zermelo–Fraenkel set theory with the axiom of choice (ZFC)) spectrum of cardinals in which there is a universal model. Two other examples are the study (with Malliaris) of the Keisler order leading to a new ZFC result on cardinal invariants and attempts to clarify the “main gap” by reducing the (...) dependence of certain versions on (highly independent) cardinal arithmetic. (shrink)

In the paper Randomizations of Scattered Sentences, Keisler showed that if Martin’s axiom for aleph one holds, then every scattered sentence has few separable randomizations, and asked whether the conclusion could be proved in ZFC alone. We show here that the answer is “yes”. It follows that the absolute Vaught conjecture holds if and only if every \-sentence with few separable randomizations has countably many countable models.

This paper develops the idea that valid arguments are equivalent to true conditionals by combining Kripke’s theory of truth with the evidential account of conditionals offered by Crupi and Iacona. As will be shown, in a first-order language that contains a naïve truth predicate and a suitable conditional, one can define a validity predicate in accordance with the thesis that the inference from a conjunction of premises to a conclusion is valid when the corresponding conditional is true. The validity predicate (...) so defined significantly increases our expressive resources and provides a coherent formal treatment of paradoxical arguments. (shrink)

Decision theory faces a number of problematic gambles which challenge it to say what value an ideal rational agent should assign to the gamble, and why. Yet little attention has been devoted to the question of what an ideal rational agent is, and in what sense decision theory may be said to apply to one. I show that, given one arguably natural set of constraints on the preferences of an idealized rational agent, such an agent is forced to be indifferent (...) among entire families of goods, and hence cannot choose among them. This result illustrates the dangers of speaking of the choices of an ?ideal rational agent? when one does not make precise the exact nature of the idealizing assumptions. The result may also be viewed as providing an upper bound on the kinds of idealizing assumptions which can be made for rational agents, beyond which the very concept of choice becomes attenuated. (shrink)

We present familiar principles involving objects and classes (of objects), pairing (on objects), choice (selecting elements from classes), positive classes (elements of an ultrafilter), and definable classes (definable using the preceding notions). We also postulate the existence of a divine object in the formalized sense of lying in every definable positive class. ZFC (even extended with certain hypotheses just shy of the existence of a measurable cardinal) is interpretable in the resulting system. This establishes the consistency of mathematics relative to (...) the consistency of these systems. Measurable cardinals are used to interpret and prove the consistency of the system. Positive classes and various kinds of divine objects have played significant roles in theology. (shrink)

This volume announces a new era in the philosophy of God. Many of its contributions work to create stronger links between the philosophy of God, on the one hand, and mathematics or metamathematics, on the other hand. It is about not only the possibilities of applying mathematics or metamathematics to questions about God, but also the reverse question: Does the philosophy of God have anything to offer mathematics or metamathematics? The remaining contributions tackle stereotypes in the philosophy of religion. The (...) volume includes 35 contributions. It is divided into nine parts: 1. Who Created the Concept of God; 2. Omniscience, Omnipotence, Timelessness and Spacelessness of God; 3. God and Perfect Goodness, Perfect Beauty, Perfect Freedom; 4. God, Fundamentality and Creation of All Else; 5. Simplicity and Ineffability of God; 6. God, Necessity and Abstract Objects; 7. God, Infinity, and Pascal's Wager; 8. God and (Meta-)Mathematics; and 9. God and Mind. (shrink)

I argue that absolutism, the view that absolutely unrestricted quantification is possible, is to blame for both the paradoxes that arise in naive set theory and variants of these paradoxes that arise in plural logic and in semantics. The solution is restrictivism, the view that absolutely unrestricted quantification is not possible. -/- It is generally thought that absolutism is true and that restrictivism is not only false, but inexpressible. As a result, the paradoxes are blamed, not on illicit quantification, but (...) on the logical conception of set which motivates naive set theory. The accepted solution is to replace this with the iterative conception of set. -/- I show that this picture is doubly mistaken. After a close examination of the paradoxes in chapters 2--3, I argue in chapters 4 and 5 that it is possible to rescue naive set theory by restricting quantification over sets and that the resulting restrictivist set theory is expressible. In chapters 6 and 7, I argue that it is the iterative conception of set and the thesis of absolutism that should be rejected. (shrink)

A number of philosophers have attempted to solve the problem of null-probability possible events in Bayesian epistemology by proposing that there are infinitesimal probabilities. Hájek and Easwaran have argued that because there is no way to specify a particular hyperreal extension of the real numbers, solutions to the regularity problem involving infinitesimals, or at least hyperreal infinitesimals, involve an unsatisfactory ineffability or arbitrariness. The arguments depend on the alleged impossibility of picking out a particular hyperreal extension of the real numbers (...) and/or of a particular value within such an extension due to the use of the Axiom of Choice. However, it is false that the Axiom of Choice precludes a specification of a hyperreal extension—such an extension can indeed be specified. Moreover, for all we know, it is possible to explicitly specify particular infinitesimals within such an extension. Nonetheless, I prove that because any regular probability measure that has infinitesimal values can be replaced by one that has all the same intuitive features but other infinitesimal values, the heart of the arbitrariness objection remains. (shrink)

In this paper I argue that de Finetti provided compelling reasons for rejecting countable additivity. It is ironical therefore that the main argument advanced by Bayesians against following his recommendation is based on the consistency criterion, coherence, he himself developed. I will show that this argument is mistaken. Nevertheless, there remain some counter-intuitive consequences of rejecting countable additivity, and one in particular has all the appearances of a full-blown paradox. I will end by arguing that in fact it is no (...) paradox, and that what it shows is that conditionalisation, often claimed to be integral to the Bayesian canon, has to be rejected as a general rule in a finitely additive environment. (shrink)

In this paper we give a positive answer to a problem posed by Hofer-Szabó and Rédei (Int. J. Theor. Phys. 43:1819–1826, 2004) regarding the existence of infinite Reichenbachian common cause systems (RCCSs). An example of a countably infinite RCCS is presented. It is also determined that no RCCSs of greater cardinality exist.

Let κ be a cardinal, and let H κ be the class of sets of hereditary cardinality less than κ ; let τ (κ) > κ be the height of the smallest transitive admissible set containing every element of {κ}∪H κ . We show that a ZFC-definable notion of long unfoldability, a generalisation of weak compactness, implies in the core model K, that the mouse order restricted to H κ is as long as τ. (It is known that some weak (...) large cardinal property is necessary for the latter to hold.) In other terms we delimit its strength as follows: Theorem Con(ZFC+ω2-Π 1 1-Determinacy) ⇒ ⇒Con(ZFC+V=K+∃ a long unfoldable cardinal ⇒ ⇒Con(ZFC+∀X(X # exists) + ‘‘ $\forall D \subseteq \omega_1 D$ is universally Baire ⇔ ∃r∈R(D∈L(r)))’’, and this is set-generically absolute). We isolate a notion of ω-closed cardinal which is weaker than an ω1-Erd\ os cardinal, and show that this bounds the first long unfoldable: Theorem Let κ be ω -closed. Then there is a long unfoldable ł<κ. (shrink)

We establish several first- or second-order properties of models of first-order theories by considering their elements as atoms of a new universe of set theory and by extending naturally any structure of Boolean model on the atoms to the whole universe. For example, complete f-rings are "boundedly algebraically compact" in the language $(+,-,\cdot,\wedge,\vee,\leq)$ , and the positive cone of a complete l-group with infinity adjoined is algebraically compact in the language (+, ∨, ≤). We also give an example with any (...) first-order language. The proofs can be translated into "naive set theory" in a uniform way. (shrink)

In this paper, we explore the role of syntactic representations in set theory. We highlight a common inferential scheme in set theory, which we call the Syntactic Representation Inferential Scheme, in which the set theorist infers information about a concept based on the way that concept can be represented syntactically. However, the actual syntactic representation is only indicated, not explicitly provided. We consider this phenomenon in relation to the derivation indicator position that asserts that the ordinary proofs given in mathematical (...) discourse indicate syntactic derivations in a formal logical system. In particular, we note that several of the arguments against the derivation indicator position would seem to imply that set theorists could gain no benefits from the syntactic representations of concepts indicated by their definitions, yet set theorists clearly do. (shrink)

Traditional models of mathematical proof describe proofs as sequences of assertion where each assertion is a claim about mathematical objects. However, Tanswell observed that in practice, many proofs do not follow these models. Proofs often contain imperatives, and other instructions for the reader to perform mathematical actions. The purpose of this paper is to examine the role of instructions in proofs by systematically analyzing how instructions are used in Kunen’s Set theory: An introduction to independence proofs, a widely used graduate (...) text in set theory. I use Kunen’s text to describe how instructions and constructions in proof work in mathematical practice and explore epistemic consequences of how proofs are read and understood. (shrink)

This essay clarifies quantifier variance and uses it to provide a theory of indefinite extensibility that I call the variance theory of indefinite extensibility. The indefinite extensibility response to the set-theoretic paradoxes sees each argument for paradox as a demonstration that we have come to a different and more expansive understanding of ‘all sets’. But indefinite extensibility is philosophically puzzling: extant accounts are either metasemantically suspect in requiring mysterious mechanisms of domain expansion, or metaphysically suspect in requiring nonstandard assumptions about (...) mathematical objects. Happily, the view of quantifier meanings that underwrites quantifier variance can be used to provide an account of indefinite extensibility that is both metasemantically and metaphysically satisfying. Section 1 introduces the puzzle of indefinite extensibility; section 2 develops and clarifies the metasemantics of quantifier variance; section 3 solves section 1's puzzle of indefinite extensibility by applying section 2's account of quantifier meanings; and section 4 compares the theory developed in section 3 to several other theories in the literature. (shrink)

This is an introductory paper to a series of results linking generic absoluteness results for second and third order number theory to the model theoretic notion of model companionship. Specifically we develop here a general framework linking Woodin’s generic absoluteness results for second order number theory and the theory of universally Baire sets to model companionship and show that (with the required care in details) a $$\Pi _2$$ -property formalized in an appropriate language for second order number theory is forcible (...) from some $$T\supseteq \mathsf {ZFC}+$$ large cardinals if and only if it is consistent with the universal fragment of T if and only if it is realized in the model companion of T. In particular we show that the first order theory of $$H_{\omega _1}$$ is the model companion of the first order theory of the universe of sets assuming the existence of class many Woodin cardinals, and working in a signature with predicates for $$\Delta _0$$ -properties and for all universally Baire sets of reals. We will extend these results also to the theory of $$H_{\aleph _2}$$ in a follow up of this paper. (shrink)

The mantle is the intersection of all ground models of V. We show that if there exists an extendible cardinal then the mantle is the smallest ground model of V.

A transitive model M of ZFC is called a ground if the universe V is a set forcing extension of M. We show that the grounds ofV are downward set-directed. Consequently, we establish some fundamental theorems on the forcing method and the set-theoretic geology. For instance, the mantle, the intersection of all grounds, must be a model of ZFC. V has only set many grounds if and only if the mantle is a ground. We also show that if the universe (...) has some very large cardinal, then the mantle must be a ground. (shrink)

Iterated admissibility embodies a minimal criterion of rationality in interactions. The epistemic characterization of this solution has been actively investigated in recent times: it has been shown that strategies surviving \ rounds of iterated admissibility may be identified as those that are obtained under a condition called rationality and m assumption of rationality in complete lexicographic type structures. On the other hand, it has been shown that its limit condition, with an infinity assumption of rationality ), might not be satisfied (...) by any state in the epistemic structure, if the class of types is complete and the types are continuous. In this paper we analyze the problem in a different framework. We redefine the notion of type as well as the epistemic notion of assumption. These new definitions are sufficient for the characterization of iterated admissibility as the class of strategies that indeed satisfy \. One of the key methodological innovations in our approach involves defining a new notion of generic types and employing these in conjunction with Cohen’s technique of forcing. (shrink)

We examine the differences between three standard classes of forcing notions relative to the way they collapse the continuum. It turns out that proper and semi-proper posets behave differently in that respect from the class of posets that preserve stationary subsets of \.

The use of tensed language and the metaphor of set ‘formation’ found in informal descriptions of the iterative conception of set are seldom taken at all seriously. Both are eliminated in the nonmodal stage theories that formalise this account. To avoid the paradoxes, such accounts deny the Maximality thesis, the compelling thesis that any sets can form a set. This paper seeks to save the Maximality thesis by taking the tense more seriously than has been customary (although not literally). A (...) modal stage theory, MST, is developed in a bimodal language, governed by a tenselike logic. Such a language permits a very natural axiomatisation of the iterative conception, which upholds the Maximality thesis. It is argued that the modal approach is consonant with mathematical practice and a plausible metaphysics of sets and shown that MST interprets a natural extension of Zermelo set theory less the axiom of Infinity and, when extended with a further axiom concerning the extent of the hierarchy, interprets Zermelo–Fraenkel set theory. (shrink)

The Aristotelian square of oppositions is a well-known diagram in logic and linguistics. In recent years, several extensions of the square have been discovered. However, these extensions have failed to become as widely known as the square. In this paper we argue that there is indeed a fundamental difference between the square and its extensions, viz., a difference in informativity. To do this, we distinguish between concrete Aristotelian diagrams and, on a more abstract level, the Aristotelian geometry. We then introduce (...) two new logical geometries, and develop a formal, well-motivated account of their informativity. This enables us to show that the square is strictly more informative than many of the more complex diagrams. (shrink)

In this paper, we study the relationship between the cofinalityc(Sym(ω)) of the infinite symmetric group and the minimal cardinality $$\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle\thicksim}$}}{b} $$ of an unbounded familyF of ω ω.

In this paper, we give details of results of Shelah concerning iterated Namba forcing over a ground model of CH and iteration of P[W] where W is a stationary subset of ω 2 concentrating on points of countable cofinality.

We investigate the indestructibility properties of strongly compact cardinals in universes where strong compactness suffers from identity crisis. We construct an iterative poset that can be used to establish Kimchi–Magidor theorem from (in The independence between the concepts of compactness and supercompactness, circulated manuscript), i.e., that the first n strongly compact cardinals can be the first n measurable cardinals. As an application, we show that the first n strongly compact cardinals can be the first n measurable cardinals while the strong (...) compactness of each strongly compact cardinal is indestructible under Levy collapses (our theorem is actually more general, see Sect. 3). A further application is that the class of strong cardinals can be nonempty yet coincide with the class of strongly compact cardinals while strong compactness of any strongly compact cardinal κ is indestructible under κ-directed closed posets that force GCH at κ. (shrink)

During his Fall 2005 set theory seminar, Woodin asked whether V-supercompactness implies HOD-supercompactness. We show, as he predicted, that that the answer is no.

It is now the majority view amongst philosophers and theologians that any world could have been better. This places the choice of which world to create into an especially challenging class of decision problems: those that are discontinuous in the limit. I argue that combining some weak, plausible norms governing this type of problem with a creator who has the attributes of the god of classical theism results in a paradox: no world is possible. After exploring some ways out of (...) the paradox, I conclude that the classical theist should accept Marilyn Adams’s view that no norms apply to gods. (shrink)

Our main result states that a finite iteration of Universal Meager forcing notions adds generic filters for many forcing notions determined by universality parameters. We also give some results concerning cardinal characteristics of the σ-ideals determined by those universality parameters.

We prove that the Sacks forcing collapses the continuum onto ${\frak d}$ , answering the question of Carlson and Laver. Next we prove that if a proper forcing of the size at most continuum collapses $\omega_2$ then it forces $\diamondsuit_{\omega_{1}}$.

In this paper, I argue against Penelope Maddy's set-theoretic realism by arguing (1) that it is perfectly consistent with mathematical Platonism to deny that there is a fact of the matter concerning statements which are independent of the axioms of set theory, and that (2) denying this accords further that many contemporary Platonists assert that there is a fact of the matter because they are closet foundationalists, and that their brand of foundationalism is in radical conflict with actual mathematical practice.

Transfinite recursion is an essential component of set theory. In this paper, we seek intrinsically justified reasons for believing in recursion and the notions of higher computation that surround it. In doing this, we consider several kinds of recursion principles and prove results concerning their relation to one another. We then consider philosophical motivations for these formal principles coming from the idea that computational notions lie at the core of our conception of set. This is significant because, while the iterative (...) conception of set has been widely recognized as insufficient to establish replacement and recursion, its supplementation by considerations pertaining to algorithms suggests a new and philosophically well-motivated reason to believe in such principles. (shrink)

Ortega y Gasset is known for his philosophy of life and his effort to propose an alternative to both realism and idealism. The goal of this article is to focus on an unfamiliar aspect of his thought. The focus will be given to Ortega’s interpretation of the advancements in modern mathematics in general and Cantor’s theory of transfinite numbers in particular. The main argument is that Ortega acknowledged the historical importance of the Cantor’s Set Theory, analyzed it and articulated a (...) response to it. In his writings he referred many times to the advancements in modern mathematics and argued that mathematics should be based on the intuition of counting. In response to Cantor’s mathematics Ortega presented what he defined as an ‘absolute positivism’. In this theory he did not mean to naturalize cognition or to follow the guidelines of the Comte’s positivism, on the contrary. His aim was to present an alternative to Cantor’s mathematics by claiming that mathematicians are allowed to deal only with objects that are immediately present and observable to intuition. Ortega argued that the infinite set cannot be present to the intuition and therefore there is no use to differentiate between cardinals of different infinite sets. (shrink)