It is shown how the 300 rays associated with the antipodal pairs of vertices of a 120-cell (a four-dimensional regular polytope) can be used to give numerous “parity proofs” of the Kochen–Specker theorem ruling out the existence of noncontextual hidden variables theories. The symmetries of the 120-cell are exploited to give a simple construction of its Kochen–Specker diagram, which is exhibited in the form of a “basis table” showing all the orthogonalities between its rays. The basis table consists (...) of 675 bases (a basis being a set of four mutually orthogonal rays), but all the bases can be written down from the few listed in this paper using some simple rules. The basis table is shown to contain a wide variety of parity proofs, ranging from 19 bases (or contexts) at the low end to 41 bases at the high end. Some explicit examples of these proofs are given, and their implications are discussed. (shrink)

A diagrammatic representation is given of the 24 rays of Peres that makes it easy to pick out all the 512 parity proofs of the Kochen-Specker theorem contained in them. The origin of this representation in the four-dimensional geometry of the rays is pointed out.

The set of 60 real rays in four dimensions derived from the vertices of a 600-cell is shown to possess numerous subsets of rays and bases that provide basis-critical parity proofs of the Bell-Kochen-Specker (BKS) theorem (a basis-critical proof is one that fails if even a single basis is deleted from it). The proofs vary considerably in size, with the smallest having 26 rays and 13 bases and the largest 60 rays and 41 bases. There are at (...) least 90 basic types of proofs, with each coming in a number of geometrically distinct varieties. The replicas of all the proofs under the symmetries of the 600-cell yield a total of almost a hundred million parity proofs of the BKS theorem. The proofs are all very transparent and take no more than simple counting to verify. A few of the proofs are exhibited, both in tabular form as well as in the form of MMP hypergraphs that assist in their visualization. A survey of the proofs is given, simple procedures for generating some of them are described and their applications are discussed. It is shown that all four-dimensional parity proofs of the BKS theorem can be turned into experimental disproofs of noncontextuality. (shrink)

Sam Buss produced the first polynomial size Frege proof of thepigeonhole principle. We introduce a variation of that problem and producea simpler proof based on parity. The proof appearing here has an upperbound that is quadratic in the size of the input formula.

This paper begins with a response to Josh Gert’s challenge that ‘on a par with’ is not a sui generis fourth value relation beyond ‘better than’, ‘worse than’, and ‘equally good’. It then explores two further questions: can parity be modeled by an interval representation of value? And what should one rationally do when faced with items on a par? I argue that an interval representation of value is incompatible with the possibility that items are on a par (a (...) mathematical proof is given in the appendix). I also suggest that there are three senses of ‘rationally permissible’ which, once distinguished, show that parity does distinctive practical work that cannot be done by the usual trichotomy of relations or by incomparability. In this way, we have an additional argument for parity from the workings of practical reason. (shrink)

This paper considers the implications for the relational-substantival debate of observations of parity nonconservation in weak interactions, a much neglected topic. It is argued that 'geometric proofs' of absolute space, first proposed by Kant (1768), fail, but that parity violating laws allow 'mechanical proofs', like Newton's laws. Parity violating laws are explained and arguments analogous to those of Newton's Scholium are constructed to show that they require absolute spacetime structure--namely, an orientation--as Newtonian mechanics requires affine (...) structure. Finally, it is considered how standard relationist responses to Newton's argument might respond to the new challenge of parity nonconservation. (shrink)

The Routley star, an involutive function between possible worlds or set-ups against which negation is evaluated, is a hallmark feature of Richard Sylvan and Val Plumwood's set-up semantics for the logic of first-degree entailment. Less frequently acknowledged is the weaker mate function described by Sylvan and his collaborators, which results from stripping the requirement of involutivity from the Routley star. Between the mate function and the Routley star, however, lies an broad field of intermediate semantical conditions characterizing an infinite number (...) of consequence relations closely related to first-degree entailment. In this paper, we consider the semantics and proof theory for deductive systems corresponding to set-up models in which the mate function is cyclical. We describe modifications to Anderson and Belnap's consecution calculus LE_fde2 that correspond to these constraints, for which we prove soundness and completeness with respect to the set-up semantics. Finally, we show that a number of familiar metalogical properties are coordinated with the parity of a mate function's period, including refined versions of the variable-sharing property and the property of gentle explosiveness. (shrink)

