Free logics are a family of first-order logics which came about as a result of examining the existence assumptions of classical logic (Hintikka _The Journal of Philosophy_, _56_, 125–137 1959 ; Lambert _Notre Dame Journal of Formal Logic_, _8_, 133–144 1967, 1997, 2001 ). What those assumptions are varies, but the central ones are that (i) the domain of interpretation is not empty, (ii) every name denotes exactly one object in the domain and (iii) the quantifiers have existential import. Free (...) logics reject the claim that names need to denote in (ii). _Positive_ free logic concedes that some atomic formulas containing non-denoting names (including self-identity) are true, _negative_ free logic treats them as uniformly false, and _neutral_ free logic as taking a third value. There has been a renewed interest in analyzing proof theory of free logic in recent years, based on intuitionistic logic in Maffezioli and Orlandelli (_Bulletin of the Section of Logic_, _48_(2), 137–158 2019 ) as well as classical logic in Pavlović and Gratzl (_Journal of Philosophical Logic_, _50_, 117–148 2021 ), there for the positive and negative variants. While the latter streamlines the presentation of free logics and offers a more unified approach to the variants under consideration, it does not cover neutral free logic, since there is some lack of both clear formal intuitions on the semantic status of formulas with empty names, as well as a satisfying account of the conditional in this context. We discuss extending the results to this third major variant of free logics. We present a series of G3 sequent calculi adapted from Fjellstad (_Studia Logica_, _105_(1), 93–119 2017, _Journal of Applied Non-Classical Logics_, _30_(3), 272–289 2020 ), which possess all the desired structural properties of a good proof system, including admissibility of contraction and all versions of the cut rule. At the same time, we maintain the unified approach to free logics and moreover argue that greater clarity of intuitions is achieved once neutral free logic is conceptualized as consisting of two sub-varieties. (shrink)

In Honour of John Crossley’s 85th Birthday.

Structuralism about mathematical objects and structuralist accounts of physical computation both face indeterminacy objections. For the former, the problem arises for cases such as the complex roots i and \, for which a automorphism can be defined, thus establishing the structural identity of these importantly distinct mathematical objects. In the case of the latter, the problem arises for logical duals such as AND and OR, which have invertible structural profiles :369–400, 2001). This makes their physical implementations indeterminate, in the sense (...) that their structural profiles alone cannot establish whether a given physical component is an AND-gate or an OR-gate. Doherty has recently shown both problems to be analogous, and has argued that computational structuralism is threatened with the absurd conclusion that computational digits might be indiscernible, such that, if structural properties are all that we have to go on, the binary digit 0 must be treated as identical to the binary digit 1. However, we think that a solution to the indiscernibility problem for mathematical structuralists, drawing on the work of David Hilbert, can be adapted for the analogous problem in the computational case, thereby rescuing the structuralist approach to physical computation. (shrink)

Ranging from Alan Turing’s seminal 1936 paper to the latest work on Kolmogorov complexity and linear logic, this comprehensive new work clarifies the relationship between computability on the one hand and constructivity on the other. The authors argue that even though constructivists have largely shed Brouwer’s solipsistic attitude to logic, there remain points of disagreement to this day. Focusing on the growing pains computability experienced as it was forced to address the demands of rapidly expanding applications, the content maps the (...) developments following Turing’s ground-breaking linkage of computation and the machine, the resulting birth of complexity theory, the innovations of Kolmogorov complexity and resolving the dissonances between proof theoretical semantics and canonical proof feasibility. Finally, it explores one of the most fundamental questions concerning the interface between constructivity and computability: whether the theory of recursive functions is needed for a rigorous development of constructive mathematics. This volume contributes to the unity of science by overcoming disunities rather than offering an overarching framework. It posits that computability’s adoption of a classical, ontological point of view kept these imperatives separated. In studying the relationship between the two, it is a vital step forward in overcoming the disagreements and misunderstandings which stand in the way of a unifying view of logic. (shrink)

The goal of this paper is to propose correspondence analysis as a technique for generating the so-called erotetic calculi which constitute the method of Socratic proofs by Andrzej Wiśniewski. As we explain in the paper, in order to successfully design an erotetic calculus one needs invertible sequent-calculus-style rules. For this reason, the proposed correspondence analysis resulting in invertible rules can constitute a new foundation for the method of Socratic proofs. Correspondence analysis is Kooi and Tamminga's technique for designing proof systems. (...) In this paper it is used to consider sequent calculi with non-branching, invertible rules for the negation fragment of classical propositional logic and its extensions by binary Boolean functions. (shrink)

