We investigate incomplete symbols, i.e. definite descriptions with scope-operators. Russell famously introduced definite descriptions by contextual definitions; in this article definite descriptions are introduced by rules in a specific calculus that is very well suited for proof-theoretic investigations. That is to say, the phrase ‘incomplete symbols’ is formally interpreted as to the existence of an elimination procedure. The last section offers semantical tools for interpreting the phrase ‘no meaning in isolation’ in a formal way.

Russell urged that some phrases having no meaning in isolation could nonetheless, Contribute to the meaning of sentences in which they occur. In the case of definite descriptive phrases, A proof is offered. It is argued that russell's proof is valid, Contrary to some commentators. Proper understanding of the notion of "incomplete symbol" plays a key role in the assessment of the argument, As well as in full appreciation of the radical departure of russell's analysis from "surface" grammar.

Early in Principia Mathematica Russell presents an argument that "‘the author of Waverley’ means nothing", an argument that he calls a "definite proof". He generalizes it to claim that definite descriptions are incomplete symbols having meaning only in sentential context. This Principia "proof" went largely unnoticed until Russell reaffirmed a near-identical "proof" in his philosophical autobiography nearly 50 years later. The "proof" is important, not only because it grounds our understanding of incomplete symbols in the Principia (...) programme, but also because failure to understand it fully has been a source of much unjustified criticism of Russell to the effect that he was wedded to a naive theory of meaning and prone to carelessness and confusion in his philosophy of logic and language generally. In my paper, I (1) defend Russell’s "proof" against attacks from several sources over the last half century, (2) examine the implications of the "proof" for understanding Russell’s treatment of class symbols in Principia, and (3) see how the Principia notion of incomplete symbol was carried forward into Russell’s conception of philosophical analysis as it developed in his logical atomist period after 1910. (shrink)

Susan Stebbing’s work on incomplete symbols and analysis was instrumental in clarifying, sharpening, and improving the project of logical constructions which was pivotal to early analytic philosophy. She dispelled use-mention confusions by restricting the term ‘incomplete symbol’ to expressions eliminable through analysis, rather than those expressions’ purported referents, and distinguished linguistic analysis from analysis of facts. In this paper I explore Stebbing’s role in analytic philosophy’s development from anti-holism, presupposing that analysis terminates in simples, to the more (...) holist or foundherentist analytic philosophy of the later 20th century. I read Stebbing as a transitional figure who made room for more holist analytic movements, e.g., applications of incomplete symbol theory to Quinean ontological commitment. Stebbing, I argue, is part of a historical narrative which starts with the holism of Bradley, an early influence on her, to which Moore and Russell’s logical analysis was a response. They countered Bradley’s holist reservations about facts with the view that the world is built up out of individually knowable simples. Stebbing, a more subtle and sympathetic reader of the British idealists, defends analysis, but with important refinements and caveats which prepared the way for a return to foundherentism and holism within analytic philosophy. (shrink)

Russellian incomplete symbols are usually conceived as an analytical residue—as what remains of the would-be entities when properly analyzed. This article aims to reverse the approach in raising another question: what, if any, does the incomplete symbol contribute to the completely analyzed language? I will first show that, from a technical point of view, there is no difference between the way Russell defines his denoting phrases in “On Denoting” and the way Frege defines his second-order concepts. But (...) I will secondly support that the two notions have two widely different conceptual meanings: the same logical procedures which are used by Frege to increase the deductive power of his system allow Russell to logically relate quantificational notation to ordinary language. Focusing on Russell’s treatment of _OD’s_ puzzles, I will thirdly argue that this shift constitutes the source of a deep transformation in the way logic and language are related. (shrink)

Russell's notion of an incomplete symbol has become a standard against which philosophers compare their views on the relationship between language and the world. But Russell's exact characterization of incomplete symbols and the role they play in his philosophy are still disputed. In this paper, I trace the development of the notion of an incomplete symbol in Russell's philosophy. I suggest – against Kaplan, Evans, and others – that Russell's many characterizations of the notion of an (...) incomplete symbol are compatible. To this end, I examine and reject arguments for the purported incompatibility between declaring an expression to be incomplete and incorporating that symbol into a compositional semantic theory. I then examine how Russell puts the notion of an incomplete symbol to use in metaphysics. (shrink)

