In this paper, we investigate the family LS0.5 of many-valued modal logics LS0.5's. We prove that the modalities of necessity and possibility of the logics LS0.5's capture well-defined bivalent concepts of logical validity and logical consistency. We also show that these modalities can be used as recovery operators.

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 traditional analysis of the basic version of the double-slit experiment leads to the conclusion that wave-particle duality is a fundamental fact of nature. However, such a conclusion means to imply that we are not only required to have two contradictory pictures of reality but also compelled to abandon the objectiveness of the truth values, “true” and “false”. Yet, even if we could accept wave-like behavior of quantum particles as the best explanation for the build-up of an interference pattern in (...) the double-slit experiment, without the objectivity of the truth values we would never have certainty regarding any statement about the world. The present paper discusses ways to reconcile the correct description of the double-slit experiment with the objectiveness of “true” and “false”. (shrink)

This paper collects and presents unpublished notes of Kurt Gödel concerning the field of many-valued logic. In order to get a picture as complete as possible, both formal and philosophical notes, transcribed from the Gabelsberger shorthand system, are included.

Il s’agit de comprendre dans cet article l’opposition formulée par Gilles-Gaston Granger entre deux types de négation : la négation « radicale », d’un côté, et les négations « appliquées » de l’autre. Nous examinerons les propriétés de cette opposition, ainsi que les enseignements à en tirer sur la philosophie de la logique de Granger. Puis nous proposerons une théorie constructive des valeurs logiques considérées comme des objets structurés, consolidant à la fois l’unité de la théorie logique de Granger et (...) son pluralisme philosophique. (shrink)

Kooi and Tamminga's correspondence analysis is a technique for designing proof systems, mostly, natural deduction and sequent systems. In this paper it is used to generate sequent calculi with invertible rules, whose only branching rule is the rule of cut. The calculi pertain to classical propositional logic and any of its fragments that may be obtained from adding a set of rules characterizing a two-argument Boolean function to the negation fragment of classical propositional logic. The properties of soundness and completeness (...) of the calculi are demonstrated. The proof of completeness is conducted by Kalmár's method. Most of the presented sequent-calculus rules have been obtained automatically, by a rule-generating algorithm implemented in Python. Correctness of the algorithm is demonstrated. This automated approach allowed us to analyse thousands of possible rules' schemes, hundreds of rules corresponding to Boolean functions, and to nd dozens of those invertible. Interestingly, the analysis revealed that the presented proof-theoretic framework provides a syntactic characteristics of such an important semantic property as functional completeness. (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)

This paper presents a semantical analysis of the Weak Kleene Logics Kw3 and PWK from the tradition of Bochvar and Halldén. These are three-valued logics in which a formula takes the third value if at least one of its components does. The paper establishes two main results: a characterisation result for the relation of logical con- sequence in PWK – that is, we individuate necessary and sufficient conditions for a set.

In this paper, we extend the expressive power of the logics K3, LP and FDE with anormality operator, which is able to express whether a for-mula is assigned a classical truth value or not. We then establish classical recapture theorems for the resulting logics. Finally, we compare the approach via normality operator with the classical collapse approach devisedby Jc Beall.

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)

In this paper, I consider a family of three-valued regular logics: the well-known strong and weak S.C. Kleene’s logics and two intermedi- ate logics, where one was discovered by M. Fitting and the other one by E. Komendantskaya. All these systems were originally presented in the semantical way and based on the theory of recursion. However, the proof theory of them still is not fully developed. Thus, natural deduction sys- tems are built only for strong Kleene’s logic both with one (...) (A. Urquhart, G. Priest, A. Tamminga) and two designated values (G. Priest, B. Kooi, A. Tamminga). The purpose of this paper is to provide natural deduction systems for weak and intermediate regular logics both with one and two designated values. (shrink)

The Belnap–Dunn logic is a well-known and well-studied four-valued logic, but until recently little has been known about its extensions, i.e. stronger logics in the same language, called super-Belnap logics here. We give an overview of several results on these logics which have been proved in recent works by Přenosil and Rivieccio. We present Hilbert-style axiomatizations, describe reduced matrix models, and give a description of the lattice of super-Belnap logics and its connections with graph theory. We adopt the point of (...) view ofAlgebraic Logic, exploring applications of the general theory of algebraization of logics to the super-Belnap family. In this respect we establish a number of new results, including a description of the algebraic counterparts, Leibniz filters, and strong versions of super-Belnap logics, as well as the classification of these logics within the Leibniz and Frege hierarchies. (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)

