Incompleteness and the Halting Problem

Studia Logica - We present an abstract framework in which we give simple proofs for Gödel’s First and Second Incompleteness Theorems and obtain, as consequences, Davis’,...     

Incompleteness and the Barcan formula

A (normal) system of prepositional modal logic is said to be complete iff it is characterized by a class of (Kripke) frames. When we move to modal predicate logic the question of completeness can again be raised. It is not hard to prove that if a predicate modal logic is complete then it is characterized by the class of all frames for the propositional logic on which it is based. Nor is it hard to prove that if a propositional modal logic is incomplete then so is the predicate logic based on it. But the interesting question is whether a complete propositional modal logic can have an incomplete extension. In 1967 Kripke announced the incompleteness of a predicate extension of S4. The purpose of the present article is to present several such systems. In the first group it is the systemswith the Barcan Formula which are incomplete, while those without are complete. In the second group it is thosewithout the Barcan formula which are incomplete, while those with the Barcan Formula are complete. But all these are based on propositional systems which are characterized by frames satisfying in each case a single first-order sentence.     

Fictionalism and Incompleteness

The modal fictionalist faces a problem due to the fact that her chosen story seems to be incomplete—certain things are neither fictionally true nor fictionally false. The significance of this problem is not localized to modal fictionalism, however, since many fictionalists will face it too. By examining how the fictionalist should analyze the notion of truth according to her story, and, in particular, the role that conditionals play for the fictionalist, I develop a novel and elegant solution to the incompleteness problem.     

Inductive Incompleteness

Nelson Goodman cast the ‘problem of induction’ as the task of articulating the principles and standards by which to distinguish valid from invalid inductive inferences. This paper explores some logical bounds on the ability of a rational reasoner to accomplish this task. By a simple argument, either an inductive inference method cannot admit its own fallibility, or there exists some non-inferable hypothesis whose non-inferability the method cannot infer (violating the principle of ‘negative introspection’). The paper discusses some implications of this limited self-knowledge for the justifiability of inductive inferences, auto-epistemic logic, and the epistemic foundations of game theory.     

Modal Incompleteness Revisited

In this paper, we are going to analyze the phenomenon of modal incompleteness from an algebraic point of view. The usual method of showing that a given logic L is incomplete is to show that for some L and some cannot be separated from by a suitably wide class of complete algebras — usually Kripke algebras. We are going to show that classical examples of incomplete logics, e.g., Fine logic, are not complete with respect to any class of complete BAOs. Even above Grz it is possible to find a continuum of such logics, which immediately implies the existence of a continuum of neighbourhood-incomplete Grz logics. Similar results can be proved for Löb logics. In addition, completely incomplete logics above Grz may be found uniformly as a result of failures of some admissible rule of a special kind.     

Logical Consequence and the Paradoxes

We group the existing variants of the familiar set-theoretical and truth-theoretical paradoxes into two classes: connective paradoxes, which can in principle be ascribed to the presence of a contracting connective of some sort, and structural paradoxes, where at most the faulty use of a structural inference rule can possibly be blamed. We impute the former to an equivocation over the meaning of logical constants, and the latter to an equivocation over the notion of consequence. Both equivocation sources are tightly related, and can be cleared up by adopting a particular substructural logic in place of classical logic. We then argue that our perspective can be justified via an informational semantics of contraction-free substructural logics.     

Minimalism and Paradoxes

This paper argues against minimalism about truth. It does so by way of acomparison of the theory of truth with the theory of sets, and considerationof where paradoxes may arise in each. The paper proceeds by asking twoseemingly unrelated questions. First, what is the theory of truth about?Answering this question shows that minimalism bears important similaritiesto naive set theory. Second, why is there no strengthened version ofRussell's paradox, as there is a strengthened Liar paradox? Answering thisquestion shows that like naive set theory, minimalism is unable to makeadequate progress in resolving the paradoxes, and must be replaced by adrastically different sort of theory. Such a theory, it is shown, must befundamentally non-minimalist.     

Antonyms and Paradoxes

Adjectives can be gradable or non-gradable and this aspect of their meaning is responsible for their different distribution and also for their classification into two different classes of antonyms. Non-gradable antonyms are called contradictories: they are neither true nor false together and exclude any middle term; gradable antonyms are called contraries: they are not simultaneously true, but may be simultaneously false. While with contraries a negative disjunction (neque...neque) can define an intermediate level, with contradictories it simply means that either term of the disjunction is excluded. There are however some Latin examples, such as neque vivus neque mortuus (`neither alive nor dead'), where the negation of a contradictory pair is used to convey a third, intermediate value. This third possibility is precisely what gives place to a paradox. Such an intermediate level can be defined also by terms like semivivus, semianimis (`half-dead'). Following Ducrot's theory on argumentation, such terms represent an argumentative attenuation, not with respect to life, rather with respect to death. With contradictories, in fact, the use of semi-, like the use of negation, gives the assertion of the opposite term as a result.     

The Incompleteness of RGL

RGLis a version of the modal logic GLbased on the relevant logic R. It is shown that the class of RKframes that verify all theorems of RGLalso verify a scheme that we call (!). If RGLhas (!) as a theorem, however, it is not a relevant logic. I go on to show that not all instances of (!) are theorems of RGL, hence this logic is not complete over any class of RKframes.     

On Interpreting Chaitin's Incompleteness Theorem

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.