The paraconsistent system CPQ-ZFC/F is defined. It is shown using strong non-finitary methods that the theorems of CPQ-ZFC/F are exactly the theorems of classical ZFC minus foundation. The proof presented in the paper uses the assumption that a strongly inaccessible cardinal exists. It is then shown using strictly finitary methods that CPQ-ZFC/F is non-trivial. CPQ-ZFC/F thus provides a formulation of set theory that has the same deductive power as the corresponding classical system but is more reliable in that non- (...) class='Hi'>triviality is provable by strictly finitary methods. This result does not contradict Gödel's incompleteness theorem because the proof of the deductive equivalence of the paraconsistent and classical systemss use non-finitary methods. (shrink)

Inquiry into the meaning of logical terms in natural language (‘and’, ‘or’, ‘not’, ‘if’) has generally proceeded along two dimensions. On the one hand, semantic theories aim to predict native speaker intuitions about the natural language sentences involving those logical terms. On the other hand, logical theories explore the formal properties of the translations of those terms into formal languages. Sometimes, these two lines of inquiry appear to be in tension: for instance, our best logical investigation into conditional connectives may (...) show that there is no conditional operator that has all the properties native speaker intuitions suggest if has. Indicative conditionals have famously been the source of one such tension, ever since the triviality proofs of both Lewis (1976) and Gibbard (1981) established conclusions which are in prima facie tension with ordinary judgments about natural language indicative conditionals. In a recent series of papers, Branden Fitelson has strengthened both triviality results (Fitelson 2013, 2015, 2016), revealing a common culprit: a logical schema known as IMPORT-EXPORT. Fitelson’s results focus the tension between the logical results and ordinary judgments, since IMPORT-EXPORT seems to be supported by intuitions about natural language. In this paper, we argue that the intuitions which have been taken to support IMPORT-EXPORT are really evidence for a closely related, but subtly different, principle. We show that the two principles are independent by showing how, given a standard assumption about the conditional operator in the formal language in which IMPORT-EXPORT is stated, many existing theories of indicative conditionals validate one, but not the other. Moreover, we argue that once we clearly distinguish these principles, we can use propositional anaphora to show that IMPORT-EXPORT is in fact not valid for natural language indicative conditionals (given this assumption about the formal conditional operator). This gives us a principled and independently motivated way of rejecting a crucial premise in many triviality results, while still making sense of the speaker intuitions which appeared to motivate that premise. We suggest that this strategy has broad application and an important lesson: in theorizing about the logic of natural language, we must pay careful attention to the translation between the formal languages in which logical results are typically proved, and natural languages which are the subject matter of semantic theory. (shrink)

This paper investigates the link between informational consequence and credence. I first suggest a natural constraint, namely that informational consequence should preserve certainty: on any rational credence distribution, when the premises of an informational inferences have credence 1, the conclusion also has credence 1. Then I show that the certainty‐preserving constraint leads to triviality. In particular, the following three claims are incompatible: (i) informational consequence is extensionally distinct from classical consequence; (ii) informational inferences preserve certainty; (iii) credences obey (a (...) subset of) classical Bayesian constraints. The proof is straightforward, but the theoretical implications are substantial. Informational theorists need to either give up the idea that credence applies to epistemic discourse, or develop a nonclassical theory of credence and credal update. Moreover, the result also suggests that there is a connection between informational consequence and triviality results, including classical triviality results like Lewis's. (shrink)

This paper discusses and relates two puzzles for indicative conditionals: a puzzle about indeterminacy and a puzzle about triviality. Both puzzles arise because of Ramsey's Observation, which states that the probability of a conditional is equal to the conditional probability of its consequent given its antecedent. The puzzle of indeterminacy is the problem of reconciling this fact about conditionals with the fact that they seem to lack truth values at worlds where their antecedents are false. The puzzle of (...) class='Hi'>triviality is the problem of reconciling Ramsey's Observation with various triviality proofs which establish that Ramsey's Observation cannot hold in full generality. In the paper, I argue for a solution to the indeterminacy puzzle and then apply the resulting theory to the triviality puzzle. On the theory I defend, the truth conditions of indicative conditionals are highly context dependent and such that an indicative conditional may be indeterminate in truth value at each possible world throughout some region of logical space and yet still have a nonzero probability throughout that region. (shrink)

