In 1837, Dirichlet proved that there are infinitely many primes in any arithmetic progression in which the terms do not all share a common factor. We survey implicit and explicit uses ofDirichlet characters in presentations of Dirichlet’s proof in the nineteenth and early twentieth centuries, with an eye toward understanding some of the pragmatic pressures that shaped the evolution of modern mathematical method.

This article locates Weyl''s philosophy of mathematics and its relationship to his philosophy of science within the epistemological and ontological framework of Husserl''s phenomenology as expressed in the Logical Investigations and Ideas. This interpretation permits a unified reading of Weyl''s scattered philosophical comments in The Continuum and Space-Time-Matter. But the article also indicates that Weyl employed Poincaré''s predicativist concerns to modify Husserl''s semantics and trim Husserl''s ontology. Using Poincaré''s razor to shave Husserl''s beard leads to limitations on the least upper (...) bound theorem in the foundations of analysis and Dirichlet''s principle in the foundations of physics. Finally, the article opens the possibility of reading Weyl as a systematic thinker, that he follows Husserl''s so-called transcendental turn in the Ideas. This permits an even more unified reading of Weyl''s scattered philosophical comments. (shrink)

This article locates Weyl’s philosophy of mathematics and its relationship to his philosophy of science within the epistemological and ontological framework of Husserl’s phenomenology as expressed in the Logical Investigations and Ideas. This interpretation permits a unified reading of Weyl’s scattered philosophical comments in The Continuum and Space-Time-Matter. But the article also indicates that Weyl employed Poincar“s predicativist concerns to modify Husserl’s semantics and trim Husserl’s ontology. Using Poincar“s razor to shave Husserl’s beard leads to limitations on the least upper (...) bound theorem in the foundations of analysis and Dirichlet’s principle in the foundations of physics. Finally, the article opens the possibility of reading Weyl as a systematic thinker, that he follows Husserl’s so-called transcendental turn in the Ideas. This permits an even more unified reading of Weyl’s scattered philosophical comments. (shrink)

In 1837, Dirichlet proved that there are infinitely many primes in any arithmetic progression in which the terms do not all share a common factor. Modern presentations of the proof are explicitly higher-order, in that they involve quantifying over and summing over Dirichlet characters, which are certain types of functions. The notion of a character is only implicit in Dirichlet’s original proof, and the subsequent history shows a very gradual transition to the modern mode of presentation. In this essay, we (...) describe an approach to the philosophy of mathematics in which it is an important task to understand the roles of our ontological posits and assess the extent to which they enable us to achieve our mathematical goals. We use the history of Dirichlet’s theorem to understand some of the reasons that functions are treated as ordinary objects in contemporary mathematics, as well as some of the reasons one might want to resist such treatment. We also use these considerations to illuminate the formal treatment of functions and objects in Frege’s logical foundation, and we argue that his philosophical and logical decisions were influenced by many of the same factors. (shrink)

This chapter contains sections titled: Polarization Light Quanta The Entangled State How Do They Do It? Bell's Theorem(s) Aspect's Experiment What Is Weird About the Quantum Connection? Appendix A: The GHZ Scheme.

A layman's guide to the mechanics of Gödel's proof together with a lucid discussion of the issues which it raises. Includes an essay discussing the significance of Gödel's work in the light of Wittgenstein's criticisms.

We define the effective integrability of Fine-computable functions and effectivize some fundamental limit theorems in the theory of Lebesgue integrals such as the Bounded Convergence Theorem, the Dominated Convergence Theorem, and the Second Mean Value Theorem. It is also proved that the Walsh-Fourier coefficients of an effectively integrable Fine-computable function form a Euclidian computable sequence of reals which converges effectively to zero. This property of convergence is the effectivization of the Walsh-Riemann-Lebesgue Theorem. The article is closed (...) with the effective version of Dirichlet's test. (shrink)

In Newtonian gravity it is a moot question whether energy should be localized in the field or inside matter. An argument from relativity suggests a compromise in which the contribution from the field in vacuum is positive definite. We show that the same compromise is implied by Noether’s theorem applied to a variational principle for perfect fluids, if we assume Dirichlet boundary conditions on the potential. We then analyse a thought experiment due to Bondi and McCrea that gives a (...) clean example of inductive energy transfer by gravity. Some history of the problem is included. (shrink)