This article offers an explanation of perhaps Wittgenstein’s strangest and least intuitive thesis – the semantical mutation thesis – according to which one can never answer a mathematical conjecture because the new proof alters the very meanings of the terms involved in the original question. Instead of basing our justification on the distinction between mere calculation and proofs of isolated propositions, characteristic of Wittgenstein’s intermediary period, we generalize it to include conjectures involving effective procedures as well.

I apply Kooi and Tamminga's (2012) idea of correspondence analysis for many-valued logics to strong three-valued logic (K3). First, I characterize each possible single entry in the truth-table of a unary or a binary truth-functional operator that could be added to K3 by a basic inference scheme. Second, I define a class of natural deduction systems on the basis of these characterizing basic inference schemes and a natural deduction system for K3. Third, I show that each of the resulting natural (...) deduction systems is sound and complete with respect to its particular semantics. Among other things, I thus obtain a new proof system for Lukasiewicz's three-valued logic. (shrink)

A survey is given of three-valued paraconsistent propositionallogics connected with Jaśkowski’s criterion for constructing paraconsistentlogics. Several problems are raised and four new matrix three-valued paraconsistent logics are suggested.

This article has one aim, to reject the claim that negation is semantically ambiguous. The first section presents the putative incompatibility between truth-value gaps and the truth-schema; the second section presents the motivation for the ambiguity thesis; the third section summarizes arguments against the claim that natural language negation is semantically ambiguous; and the fourth section indicates the problems of an introduction of two distinct negation operators in natural language.

The Monist’s call for papers for this issue ended: “if formalism is true, then it must be possible in principle to mechanize meaning in a conscious thinking and language-using machine; if intentionalism is true, no such project is intelligible”. We use the Grelling-Nelson paradox to show that natural language is indefinitely extensible, which has two important consequences: it cannot be formalized and model theoretic semantics, standard for formal languages, is not suitable for it. We also point out that object-object mapping (...) theories of semantics, the usual account for the possibility of non intentional semantics, doesn’t seem able to account for the indefinitely extensible productivity of natural language. (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)

This little gem is stated unbilled and proved in the last two lines of §2 of the short note Kleene [1938]. In modern notation, with all the hypotheses stated explicitly and in a strong form, it reads as follows:Second Recursion Theorem. Fix a set V ⊆ ℕ, and suppose that for each natural number n ϵ ℕ = {0, 1, 2, …}, φn: ℕ1+n ⇀ V is a recursive partial function of arguments with values in V so that the standard (...) assumptions and hold with. Every n-ary recursive partial function with values in V is for some e. For all m, n, there is a recursive function : Nm+1 → ℕ such that.Then, for every recursive, partial function f of arguments with values in V, there is a total recursive function of m arguments such thatProof. Fix e ϵ ℕ such that and let.We will abuse notation and write ž; rather than ž() when m = 0, so that takes the simpler formin this case ). (shrink)

1. Pohlers and The Problem. I first met Wolfram Pohlers at a workshop on proof theory organized by Walter Felscher that was held in Tübingen in early April, 1973. Among others at that workshop relevant to the work surveyed here were Kurt Schütte, Wolfram’s teacher in Munich, and Wolfram’s fellow student Wilfried Buchholz. This is not meant to slight in the least the many other fine logicians who participated there.2 In Tübingen I gave a couple of survey lectures on results (...) and problems in proof theory that had been occupying much of my attention during the previous decade. The following was the central problem that I emphasized there: The need for an ordinally informative, conceptually clear, proof-theoretic reduction of classical theories of iterated arithmetical inductive definitions to corresponding constructive systems. As will be explained below, meeting that need would be significant for the then ongoing efforts at establishing the constructive foundation for and proof-theoretic ordinal analysis of certain impredicative subsystems of classical analysis. I also spoke in Tübingen about. (shrink)