In the context of his theory of numberings, Ershov showed that Kleene's recursion theorem holds for any precomplete numbering. We discuss various generalizations of this result. Among other things, we show that Arslanov's completeness criterion also holds for every precomplete numbering, and we discuss the relation with Visser's ADN theorem, as well as the uniformity or nonuniformity of the various fixed point theorems. Finally, we base numberings on partial combinatory algebras and prove a generalization of Ershov's theorem in this context.

Throughout this paper, we are trying to show how and why our Mathematical frame-work seems inappropriate to solve problems in Theory of Computation. More exactly, the concept of turning back in time in paradoxes causes inconsistency in modeling of the concept of Time in some semantic situations. As we see in the first chapter, by introducing a version of “Unexpected Hanging Paradox”,first we attempt to open a new explanation for some paradoxes. In the second step, by applying this paradox, it (...) is demonstrated that any formalized system for the Theory of Computation based on Classical Logic and Turing Model of Computation leads us to a contradiction. We conclude that our mathematical frame work is inappropriate for Theory of Computation. Furthermore, the result provides us a reason that many problems in Complexity Theory resist to be solved.(This work is completed in 2017 -5- 2, it is in vixra in 2017-5-14, presented in Unilog 2018, Vichy). (shrink)

B. Kooi and A. Tamminga present a correspondence analysis for extensions of G. Priest’s logic of paradox. Each unary or binary extension is characterizable by a special operator and analyzable via a sound and complete natural deduction system. The present paper develops a sound and complete proof searching technique for the binary extensions of the logic of paradox.

In this paper we explain that the paraconsistent logic LP promoted by Graham Priest can only be supported by trivial dialetheists, i.e., those who believe that all sentences are dialetheias.

Self-reference has played a prominent role in the development of metamathematics in the past century, starting with Gödel’s first incompleteness theorem. Given the nature of this and other results in the area, the informal understanding of self-reference in arithmetic has sufficed so far. Recently, however, it has been argued that for other related issues in metamathematics and philosophical logic a precise notion of self-reference and, more generally, reference is actually required. These notions have been so far elusive and are surrounded (...) by an aura of scepticism that has kept most philosophers away. In this paper I suggest we shouldn’t give up all hope. First, I introduce the reader to these issues. Second, I discuss the conditions a good notion of reference in arithmetic must satisfy. Accordingly, I then introduce adequate notions of reference for the language of first-order arithmetic, which I show to be fruitful for addressing the aforementioned issues in metamathematics. (shrink)

Using infinite time Turing machines we define two successive extensions of Kleene’s ${\mathcal{O}}$ and characterize both their height and their complexity. Specifically, we first prove that the one extension—which we will call ${\mathcal{O}^{+}}$ —has height equal to the supremum of the writable ordinals, and that the other extension—which we will call ${\mathcal{O}}^{++}$ —has height equal to the supremum of the eventually writable ordinals. Next we prove that ${\mathcal{O}^+}$ is Turing computably isomorphic to the halting problem of infinite time Turing computability, (...) and that ${\mathcal{O}^{++}}$ is Turing computably isomorphic to the halting problem of eventual computability. (shrink)

We associate the semantic game with chance moves conceived by Blinov with Blamey’s partial logic. We give some equivalent alternatives to the semantic game, some of which are with a third player, borrowing the idea of introducing the pseudo-player called Nature in game theory. We observe that IF propositional logic proposed by Sandu and Pietarinen can be equivalently translated to partial logic, which implies that imperfect information may not be necessary for IF propositional logic. We also indicate that some independent (...) quantifiers can be regarded as dependent quantifiers of indeterminate sequence, using the interjunction connective in partial logic. We conclude our paper by indicating some further research in a more general setting. (shrink)