Urmson is correct in holding that russell's use of "logical fiction" does usually involve ontological implications. But the issue is more complex than he seems to realize. Because russell's program of logical construction is revisionary, The question "are there really x's?" is ambiguous and can be taken as asking either: (a) are there x's as thought of pre-Analytically? or (b) are there x's as thought of post-Analytically? russell gives different answers in each case.

J. o. urmson's contention that russell held that 'to show that 'x' is an incomplete symbol is tantamount to showing that there are no x's' is shown to rest partly upon a misreading of "principia", pp. 71-72, where russell reveals what he means by a 'definite proof' that a symbol is incomplete, and partly upon a misunderstanding of russell's use of the expression 'logical fiction'.

Russell’s use of incomplete symbols constituted progress in philosophy. They allowed Russell to make true negative existential claims, like ‘the present King of France does not exist’, and to analyse away logical constructs like tables. Russell’s view rested on the availability of complete symbols, logically proper names, which single out objects which we know by acquaintance, which we are committed to, and to whose existence discourse about apparent complexes can be reduced. Susan Stebbing enthusiastically embraced incomplete (...) symbols for use in negative existentials and in her innovative theory of metaphysical analysis. Yet she also raised trenchant objections to Russell’s assumption that complete symbols are purely referring expressions, equivalent to mere demonstration or pointing. Stebbing thought it could not be assumed that analysis terminates in objects of acquaintance. In this chapter I lay out Stebbing’s arguments and argue that they bear a striking similarity to those made by Stebbing’s former college’s Mistress, Constance Jones, whose influence on Russell is now largely forgotten but worth recovering. Jones defended a sense-reference (signification-denotation) distinction before Frege. Russell’s objections to that distinction in ‘On Denoting’ appear to borrow from Jones’s presentation of it. In Russell and Jones’s 1911 exchange at the Aristotelian Society, Jones’s arguments that names have signification and are more than mere noises or shapes, and that unless both signification and denotation are taken into account, all identity statements reduce to the trivial ‘a=a’ form, foreshadow Stebbing’s later arguments against complete symbols. (shrink)

Russell claims in his autobiography and elsewhere that he discovered his 1905 theory of descriptions while attempting to solve the logical and semantic paradoxes plaguing his work on the foundations of mathematics. In this paper, I hope to make the connection between his work on the paradoxes and the theory of descriptions and his theory of incomplete symbols generally clearer. In particular, I argue that the theory of descriptions arose from the realization that not only can a class (...) not be thought of as a single thing, neither can the meaning/intension of any expression capable of singling out one collection (class) of things as opposed to another. If this is right, it shows that Russell’s method of solving the logical paradoxes is wholly incompatible with anything like a Fregean dualism between sense and reference or meaning and denotation. I also discuss how this realization lead to modifications in his understanding of propositions and propositional functions, and suggest that Russell’s confrontation with these issues may be instructive for ongoing research. (shrink)

The proposed theory is broad enough to accommodate the reduction or elimination of prior influences by a variety of acts symbolizing separation. However, it does not account for stability in psychological variables, and is contradicted by widely documented stability in people's actual attitudes and behavior over time, in multiple domains, despite people's pervasive everyday acts of symbolic separation.

We present an analogue of Gödel’s second incompleteness theorem for systems of second-order arithmetic. Whereas Gödel showed that sufficiently strong theories that are $\Pi ^0_1$ -sound and $\Sigma ^0_1$ -definable do not prove their own $\Pi ^0_1$ -soundness, we prove that sufficiently strong theories that are $\Pi ^1_1$ -sound and $\Sigma ^1_1$ -definable do not prove their own $\Pi ^1_1$ -soundness. Our proof does not involve the construction of a self-referential sentence but rather relies on ordinal analysis.