May's Theorem [K. O. May, Econometrica 20 (1952) 680-684] characterizes majority voting on two alternatives as the unique preferential voting method satisfying several simple axioms. Here we show that by adding some desirable axioms to May's axioms, we can uniquely determine how to vote on three alternatives. In particular, we add two axioms stating that the voting method should mitigate spoiler effects and avoid the so-called strong no show paradox. We prove a theorem stating that any preferential voting (...) method satisfying our enlarged set of axioms, which includes some weak homogeneity and preservation axioms, agrees with Minimax voting in all three-alternative elections, except perhaps in some improbable knife-edged elections in which ties may arise and be broken in different ways. (shrink)

Bell’s theorem admits several interpretations or ‘solutions’, the standard interpretation being ‘indeterminism’, a next one ‘nonlocality’. In this article two further solutions are investigated, termed here ‘superdeterminism’ and ‘supercorrelation’. The former is especially interesting for philosophical reasons, if only because it is always rejected on the basis of extra-physical arguments. The latter, supercorrelation, will be studied here by investigating model systems that can mimic it, namely spin lattices. It is shown that in these systems the Bell inequality can be (...) violated, even if they are local according to usual definitions. Violation of the Bell inequality is retraced to violation of ‘measurement independence’. These results emphasize the importance of studying the premises of the Bell inequality in realistic systems. (shrink)

The principal goal of this entry is to present Frege's Theorem (i.e., the proof that the Dedekind-Peano axioms for number theory can be derived in second-order logic supplemented only by Hume's Principle) in the most logically perspicuous manner. We strive to present Frege's Theorem by representing the ideas and claims involved in the proof in clear and well-established modern logical notation. This prepares one to better prepared to understand Frege's own notation and derivations, and read Frege's original work (...) (whether in German or in translation). Moreover, this should prepare the reader to understand a number of scholarly books and articles in the secondary literature on Frege's work. (shrink)

In this short survey article, I discuss Bell’s theorem and some strategies that attempt to avoid the conclusion of non-locality. I focus on two that intersect with the philosophy of probability: (1) quantum probabilities and (2) superdeterminism. The issues they raised not only apply to a wide class of no-go theorems about quantum mechanics but are also of general philosophical interest.

Vardanyan’s Theorems [36, 37] state that $\mathsf {QPL}(\mathsf {PA})$ —the quantified provability logic of Peano Arithmetic—is $\Pi ^0_2$ complete, and in particular that this already holds when the language is restricted to a single unary predicate. Moreover, Visser and de Jonge [38] generalized this result to conclude that it is impossible to computably axiomatize the quantified provability logic of a wide class of theories. However, the proof of this fact cannot be performed in a strictly positive signature. The system $\mathsf (...) {QRC_1}$ was previously introduced by the authors [1] as a candidate first-order provability logic. Here we generalize the previously available Kripke soundness and completeness proofs, obtaining constant domain completeness. Then we show that $\mathsf {QRC_1}$ is indeed complete with respect to arithmetical semantics. This is achieved via a Solovay-type construction applied to constant domain Kripke models. As corollaries, we see that $\mathsf {QRC_1}$ is the strictly positive fragment of $\mathsf {QGL}$ and a fragment of $\mathsf {QPL}(\mathsf {PA})$. (shrink)

According to a popular narrative, in 1932 von Neumann introduced a theorem that intended to be a proof of the impossibility of hidden variables in quantum mechanics. However, the narrative goes, Bell later spotted a flaw that allegedly shows its irrelevance. Bell’s widely accepted criticism has been challenged by Bub and Dieks: they claim that the proof shows that viable hidden variables theories cannot be theories in Hilbert space. Bub’s and Dieks’ reassessment has been in turn challenged by Mermin (...) and Schack. Hereby I critically assess their reply, with the aim of bringing further clarification concerning the meaning, scope and relevance of von Neumann’s theorem. I show that despite Mermin and Schack’s response, Bub’s and Dieks’ reassessment is quite correct, and that this reading gets strongly reinforced when we carefully consider the connection between von Neumann’s proof and Gleason’s theorem. (shrink)