The development of recursion theory motivated Kleene to create regular three-valued logics. Remove it taking his inspiration from the computer science, Fitting later continued to investigate regular three-valued logics and defined them as monotonic ones. Afterwards, Komendantskaya proved that there are four regular three-valued logics and in the three-valued case the set of regular logics coincides with the set of monotonic logics. Next, Tomova showed that in the four-valued case regularity and monotonicity do not coincide. She counted that there are (...) 6400 four-valued regular logics, but only six of them are monotonic. The purpose of this paper is to create natural deduction systems for them. We also describe some functional properties of these logics. (shrink)

An overview of contemporary part-whole theories, with reference to both their axiomatic developments and their philosophical underpinnings.

Since its first appearance in 1966, the notion of a supervaluation has been regarded by many as a powerful tool for dealing with semantic gaps. Only recently, however, applications to semantic gluts have also been considered. In previous work I proposed a general framework exploiting the intrinsic gap/glut duality. Here I also examine an alternative account where gaps and gluts are treated on a par: although they reflect opposite situations, the semantic upshot is the same in both cases--the value of (...) some expressions is not uniquely defined. Other strategies for generalizing supervaluations are considered and some comparative facts are discussed. (shrink)

Imperatives cannot be true or false, so they are shunned by logicians. And yet imperatives can be combined by logical connectives: "kiss me and hug me" is the conjunction of "kiss me" with "hug me". This example may suggest that declarative and imperative logic are isomorphic: just as the conjunction of two declaratives is true exactly if both conjuncts are true, the conjunction of two imperatives is satisfied exactly if both conjuncts are satisfied—what more is there to say? Much more, (...) I argue. "If you love me, kiss me", a conditional imperative, mixes a declarative antecedent ("you love me") with an imperative consequent ("kiss me"); it is satisfied if you love and kiss me, violated if you love but don't kiss me, and avoided if you don't love me. So we need a logic of three -valued imperatives which mixes declaratives with imperatives. I develop such a logic. (shrink)

The aim of this paper is to comprehensively question the validity of the standard way of interpreting Chaitin's famous incompleteness theorem, which says that for every formalized theory of arithmetic there is a finite constant c such that the theory in question cannot prove any particular number to have Kolmogorov complexity larger than c. The received interpretation of theorem claims that the limiting constant is determined by the complexity of the theory itself, which is assumed to be good measure of (...) the strength of the theory. I exhibit certain strong counterexamples and establish conclusively that the received view is false. Moreover, I show that the limiting constants provided by the theorem do not in any way reflect the power of formalized theories, but that the values of these constants are actually determined by the chosen coding of Turing machines, and are thus quite accidental. (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)

By and large, the conditional connective in three-valued logic has two different functions. First, by means of a deduction theorem, it can express a specific relation of logical consequence in the logical language itself. Second, it can represent natural language structures such as "if/then'' or "implies''. This chapter surveys both approaches, shows why none of them will typically end up with a three-valued material conditional, and elaborates on connections to probabilistic reasoning.

We work with weakly precomplete equivalence relations introduced by Badaev. The weak precompleteness is a natural notion inspired by various fixed point theorems in computability theory. Let E be an equivalence relation on the set of natural numbers $$\omega $$, having at least two classes. A total function f is a diagonal function for E if for every x, the numbers x and f(x) are not E-equivalent. It is known that in the case of c.e. relations E, the weak precompleteness (...) of E is equivalent to the lack of computable diagonal functions for E. Here we prove that this result fails already for $$\Delta ^0_2$$ equivalence relations, starting with the $$\Pi ^{-1}_2$$ level. We focus on the Turing degrees of possible diagonal functions. We prove that for any noncomputable c.e. degree $${\textbf{d}}$$, there exists a weakly precomplete c.e. equivalence E admitting a $${\textbf{d}}$$ -computable diagonal function. We observe that a Turing degree $${\textbf{d}}$$ can compute a diagonal function for every $$\Delta ^0_2$$ equivalence relation E if and only if $${\textbf{d}}$$ computes $${\textbf{0}}'$$. On the other hand, every PA degree can compute a diagonal function for an arbitrary c.e. equivalence E. In addition, if $${\textbf{d}}$$ computes diagonal functions for all c.e. E, then $${\textbf{d}}$$ must be a DNC degree. (shrink)