Against the view that symbol-based semiosis is a human cognitive uniqueness, we have argued that non-human primates such as African vervet monkeys possess symbolic competence, as formally defined by Charles S. Peirce. Here I develop this argument by showing that the equivocal role ascribed to symbols by “folk semiotics” stems from an incomplete application of the Peircean logical framework for the classification of signs, which describes three kinds of symbols: rheme, dicent and argument. In an attempt to (...) advance in the classifying semiotic processes, Peirce proposed several typologies, with different degrees of refinement. Around 1903, he developed a division into ten classes. According to this typology, symbols can be further analysed in three subclasses (rheme, dicent, argument). I proceed to demonstrate that vervet monkeys employ dicent symbols. There are remarkable implications of this argument since ‘symbolic species theory’ fails to explore the vast Peircean semiotic philosophy to frame questions regarding the emergence and evolution of symbolic processes. (shrink)

There has been a recent interest in hierarchical generalizations of classic incompleteness results. This paper provides evidence that such generalizations are readily obtainable from suitably formulated hierarchical versions of the principles used in the original proofs. By collecting such principles, we prove hierarchical versions of Mostowski’s theorem on independent formulae, Kripke’s theorem on flexible formulae, Woodin’s theorem on the universal algorithm, and a few related results. As a corollary, we obtain the expected result that the formula expressing “$\mathrm {T}$is$\Sigma _n$-ill” (...) is a canonical example of a$\Sigma _{n+1}$formula that is$\Pi _{n+1}$-conservative over$\mathrm {T}$. (shrink)

§1. Overview. Philosophers and mathematicians have drawn lots of conclusions from Gödel's incompleteness theorems, and related results from mathematical logic. Languages, minds, and machines figure prominently in the discussion. Gödel's theorems surely tell us something about these important matters. But what?A descriptive title for this paper would be “Gödel, Lucas, Penrose, Turing, Feferman, Dummett, mechanism, optimism, reflection, and indefinite extensibility”. Adding “God and the Devil” would probably be redundant. Despite the breath-taking, whirlwind tour, I have the modest aim of forging (...) connections between different parts of this literature and clearing up some confusions, together with the less modest aim of not introducing any more confusions.I propose to focus on three spheres within the literature on incompleteness. The first, and primary, one concerns arguments that Gödel's theorem refutes the mechanistic thesis that the human mind is, or can be accurately modeled as, a digital computer or a Turing machine. The most famous instance is the much reprinted J. R. Lucas [18]. To summarize, suppose that a mechanist provides plans for a machine,M, and claims that the output ofMconsists of all and only the arithmetic truths that a human, or the totality of human mathematicians, will ever or can ever know. We assume that the output ofMis consistent. (shrink)

This paper explores the relationship borne by the traditional paradoxes of set theory and semantics to formal incompleteness phenomena. A central tool is the application of the Arithmetized Completeness Theorem to systems of second-order arithmetic and set theory in which various “paradoxical notions” for first-order languages can be formalized. I will first discuss the setting in which this result was originally presented by Hilbert & Bernays (1939) and also how it was later adapted by Kreisel (1950) and Wang (1955) in (...) order to obtain formal undecidability results. A generalization of this method will then be presented whereby Russell’s paradox, a variant of Mirimanoff’s paradox, the Liar, and the Grelling–Nelson paradox may be uniformly transformed into incompleteness theorems. Some additional observations are then framed relating these results to the unification of the set theoretic and semantic paradoxes, the intensionality of arithmetization (in the sense of Feferman, 1960), and axiomatic theories of truth. (shrink)

By means of models in toposes of C-sets (where C is a small category), necessary conditions are found for the minimum quantified extension of a propositional (intermediate, modal) logic to be complete with respect to Kripke semantics; in particular, many well-known systems turn out to be incomplete.