In this paper I argue for an association between impurity and explanatory power in contemporary mathematics. This proposal is defended against the ancient and influential idea that purity and explanation go hand-in-hand (Aristotle, Bolzano) and recent suggestions that purity/impurity ascriptions and explanatory power are more or less distinct (Section 1). This is done by analyzing a central and deep result of additive number theory, Szemerédi’s theorem, and various of its proofs (Section 2). In particular, I focus upon the radically (...) impure (ergodic) proof due to Furstenberg (Section 3). Furstenberg’s ergodic proof is striking because it utilizes intuitively foreign and infinitary resources to prove a finitary combinatorial result and does so in a perspicuous fashion. I claim that Furstenberg’s proof is explanatory in light of its clear expression of a crucial structural result, which provides the “reason why” Szemerédi’s theorem is true. This is, however, rather surprising: how can such intuitively different conceptual resources “get a grip on” the theorem to be proved? I account for this phenomenon by articulating a new construal of the content of a mathematical statement, which I call structural content (Section 4). I argue that the availability of structural content saves intuitive epistemic distinctions made in mathematical practice and simultaneously explicates the intervention of surprising and explanatorily rich conceptual resources. Structural content also disarms general arguments for thinking that impurity and explanatory power might come apart. Finally, I sketch a proposal that, once structural content is in hand, impure resources lead to explanatory proofs via suitably understood varieties of simplification and unification (Section 5). (shrink)

I demonstrate that Bell's theorem is based on circular reasoning and thus a fundamentally flawed argument. It unjustifiably assumes the additivity of expectation values for dispersion-free states of contextual hidden variable theories for non-commuting observables involved in Bell-test experiments, which is tautologous to assuming the bounds of ±2 on the Bell-CHSH sum of expectation values. Its premises thus assume in a different guise the bounds of ±2 it sets out to prove. Once this oversight is ameliorated from Bell's argument (...) by identifying the impediment that leads to it and local realism is implemented correctly, the bounds on the Bell-CHSH sum of expectation values work out to be ±2√2 instead of ±2, thereby mitigating the conclusion of Bell's theorem. Consequently, what is ruled out by any of the Bell-test experiments is not local realism but the linear additivity of expectation values, which does not hold for non-commuting observables in any hidden variable theories to begin with. (shrink)

Tarski's theorem essentially says that the Liar paradox is paradoxical in the minimal reflexive frame. We generalise this result to the Liar-like paradox $\lambda^\alpha$ for all ordinal $\alpha\geq 1$. The main result is that for any positive integer $n = 2^i(2j+1)$, the paradox $\lambda^n$ is paradoxical in a frame iff this frame contains at least a cycle the depth of which is not divisible by $2^{i+1}$; and for any ordinal $\alpha \geq \omega$, the paradox $\lambda^\alpha$ is paradoxical in a (...) frame iff this frame contains at least an infinite walk which has an arbitrarily large depth. We thus get that $\lambda^n$ has a degree of paradoxicality no more than $\lambda^m$ iff the multiplicity of 2 in the (unique) prime factorisation of $n$ is no more than that in the prime factorisation of $m$; and all tranfinite $\lambda^\alpha$ has the same degree of paradoxcality but has a higher degree of paradoxicality than any $\lambda^n$. (shrink)

This paper initiates the reverse mathematics of social choice theory, studying Arrow's impossibility theorem and related results including Fishburn's possibility theorem and the Kirman–Sondermann theorem within the framework of reverse mathematics. We formalise fundamental notions of social choice theory in second-order arithmetic, yielding a definition of countable society which is tractable in RCA0. We then show that the Kirman–Sondermann analysis of social welfare functions can be carried out in RCA0. This approach yields a proof of Arrow's (...) class='Hi'>theorem in RCA0, and thus in PRA, since Arrow's theorem can be formalised as a Π01 sentence. Finally we show that Fishburn's possibility theorem for countable societies is equivalent to ACA0 over RCA0. (shrink)

The paper considers the claim that quantum theories with a deterministic dynamics of objects in ordinary space-time, such as Bohmian mechanics, contradict the assumption that the measurement settings can be freely chosen in the EPR experiment. That assumption is one of the premises of Bell’s theorem. I first argue that only a premise to the effect that what determines the choice of the measurement settings is independent of what determines the past state of the measured system is needed for (...) the derivation of Bell’s theorem. Determinism as such does not undermine that independence . Only entanglement could do so. However, generic entanglement without collapse on the level of the universal wave-function can go together with effective wave-functions for subsystems of the universe, as in Bohmian mechanics. The paper argues that such effective wave-functions are sufficient for the mentioned independence premise to hold. (shrink)