This paper concerns Alan Turing’s ideas about machines, mathematical methods of proof, and intelligence. By the late 1930s, Kurt Gödel and other logicians, including Turing himself, had shown that no finite set of rules could be used to generate all true mathematical statements. Yet according to Turing, there was no upper bound to the number of mathematical truths provable by intelligent human beings, for they could invent new rules and methods of proof. So, the output of a human mathematician, for (...) Turing, was not a computable sequence (i.e., one that could be generated by a Turing machine). Since computers only contained a finite number of instructions (or programs), one might argue, they could not reproduce human intelligence. Turing called this the “mathematical
objection” to his view that machines can think. Logico-mathematical reasons, stemming from his own work, helped to convince Turing that it should be possible to reproduce human intelligence, and eventually compete with it, by developing the appropriate kind of digital computer. He felt it
should be possible to program a computer so that it could learn or discover new rules, overcoming the limitations imposed by the incompleteness and undecidability results in the same way that human
mathematicians presumably do. (shrink)

In a series of works, Pablo Cobreros, Paul Égré, David Ripley and Robert van Rooij have proposed a nontransitive system (call it ‘_K__3__L__P_’) as a basis for a solution to the semantic paradoxes. I critically consider that proposal at three levels. At the level of the background logic, I present a conception of classical logic on which _K__3__L__P_ fails to vindicate classical logic not only in terms of structural principles, but also in terms of operational ones. At the level of (...) the theory of truth, I raise a cluster of philosophical difficulties for a _K__3__L__P_-based system of naive truth, all variously related to the fact that such a system proves things that would seem already by themselves repugnant, even in the absence of transitivity. At the level of the theory of validity, I consider an extension of the _K__3__L__P_-based system of naive validity that is supposed to certify that validity in that system does not fall short of naive validity, argue that such an extension is untenable in that its nontriviality depends on the inadmissibility of a certain irresistible instance of transitivity (whence the advertised “final cut”) and conclude on this basis that the _K__3__L__P_-based system of naive validity cannot coherently be adopted either. At all these levels, a crucial role is played by certain metaentailments and by the extra strength they afford over the corresponding entailments: on the one hand, such strength derives from considerations that would seem just as compelling in a general nontransitive framework, but, on the other hand, such strength wreaks havoc in the particular setting of _K__3__L__P_. (shrink)

The paper’s novelty is in combining two comparatively new fields of research: non-transitive logic and the proof method of correspondence analysis. To be more detailed, in this paper the latter is adapted to Weir’s non-transitive trivalent logic \({\mathbf{NC}}_{\mathbf{3}}\). As a result, for each binary extension of \({\mathbf{NC}}_{\mathbf{3}}\), we present a sound and complete Lemmon-style natural deduction system. Last, but not least, we stress the fact that Avron and his co-authors’ general method of obtaining _n_-sequent proof systems for any _n_-valent logic (...) with deterministic or non-deterministic matrices is not applicable to \({\mathbf{NC}}_{\mathbf{3}}\) and its binary extensions. (shrink)

The rich body of physical theories defines the foundation of our understanding of the world. Its mathematical formulation is based on classical Aristotelian logic. In the philosophy of science the ambiguities, paradoxes, and the possibility of subjective interpretations of facts have challenged binary logic, leading, among other developments, to Gotthard Günther’s theory of polycontexturality. Günther’s theory explains how observers with subjective perception can become aware of their own subjectivity and provides means to describe contradicting or even paradox observations in a (...) logically sound formalism. Here we summarize the formalism behind Günther’s theory and apply it to two well-known examples from physics where different observers operate in distinct and only locally valid logical systems. Using polycontextural logic we show how the emerging awareness of these limitations of logical systems entails the design of mathematical transformations, which then become an integral part of the theory. In our view, this approach offers a novel perspective on the structure of physical theories and, at the same time, emphasizes the relevance of the theory of polycontexturality in modern sciences. (shrink)