Gödel’s first incompleteness result from 1931 states that there are true assertions about the natural numbers which do not follow from the Peano axioms. Since 1931 many researchers have been looking for natural examples of such assertions and breakthroughs were obtained in the seventies by Jeff Paris [Some independence results for Peano arithmetic. J. Symbolic Logic 43 725–731] , Handbook of Mathematical Logic, North-Holland, Amsterdam, 1977] and Laurie Kirby [L. Kirby, Jeff Paris, Accessible independence results for Peano Arithmetic, Bull. of (...) the LMS 14 285–293]) and Harvey Friedman [S.G. Simpson, Non-provability of certain combinatorial properties of finite trees, in: Harvey Friedman’s Research on the Foundations of Mathematics, North-Holland, Amsterdam, 1985, pp. 87–117; R. Smith, The consistency strength of some finite forms of the Higman and Kruskal theorems, in: Harvey Friedman’s Research on the Foundations of Mathematics, North-Holland, Amsterdam, 1985, pp. 119–136] who produced the first mathematically interesting independence results in Ramsey theory and well-order and well-quasi-order theory .In this article we investigate Friedman-style principles of combinatorial well-foundedness for the ordinals below ε0. These principles state that there is a uniform bound on the length of decreasing sequences of ordinals which satisfy an elementary recursive growth rate condition with respect to their Gödel numbers.For these independence principles we classify their phase transitions, i.e. we classify exactly the bounding conditions which lead from provability to unprovability in the induced combinatorial well-foundedness principles.As Gödel numbering for ordinals we choose the one which is induced naturally from Gödel’s coding of finite sequences from his classical 1931 paper on his incompleteness results.This choice makes the investigation highly non-trivial but rewarding and we succeed in our objectives by using an intricate and surprising interplay between analytic combinatorics and the theory of descent recursive functions. For obtaining the required bounds on count functions for ordinals we use a classical 1961 Tauberian theorem of Parameswaran which apparently is far remote from Gödel’s theorem. (shrink)

Motivated by the problem of finding finite versions of classical incompleteness theorems, we present some conjectures that go beyond NP ≠ coNP. These conjectures formally connect computational complexity with the difficulty of proving some sentences, which means that high computational complexity of a problem associated with a sentence implies that the sentence is not provable in a weak theory, or requires a long proof. Another reason for putting forward these conjectures is that some results in proof complexity seem to be (...) special cases of such general statements and we want to formalize and fully understand these statements. Roughly speaking, we are trying to connect syntactic complexity, by which we mean the complexity of sentences and strengths of the theories in which they are provable, with the semantic concept of complexity of the computational problems represented by these sentences. -/- We have introduced the most fundamental conjectures in our earlier works. Our aim in this article is to present them in a more systematic way, along with several new conjectures, and prove new connections between them and some other statements studied before. (shrink)

In this article, we tell a story about incompleteness in modal logic. The story weaves together an article of van Benthem, “Syntactic aspects of modal incompleteness theorems,” and a longstanding open question: whether every normal modal logic can be characterized by a class of completely additive modal algebras, or as we call them, ${\cal V}$-baos. Using a first-order reformulation of the property of complete additivity, we prove that the modal logic that starred in van Benthem’s article resolves the open question (...) in the negative. In addition, for the case of bimodal logic, we show that there is a naturally occurring logic that is incomplete with respect to ${\cal V}$-baos, namely the provability logic $GLB$. We also show that even logics that are unsound with respect to such algebras do not have to be more complex than the classical propositional calculus. On the other hand, we observe that it is undecidable whether a syntactically defined logic is ${\cal V}$-complete. After these results, we generalize the Blok Dichotomy to degrees of ${\cal V}$-incompleteness. In the end, we return to van Benthem’s theme of syntactic aspects of modal incompleteness. (shrink)