This paper addresses the strength of Ramsey's theorem for pairs ($RT^2_2$) over a weak base theory from the perspective of 'proof mining'. Let $RT^{2-}_2$ denote Ramsey's theorem for pairs where the coloring is given by an explicit term involving only numeric variables. We add this principle to a weak base theory that includes weak König's Lemma and a substantial amount of $\Sigma^0_1$-induction (enough to prove the totality of all primitive recursive functions but not of all primitive recursive functionals). (...) In the resulting theory we show the extractability of primitive recursive programs and uniform bounds from proofs of $\forall\exists$-theorems. There are two components of this work. The first component is a general proof-theoretic result, due to the second author, that establishes conservation results for restricted principles of choice and comprehension over primitive recursive arithmetic PRA as well as a method for the extraction of primitive recursive bounds from proofs based on such principles. The second component is the main novelty of the paper: it is shown that a proof of Ramsey's theorem due to Erdős and Rado can be formalized using these restricted principles. So from the perspective of proof unwinding the computational content of concrete proofs based on $RT^2_2$ the computational complexity will, in most practical cases, not go beyond primitive recursive complexity. This even is the case when the theorem to be proved has function parameters f and the proof uses instances of $RT^2_2$ that are primitive recursive in f. (shrink)

Historically, Ehrenfest’s theorem is the first one which shows that classical physics can emerge from quantum physics as a kind of approximation. We recall the theorem in its original form, and we highlight its generalizations to the relativistic Dirac particle and to a particle with spin and izospin. We argue that apparent classicality of the macroscopic world can probably be explained within the framework of standard quantum mechanics.

We consider the relation between versions of Ramsey’s Theorem and König’s Infinity Lemma, in the absence of the axiom of choice.

We argue that Löb's Theorem implies a limitation on mechanism. Specifically, we argue, via an application of a generalized version of Löb's Theorem, that any particular device known by an observer to be mechanical cannot be used as an epistemic authority (of a particular type) by that observer: either the belief-set of such an authority is not mechanizable or, if it is, there is no identifiable formal system of which the observer can know (or truly believe) it to (...) be the theorem-set. This gives, we believe, an important and hitherto unnoticed connection between mechanism and the use of authorities by human-like epistemic agents. (shrink)

A version of Frege's theorem can be proved in a plural logic with pair abstraction. We talk through this and discuss the philosophical implications of the result.

Bell’s theorem has fascinated physicists and philosophers since his 1964 paper, which was written in response to the 1935 paper of Einstein, Podolsky, and Rosen. Bell’s theorem and its many extensions have led to the claim that quantum mechanics and by inference nature herself are nonlocal in the sense that a measurement on a system by an observer at one location has an immediate effect on a distant entangled system. Einstein was repulsed by such “spooky action at a (...) distance” and was led to question whether quantum mechanics could provide a complete description of physical reality. In this paper I argue that quantum mechanics does not require spooky action at a distance of any kind and yet it is entirely reasonable to question the assumption that quantum mechanics can provide a complete description of physical reality. The magic of entangled quantum states has little to do with entanglement and everything to do with superposition, a property of all quantum systems and a foundational tenet of quantum mechanics. (shrink)

A brief, non-technical introduction to technical and philosophical aspects of Frege's philosophy of arithmetic. The exposition focuses on Frege's Theorem, which states that the axioms of arithmetic are provable, in second-order logic, from a single non-logical axiom, "Hume's Principle", which itself is: The number of Fs is the same as the number of Gs if, and only if, the Fs and Gs are in one-one correspondence.