Motivated by supplying a new strategy for connexive logic and a better semantics for conditionals so that negating a conditional amounts to negating its consequent under the condition, we propose a new semantics for connexive conditional logic, by combining Kleene’s three-valued logic and a slight modification of Stalnaker’s semantics for conditionals. In the new semantics, selection functions for selecting closest worlds for evaluating conditionals can be undefined. Truth and falsity conditions for conditionals are then supplemented with a precondition that the (...) selection function is defined. Based on the new semantics, we define six conditional logics by different classes of models, using two notions of validity, one preserving truth and the other preserving tolerant truth. We prove soundness and completeness of these logics and compare them with some conditional logics in the literature. Our partial function plus precondition strategy may be used in other semantic frameworks to generate more connexive logics. (shrink)

We consider so‐called extremal numberings that form the greatest or minimal degrees under the reducibility of all A‐computable numberings of a given family of subsets of, where A is an arbitrary oracle. Such numberings are very common in the literature and they are called universal and minimal A‐computable numberings, respectively. The main question of this paper is when a universal or a minimal A‐computable numbering satisfies the Recursion Theorem (with parameters). First we prove that the Turing degree of a set (...) A is hyperimmune if and only if every universal A‐computable numbering satisfies the Recursion Theorem. Next we prove that any universal A‐computable numbering satisfies the Recursion Theorem with parameters if A computes a non‐computable c.e. set. We also consider the property of precompleteness of universal numberings, which in turn is closely related to the Recursion Theorem. Ershov proved that a numbering is precomplete if and only if it satisfies the Recursion Theorem with parameters for partial computable functions. In this paper, we show that for a given A‐computable numbering, in the general case, the Recursion Theorem with parameters for total computable functions is not equivalent to the precompleteness of the numbering, even if it is universal. Finally we prove that if A is high, then any infinite A‐computable family has a minimal A‐computable numbering that satisfies the Recursion Theorem. (shrink)

In Honour of John Crossley’s 85th Birthday.

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)

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)

This paper introduces a logical analysis of convex combinations within the framework of Łukasiewicz real-valued logic. This provides a natural link between the fields of many-valued logics and decision theory under uncertainty, where the notion of convexity plays a central role. We set out to explore such a link by defining convex operators on MV-algebras, which are the equivalent algebraic semantics of Łukasiewicz logic. This gives us a formal language to reason about the expected value of bounded random variables. As (...) an illustration of the applicability of our framework we present a logical version of the Anscombe–Aumann representation result. (shrink)

Hay and, then, Johnson extended the classic Rice and Rice-Shapiro Theorems for computably enumerable sets, to analogs for all the higher levels in the finite Ershov Hierarchy. The present paper extends their work to analogs in the transfinite Ershov Hierarchy. Some of the transfinite cases are done for all transfinite notations in Kleene's important system of notations, equation image. Other cases are done for all transfinite notations in a very natural, proper subsystem equation image of equation image, where equation image (...) has at least one notation for each constructive ordinal. In these latter cases it is open as to what happens for the entire set of transfinite notations in equation image. (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)

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)

The mediaeval logic of Aristotelian privation, represented by Ockham's expositionof All A is non-P as All S is of a type T that is naturally P and no S is P, iscritically evaluated as an account of privative negation. It is argued that there aretwo senses of privative negation: (1) an intensifier (as in subhuman), the dualof Neoplatonic hypernegation (superhuman), which is studied in linguistics asan operator on scalar adjectives, and (2) a (often lexicalized) Boolean complementrelative to the extension of (...) a privative negation in sense (1) (e.g., Brute). Thissecond sense, which is the privative negation discussed in modern linguistics, isshown to be Aristotle's. It is argued that Ockham's exposition fails to capture muchof the logic of Aristotelian privation due to limitations in the expressive power of thesyllogistic. (shrink)

We consider the informal concept of "computability" or "effective calculability" and two of the formalisms commonly used to define it, "(Turing) computability" and "(general) recursiveness". We consider their origin, exact technical definition, concepts, history, general English meanings, how they became fixed in their present roles, how they were first and are now used, their impact on nonspecialists, how their use will affect the future content of the subject of computability theory, and its connection to other related areas. After a careful (...) historical and conceptual analysis of computability and recursion we make several recommendations in section §7 about preserving the intensional differences between the concepts of "computability" and "recursion." Specifically we recommend that: the term "recursive" should no longer carry the additional meaning of "computable" or "decidable;" functions defined using Turing machines, register machines, or their variants should be called "computable" rather than "recursive;" we should distinguish the intensional difference between Church's Thesis and Turing's Thesis, and use the latter particularly in dealing with mechanistic questions; the name of the subject should be "Computability Theory" or simply Computability rather than "Recursive Function Theory.". (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)