RésuméLa théorie des expressions incomplétes dans Principia Mathematica, se fonde sur le principe déja appliqué par Russell dans “On Denoting”, selon lequel il est souhaitable dans certains cas, ?on;établir le statut syntaxique des expressions catégorématiques. Grâce à la théorie intensionnelle ramifyée des types, les expressions incomplétes réféientiellement pourront être logiquement caractérisées par un mode de dérivation principalement basé sur la quantification non‐objectuelle. Ľintroduction des classes cependant, n'est en aucune façon reliée à ce mode intensionnel de dérivation; il en résulte qu'elles (...) fonctionnent en réalité dans ce contexte comme des expressions pourvues de dénotation et ce n'est que par une analogie grammaticale que Russell peut les comparer, du point de vue de leur élimination, aux expressions incomplétes de Principia Mathematica.SummaryThe theory of incomplete symbols in Principia Mathematica is founded on the principle already applied by Russell in “On Denoting“ that it is desirable in certain cases, to establish the syntactical status of “categorematic” expressions. Thanks to the intensional ramified theory of types, the referentially incomplete expressions could be logically caracterised by a mode of derivation primarily based on non‐objectual quantification. The introduction of classes, however, is by no way linked to that intensional mode of derivation; as a result, they function, in that context, like denotative expressions and it is only by a “grammatical” analogy that Russell can compare them, as regards their elimination, to the incomplete symbols in Principia Mathematica.ZusammenfassungDie Theorie der unvollstandigen Symbole in den Principia Mathematica gründet auf dem von Russell schon in “On Denoting” angewendeten Prinzip, wonach es in gewissen Fällen wün‐schenswert ist, den syntaktischen Status kategorematischer Ausdrücke festzulegen. Aufgrund der intensionalen verzweigten Typentheorie könnte man die referentiell unvollständigen Ausdrücke logisch durch eine im wesentlichen auf die nicht objektuelle Quantifi‐kation abstellende Ableitungsart charakterisieren. Die Einführung der Klassen dagegen hüngt keineswegs von dieser intensionalen Ableitungsart ab; daraus geht hervor, dass sie in diesem Kontext wie denotative Ausdrücke funktionieren, und es gelingt Russell nur vermittels einer grammatische Analogie, sie hinsichtlich ihrer Elimination mit den unvollständigen Symbolen der Principia Mathematica zu vergleichen. (shrink)

Let n be a positive integer. By a $\beta_{n}-model$ we mean an $\omega-model$ which is elementary with respect to $\sigma_{n}^{1}$ formulas. We prove the following $\beta_{n}-model$ version of $G\ddot{o}del's$ Second Incompleteness Theorem. For any recursively axiomatized theory S in the language of second order arithmetic, if there exists a $\beta_{n}-model$ of S, then there exists a $\beta_{n}-model$ of S + "there is no countable $\beta_{n}-model$ of S". We also prove a $\beta_{n}-model$ version of $L\ddot{o}b's$ Theorem. As a corollary, we obtain (...) a $\beta_{n}-model$ which is not a $\beta_{n+1}-model$. (shrink)

Full proofs of the Gödel incompleteness theorems are highly intricate affairs. Much of the intricacy lies in the details of setting up and checking the properties of a coding system representing the syntax of an object language within that same language. These details are seldom illuminating and tend to obscure the core of the argument. For this reason a number of efforts have been made to present the essentials of the proofs of Gödel's theorems without getting mired in syntactic or (...) computational details. One of the most important of these efforts was made by Löb [8] in connection with his analysis of sentences asserting their own provability. Löb formulated three conditions, on the provability predicate in a formal system which are jointly sufficient to yield the Gödel's second incompleteness theorem for it. A key role in Löb's analysis is played by what later became known as the diagonalization or fixed point property of formal systems, a property which had already, in essence, been exploited by Gödel in his original proofs of the incompleteness theorems. The fixed point property plays a central role in Lawvere's [7] category-theoretic account of incompleteness phenomena. (shrink)

We define a property R(A 0 , A 1 ) in the partial order E of computably enumerable sets under inclusion, and prove that R implies that A 0 is noncomputable and incomplete. Moreover, the property is nonvacuous, and the A 0 and A 1 which we build satisfying R form a Friedberg splitting of their union A, with A 1 prompt and A promptly simple. We conclude that A 0 and A 1 lie in distinct orbits under automorphisms (...) of E, yielding a strong answer to a question previously explored by Downey, Stob, and Soare about whether halves of Friedberg splittings must lie in the same orbit. (shrink)

It is well known that Gödel’s incompleteness theorems hold for ∑1-definable theories containing Peano arithmetic. We generalize Gödel’s incompleteness theorems for arithmetically definable theories. First, we prove that every ∑n+1-definable ∑n-sound theory is incomplete. Secondly, we generalize and improve Jeroslow and Hájek’s results. That is, we prove that every consistent theory having ∏n+1set of theorems has a true but unprovable ∏nsentence. Lastly, we prove that no ∑n+1-definable ∑n-sound theory can prove its own ∑n-soundness. These three results are generalizations of (...) Rosser’s improvement of the first incompleteness theorem, Gödel’s first incompleteness theorem, and the second incompleteness theorem, respectively. (shrink)