The previous two parts of the paper demonstrate that the interpretation of Fermat’s last theorem (FLT) in Hilbert arithmetic meant both in a narrow sense and in a wide sense can suggest a proof by induction in Part I and by means of the Kochen - Specker theorem in Part II. The same interpretation can serve also for a proof FLT based on Gleason’s theorem and partly similar to that in Part II. The concept of (probabilistic) measure (...) of a subspace of Hilbert space and especially its uniqueness can be unambiguously linked to that of partial algebra or incommensurability, or interpreted as a relation of the two dual branches of Hilbert arithmetic in a wide sense. The investigation of the last relation allows for FLT and Gleason’s theorem to be equated in a sense, as two dual counterparts, and the former to be inferred from the latter, as well as vice versa under an additional condition relevant to the Gödel incompleteness of arithmetic to set theory. The qubit Hilbert space itself in turn can be interpreted by the unity of FLT and Gleason’s theorem. The proof of such a fundamental result in number theory as FLT by means of Hilbert arithmetic in a wide sense can be generalized to an idea about “quantum number theory”. It is able to research mathematically the origin of Peano arithmetic from Hilbert arithmetic by mediation of the “nonstandard bijection” and its two dual branches inherently linking it to information theory. Then, infinitesimal analysis and its revolutionary application to physics can be also re-realized in that wider context, for example, as an exploration of the way for physical quantity of time (respectively, for time derivative in any temporal process considered in physics) to appear at all. Finally, the result admits a philosophical reflection of how any hierarchy arises or changes itself only thanks to its dual and idempotent counterpart. (shrink)

A proof of Bell’s theorem without inequalities is presented in which distant local setups do not need to be aligned, since the required perfect correlations are achieved for any local rotation of the local setups.

Haag's theorem has been interpreted as establishing that quantum field theory cannot consistently represent interacting fields. Earman and Fraser have clarified how it is possible to give mathematically consistent calculations in scattering theory despite the theorem. However, their analysis does not fully address the worry raised by the result. In particular, I argue that their approach fails to be a complete explanation of why Haag's theorem does not undermine claims about the empirical adequacy of particular quantum field (...) theories. I then show that such empirical adequacy claims are protected from Haag's result by the techniques that are required to obtain theoretical predictions for realistic experimental observables. I conclude by showing how Haag's theorem is illustrative of a general tension between the foundational significance of results that can be obtained in perturbation theory and non-perturbative characterizations of the content of quantum field theory. (shrink)

Bayes's theorem is a tool for assessing how probable evidence makes some hypothesis. The papers in this volume consider the worth and applicability of the theorem. Richard Swinburne sets out the philosophical issues. Elliott Sober argues that there are other criteria for assessing hypotheses. Colin Howson, Philip Dawid and John Earman consider how the theorem can be used in statistical science, in weighing evidence in criminal trials, and in assessing evidence for the occurrence of miracles. David Miller (...) argues for the worth of the probability calculus as a tool for measuring propensities in nature rather than the strength of evidence. The volume ends with the original paper containing the theorem, presented to the Royal Society in 1763. (shrink)

A variation of Bell's theorem that deals with the indeterministic case is formulated and proved within the logical framework of Lewis's theory of counterfactuals. The no-faster-than-light-influence condition is expressed in terms of Lewis would counterfactual conditionals. Objections to this procedure raised by certain philosophers of science are examined and answered. The theorem shows that the incompatibility between the predictions of quantum theory and the idea of no faster-than-light influence cannot be ascribed to any auxiliary or tacit assumption of (...) either determinism or the related idea that outcomes of unperformed measurements are determinate within nature. In addition, the theorem provides an example of an application of Lewis's theory of counterfactuals in a rigorous scientific context. (shrink)

In response to recent work on the aggregation of individual judgments on logically connected propositions into collective judgments, it is often asked whether judgment aggregation is a special case of Arrowian preference aggregation. We argue for the converse claim. After proving two impossibility theorems on judgment aggregation (using "systematicity" and "independence" conditions, respectively), we construct an embedding of preference aggregation into judgment aggregation and prove Arrow’s theorem (stated for strict preferences) as a corollary of our second result. Although we (...) thereby provide a new proof of Arrow’s theorem, our main aim is to identify the analogue of Arrow’s theorem in judgment aggregation, to clarify the relation between judgment and preference aggregation, and to illustrate the generality of the judgment aggregation model. JEL Classi…cation: D70, D71.. (shrink)

It was shown by Cholak, Jockusch, and Slaman that every computable 2-coloring of pairs admits an infinite low₂ homogeneous set H. We answer a question of the same authors by showing that H may be chosen to satisfy in addition $C\,\not \leqslant _T \,H$, where C is a given noncomputable set. This is shown by analyzing a new and simplified proof of Seetapun's cone avoidance theorem for Ramsey's theorem. We then extend the result to show that every computable (...) 2-coloring of pairs admits a pair of low₂ infinite homogeneous sets whose degrees form a minimal pair. (shrink)