The combinatorial parity principle states that there is no perfect matching on an odd number of vertices. This principle generalizes the pigeonhole principle, which states that for a fixed bipartition of the vertices, there is no perfect matching between them. Therefore, it follows from recent lower bounds for the pigeonhole principle that the parity principle requires exponential-size bounded-depth Frege proofs. Ajtai previously showed that the parity principle does not have polynomial-size bounded-depth Frege proofs even with (...) the pigeonhole principle as an axiom schema. His proof utilizes nonstandard model theory and is nonconstructive. We improve Ajtai's lower bound from barely superpolynomial to exponential and eliminate the nonstandard model theory. Our lower bound is also related to the inherent complexity of particular search classes . In particular, oracle separations between the complexity classes PPA and PPAD, and between PPA and PPP also follow from our techniques. (shrink)

The author of “Parsimony and inference to the best mathematical explanation” argues for platonism by way of an enhanced indispensability argument based on an inference to yet better mathematical optimization explanations in the natural sciences. Since such explanations yield beneficial trade-offs between stronger mathematical existential claims and fewer concrete ontological commitments than those involved in merely good mathematical explanations, one must countenance the mathematical objects that play a theoretical role in them via an application of the relevant mathematical results. The (...) nominalist’s challenge is thus to undermine the platonistic force of such explanations by way of alternative nominalistic ones. The author’s contention is that such nominalistic explanations should provide a paraphrase of the proofs of the mathematical results being applied. There are reasons to doubt that proofs, construed here as formal derivations, actually contribute to the platonistc force to be undermined and, by parity, that nominalized proofs should bear responsability for the corresponding undermining. A discussion of two examples and of associated arguments by Lange, Pincock, Steiner and Tallant, point to a a wealth of worries concerning the construal of this explanatory role. Among those figure the distinction between the weak and strong role of proofs, the distinction between causal or “ordinary” explanations and genuine mathematical ones, and the unifying role of optimization explanations. More generally, the very idea that the explanatory advantages yielded by applied mathematical claims may be construed as gradual or progressive and the associated notion that the feasibility of their nominalistic paraphrases decreases as the generality and force of these claim increases, deserves a closer attention. (shrink)

Charting a "middle way" between the extremes represented by Alvin Plantinga and Richard Swinburne, Garth Hallett explores the thesis that if belief in other minds is rational and true (as it surely is), so too is belief in God. He makes a strong case that when this parity claim is appropriately restricted to a single, sound other-minds belief, belief in God and belief in other minds do prove epistemically comparable. This result, and the distinctive path that leads to it, (...) will interest students and scholars in philosophy of religion and theology. (shrink)

Charting a "middle way" between the extremes represented by Alvin Plantinga and Richard Swinburne, Garth Hallett explores the thesis that if belief in other minds is rational and true, so too is belief in God. He makes a strong case that when this parity claim is appropriately restricted to a single, sound other-minds belief, belief in God and belief in other minds do prove epistemically comparable. This result, and the distinctive path that leads to it, will interest students and (...) scholars in philosophy of religion and theology. (shrink)

We tackle the problem of preservation of totality by composition in arena games. We first explain how this problem reduces to a finiteness theorem on what we call pointer structures, similar to the parity pointer functions of Harmer, Hyland and Mélliès and the interaction sequences of Coquand. We discuss how this theorem relates to normalization of linear head reduction in simply-typed lambda-calculus, leading us to a semantic realizability proof à la Kleene of our theorem. We then present another proof (...) of a more combinatorial nature. Finally, we discuss the exact class of strategies to which our theorems apply. (shrink)