The most common way of proving decidability in propositional modal logic is to shew that the system in question has the finite model property. This is not however the only way. Gabbay in [4] proves the decidability of many modal systems using Rabin's result in [8] on the decidability of the second-order theory of successor functions. In particular [4, pp. 258-265] he is able to prove the decidability of a system which lacks the finite model property. Gabbay's system is however (...) complete, in the sense of being characterized by a class of frames, and the question arises whether there is a decidable modal logic which is not complete. Since no incomplete modal logic has the finite model property [9, p. 33], any proof of decidability must employ some such method as Gabbay's. In this paper I use the Gabbay/Rabin technique to prove the decidability of a finitely axiomatized normal modal propositional logic which is not characterized by any class of frames. I am grateful to the referee for suggesting improvements in substance and presentation.The terminology I am using is standard in modal logic. By aframeis understood a pair 〈W, R〉 in whichWis a class (of “possible worlds”) andR⊆W2. To avoid confusion in what follows, a frame will henceforth be referred to as aKripkeframe. By contrast, ageneral frameis a pair 〈,Π〉 in whichis a Kripke frame andΠis a collection of subsets ofWclosed under the Boolean operations and satisfying the condition that ifAis inΠthen so isR−1“A. A model on a frame (of either kind) is obtained by adding a functionVwhich assigns sets of worlds to propositional variables. In the case of a general frame we require thatV(p) ∈Π. (shrink)

Full proofs of the Gödel incompleteness theorems are highly intricate affairs. Much of the intricacy lies in the details of setting up and checking the properties of a coding system representing the syntax of an object language (typically, that of arithmetic) within that same language. These details are seldom illuminating and tend to obscure the core of the argument. For this reason a number of efforts have been made to present the essentials of the proofs of Gödel’s theorems without getting (...) mired in syntactic or computational details. One of the most important of these efforts was made by Löb [8] in connection with his analysis of sentences asserting their own provability. Löb formulated three conditions (now known as the Hilbert-Bernays-Löb derivability conditions), on the provability predicate in a formal system which are jointly sufficient to yield the Gödel’s second incompleteness theorem for it. A key role in Löb’s analysis is played by (a special case of) what later became known as the diagonalization or fixed point property of formal systems, a property which had already, in essence, been exploited by Gödel in his original proofs of the incompleteness theorems. The fixed point property plays a central role in Lawvere’s [7] category-theoretic account of incompleteness phenomena (see also [10]). Incompleteness theorems have also been subjected to intensive investigation within the framework of modal logic (see, e.g.[4], [5]). In this formulation the modal operator takes up the role previously played by the provability predicate, and the derivability conditions on the latter are translated into algebraic conditions (the so-called GL, i.e., Gödel–Löb, conditions) on the former. My purpose here is to present a framework for incompleteness phenomena, fully compatible with intuitionistic or constructive principles, in which the idea of a coding system is retained, only in a 2 simple, but very general form, a form wholly free of syntactical notions. As codes we shall take the elements of an arbitrary given nonempty set, possibly, but not necessarily, the set of natural numbers.. (shrink)

The truth-table degree of the set of shortest programs remains an outstanding problem in recursion theory. We examine two related sets, the set of shortest descriptions and the set of domain-random strings, and show that the truth-table degrees of these sets depend on the underlying acceptable numbering. We achieve some additional properties for the truth-table incomplete versions of these sets, namely retraceability and approximability. We give priority-free constructions of bounded truth-table chains and bounded truth-table antichains inside the truth-table complete (...) degree by identifying an acceptable set of domain-random strings within each degree. (shrink)

Maya Deren was a Russian-born American filmmaker, theorist, poet, and photographer working at the forefront of the American avant-garde in the 1940s and 1950s. Influenced by Jean Cocteau and Marcel Duchamp, she is best known for her seminal film Meshes of the Afternoon, a dream-like experiment with time and symbol, looped narrative and provocative imagery, setting the stage for the twentieth-century's groundbreaking aesthetic movements and films. Maya Deren assesses both the filmmaker's completed work and her numerous unfinished projects, arguing Deren's (...) overarching aesthetic is founded on principles of incompletion, contingency, and openness. Combining the contrasting approaches of documentary, experimental, and creative film, Deren created a wholly original experience for film audiences that disrupted the subjectivity of cinema, its standards of continuity, and its dubious facility with promoting categories of realism. This critical retrospective reflects on the development of Deren's career and the productive tensions she initiated that continue to energize film. (shrink)