Haag’s theorem has been interpreted as establishing that quantum field theory cannot consistently represent interacting fields. Earman and Fraser have clarified how it is possible to give mathematically consistent calculations in scattering theory despite the theorem. However, their analysis does not fully address the worry raised by the result. In particular, I argue that their approach fails to be a complete explanation of why Haag’s theorem does not undermine claims about the empirical adequacy of particular quantum field (...) theories. I then show that such empirical adequacy claims are protected from Haag’s result by the techniques that are required to obtain theoretical predictions for realistic experimental observables. I conclude by showing how Haag’s theorem is illustrative of a general tension between the foundational significance of results that can be obtained in perturbation theory and non-perturbative characterizations of the content of quantum field theory. 1 Introduction2 Haag’s Theorem and the Interaction Picture3 Earman and Fraser on the Success of Scattering Theory4 Haag’s Theorem and Empirical Adequacy5 Conclusion. (shrink)

Hindman's Theorem is a prototypical example of a combinatorial theorem with a proof that uses the topology of the ultrafilters. We show how the methods of this proof, including topological arguments about ultrafilters, can be translated into second order arithmetic.

It has been a longstanding problem to show how the irreversible behaviour of macroscopic systems can be reconciled with the time-reversal invariance of these same systems when considered from a microscopic point of view. A result by Lanford shows that, under certain conditions, the famous Boltzmann equation, describing the irreversible behaviour of a dilute gas, can be obtained from the time-reversal invariant Hamiltonian equations of motion for the hard spheres model. Here, we examine how and in what sense Lanford’s (...) class='Hi'>theorem succeeds in deriving this remarkable result. Many authors have expressed different views on the question which of the ingredients in Lanford’s theorem is responsible for the emergence of irreversibility. We claim that these interpretations miss the target. In fact, we argue that there is no time-asymmetric ingredient at all. (shrink)

We prove the following theorem: For a partially ordered set Q such that every countable subset of Q has a strict upper bound, there is a forcing notion satisfying the countable chain condition such that, in the forcing extension, there is a basis of the null ideal of the real line which is order-isomorphic to Q with respect to set-inclusion. This is a variation of Hechler’s classical result in the theory of forcing. The corresponding theorem for the meager (...) ideal was established by Bartoszyński and Kada. (shrink)

The book begins with an overview that introduces the Theorem and the issues surrounding it, and explores how the essays that follow contribute to our understanding of those issues.

We study the logical and computational properties of basic theorems of uncountable mathematics, in particular Pincherle's theorem, published in 1882. This theorem states that a locally bounded function is bounded on certain domains, i.e. one of the first ‘local-to-global’ principles. It is well-known that such principles in analysis are intimately connected to (open-cover) compactness, but we nonetheless exhibit fundamental differences between compactness and Pincherle's theorem. For instance, the main question of Reverse Mathematics, namely which set existence axioms (...) are necessary to prove Pincherle's theorem, does not have an unique or unambiguous answer, in contrast to compactness. We establish similar differences for the computational properties of compactness and Pincherle's theorem. We establish the same differences for other local-to-global principles, even going back to Weierstrass. We also greatly sharpen the known computational power of compactness, for the most shared with Pincherle's theorem however. Finally, countable choice plays an important role in the previous, we therefore study this axiom together with the intimately related Lindelöf lemma. (shrink)

This paper reassesses the question of whether Craig’s theorem poses a challenge to Quine's empirical underdetermination thesis. It will be demonstrated that Quine’s account of this issue in his paper “Empirically Equivalent Systems of the World” (1975) is flawed and that Quine makes too strong a concession to the Craigian challenge. It will further be pointed out that Craig’s theorem would threaten the empirical underdetermination thesis only if the set of all relevant observation conditionals could be shown to (...) be recursively enumerable — a condition which Quine seems to overlook — and it will be argued that, at least within the framework of Quine’s philosophy, it is doubtful whether this condition is satisfiable. (shrink)

In his 1967 paper Vaught used an ingenious argument to show that every recursively enumerable first order theory that directly interprets the weak system VS of set theory is axiomatizable by a scheme. In this paper we establish a strengthening of Vaught's theorem by weakening the hypothesis of direct interpretability of VS to direct interpretability of the finitely axiomatized fragment VS2 of VS. This improvement significantly increases the scope of the original result, since VS is essentially undecidable, but VS2 (...) has decidable extensions. We also explore the ramifications of our work on finite axiomatizability of schemes in the presence of suitable comprehension principles. (shrink)