The CPT theorem states that any causal, Lorentz-invariant, thermodynamically well-behaved quantum field theory must also be invariant under a reflection symmetry that reverses the direction of time, flips spatial parity, and conjugates charge. Although its physical basis remains obscure, CPT symmetry appears to be necessary in order to unify quantum mechanics with relativity. This paper attempts to decipher the physical reasoning behind proofs of the CPT theorem in algebraic quantum field theory. Ultimately, CPT symmetry is linked to a (...) systematic reversal of the C*-algebraic Lie product that encodes the generating relationship between observables and symmetries. In any physically reasonable relativistic quantum field theory it is always possible to systematically reverse this generating relationship while preserving the dynamics, spectra, and localization properties of physical systems. Rather than the product of three separate reflections, CPT symmetry is revealed to be a single global reflection of the theory’s state space. (shrink)

Game theory is usually considered applied mathematics, but a few game‐theoretic results, such as Borel determinacy, were developed by mathematicians for mathematics in a broad sense. These results usually state determinacy, i.e., the existence of a winning strategy in games that involve two players and two outcomes saying who wins. In a multi‐outcome setting, the notion of winning strategy is irrelevant yet usually replaced faithfully with the notion of (pure) Nash equilibrium. This article shows that every determinacy result over an (...) arbitrary game structure, e.g., a tree, is transferable into existence of multi‐outcome (pure) Nash equilibrium over the same game structure. The equilibrium‐transfer theorem requires cardinal or order‐theoretic conditions on the strategy sets and the preferences, respectively, whereas counter‐examples show that every requirement is relevant, albeit possibly improvable. When the outcomes are finitely many, the proof provides an algorithm computing a Nash equilibrium without significant complexity loss compared to the two‐outcome case. As examples of application, this article generalises Borel determinacy, positional determinacy of parity games, and finite‐memory determinacy of Muller games. (shrink)

To what extent are the subjects of our thoughts and talk real? This is the question of realism. In this book, Justin Clarke-Doane explores arguments for and against moral realism and mathematical realism, how they interact, and what they can tell us about areas of philosophical interest more generally. He argues that, contrary to widespread belief, our mathematical beliefs have no better claim to being self-evident or provable than our moral beliefs. Nor do our mathematical beliefs have better claim to (...) being empirically justified than our moral beliefs. It is also incorrect that reflection on the "genealogy" of our moral beliefs establishes a lack of parity between the cases. In general, if one is a moral antirealist on the basis of epistemological considerations, then one ought to be a mathematical antirealist as well. And, yet, Clarke-Doane shows that moral realism and mathematical realism do not stand or fall together -- and for a surprising reason. Moral questions, insofar as they are practical, are objective in a sense that mathematical questions are not. Moreover, the sense in which they are objective can be explained only by assuming practical anti-realism. One upshot of the discussion is that the concepts of realism and objectivity, which are widely identified, are actually in tension. Another is that the objective questions in the neighborhood of questions of logic, modality, grounding, and nature are practical questions too. Practical philosophy should, therefore, take center stage. (shrink)

According to the mixed lexicographic/additive account of ‘better than’ and similar aggregative value comparatives like ‘healthier than’, values are multidimensional and different aspects of a value are aggregated into an overall assessment in a lexicographic way, based on an ordering of value aspects. It is argued that this theory can account for an acceptable definition of Chang’s notion of parity and that it also offers a solution to Temkin’s and Rachels’s Spectrum Cases without giving up the transitivity of overall (...) betterness. Formal details and proofs are provided in an “Appendix”. (shrink)