In this paper, we study logical systems which represent entailment relations of two kinds. We extend the approach of finding ‘exactly true’ and ‘non-falsity’ versions of four-valued logics that emerged in series of recent works [Pietz & Rivieccio (2013). Nothing but the truth. Journal of Philosophical Logic, 42(1), 125–135; Shramko (2019). Dual-Belnap logic and anything but falsehood. Journal of Logics and their Applications, 6, 413–433; Shramko et al. (2017). First-degree entailment and its relatives. Studia Logica, 105(6), 1291–1317] to the case (...) of infectious logics, namely to the case of Deutsch's logic Sfde introduced in Deutsch [Relevant analytic entailment. The Relevance Logic Newsletter, 2(1), 26–44; The completeness of S. Studia Logica, 38(2), 137–147]. The particular systems obtained in this way are Setl and Snfl. We present them in the form of sequent calculi and prove corresponding soundness and completeness theorems. We illuminate the connection between Setl, Snfl and two well-known systems, strong Kleene three-valued logic K3 and Priest's Logic of Paradox LP. This connection allows us to investigate the characterisation of the entailment relations associated with Setl and Snfl as well as to introduce the notion of ‘infectious analogue’ of a certain logic. We also study implicative extensions of Setl and Snfl and prove soundness and completeness theorems for them as well. (shrink)

We discuss the effectivity of Arslanov’s completeness criterion. In particular, we show that a parameterized version, similar to the recursion theorem with parameters, fails. We also discuss the effectivity of another extension of the recursion theorem, namely Visser’s ADN theorem, as well as that of a joint generalization of the ADN theorem and Arslanov’s completeness criterion.

Logical pluralists are committed to the idea of a neutral metalanguage, which serves as a framework for debates in logic. Two versions of this neutrality can be found in the literature: an agreed upon collection of inferences, and a metalanguage that is neutral as such. I discuss both versions and show that they are not immune to Quinean criticism, which builds on the notion of meaning. In particular, I show that the first version of neutrality is sub-optimal, and hard to (...) reconcile with the theories of meaning for logical constants, and the second version collapses mathematically, if rival logics, as object languages, are treated with charity in the metalanguage. I substantiate by proving a collapse theorem that generalizes familiar results. Thus, the existence of a neutral metalanguage cannot be taken for granted, and meaning-invariant logical pluralism might turn out to be dubious. (shrink)

In this paper, we approach the problem of classical recapture for LP and K3 by using normality operators. These generalize the consistency and determinedness operators from Logics of Formal Inconsistency and Underterminedness, by expressing, in any many-valued logic, that a given formula has a classical truth value (0 or 1). In particular, in the rst part of the paper we introduce the logics LPe and Ke3 , which extends LP and K3 with normality operators, and we establish a classical recapture (...) result based on the two logics. In the second part of the paper, we compare the approach in terms of normality operators with an established approach to classical recapture, namely minimal inconsistency. Finally, we discuss technical issues connecting LPe and Ke3 to the tradition of Logics of Formal Inconsistency and Underterminedness. (shrink)

Psychological research on people’s understanding of natural language connectives has traditionally used truth table tasks, in which participants evaluate the truth or falsity of a compound sentence given the truth or falsity of its components in the framework of propositional logic. One perplexing result concerned the indicative conditional if A then C which was often evaluated as true when A and C are true, false when A is true and C is false but irrelevant“ (devoid of value) when A is (...) false (whatever the value of C). This was called the “psychological defective table of the conditional.” Here we show that far from being anomalous the “defective” table pattern reveals a coherent semantics for the basic connectives of natural language in a trivalent framework. This was done by establishing participants’ truth tables for negation, conjunction, disjunction, conditional, and biconditional, when they were presented with statements that could be certainly true, certainly false, or neither. We review systems of three-valued tables from logic, linguistics, foundations of quantum mechanics, philosophical logic, and artificial intelligence, to see whether one of these systems adequately describes people’s interpretations of natural language connectives. We find that de Finetti’s (1936/1995) three-valued system is the best approximation to participants’ truth tables. (shrink)

We develop a Gentzen-style proof theory for super-Belnap logics, expanding on an approach initiated by Pynko. We show that just like substructural logics may be understood proof-theoretically as logics which relax the structural rules of classical logic but keep its logical rules as well as the rules of Identity and Cut, super-Belnap logics may be seen as logics which relax Identity and Cut but keep the logical rules as well as the structural rules of classical logic. A generalization of the (...) cut elimination theorem for classical propositional logic is then proved and used to establish interpolation for various super-Belnap logics. In particular, we obtain an alternative syntactic proof of a refinement of the Craig interpolation theorem for classical propositional logic discovered recently by Milne. (shrink)

A 4-valued framework is proposed to distinguish intuitionistically valid formulas within classical validities.