This paper presents a range of new triviality proofs pertaining to naïve truth theory formulated in paraconsistent relevant logics. It is shown that excluded middle together with various permutation principles such as A → (B → C)⊩B → (A → C) trivialize naïve truth theory. The paper also provides some new triviality proofs which utilize the axioms ((A → B)∧ (B → C)) → (A → C) and (A → ¬A) → ¬A, the fusion connective and the Ackermann (...) constant. An overview over various ways to formulate Leibniz’s law in non-classical logics and two new triviality proofs for naïve set theory are also provided. (shrink)

§1. Introduction. The classical propositional calculus has an undeserved reputation among logicians as being essentially trivial. I hope to convince the reader that it presents some of the most challenging and intriguing problems in modern logic. Although the problem of the complexity of propositional proofs is very natural, it has been investigated systematically only since the late 1960s. Interest in the problem arose from two fields connected with computers, automated theorem proving and computational complexity theory. The earliest paper in the (...) subject is a ground-breaking article by Tseitin [62], the published version of a talk given in 1966 at a Leningrad seminar. In the three decades since that talk, substantial progress has been made in determining the relative complexity of proof systems, and in proving strong lower bounds for some restricted proof systems. However, major problems remain to challenge researchers. The present paper provides a survey of the field, and of some of the techniques that have proved successful in deriving lower bounds on the complexity of proofs. A major area only touched upon here is the proof theory of bounded arithmetic and its relation to the complexity of propositional proofs. The reader is referred to the book by Buss [10] for background in bounded arithmetic. The forthcoming book by Krajíček [40] also gives a good introduction to bounded arithmetic, as well as covering most of the basic results in complexity of propositional proofs. (shrink)

§1. Introduction. The classical propositional calculus has an undeserved reputation among logicians as being essentially trivial. I hope to convince the reader that it presents some of the most challenging and intriguing problems in modern logic. Although the problem of the complexity of propositional proofs is very natural, it has been investigated systematically only since the late 1960s. Interest in the problem arose from two fields connected with computers, automated theorem proving and computational complexity theory. The earliest paper in the (...) subject is a ground-breaking article by Tseitin [62], the published version of a talk given in 1966 at a Leningrad seminar. In the three decades since that talk, substantial progress has been made in determining the relative complexity of proof systems, and in proving strong lower bounds for some restricted proof systems. However, major problems remain to challenge researchers. The present paper provides a survey of the field, and of some of the techniques that have proved successful in deriving lower bounds on the complexity of proofs. A major area only touched upon here is the proof theory of bounded arithmetic and its relation to the complexity of propositional proofs. The reader is referred to the book by Buss [10] for background in bounded arithmetic. The forthcoming book by Krajíček [40] also gives a good introduction to bounded arithmetic, as well as covering most of the basic results in complexity of propositional proofs. (shrink)

I give an account of proof terms for derivations in a sequent calculus for classical propositional logic. The term for a derivation δ of a sequent Σ≻Δ encodes how the premises Σ and conclusions Δ are related in δ. This encoding is many–to–one in the sense that different derivations can have the same proof term, since different derivations may be different ways of representing the same underlying connection between premises and conclusions. However, not all proof terms for (...) a sequent Σ≻Δ are the same. There may be different ways to connect those premises and conclusions. -/- Proof terms can be simplified in a process corresponding to the elimination of cut inferences in sequent derivations. However, unlike cut elimination in the sequent calculus, each proof term has a unique normal form (from which all cuts have been eliminated) and it is straightforward to show that term reduction is strongly normalising—every reduction process terminates in that unique normal form. Further- more, proof terms are invariants for sequent derivations in a strong sense—two derivations δ1 and δ2 have the same proof term if and only if some permutation of derivation steps sends δ1 to δ2 (given a relatively natural class of permutations of derivations in the sequent calculus). Since not every derivation of a sequent can be permuted into every other derivation of that sequent, proof terms provide a non-trivial account of the identity of proofs, independent of the syntactic representation of those proofs. (shrink)