The present paper attempts to provide an exact truthmaker semantical analysis of modalized propositions. According to the present proposal, an exact truthmaker for “Necessarily _P_” is a state that bans every exact truthmaker for “Not _P_”, and an exact truthmaker for “Possibly _P_” is a state that allows an exact truthmaker for _P_. Based on this proposal, a formal semantics will be developed; and the soundness and completeness results for a well-known family of the systems of normal modal propositional logic (...) will be established. It shall be seen that the present analysis offers an exactification of the standard Kripke semantics in the sense that it analyzes the accessibility relation between possible worlds in terms of the banning and allowing relations between the constituent states, and thereby gives an account of “truth at a possible world” in terms of exact truthmaking. (shrink)

We present a novel treatment of set theory in a four-valued paraconsistent and paracomplete logic, i.e., a logic in which propositions can be both true and false, and neither true nor false. Our approach is a significant departure from previous research in paraconsistent set theory, which has almost exclusively been motivated by a desire to avoid Russell’s paradox and fulfil naive comprehension. Instead, we prioritise setting up a system with a clear ontology of non-classical sets, which can be used to (...) reason informally about incomplete and inconsistent phenomena, and is sufficiently similar to ${\mathrm {ZFC}}$ to enable the development of interesting mathematics. We propose an axiomatic system ${\mathrm {BZFC}}$, obtained by analysing the ${\mathrm {ZFC}}$ -axioms and translating them to a four-valued setting in a careful manner, avoiding many of the obstacles encountered by other attempted formalizations. We introduce the anti-classicality axiom postulating the existence of non-classical sets, and prove a surprising results stating that the existence of a single non-classical set is sufficient to produce any other type of non-classical set. Our theory is naturally bi-interpretable with ${\mathrm {ZFC}}$, and provides a philosophically satisfying view in which non-classical sets can be seen as a natural extension of classical ones, in a similar way to the non-well-founded sets of Peter Aczel [1]. Finally, we provide an interesting application concerning Tarski semantics, showing that the classical definition of the satisfaction relation yields a logic precisely reflecting the non-classicality in the meta-theory. (shrink)

Two semantic paradoxes, the Liar and Curry’s paradox, are analysed using a newly developed conception of procedural semantics (semantics according to which the truth of propositions is determined algorithmically), whose main characteristic is its departure from methodological realism. Rather than determining pre-existing facts, procedures are constitutive of them. Of this semantics, two versions are considered: closed (where the halting of procedures is presumed) and open (without this presumption). To this end, a procedural approach to deductive reasoning is developed, based on (...) the idea of simulation. As is shown, closed semantics supports classical logic, but cannot in any straightforward way accommodate the concept of truth. In open semantics, where paradoxical propositions naturally ‘belong’, they cease to be paradoxical; yet, it is concluded that the natural choice—for logicians and common people alike—is to stick to closed semantics, pragmatically circumventing problematic utterances. (shrink)

Alonzo Church (1903–1995) was a renowned mathematical logician, philosophical logician, philosopher, teacher and editor. He was one of the founders of the discipline of mathematical logic as it developed after Cantor, Frege and Russell. He was also one of the principal founders of the Association for Symbolic Logic and the Journal of Symbolic Logic. The list of his students, mathematical and philosophical, is striking as it contains the names of renowned logicians and philosophers. In this article, we focus primarily on (...) Church’s philosophical contributions. (For an account of his life and academic history see the Introduction to The Collected Works of Alonzo Church (2019).) However, we also discuss his mathematical results when it is desirable to do so in order to pursue a philosophical issue. (shrink)

Epistemicists claim that if it is vague whether p, it is unknowable whether p. Some contest this on epistemic grounds: vague intuitions about vague matters need not fully preclude knowledge, if those intuitions are response-dependent in some special sense of enabling vague knowledge. This paper defends the epistemicist principle that vagueness entails ignorance against such objections. I argue that not only is response-dependence an implausible characterization of actual vague matters, its mere possibility poses no threat to epistemicism and is properly (...) accounted for by the epistemicist’s own principles. (shrink)