ABSTRACT We propose a combination of a fragment of four-valued logic and process algebra. This fragment is geared to a simple relation with process algebra via the conditional guard construct, and can easily be extended to a truth-functionally complete logic. We present an operational semantics in SOS-style, and a completeness result for ACP with conditionals and four- valued logic. Completeness is preserved under the restriction to some other non-classical logics.

Every truth-functional three-valued propositional logic can be conservatively translated into the modal logic S5. We prove this claim constructively in two steps. First, we define a Translation Manual that converts any propositional formula of any three-valued logic into a modal formula. Second, we show that for every S5-model there is an equivalent three-valued valuation and vice versa. In general, our Translation Manual gives rise to translations that are exponentially longer than their originals. This fact raises the question whether there are (...) three-valued logics for which there is a shorter translation into S5. The answer is affirmative: we present an elegant linear translation of the Logic of Paradox and of Strong Three-valued Logic into S5. (shrink)

We introduce a conceptual model for reaching group decisions. Our model extends a well-known, single-agent cognitive model, the recognition-primed decision (RPD) model. The RPD model includes a recognition phase and an evaluation phase. Group extensions of the RPD model, applicable to a group of RPD agents, have been considered in the literature, however the proposed models do not formalize how distributed and possibly inconsistent information can be combined in either phase. We show how such information can be utilized by aggregating (...) it using a specific social choice method, namely judgment aggregation. Our model is applicable to hierarchical groups of agents containing at least one RPD agent. (shrink)

§1. The origins of recursion theory. In dedicating a book to Steve Kleene, I referred to him as the person who made recursion theory into a theory. Recursion theory was begun by Kleene's teacher at Princeton, Alonzo Church, who first defined the class of recursive functions; first maintained that this class was the class of computable functions ; and first used this fact to solve negatively some classical problems on the existence of algorithms. However, it was Kleene who, in his (...) thesis and in his subsequent attempts to convince himself of Church's Thesis, developed a general theory of the behavior of the recursive functions. He continued to develop this theory and extend it to new situations throughout his mathematical career. Indeed, all of the research which he did had a close relationship to recursive functions.Church's Thesis arose in an accidental way. In his investigations of a system of logic which he had invented, Church became interested in a class of functions which he called the λ-definable functions. Initially, Church knew that the successor function and the addition function were λ-definable, but not much else. During 1932, Kleene gradually showed1 that this class of functions was quite extensive; and these results became an important part of his thesis 1935a. (shrink)

Many-valued logics are standardly defined by logical matrices. They are truth-functional. In this paper non truth-functional many-valued semantics are presented, in a philosophical and mathematical perspective.

The aim of this paper is to define a partial Propositional Type Theory. Our system is partial in a double sense: the hierarchy of (propositional) types contains partial functions and some expressions of the language, including formulas, may be undefined. The specific interpretation we give to the undefined value is that of Kleene’s strong logic of indeterminacy. We present a semantics for the new system and prove that every element of any domain of the hierarchy has a name in the (...) object language. Finally, we provide a proof system and a (constructive) proof of completeness. (shrink)

For every partial combinatory algebra, we define a hierarchy of extensionality relations using ordinals. We investigate the closure ordinals of pca’s, i.e., the smallest ordinals where these relations become equal. We show that the closure ordinal of Kleene’s first model is ${\omega _1^{\textit {CK}}}$ and that the closure ordinal of Kleene’s second model is $\omega _1$. We calculate the exact complexities of the extensionality relations in Kleene’s first model, showing that they exhaust the hyperarithmetical hierarchy. We also discuss embeddings of (...) pca’s. (shrink)

In the paper, we apply Kooi and Tamminga’s correspondence analysis to some conventional and functionally incomplete fragments of classical propositional logic. In particular, the paper deals with the implication, disjunction, and negation fragments. Additionally, we consider an application of correspondence analysis to some connectiveless fragment with certain basic properties of the logical consequence relation only. As a result of the application, one obtains a sound and complete natural deduction system for any binary extension of each fragment in question. With the (...) focus on exclusive disjunction we comparatively study the proposed systems. Finally, we discuss Segerberg’s systems for connectiveless and negation fragments and compare them with our systems. (shrink)