I argue that No-Ought-From-Is (in the sense that I believe it) is a relatively trivial affair. Of course, when people try to derive substantive or non-vacuous moral conclusions from non-moral premises, they are making a mistake. But No-Non-Vacuous-Ought-From-Is is meta-ethically inert. It tells us nothing about the nature of the moral concepts. It neither refutes naturalism nor supports non-cognitivism. And this is not very surprising since it is merely an instance of an updated version of the conservativeness of logic (in (...) a logically valid inference you don’t get out what you haven’t put in): so long as the expressions F are non-logical, you cannot get non-vacuous F-conclusions from non-F premises. However, the triviality of No-Non-Vacuous-Ought-From-Is is important and its non-profundity profound. No-Ought-From-Is is widely supposed to tell us something significant about the nature of the moral concepts. If, in fact, it tells us nothing, this is a point well worth shouting from the housetops. This brings me to my dispute with Gerhard Schurz who has proved a related version of No-Ought-From-Is, No-Ought-Relevant-Ought-From-Is, a proof which relaxes my assumption that ‘ought’ should not be treated as a logical constant. But if ought is not a logical expression then it does not really matter much that No-Ought-From-Is would be salvageable even if it were. Furthermore, Schurz’s proof depends on special features of the moral concepts and this might afford the basis for an abductive argument to something like non-cognitivism. As an error theorist, and therefore a cognitivist, I object. Finally I take a dim view of deontic logic. Many of its leading principles are false, bordering on the nonsensical, and even the reasonably plausible ones are subject to devastating counter-examples. (shrink)

Functionalism has become one of the predominant theories in the philosophy of mind, with its many merits supposedly including its capacity for precise formulation. The most common method to express this precise formulation is by means of the modified Ramsey sentence. In this article, I will apply work from the field of the philosophy of science to functionalism for the first time, examining how Newman’s objection undermines the Ramsey sentence as a means of formalising functionalism. I will also present a (...) formal variation on Newman’s objection through mathematical induction. Together, these proofs suggest that functionalism formalised by the Ramsey sentence trivially reduces to a kind of behaviourism plus a cardinality constraint on the number of relations holding between mental-relevant behaviours. As most functionalists see functionalism as a distinct theory of mind from behaviourism, this suggests that the modified Ramsey sentence cannot form a satisfactory formalism for functionalism. (shrink)

Dag Prawitz (1971) put forward the idea that an admissible reduction process does not affect the identity of proofs represented by derivations in natural deduction. The idea relies on his conjecture that two derivations represent the same proof if and only if they are equivalent in the sense that they are reflexive, transitive and symmetric closure of the immediate reducibility relation. Schroeder-Heister and Tranchini (2017) accept Prawitz’s conjecture and propose the triviality test as the criterion for admissible reductions. (...) In the present paper, we will consider two main troubles of the triviality test. The first is the obscurity of a method of evaluating admissible reductions. The second is the circularity problem that the triviality test already assumes the set of admissible reduction procedures. For the solution of the problems, we will propose the spoiler test which immunes the problems of the triviality test and has the role of the criterion for admissible reductions. At last, we shall cover a plausible problem of the spoiler test that can be caused by Crabbé’s case. (shrink)

This paper expounds a simple and non-trivial Ramsey Test. Drawing on the work of Peter Gärdenfors, it aims to help establish an epistemic alternative to the semantics of variably strict conditionals by Robert Stalnaker (in: Rescher (ed), Studies in logical theory, Blackwell, Oxford, 1968) and David Lewis (Counterfactuals, Blackwell, Oxford, 1973). The novelty of the present contribution lies in considering the framework of Preferred Subtheories as model of belief change upon which conditionals are defined. The resulting semantics avoids triviality (...) in the sense that a major premise of the proof of Gärdenfors’ triviality theorem is violated. (shrink)

All the way through An.Pr. A9 11, Aristotle gives a new and separate proof of each modal syllogism. He does not take the mixed syllogisms as entirely trivial and obvious. He tries to explain them and to establish their validity. And that is where ...

This paper describes formalizations of Tait's normalization proof for the simply typed λ-calculus in the proof assistants Minlog, Coq and Isabelle/HOL. From the formal proofs programs are machine-extracted that implement variants of the well-known normalization-by-evaluation algorithm. The case study is used to test and compare the program extraction machineries of the three proof assistants in a non-trivial setting.

A minimal theorem in a logic L is an L-theorem which is not a non-trivial substitution instance of another L-theorem. Komori (1987) raised the question whether every minimal implicational theorem in intuitionistic logic has a unique normal proof in the natural deduction system NJ. The answer has been known to be partially positive and generally negative. It is shown here that a minimal implicational theorem A in intuitionistic logic has a unique -normal proof in NJ whenever A is (...) provable without non-prime contraction. The non-prime contraction rule in NJ is the implication introduction rule whose cancelled assumption differs from a propositional variable and appears more than once in the proof. Our result improves the known partial positive solutions to Komori's problem. Also, we present another simple example of a minimal implicational theorem in intuitionistic logic which does not have a unique -normal proof in NJ. (shrink)