The proofs of Gödel (1931), Rosser (1936), Kleene (first 1936 and second 1950), Chaitin (1970), and Boolos (1989) for the first incompleteness theorem are compared with each other, especially from the viewpoint of the second incompleteness theorem. It is shown that Gödel’s (first incompleteness theorem) and Kleene’s first theorems are equivalent with the second incompleteness theorem, Rosser’s and Kleene’s second theorems do deliver the second incompleteness theorem, and Boolos’ theorem is derived from the second incompleteness theorem in the standard way. (...) It is also shown that none of Rosser’s, Kleene’s second or Boolos’ theorems is equivalent with the second incompleteness theorem, and Chaitin’s incompleteness theorem neither delivers nor is derived from the second incompleteness theorem. We compare (the strength of) these six proofs with one another. (shrink)

In this paper, we examine the limit of applicability of Gödel’s first incompleteness theorem. We first define the notion “$\textsf {G1}$ holds for the theory $T$”. This paper is motivated by the following question: can we find a theory with a minimal degree of interpretation for which $\textsf {G1}$ holds. To approach this question, we first examine the following question: is there a theory T such that Robinson’s $\mathbf {R}$ interprets T but T does not interpret $\mathbf {R}$ and $\textsf (...) {G1}$ holds for T? In this paper, we show that there are many such theories based on Jeřábek’s work using some model theory. We prove that for each recursively inseparable pair $\langle A,B\rangle $, we can construct a r.e. theory $U_{\langle A,B\rangle }$ such that $U_{\langle A,B\rangle }$ is weaker than $\mathbf {R}$ w.r.t. interpretation and $\textsf {G1}$ holds for $U_{\langle A,B\rangle }$. As a corollary, we answer a question from Albert Visser. Moreover, we prove that for any Turing degree $\mathbf {0}< \mathbf {d}<\mathbf {0}^{\prime }$, there is a theory T with Turing degree $\mathbf {d}$ such that $\textsf {G1}$ holds for T and T is weaker than $\mathbf {R}$ w.r.t. Turing reducibility. As a corollary, based on Shoenfield’s work using some recursion theory, we show that there is no theory with a minimal degree of Turing reducibility for which $\textsf {G1}$ holds. (shrink)

Among the more important changes in this revised edition: the incompleteness of the first set of natural deduction rules is proved; many proofs are shortened and simplified, especially in the development of the first-order functional calculus; there is a more lucid exposition of the quantification rules; more exercises are provided, with answers given for a number of them. The changes are all improvements, but none of them are of a sufficiently radical nature to be likely to alter anyone's original opinion (...) of Copi's book—A. E. J. (shrink)

An ordered field is said to be Scott complete iff it is complete with respect to its uniform structure. Zakon has asked whether nonstandard real lines are Scott complete. We prove in ZFC that for any complete Boolean algebra B which is not (ω, 2)-distributive there is an ultrafilter U of B such that the Boolean ultrapower of the real line modulo U is not Scott complete. We also show how forcing in set theory gives rise to examples of Boolean (...) ultrapowers of the real line which are not Scott complete. (shrink)

We call a logic regular for a semantics when the satisfaction predicate for at least one of its nontheorems is closed under double negation. Such intuitionistic theories as second-order Heyting arithmetic HAS and the intuitionistic set theory IZF prove completeness for no regular logics, no matter how simple or complicated. Any extensions of those theories proving completeness for regular logics are classical, i.e., they derive the tertium non datur. When an intuitionistic metatheory features anticlassical principles or recognizes that a logic (...) regular for a semantics is nonclassical, it proves explicitly that the logic is incomplete with respect to that semantics. Logics regular relative to Tarski. Beth and Kripke semantics form a large collection that includes propositional and predicate intuitionistic, intermediate and classical logics. These results are corollaries of a single theorem. A variant of its proof yields a generalization of the Gödel-Kreisel Theorem linking weak completeness for intuitionistic predicate logic to Markov's Principle. (shrink)