Halin in 1965 proved that if a graph has [Formula: see text] many pairwise disjoint rays for each [Formula: see text] then it has infinitely many pairwise disjoint rays. We analyze the complexity of this and other similar results in terms of computable and proof theoretic complexity. The statement of Halin’s theorem and the construction proving it seem very much like standard versions of compactness arguments such as König’s Lemma. Those results, while not computable, are relatively simple. They only (...) use arithmetic procedures or, equivalently, finitely many iterations of the Turing jump. We show that several Halin-type theorems are much more complicated. They are among the theorems of hyperarithmetic analysis. Such theorems imply the ability to iterate the Turing jump along any computable well ordering. Several important logical principles in this class have been extensively studied beginning with work of Kreisel, H. Friedman, Steel and others in the 1960s and 1970s. Until now, only one purely mathematical example was known. Our work provides many more and so answers Question 30 of Montalbán’s Open Questions in Reverse Mathematics in 2011. Some of these theorems including ones in Halin in 1965 are also shown to have unusual proof theoretic strength as well. (shrink)

Arrow's Theorem, in its social choice function formulation, assumes that all nonempty finite subsets of the universal set of alternatives is potentially a feasible set. We demonstrate that the axioms in Arrow's Theorem, with weak Pareto strengthened to strong Pareto, are consistent if it is assumed that there is a prespecified alternative which is in every feasible set. We further show that if the collection of feasible sets consists of all subsets of alternatives containing a prespecified list of (...) alternatives and if there are at least three additional alternatives not on this list, replacing nondictatorship by anonymity results in an impossibility theorem. (shrink)

According to a recent paper by Tim Maudlin, Bell’s theorem has nothing to tell us about realism or the descriptive completeness of quantum mechanics. What it shows is that quantum mechanics is non-local, no more and no less. What I intend to do in this paper is to challenge Maudlin’s assertion about the import of Bell’s proof. There is much that I agree with in the paper; in particular, it does us the valuable service of demonstrating that Einstein’s objections (...) to quantum mechanics have nothing to do with its indeterminism. But I do think that Maudlin’s conclusion is overly cut-and-dried. Quantum mechanics is far from a unified edifice, and what Bell’s theorem shows depends on what version of quantum mechanics you look at. In particular, I’ll try to make the case that there’s an interesting, if ultimately uncompelling anti-realist construal of the import of Bell’s theorem. And I also want to suggest that locality isn’t quite as decisively defeated as Maudlin claims. (shrink)

Kenneth Arrow’s “impossibility” theorem—or “general possibility” theorem, as he called it—answers a very basic question in the theory of collective decision-making. Say there are some alternatives to choose among. They could be policies, public projects, candidates in an election, distributions of income and labour requirements among the members of a society, or just about anything else. There are some people whose preferences will inform this choice, and the question is: which procedures are there for deriving, from what is (...) known or can be found out about their preferences, a collective or “social” ordering of the alternatives from better to worse? The answer is startling. Arrow’s theorem says there are no such procedures whatsoever—none, anyway, that satisfy certain apparently quite reasonable assumptions concerning the autonomy of the people and the rationality of their preferences. The technical framework in which Arrow gave the question of social orderings a precise sense and its rigorous answer is now widely used for studying problems in welfare economics. The impossibility theorem itself set much of the agenda for contemporary social choice theory. Arrow accomplished this while still a graduate student. In 1972, he received the Nobel Prize in economics for his contributions. (shrink)

The stable Ramsey's theorem for pairs has been the subject of numerous investigations in mathematical logic. We introduce a weaker form of it by restricting from the class of all stable colorings to subclasses of it that are nonnull in a certain effective measure-theoretic sense. We show that the sets that can compute infinite homogeneous sets for nonnull many computable stable colorings and the sets that can compute infinite homogeneous sets for all computable stable colorings agree below $\emptyset'$ but (...) not in general. We also answer the analogs of two well-known questions about the stable Ramsey's theorem by showing that our weaker principle does not imply COH or WKL 0 in the context of reverse mathematics. (shrink)