This article generalises the refined A-translation method for extracting programs from classical proofs [U. Berger,W. Buchholz, H. Schwichtenberg, Refined program extraction from classical proofs, Annals of Pure and Applied Logic 114 3–25] to the scenario where additional assumptions such as choice principles are involved. In the case of choice principles, this is done by adding computational content to the ‘translated’ assumptions, an idea which goes back to [S. Berardi, M. Bezem, T. Coquand, On the computational content of the axiom of (...) choice, JSL 63 600–622] and has been further elaborated in [U. Berger, P. Oliva, Modified bar recursion and classical dependent choice, in: M. Baaz, S.D. Friedman, J. Kraijcek , Logic Colloquium ’01, in: Lecture Notes in Logic, vol. 20, Springer, Berlin, 2005, pp. 89–107]. We further investigate the applicability of this extension by means of a small but non-trivial example, and discuss the formalisation as well as some optimisations necessary in order to extract terminating programs. Both formalisation and term extraction have been implemented in the interactive proof assistant Minlog. (shrink)

We give two new characterizations of K-triviality. We show that if for all Y such that Ω is Y-random, Ω is -random, then A is K-trivial. The other direction was proved by Stephan and Yu, giving us the first titular characterization of K-triviality and answering a question of Yu. We also prove that if A is K-trivial, then for all Y such that Ω is Y-random, ≡LRY. This answers a question of Merkle and Yu. The other direction is (...) immediate, so we have the second characterization of K-triviality.The proof of the first characterization uses a new cupping result. We prove that if A≰LRB, then for every set X there is a B-random set Y such that X is computable from Y⊕A. (shrink)

It has been argued that reduction procedures are closely connected to the question about identity of proofs and that accepting certain reductions would lead to a trivialization of identity of proofs in the sense that every derivation of the same conclusion would have to be identified. In this paper it will be shown that the question, which reductions we accept in our system, is not only important if we see them as generating a theory of proof identity but is (...) also decisive for the more general question whether a proof has meaningful content. There are certain reductions which would not only force us to identify proofs of different arbitrary formulas but which would render derivations in a system allowing them meaningless. To exclude such cases, a minimal criterion is proposed which reductions have to fulfill to be acceptable. (shrink)

Is there a nontrivial automorphism of the Turing degrees? It is a major open problem of computability theory. Past results have limited how nontrivial automorphisms could possibly be. Here we consider instead how an automorphism might be induced by a function on reals, or even by a function on integers. We show that a permutation of ω cannot induce any nontrivial automorphism of the Turing degrees of members of 2ω, and in fact any permutation that induces the trivial automorphism must (...) be computable.A main idea of the proof is to consider the members of 2ω to be probabilities, and use statistics: from random outcomes from a distribution we can compute that distribution, but not much more. (shrink)

We develop a reading of Moore’s “Proof of an External World” that emphasizes the connections between this paper and Moore’s earlier concerns and strategies. Our reading has the benefit of explaining why the claims that Moore advances in “Proof of an External World” would have been of interest to him, and avoids attributing to him arguments that are either trivial or wildly unsuccessful. Part of the evidence for our view comes from unpublished drafts which, we believe, contain important (...) clues concerning Moore’s aims and intent. While our approach to PEW may be classified alongside other broadly "metaphysical" readings, we believe that a proper recognition of the continuity in Moore’s philosophical concerns and strategies across his philosophical career shows that the customary distinction between "epistemological" and "metaphysical" interpretative approaches to PEW is at best superficial. (shrink)

Much has been said about Moore’s proof of the external world, but the notion of proof that Moore employs has been largely overlooked. I suspect that most have either found nothing wrong with it, or they have thought it somehow irrelevant to whether the proof serves its antiskeptical purpose. I show, however, that Moore’s notion of proof is highly problematic. For instance, it trivializes in the sense that any known proposition is provable. This undermines Moore’s (...) class='Hi'>proof as he conceives it since it introduces a skeptical regress that he goes at length to resist. I go on to consider various revisions of Moore’s notion of proof and finally settle on one that I think is adequate for Moore’s purposes and faithful to what he says concerning immediate knowledge. (shrink)

The “four-color” theorem seems to be generalizable as follows. The four-letter alphabet is sufficient to encode unambiguously any set of well-orderings including a geographical map or the “map” of any logic and thus that of all logics or the DNA plan of any alive being. Then the corresponding maximally generalizing conjecture would state: anything in the universe or mind can be encoded unambiguously by four letters. That admits to be formulated as a “four-letter theorem”, and thus one can search for (...) a properly mathematical proof of the statement. It would imply the “four colour theorem”, the proof of which many philosophers and mathematicians believe not to be entirely satisfactory for it is not a “human proof”, but intermediated by computers unavoidably since the necessary calculations exceed the human capabilities fundamentally. It is furthermore rather unsatisfactory because it consists in enumerating and proving all cases one by one. Sometimes, a more general theorem turns out to be much easier for proving including a general “human” method, and the particular and too difficult for proving theorem to be implied as a corollary in certain simple conditions. The same approach will be followed as to the four colour theorem, i.e. to be deduced more or less trivially from the “four-letter theorem” if the latter is proved. References are only classical and thus very well-known papers: their complete bibliographic description is omitted. (shrink)