This thesis aims to clarify a number of conceptual aspects of the debate surrounding algorithmic fairness. The particular focus here is the role of causal modeling in defining criteria of algorithmic fairness. In Chapter 1, I argue that in the discussion of algorithmic fairness, two fundamentally distinct notions of fairness have been conflated. Subsequently, I propose that what is usually taken to be the problem of algorithmic fairness should be divided into two subproblems, the problem of predictive fairness, and the (...) problem of allocative fairness. At the core of Chapter 2 is the proof of a theorem that establishes that three of the most popular (predictive) fairness criteria are pairwise incompatible. In particular, I show that under certain conditions, a predictive algorithm that satisfies a criterion called counterfactual fairness will with logical necessity violate two other popular predictive fairness criteria called equalized odds and predictive parity. In Chapter 3, a new predictive fairness criterion is developed using a mathematical framework for causal modeling. This fairness criterion, which I call causal relevance fairness, is a relaxation of another popular fairness criterion, counterfactual fairness, but turns out to be more closely in line with philosophical theories of discrimination. In Chapter 4, another infamous impossibility result in algorithmic fairness is analyzed through the lens of causality. I argue that by using a causal inference method called matching, we can modify the two fairness criteria equalized odds and predictive parity in a way that resolves the impossibility. Lastly, Chapter 5 contains an empirical case study. In it, the fairness of a popular recidivism risk prediction tool is analyzed using the criteria of (predictive) fairness developed earlier. (shrink)

:According to Leibniz’s theory for contingent truths about created individuals, this kind of truth cannot be proved in a finite number of steps, because the analyses of the concepts corresponding to these individuals required for the proofs proceed to infinity. Some commentators pointed out that such truths.

In this paper we study the method of refutation rules in the modal logic K4. We introduce refutation rules with certain normal forms that provide a new syntactic decision procedure for this logic. As corollaries we obtain such results for the following important extensions: S4, the provability logic G, and Grzegorczyk's logic. We also show that tree-type models can be constructed from syntactic refutations of this kind.

Cook and Reckhow defined a propositional formulation of the pigeonhole principle. This paper shows that there are Frege proofs of this propositional pigeonhole principle of polynomial size. This together with a result of Haken gives another proof of Urquhart's theorem that Frege systems have an exponential speedup over resolution. We also discuss connections to provability in theories of bounded arithmetic.

In this paper, we prove the wellfoundedness of recursive notation systems for reflecting ordinals up to Π₃-reflection by relevant inductive definitions.

A new semantics is presented for the logic of proofs (LP), [1, 2], based on the intuition that it is a logic of explicit knowledge. This semantics is used to give new proofs of several basic results concerning LP. In particular, the realization of S4 into LP is established in a way that carefully examines and explicates the role of the + operator. Finally connections are made with the conventional approach, via soundness and completeness results.

This text is an outgrowth of notes prepared by J. Y. Girard for a course at the University of Paris VII. It deals with the mathematical background of the application to computer science of aspects of logic (namely the correspondence between proposition & types). Combined with the conceptual perspectives of Girard's ideas, this sheds light on both the traditional logic material & its prospective applications to computer science. The book covers a very active & exciting research area, & it will (...) be essential reading for all those working in logic & computer science. (shrink)

We show how to extract effective bounds Φ for $\bigwedge u^1 \bigwedge v \leq_\gamma tu \bigvee w^\eta G_0$ -sentences which depend on u only (i.e. $\bigwedge u \bigwedge v \leq_\gamma tu \bigvee w \leq_\eta \Phi uG_0$ ) from arithmetical proofs which use analytical assumptions of the form \begin{equation*}\tag{*}\bigwedge x^\delta\bigvee y \leq_\rho sx \bigwedge z^\tau F_0\end{equation*} (γ, δ, ρ, and τ are arbitrary finite types, η ≤ 2, G0 and F0 are quantifier-free, and s and t are closed terms). If (...) τ ≤ 2, (*) can be weakened to $\bigwedge x^\delta, z^\tau\bigvee y \leq_\rho sx \bigwedge \tilde{z} \leq_\tau z F_0$ . This is used to establish new conservation results about weak König's lemma. Applications to proofs in classical analysis, especially uniqueness proofs in approximation theory, will be given in subsequent papers. (shrink)

