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)

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)

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 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)

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)

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)

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)

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)

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)

Shramko [. Truth, falsehood, information and beyond: The American plan generalized. In K. Bimbo, J. Michael Dunn on information based logics, outstanding contributions to logic...

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)

Mathematicians often intentionally leave gaps in their proofs. Based on interviews with mathematicians about their refereeing practices, this paper examines the character of intentional gaps in published proofs. We observe that mathematicians’ refereeing practices limit the number of certain intentional gaps in published proofs. The results provide some new perspectives on the traditional philosophical questions of the nature of proof and of what grounds mathematical knowledge.

The initial premise of this paper is that the structure of a proof is inherent in the definition of the proof. Side conditions to deal with the discharging of assumptions means that this does not hold for systems of natural deduction, where proofs are given by monotone inductive definitions. We discuss the idea of using higher order definitions and the notion of a functional closure as a foundation to avoid these problems. In order to focus on structural issues we (...) introduce a more abstract perspective, where a structural proof theory becomes part of a more general theory of functional closures. A notion of proof equations is discussed as a structural classifier and we compare the Russell and Ekman paradoxes to illustrate this. (shrink)

Inductive characterizations of the sets of terms, the subset of strongly normalizing terms and normal forms are studied in order to reprove weak and strong normalization for the simply-typed λ-calculus and for an extension by sum types with permutative conversions. The analogous treatment of a new system with generalized applications inspired by generalized elimination rules in natural deduction, advocated by von Plato, shows the flexibility of the approach which does not use the strong computability/candidate style à la Tait and Girard. (...) It is also shown that the extension of the system with permutative conversions by η-rules is still strongly normalizing, and likewise for an extension of the system of generalized applications by a rule of ``immediate simplification''. By introducing an infinitely branching inductive rule the method even extends to Gödel's T. (shrink)

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.

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 give examples of calculi that extend Gentzen’s sequent calculusLKby unsound quantifier inferences in such a way that derivations lead only to true sequents, and proofs therein are nonelementarily shorter thanLK-proofs.

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)

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)

In this paper individual proofs are integrated into provability logic. Systems of axioms for a logic with operators “A is provable” and “p is a proof of A” are introduced, provided with Kripke semantics and decision procedure. Completeness theorems with respect to the arithmetical interpretation are proved.

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.

A structure which generalizes formulas by including substitution terms is used to represent proofs in classical logic. These structures, called expansion trees, can be most easily understood as describing a tautologous substitution instance of a theorem. They also provide a computationally useful representation of classical proofs as first-class values. As values they are compact and can easily be manipulated and transformed. For example, we present an explicit transformations between expansion tree proofs and cut-free sequential proofs. A (...) theorem prover which represents proofs using expansion trees can use this transformation to present its proofs in more human-readable form. Also a very simple computation on expansion trees can transform them into Craig-style linear reasoning and into interpolants when they exist. We have chosen a sublogic of the Simple Theory of Types for our classical logic because it elegantly represents substitutions at all finite types through the use of the typed -calculus. Since all the proof-theoretic results we shall study depend heavily on properties of substitutions, using this logic has allowed us to strengthen and extend prior results: we are able to prove a strengthen form of the firstorder interpolation theorem as well as provide a correct description of Skolem functions and the Herbrand Universe. The latter are not straightforward generalization of their first-order definitions. (shrink)

We give proofs of the effective monotone interpolation property for the system of modal logic K, and others, and the system IL of intuitionistic propositional logic. Hence we obtain exponential lower bounds on the number of proof-lines in those systems. The main results have been given in [P. Hrubeš, Lower bounds for modal logics, Journal of Symbolic Logic 72 941–958; P. Hrubeš, A lower bound for intuitionistic logic, Annals of Pure and Applied Logic 146 72–90]; here, we give considerably (...) simplified proofs, as well as some generalisations. (shrink)

“Now, in calm weather, to swim in the open ocean is as easy to the practised swimmer as to ride in a spring-carriage ashore. But the awful lonesomeness is intolerable. The intense concentration of self in the middle of such a heartless immensity, my God! who can tell it? Mark, how when sailors in a dead calm bathe in the open sea—mark how closely they hug their ship and only coast along her sides.” (Herman Melville, Moby Dick, Chapter 94).

In different papers, Carnielli, W. & Rodrigues, A., Carnielli, W. Coniglio, M. & Rodrigues, A. and Rodrigues & Carnielli, present two logics motivated by the idea of capturing contradictions as conflicting evidence. The first logic is called BLE and the second—that is a conservative extension of BLE—is named LETJ. Roughly, BLE and LETJ are two non-classical logics in which the Laws of Explosion and Excluded Middle are not admissible. LETJ is built on top of BLE. Moreover, LETJ is a Logic (...) of Formal Inconsistency. This means that there is an operator that, roughly speaking, identifies a formula as having classical behavior. Both systems are motivated by the idea that there are different conditions for accepting or rejecting a sentence of our natural language. So, there are some special introduction and elimination rules in the theory that are capturing different conditions of use. Rodrigues & Carnielli’s paper has an interesting and challenging idea. According to them, BLE and LETJ are incompatible with dialetheia. It seems to show that these paraconsistent logics cannot be interpreted using truth-conditions that allow true contradictions. In short, BLE and LETJ talk about conflicting evidence avoiding to talk about gluts. I am going to argue against this point of view. Basically, I will firstly offer a new interpretation of BLE and LETJ that is compatible with dialetheia. The background of my position is to reject the one canonical interpretation thesis: the idea according to which a logical system has one standard interpretation. Then, I will secondly show that there is no logical basis to fix that Rodrigues & Carnielli’s interpretation is the canonical way to establish the content of logical notions of BLE and LETJ. Furthermore, the system LETJ captures inside classical logic. Then, I am also going to use this technical result to offer some further doubts about the one canonical interpretation thesis. (shrink)

Some thirty years ago, two proposals were made concerning criteria for identity of proofs. Prawitz proposed to analyze identity of proofs in terms of the equivalence relation based on reduction to normal form in natural deduction. Lambek worked on a normalization proposal analogous to Prawitz's, based on reduction to cut-free form in sequent systems, but he also suggested understanding identity of proofs in terms of an equivalence relation based on generality, two derivations having the same generality if (...) after generalizing maximally the rules involved in them they yield the same premises and conclusions up to a renaming of variables. These two proposals proved to be extensionally equivalent only for limited fragments of logic. The normalization proposal stands behind very successful applications of the typed lambda calculus and of category theory in the proof theory of intuitionistic logic. In classical logic, however, it did not fare well. The generality proposal was rather neglected in logic, though related matters were much studied in pure category theory in connection with coherence problems, and there are also links to low-dimensional topology and linear algebra. This proposal seems more promising than the other one for the general proof theory of classical logic. (shrink)