Let me begin my reply to Professor Roark’s objections in good old scholastic fashion, by a distinction. Philosophical objections can be good in two senses. In the first, trivial sense, a good objection is one that convincingly shows the presence of a genuine error in a position or reasoning. Such objections are useful, but uninspiring. In the second, non-trivial sense, a good philosophical objection broadens and deepens our understanding of the problems at issue, whether or not they manage to refute (...) the opponent’s position. In this reply I am going to argue that even if Roark’s objections may not be necessarily good in the first, trivial sense, they are.. (shrink)

The chapter is devoted to the probability and acceptability of indicative conditionals. Focusing on three influential theses, the Equation, Adams’ thesis, and the qualitative version of Adams’ thesis, Sikorski argues that none of them is well supported by the available empirical evidence. In the most controversial case of the Equation, the results of many studies which support it are, at least to some degree, undermined by some recent experimental findings. Sikorski discusses the Ramsey Test, and Lewis’s triviality proof, (...) with special attention dedicated to the popular ways of blocking it. Sikorski concludes that the role of the three theses in future studies of conditionals should be re-thought, and he presents alternative proposals. (shrink)

On Hume’s account of motivation, beliefs and desires are very different kinds of propositional attitudes. Beliefs are cognitive attitudes, desires emotive ones. An agent’s belief in a proposition captures the weight he or she assigns to this proposition in his or her cognitive representation of the world. An agent’s desire for a proposition captures the degree to which he or she prefers its truth, motivating him or her to act accordingly. Although beliefs and desires are sometimes entangled, they play very (...) different roles in rational agency. In two classic papers (Lewis 1988, 1996), David Lewis discusses several challenges to this Humean picture, but ultimately rejects them. We think that his discussion of a central anti-Humean alternative – the desire-as-belief thesis – is in need of refinnement. On this thesis, the desire for proposition p is given by the belief that p is desirable. Lewis claims that ‘[e]xcept in trivial cases, [this thesis] collapses into contradiction’(Lewis 1996, p. 308). The problem, he argues, is that the thesis is inconsistent with the purportedly plausible requirement that one’s desire for a proposition should not change upon learning that the proposition is true; call this the invariance requirement. In this paper, we revisit Lewis’s argument. We show that, if one carefully distinguishes between non-evaluative and evaluative propositions, the desire-asbelief thesis can be rendered consistent with the invariance requirement. Lewis’s conclusion holds only under certain conditions: the desire-as-belief thesis conflicts with the invariance requirement if and only if there are certain correlations between non-evaluative and evaluative propositions. But when there are such correlations, we suggest, the invariance requirement loses its plausibility. Thus Lewis’s argument against the desire-as-belief thesis appears to be valid only in cases in which it is unsound. (shrink)

In this paper I propose a new approach to the foundation of mathematics: non-monotonic set theory. I present two completely different methods to develop set theories based on adaptive logics. For both theories there is a finitistic non-triviality proof and both theories contain (a subtle version of) the comprehension axiom schema. The first theory contains only a maximal selection of instances of the comprehension schema that do not lead to inconsistencies. The second allows for all the instances, also (...) the inconsistent ones, but restricts the conclusions one can draw from them in order to avoid triviality. The theories have enough expressive power to form a justification/explication for most of the established results of classical mathematics. They are therefore not limited by Gödel’s incompleteness theorems. This remarkable result is possible because of the non-recursive character of the final proofs of theorems of non-monotonic theories. I shall argue that, precisely because of the computational complexity of these final proofs, we cannot claim that non-monotonic theories are ideal foundations for mathematics. Nevertheless, thanks to their strength, first order language and the recursive dynamic (defeasible) proofs of theorems of the theory, the non-monotonic theories form (what I call) interesting pragmatic foundations. (shrink)

