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)

In this article, I suggest an original solution to the Liar Paradox, based on the pragmatic theory of speech acts. This solution implies making a distinction between two concepts of truth: the intentional truth of a speaker’s utterances directed toward an addressee with the objective of obtaining a consensual agreement; the effective truth objectively recognized by the addressee in the speaker’s utterances. In view of reaching this new solution to the classic paradox, I conduct a critical review of solutions put (...) forward by Tarski, Kripke and Strawson. (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)

In this paper we will discuss the active part played by certain diagonal arguments in the genesis of computability theory. 1 In some cases it is enough to assume the enumerability of Y while in others the effective enumerability is a substantial demand. These enigmatical words by Kleene were our point of departure: When Church proposed this thesis, I sat down to disprove it by diagonalizing out of the class of the λ–definable functions. But, quickly realizing that the diagonalization cannot (...) be done effectively, I became overnight a supporter of the thesis. (1981, p. 59) The title of our paper alludes to this very work, a task on which Kleene claims to have set out after hearing such a remarkable statement from Church, who was his teacher at the time. There are quite a few points made in this extract that may be surprising. First, it talks about a proof by diagonalization in order to test—in fact to try to falsify—a hypothesis that is not strictly formal. Second, it states that such a proof or diagonal construction fails. Third, it seems to use the failure as a support for the thesis. Finally, the episode we have just described took place at a time, autumn 1933, in which many of the results that characterize Computability Theory had not yet materialized. The aim of this paper is to show that Church and Kleene discovered a way to block a very particular instance of a diagonal construction: one that is closely related to the content of Church's thesis. We will start by analysing the logical structure of a diagonal construction. Then we will introduce the historical context in order to analyse the reasons that might have led Kleene to think that the failure of this very specific diagonal proof could support the thesis. This is a joint paper. We have both attempted to add a small piece to an amazing historical jigsaw puzzle at a juncture we feel to be appropiate. In the paper by Manzano 1997 the aforementioned words by Kleene were quoted, and since then several logicians, Enrique Alonso first and foremost, have questioned her on this issue. Here we both submit our reply. (1999, pp. 249--273). (shrink)

The purpose of this article is to examine aspects of the development of the concept and theory of computability through the theory of recursive functions. Following a brief introduction, Section 2 is devoted to the presuppositions of computability. It focuses on certain concepts, beliefs and theorems necessary for a general property of computability to be formulated and developed into a mathematical theory. The following two sections concern situations in which the presuppositions were realized and the theory of computability was developed. (...) It is suggested in Section 3 that a central item was the problem of generalizing Gödel's incompleteness theorem. It is shown that this involved both the characterization of recursiveness and the attempt to clarify and formulate the notion of an effective process as it relates to the syntax of deductive systems. Section 4 concerns the decision problems which grew from the Hilbert program. Section 5 is devoted to the development of an informal' technique in the theory of computability often called ?argument by Church's thesis? (shrink)

In the paper, we tackle the matter of non-classical logics, in particular, paraconsistent ones, for which not every formula follows in general from inconsistent premisses. Our benchmark is Jaśkowski’s logic, modeled with the help of discussion. The second key origin of this paper is the matter of being tabular, i.e. being adequately expressible by finitely many finite matrices. We analyse Jaśkowski’s non-tabular discussive (discursive) logic $ \textbf {D}_{2}$, one of the first paraconsistent logics, from the perspective of a trivalent tabular (...) logic. We are motivated to step down from the ongoing modal $ \textbf {S5}$-perspective of developing $ \textbf {D}_{2}$ both by certain mysteries that have been surrounding it and by gaps in Jaśkowski’s arguments contra the multivalent tabular perspective. Although Jaśkowski’s idea to use $ \textbf {S5}$ in order to define $ \textbf {D}_{2}$ is very attractive since it allows one to benefit from the tools and results of modal logic, it also gives a ‘non-direct’ formulation and, as it appeared later, is superfluous with respect to what is meant to be achieved since one can define the very same logic but using modal logics weaker than S5. It is also known, due to Kotas, that discussive logic is not finite-valued. So, in light of Kotas’s result that $ \textbf {D}_{2}$ is non-tabular, we propose to associate it with a few dozen discussive formulae that Jaśkowski unequivocally and illustratively suggests to be its theorems or non-theorems rather than with axioms of its modern axiomatizations (one of which Kotas employs) in order to be capable of performing a computer-aided brute-force search for suitable trivalent matrices in the cases of one and two designated values. As a result, we find trivalent matrices with two designated values that might be dubbed ‘discussive’ because they meet Jaśkowski’s suggestion to validate and invalidate the litmus theorems and non-theorems, respectively, despite the fact that none of them validates all the negation axioms in the modern axiomatizations of $ \textbf {D}_{2}$. The matrices found are then analysed along with highlighting the ones that were previously mentioned in the literature. We conclude the paper with a comparative analysis of Omori’s results and a test of Karpenko’s hypothesis. (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)

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.

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 this paper, we present sound and complete natural deduction systems for Fitting’s four-valued generalizations of Kleene’s three-valued regular logics.

The purpose of this article is to clarify the role that many-valued logic can or should play in formal specification of software systems for modeling partiality. We analyse a representative set of specification languages. Our findings suggest that many-valued logic is less useful for modeling those aspects of partiality, for which it is traditionally intended: modeling non-termination and error values. On the other hand, many-valued logic is emerging as a mainstream tool in abstraction of formal analyses of various kinds, and (...) we suggest that specification languages feature many-valued abstraction logics. (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)

In this paper, we prove several results about the Turing jumps of low c.e. sets. We show that only Δ‐levels of the Ershov Hierarchy can properly contain the Turing jumps of c.e. sets and that there exists an arbitrarily large computable ordinal with a normal notation such that the corresponding Δ‐level is proper for the Turing jump of some c.e. set. Next, we generalize the notion of jump traceability to the jump traceability with ‐ and ‐bound for every infinite computable (...) ordinal α. It is known that jump traceability and superlowness coincide on the c.e. sets and we show that for every infinite computable ordinal α, jump traceability with ‐ or ‐bound of a c.e. set A is equivalent to the fact that. Finally, we consider the generalized truth‐table reducibilities and prove that for every (not necessarily the Turing jump of a c.e. set) set A and every limit computable ordinal α, iff. (shrink)