ABSTRACTThe paper deals with a problem posed by Mathieu Vidal to provide a formal representation for defective conditional in mathematics Vidal, M. [. The defective conditional in mathematics. Journal of Applied Non-Classical Logics, 24, 169–179]. The key feature of defective conditional is that its truth-value is indeterminate if its antecedent is false. In particular, we are interested in two explanations given by Vidal with the use of trivalent logics. By analysing a simple argument from plane geometry, where defective conditional is (...) in use, he gives two trivalent formal explanations for it. For both explanations, Vidal rigorously shows that trivalent logics cannot adequately represent defective conditional. Preserving Vidal's criteria of defective conditional ad max, we indicate some arguable points in his explanations and present an alternative explanation containing the original conjunction and disjunction in order to show that there are trivalent logics that might be an adequate formal explanation for defective conditional. (shrink)

Correspondence analysis is Kooi and Tamminga’s universal approach which generates in one go sound and complete natural deduction systems with independent inference rules for tabular extensions of many-valued functionally incomplete logics. Originally, this method was applied to Asenjo–Priest’s paraconsistent logic of paradox LP. As a result, one has natural deduction systems for all the logics obtainable from the basic three-valued connectives of LP -language) by the addition of unary and binary connectives. Tamminga has also applied this technique to the paracomplete (...) analogue of LP, strong Kleene logic \. In this paper, we generalize these results for the negative fragments of LP and \, respectively. Thus, the method of correspondence analysis works for the logics which have the same negations as LP or \, but either have different conjunctions or disjunctions or even don’t have them as well at all. Besides, we show that correspondence analyses for the negative fragments of \ and LP, respectively, are also suitable without any changes for the negative fragments of Heyting’s logic \ and its dual \ and LP). (shrink)

This chapter presents a new semantics for inductive empirical knowledge. The epistemic agent is represented concretely as a learner who processes new inputs through time and who forms new beliefs from those inputs by means of a concrete, computable learning program. The agent’s belief state is represented hyper-intensionally as a set of time-indexed sentences. Knowledge is interpreted as avoidance of error in the limit and as having converged to true belief from the present time onward. Familiar topics are re-examined within (...) the semantics, such as inductive skepticism, the logic of discovery, Duhem’s problem, the articulation of theories by auxiliary hypotheses, the role of serendipity in scientific knowledge, Fitch’s paradox, deductive closure of knowability, whether one can know inductively that one knows inductively, whether one can know inductively that one does not know inductively, and whether expert instruction can spread common inductive knowledge—as opposed to mere, true belief—through a community of gullible pupils. (shrink)

This work proposes an understanding of deductive, default and abductive reasoning as different instances of the same phenomenon: epistemic dynamics. It discusses the main intuitions behind each one of these reasoning processes, and suggest how they can be understood as different epistemic actions that modify an agent’s knowledge and/or beliefs in a different way, making formal the discussion with the use of the dynamic epistemic logic framework. The ideas in this paper put the studied processes under the same umbrella, thus (...) highlighting their relationship and allowing a better understanding of how they interact together. (shrink)

First we show that the classical two-player semantic game actually corresponds to a three-valued logic. Then we generalize this result and give an n-player semantic game for an n + 1-valued logic with n binary connectives, each associated with a player. We prove that player i has a winning strategy in game G if and only if the truth value of φ is $t_i $ in the model M, for 1 ≤ i ≤ n; and none of the players has (...) a winning strategy in G if and only if the truth value of φ is $t_o $ in M. (shrink)

Complexity is pleased to announce the installment of Prof Hiroki Sayama as its new Chief Editor. In this Editorial, Prof Sayama describes his feelings about his recent appointment, discusses some of the journal’s journey and relevance to current issues, and shares his vision and aspirations for its future.

My purpose here is purely historical. It is not an attempt to resolve the question as to whether Russell did or did not countenance nonclassical logics, and if so, which nonclassical logics, and still less to demonstrate whether he himself contributed, in any manner, to the development of nonclassical logic. Rather, I want merely to explore and insofar as possible document, whether, and to what extent, if any, Russell interacted with the various, either the various candidates or their, ideas that (...) Dejnožka and others have proposed as potentially influential in Russell’s intellectual reactions to nonclassical logic or to the philosophical concepts that might contribute to his reactions to nonclassical logics. (shrink)