This paper suggests that time could have a much richer mathematical structure than that of the real numbers. Clark & Read (1984) argue that a hypertask (uncountably many tasks done in a finite length of time) cannot be performed. Assuming that time takes values in the real numbers, we give a trivial proof of this. If we instead take the surreal numbers as a model of time, then not only are hypertasks possible but so is an ultratask (a sequence (...) which includes one task done for each ordinal number—thus a proper class of them). We argue that the surreal numbers are in some respects a better model of the temporal continuum than the real numbers as defined in mainstream mathematics, and that surreal time and hypertasks are mathematically possible. (shrink)

Many logical systems are such that the addition of Prior's binary connective tonk to them leads to triviality, see [1, 8]. Since tonk is given by some introduction and elimination rules in natural deduction or sequent rules in Gentzen's sequent calculus, the unwanted effects of adding tonk show that some kind of restriction has to be imposed on the acceptable operational inferences rules, in particular if these rules are regarded as definitions of the operations concerned. In this paper, a (...) number of simple observations is made showing that the unwanted phenomenon exemplified by tonk in some logics also occurs in contexts in which tonk is acceptable. In fact, in any non-trivial context, the acceptance of arbitrary introduction rules for logical operations permits operations leading to triviality. Connectives that in all non-trivial contexts lead to triviality will be called non-trivially trivializing connectives. (shrink)

Transmission of justification across inference is a valuable and indeed ubiquitous epistemic phenomenon in everyday life and science. It is thanks to the phenomenon of epistemic transmission that inferential reasoning is a means for substantiating predictions of future events and, more generally, for expanding the sphere of our justified beliefs or reinforcing the justification of beliefs that we already entertain. However, transmission of justification is not without exceptions. As a few epistemologists have come to realise, more or less trivial forms (...) of circularity can prevent justification from transmitting from p to q even if one has justification for p and one is aware of the inferential link from p to q. In interesting cases this happens because one can acquire justification for p only if one has independent justification for q. In this case the justification for q cannot depend on the justification for p and the inferential link from p to q, as genuine transmission would require. The phenomenon of transmission failure seems to shed light on philosophical puzzles, such as Moore's proof of a material world and McKinsey's paradox, and it plays a central role in various philosophical debates. For this reason it is being granted continued and increasing attention. (shrink)

A new technique for proving realisability results is presented, and is illustrated in detail for the simple case of arithmetic minus induction. CL is a Gentzen formulation of classical logic. CPQ is CL minus the Cut Rule. The basic proof theory and model theory of CPQ and CL is developed. For the semantics presented CPQ is a paraconsistent logic, i.e. there are non-trivial CPQ models in which some sentences are both true and false. Two systems of arithmetic minus induction (...) are introduced, CL-A and CPQ-A based on CL and CPQ, respectively. The realisability theorem for CPQ-A is proved: It is shown constructively that to each theorem A of CPQ-A there is a formula A *, a so-called “realised disjunctive form of A ”, such that variables bound by essentially existential quantifiers in A * can be written as recursive functions of free variables and variables bound by essentially universal quantifiers. Realisability is then applied to prove the consistency of CL-A, making use of certain finite non-trivial inconsistent models of CPQ-A. (shrink)

Non-trivial calculi of inductive inference are incomplete. This result is demonstrated formally elsewhere. Here the significance and background to the result is described. This note explains what is meant by incompleteness, why it is desirable, if only it could be secured, and it gives some indication of the arguments needed to establish its failure. The discussion will be informal, using illustrative examples rather than general results. Technical details and general proofs are presented in Norton.