We present an approach in which ancient Greek mathematical proofs by Hippocrates of Chios and Euclid are addressed as a form of (guided) intentional reasoning. Schematically, in a proof, we start with a sentence that works as a premise; this sentence is followed by another, the conclusion of what we might take to be an inferential step. That goes on until the last conclusion is reached. Guided by the text, we go through small inferential steps; in each one, we (...) go through an autonomous reasoning process linking the premise to the conclusion. The reasoning process is accompanied by a metareasoning process. Metareasoning gives rise to a feeling-knowing of correctness. In each step/cycle of the proof, we have a feeling-knowing of correctness. Overall, we reach a feeling of correctness for the whole proof. We suggest that this approach allows us to address the issues of how a proof functions, for us, as an enabler to ascertain the correctness of its argument and how we ascertain this correctness. (shrink)

N. Tennant; XI*—Entailment and Proofs, Proceedings of the Aristotelian Society, Volume 79, Issue 1, 1 June 1979, Pages 167–190, https://doi.org/10.1093/aristote.

In this paper we extend to non-classical set theories the standard strategy of proving independence using Boolean-valued models. This extension is provided by means of a new technique that, combining algebras (by taking their product), is able to provide product-algebra-valued models of set theories. In this paper we also provide applications of this new technique by showing that: (1) we can import the classical independence results to non-classical set theory (as an example we prove the independence of $\mathsf {CH}$ ); (...) and (2) we can provide new independence results. We end by discussing the role of non-classical algebra-valued models for the debate between universists and multiversists and by arguing that non-classical models should be included as legitimate members of the multiverse. (shrink)

Logic of proofs LP was introduced by S. Artemov in. It describes properties of the proof predicate “t is a proof of F” formalized by the formula ⟦t⟧ F. Proofs are represented by terms constructed by three elementary recursive operations on proofs. In this paper we extend the language of the logic of proofs by the additional storage predicate x ∋ F with the intended interpretation “x is a label for F”. The storage predicate can play (...) the role of syntax encoding, so it is useful for specification of operations on proofs, especially those that require formula arguments. We give a definition of a specification of an operation on proofs and introduce logics that describe such operations. For a large class of operations we prove the completeness of these logics with respect to the intended semantics. We also study the logic describing the operation of substitution. (shrink)

It is a common thought that mathematics can be not only true but also beautiful, and many of the greatest mathematicians have attached central importance to the aesthetic merit of their theorems, proofs and theories. But how, exactly, should we conceive of the character of beauty in mathematics? In this paper I suggest that Kant's philosophy provides the resources for a compelling answer to this question. Focusing on §62 of the ‘Critique of Aesthetic Judgment’, I argue against the common (...) view that Kant's aesthetics leaves no room for beauty in mathematics. More specifically, I show that on the Kantian account beauty in mathematics is a non-conceptual response felt in light of our own creative activities involved in the process of mathematical reasoning. The Kantian proposal I thus develop provides a promising alternative to Platonist accounts of beauty widespread among mathematicians. While on the Platonist conception the experience of mathematical beauty consists in an intellectual insight into the fundamental structures of the universe, according to the Kantian proposal the experience of beauty in mathematics is grounded in our felt awareness of the imaginative processes that lead to mathematical knowledge. The Kantian account I develop thus offers to elucidate the connection between aesthetic reflection, creative imagination and mathematical cognition. (shrink)

We present well-ordering proofs for Martin-Löf's type theory with W-type and one universe. These proofs, together with an embedding of the type theory in a set theoretical system as carried out in Setzer show that the proof theoretical strength of the type theory is precisely ψΩ1Ω1 + ω, which is slightly more than the strength of Feferman's theory T0, classical set theory KPI and the subsystem of analysis + . The strength of intensional and extensional version, of the (...) version à la Tarski and à la Russell are shown to be the same. (shrink)

We present a general lemma which allows proving determinacy from Woodin cardinals. The lemma can be used in many different settings. As a particular application we prove the determinacy of sets in [Formula: see text], n ≥ 1. The assumption we use to prove [Formula: see text] determinacy is optimal in the base theory of [Formula: see text] determinacy.

We prove that for sufficiently large N, there are tautologies of size O that require proofs containing Ω lines in axiomatic systems of propositional logic based on axioms and the rule of substitution for single variables. These tautologies have proofs with O lines in systems with the multiple substitution rule.