This work studies some problems connected to the role of negation in logic, treating the positive fragments of propositional calculus in order to deal with two main questions: the proof of the completeness theorems in systems lacking negation, and the puzzle raised by positive paradoxes like the well-known argument of Haskel Curry. We study the constructive com- pleteness method proposed by Leon Henkin for classical fragments endowed with implication, and advance some reasons explaining what makes difficult to extend this (...) constructive method to non-classical fragments equipped with weaker implications (that avoid Curry's objection). This is the case, for example, of Jan Lukasiewicz's n-valued logics and Wilhelm Ackermann's logic of restricted implication. Besides such problems, both Henkin's method and the triviality phenomenon enable us to propose a new positive tableau proof system which uses only positive meta-linguistic resources, and to mo- tivate a new discussion concerning the role of negation in logic proposing the concept of paratriviality. In this way, some relations between positive reasoning and infinity, the possibilities to obtain a ¯first-order positive logic as well as the philosophical connection between truth and meaning are dis- cussed from a conceptual point of view. (shrink)

We characterize when the elementary diagram of a mutually algebraic structure has a model complete theory, and give an explicit description of a set of existential formulas to which every formula is equivalent. This characterization yields a new, more constructive proof that the elementary diagram of any model of a strongly minimal, trivial theory is model complete.

Computer assisted theorem proving is an increasingly important part of mathematical methodology, as well as a long-standing topic in artificial intelligence (AI) research. However, the current generation of theorem proving software have limited functioning in terms of providing new proofs. Importantly, they are not able to discriminate interesting theorems and proofs from trivial ones. In order for computers to develop further in theorem proving, there would need to be a radical change in how the software functions. Recently, machine learning results (...) in solving mathematical tasks have shown early promise that deep artificial neural networks could learn symbolic mathematical processing. In this paper, I analyze the theoretical prospects of such neural networks in proving mathematical theorems. In particular, I focus on the question how such AI systems could be incorporated in practice to theorem proving and what consequences that could have. In the most optimistic scenario, this includes the possibility of autonomous automated theorem provers (AATP). Here I discuss whether such AI systems could, or should, become accepted as active agents in mathematical communities. (shrink)

A logic is said to be contraction free if the rule from A→(A→B) to A→B is not truth preserving. It is well known that a logic has to be contraction free for it to support a non-trivial naïve theory of sets or of truth. What is not so well known is that if there is another contracting implication expressible in the language, the logic still cannot support such a naïve theory. A logic is said to be robustly contraction free if (...) there is no such operator expressible in its language. We show that a large class of finitely valued logics are each not robustly contraction free, and demonstrate that some other contraction free logics fail to be robustly contraction free. Finally, the sublogics of Łω (with the standard connectives) are shown to be robustly contraction free. (shrink)

We give a general proof showing that if the evolution from one state to another is not reversible, then the projective measurements on the superposition of these two states are impossible. Applying this no-go result to the Schrödinger’s cat paradox implies that if something is claimed to be a real Schrödinger’s cat, there will be no measurable difference between it and a trivial classical mixture of ordinary cats in any physically implementable process, unless raising the dead becomes reality. Other (...) similar macroscopic quantum superpositions cannot be observed either, due to the lack of non-commuting measurement bases. Our proof does not involve any quantum interpretation theory and hypothesis. (shrink)

In the paper, the proof of the non-locality of quantum mechanics, given by Bedford and Stapp (1995), and appealing to the GHZ example, is analyzed. The proof does not contain any explicit assumption of realism, but instead it uses formal methods and techniques of the Lewis calculus of counterfactuals. To ascertain the validity of the proof, a formal semantic model for counterfactuals is constructed. With the help of this model it can be shown that the proof (...) is faulty, because it appeals to the unwarranted principle of “elimination of eliminated conditions” (EEC). As an additional way of showing unreasonableness of the assumption (EEC), it is argued that yet another alleged and highly controversial proof of non-locality of QM, using the Hardy example, can be made almost trivial with the help of (EEC). Finally, a general argument is produced to the effect that the locality condition in the form accepted by Stapp and Bedford is consistent with the quantum-mechanical predictions for the GHZ case under the assumption of indeterminism. This result undermines any future attempts of proving the incompatibility between the predictions of quantum theory and the idea of no faster-than-light influence in the GHZ case, quite independently of the negative assessment of the particular derivation proposed by Stapp and Bedford. (shrink)

The classical interpretation of probability together with the principle of indifference is formulated in terms of probability measure spaces in which the probability is given by the Haar measure. A notion called labelling invariance is defined in the category of Haar probability spaces; it is shown that labelling invariance is violated, and Bertrand’s paradox is interpreted as the proof of violation of labelling invariance. It is shown that Bangu’s attempt to block the emergence of Bertrand’s paradox by requiring the (...) re-labelling of random events to preserve randomness cannot succeed non-trivially. A non-trivial strategy to preserve labelling invariance is identified, and it is argued that, under the interpretation of Bertrand’s paradox suggested in the paper, the paradox does not undermine either the principle of indifference or the classical interpretation and is in complete harmony with how mathematical probability theory is used in the sciences to model phenomena. It is shown in particular that violation of labelling invariance does not entail that labelling of random events affects the probabilities of random events. It also is argued, however, that the content of the principle of indifference cannot be specified in such a way that it can establish the classical interpretation of probability as descriptively accurate or predictively successful. (shrink)

Hofstadter [1979, 2007] offered a novel Gödelian proposal which purported to reconcile the apparently contradictory theses that (1) we can talk, in a non-trivial way, of mental causation being a real phenomenon and that (2) mental activity is ultimately grounded in low-level rule-governed neural processes. In this paper, we critically investigate Hofstadter’s analogical appeals to Gödel’s [1931] First Incompleteness Theorem, whose “diagonal” proof supposedly contains the key ideas required for understanding both consciousness and mental causation. We maintain that bringing (...) sophisticated results from Mathematical Logic into play cannot furnish insights which would otherwise be unavailable. Lastly, we conclude that there are simply too many weighty details left unfilled in Hofstadter’s proposal. These really need to be fleshed out before we can even hope to say that our understanding of classical mind-body problems has been advanced through metamathematical parallels with Gödel’s work. (shrink)

This article analyzes the temporal single-system interpretation (TSSI) of Marx’s economics. From a methodological viewpoint, the TSSI lacks both a clear definition of equilibrium and a rigorous analysis of disequilibrium dynamics, and the dynamic framework is incomplete. From a substantive viewpoint, temporal single-system (TSS) claims are trivially obtained by assuming that goods exchange at values, apart possibly from out-of-steady-state random deviations. Finally, the proof of the law of the tendential fall in the profit rate is tautologically true, but its (...) theoretical relevance is unclear. (shrink)

A probability aggregation rule assigns to each profile of probability functions across a group of individuals (representing their individual probability assignments to some propositions) a collective probability function (representing the group's probability assignment). The rule is “non-manipulable” if no group member can manipulate the collective probability for any proposition in the direction of his or her own probability by misrepresenting his or her probability function (“strategic voting”). We show that, except in trivial cases, no probability aggregation rule satisfying two mild (...) conditions (non-dictatorship and consensus preservation) is non-manipulable. (shrink)

In my article on proof [Philosophia Mathematica (3) 5 (1997), 153—165], I suggested or intimated that computer proofs of mathematical theorems had been found only for relatively simple or trivial theorems. I am obligated to Martin Davis and R. S. Boyer for the information that this suggestion or intimation is incorrect. For instance, a machine proof of quadratic reciprocity was published by D. M. Russinoff in J. Automated Reasoning 8 (1992), 3–21. A machine proof of the unsolvability (...) of the halting problem has been published by R S. Boyer and J. S. Moore. This and many other examples are presented in Chapter 1 of their book, A Computational Logic Handbook, Academic Press, 1990. A second edition of this book is expected shortly. (shrink)

This book develops an intellectual framework for analyzing ethical dilemmas that is both grounded in theory and versatile enough to deal rigorously with real-world issues. It sees ethics as a necessary foundation for the social infrastructure that makes modern life possible, much as engineering is a foundation for physical infrastructure. It is not wedded to any particular ethical philosophy but draws from several traditions to construct a unified and principled approach to ethical reasoning. Rather than follow the common academic practice (...) of seeking a reflective equilibrium of moral intuitions and principles, it builds on a few bedrock principles of rational thought that serve as criteria for valid argumentation. It develops the ideas from the ground up, without presupposing any background in ethics or philosophy. Epistemologically, the book views ethics as parallel to mathematics, in that it relies on generally accepted proof techniques to establish results. Whereas mathematics rests on such proof paradigms as mathematical induction and proof by contradiction, ethics can be seen as relying on proof by applying consistency tests, such as generalizability and respect for autonomy. Utilitarianism also plays a key role, but it is reconceived as a deontological criterion. This approach obviously requires that these criteria be formulated more rigorously than is normally the case. To accomplish this, the book begins with the classical idea that an action is distinguishable from mere behavior by virtue of its having a coherent rationale, where coherence requires passing certain consistency tests such as generalizability. An action is therefore inseparable from its rationale, and generalizability is defined in terms of consistency with the rationale. A utilitarian criterion receives a similar treatment with respect to a means-end rationale. Respect for autonomy is grounded in a carefully developed action theory that takes into account such concepts as joint autonomy, implied consent, and the permissibility of interference with unethical behavior. It provides an account of responsibility that is both practical and theoretically satisfying, and it yields a novel solution of the much-discussed trolley car dilemmas. The book is written for a general audience and strives to be as readable and engaging as possible, while maintaining rigor. It begins by dispelling a raft of misconceptions that trivialize ethics and block its development as an essential tool of modern life, such as the notion that ethics is just a matter of opinion without rational foundation. After presenting the ethical principles just described, along with many examples, it provides several chapters that analyze real-life dilemmas, many obtained from the author's students and professional workshop participants. One cannot understand physics or chemistry without seeing how their principles are applied to real problems, and the same is true of ethics. These chapters demonstrate that a unified normative theory can deal with a wide range of real cases while achieving a reasonable level of objectivity and rigor. (shrink)