Deflationists have argued that truth is an ontologically thin property which has only an expressive function to perform, that is, it makes possible to express semantic generalizations like 'All the theorems are true', 'Everything Peter said is true', etc. Some of the deflationists have also argued that although truth is ontologically thin, it suffices in conjunctions with other facts not involving truth to explain all the facts about truth. The purpose of this paper is to show that in the case (...) of arithmetic, it is difficult to combine the expressive with the explanatory function of truth if the latter is understood in a deflationist way. We will make our point by investigating several logical systems: first-order logic, full second-order logic, and existential second-order (?11-) logic. (shrink)

I formulate the Zermelo-Russell paradox for naive set theory. A sketch is given of Zermelo’s solution to the paradox: the cumulative type structure. A careful analysis of the set formation process shows a missing component in this solution: the necessity of an assumed imaginary jump out of an infinite universe. Thus a set is formed by a suitable combination of concrete and imaginary operations all of which can be made or assumed by a Turing machine. Some consequences are drawn from (...) this improved analysis of the concept of set, for the theory of sets and for the philosophy and foundations of mathematics. (shrink)

A common objection to hierarchical approaches to truth is that they fragment the concept of truth. This paper defends hierarchical approaches in general against the objection of fragmentation. It argues that the fragmentation required is familiar and unprob-lematic, via a comparison with mathematical proof. Furthermore, it offers an explanation of the source and nature of the fragmentation of truth. Fragmentation arises because the concept exhibits a kind of failure of closure under reflection. This paper offers a more precise characterization of (...) the reflection involved, first in the setting of formal theories of truth, and then in a more general setting. (shrink)

It can be argued that only the equational theories of some sub-elementary function algebras are finitistic or intuitive according to a certain interpretation of Hilbert's conception of intuition. The purpose of this paper is to investigate the relation of those restricted forms of equational reasoning to classical quantifier logic in arithmetic. The conclusion reached is that Edward Nelson's ‘predicative arithmetic’ program, which makes essential use of classical quantifier logic, cannot be justified finitistically and thus requires a different philosophical foundation, possibly (...) as a restricted form of logicism. (shrink)

Reflection principles are of central interest in the development of axiomatic theories. Whereas they are independent statements they appear to have a specific epistemological status. Our trust in those principles is as warranted as our trust in the axioms of the system itself. This paper is an attempt in clarifying this special epistemic status. We provide a motivation for the adoption of uniform reflection principles by their analogy to a form of the constructive \(\omega \) -rule. Additionally, we analyse the (...) role of informal arithmetic and the conception of natural numbers as an inductive structure, also with regard to extra conceptual resources such as a primitive truth predicate. (shrink)

I had the pleasure of renewing my acquaintance with Per Lindström at the meeting of the Seventh Scandinavian Logic Symposium, held in Uppsala in August 1996. There at lunch one day, Per said he had long been curious about the development of some of the ideas in my paper [1960] on the arithmetization of metamathematics. In particular, I had used the construction of a non-standard definition !* of the set of axioms of P (Peano Arithmetic) to show that P + (...) {¬ Con!} is interpretable in P, where ! is a standard definition of the axioms of P and Con! expresses the consistency of P via that presentation. Per pointed out that there is a simple “two-line” proof of this interpretability result which does not require the use of such formulas as !*, and he wondered whether I had been aware of that. In fact, his proof had never occurred to me, and if it had at the time, it is possible I would never have been led to the use of non-natural definitions. Per regarded this as a happy accident, since subsequent work by him and others on interpretability made essential use of such definitions. In our conversation, I enlarged a bit on the background to my work on arithmetization, and when I was invited to contribute to this special issue of Theoria dedicated to Lindström, it seemed a natural choice to use the occasion to fill out the story. One caveat, though: the following is drawn largely from memory, not always reliable, supplemented by consultation of the 1960 paper and the 1957 dissertation from which it was drawn. (shrink)

The Hilbert–Bernays Theorem establishes that for any satisfiable first-order quantificational schema S, one can write out linguistic expressions that are guaranteed to yield a true sentence of elementary arithmetic when they are substituted for the predicate letters in S. The theorem implies that if L is a consistent, fully interpreted language rich enough to express elementary arithmetic, then a schema S is valid if and only if every sentence of L that can be obtained by substituting predicates of L for (...) predicate letters in S is true. The theorem therefore licenses us to define validity substitutionally in languages rich enough to express arithmetic. The heart of the theorem is an arithmetization of Gödel's completeness proof for first-order predicate logic. Hilbert and Bernays were the first to prove that there is such an arithmetization. Kleene established a strengthened version of it, and Kreisel, Mostowski, and Putnam refined Kleene's result. Despite the later refinements, Kleene's presentation of th.. (shrink)

We discuss Kunen’s algorithmic implementation of a proof for the Paris–Harrington theorem, and the author’s and da Costa’s proposed “exotic” formulation for the P = NP hypothesis. Out of those two examples we ponder the relation between mathematics within an axiomatic framework, and intuitive or informal mathematics.

We consider a seemingly popular justification (we call it the Re-flexivity Defense) for the third derivability condition of the Hilbert-Bernays-Löb generalization of Godel's Second Incompleteness Theorem (G2). We argue that (i) in certain settings (rouglily, those where the representing theory of an arithmetization is allowed to be a proper subtheory of the represented theory), use of the Reflexivity Defense to justify the tliird condition induces a fourth condition, and that (ii) the justification of this fourth condition faces serious obstacles. We (...) conclude that, in the types of settings mentioned, the Reflexivity Defense does not justify the usual ‘reading’ of G2—namely, that the consistency of the represented theory is not provable in the representing theory. (shrink)

It is argued that an instrumentalist notion of proof such as that represented in Hilbert's viewpoint is not obligated to satisfy the conservation condition that is generally regarded as a constraint on Hilbert's Program. A more reasonable soundness condition is then considered and shown not to be counter-exemplified by Godel's First Theorem. Finally, attention is given to the question of what a theory is; whether it should be seen as a "list" or corpus of beliefs, or as a method for (...) selecting beliefs. The significance of this question for assessing "intensional" results like Godel's Second Theorem, and their bearing on Hilbert's Program are discussed. (shrink)

We translate Socrates’ famous saying I know that I know nothing into the arithmetical sentence I prove that I prove nothing. Then it is easy to show that this translated saying is formally undecidable in formal arithmetic, using Gödel’s Second Incompleteness Theorem. We investigate some variations of this Socrates-Gödel sentence. In an appendix we sketch a ramified epistemic logic with propositional quantifiers in order to analyze the Socrates-Gödel sentence in a more logical way, separated from the arithmetical context.

The Paradox of the Knower was originally presented by Kaplan and Montague [26] as a puzzle about the everyday notion of knowledge in the face of self-reference. The paradox shows that any theory extending Robinson arithmetic with a predicate K satisfying the factivity axiom K → A as well as a few other epistemically plausible principles is inconsistent. After surveying the background of the paradox, we will focus on a recent debate about the role of epistemic closure principles in the (...) Knower. We will suggest this debate sheds new light on the concept of knowledge which is at issue in the paradox – i.e. is it a “thin” notion divorced from concepts such as evidence or justification, or is it a “thick” notion more closely resembling mathematical provability? We will argue that a number of features of the paradox suggest that the latter option is more plausible. Along the way, we will provide a reconstruction of the paradox using a quantified extension of Artemovʼs [2] Logic of Proofs, as well as a series of results linking the original formulation of the paradox to reflection principles for formal arithmetic. On this basis, we will argue that while the Knower can be understood to motivate a distinction between levels of knowledge, it does not provide a rationale for recognizing a uniform hierarchy of knowledge predicates in the manner suggested by Anderson. (shrink)

Proof-theoretic reflection principles are schemas which attempt to express the soundness of arithmetical theories within their own language, e.g., ${\mathtt{{Prov}_{\mathsf {PA}} \rightarrow \varphi }}$ can be understood to assert that any statement provable in Peano arithmetic is true. It has been repeatedly suggested that justification for such principles follows directly from acceptance of an arithmetical theory $\mathsf {T}$ or indirectly in virtue of their derivability in certain truth-theoretic extensions thereof. This paper challenges this consensus by exploring relationships between reflection principles (...) and principles of mathematical and transfinite induction as well as the status of the latter with respect to various foundational characterizations of number theory. (shrink)

ABSTRACT We use Gödel’s incompleteness theorems as a case study for investigating mathematical depth. We examine the philosophical question of what the depth of Gödel’s incompleteness theorems consists in. We focus on the methodological study of the depth of Gödel’s incompleteness theorems, and propose three criteria to account for the depth of the incompleteness theorems: influence, fruitfulness, and unity. Finally, we give some explanations for our account of the depth of Gödel’s incompleteness theorems.

This is a paper for a special issue of Semiotic Studies devoted to Stanislaw Krajewski’s paper. This paper gives some supplementary notes to Krajewski’s on the Anti-Mechanist Arguments based on Gödel’s incompleteness theorem. In Section 3, we give some additional explanations to Section 4–6 in Krajewski’s and classify some misunderstandings of Gödel’s incompleteness theorem related to AntiMechanist Arguments. In Section 4 and 5, we give a more detailed discussion of Gödel’s Disjunctive Thesis, Gödel’s Undemonstrability of Consistency Thesis and the definability (...) of natural numbers as in Section 7–8 in Krajewski’s, describing how recent advances bear on these issues. (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)

Some notions of the logic of questions (presupposition of a question, validation, entailment) are used for defining certain kinds of completeness of elementary theories. Presuppositional completeness, closely related to -completeness ([3], [6]), is shown to be fulfilled by strong elementary theories like Peano arithmetic.

In this article we find some sufficient and some necessary \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^1_1}$$\end{document} -conditions with oracles for a model to be resplendent or chronically resplendent. The main tool of our proofs is internal arguments, that is analogues of classical theorems and model-theoretic constructions conducted inside a model of first-order Peano Arithmetic: arithmetised back-and-forth constructions and versions of the arithmetised completeness theorem, namely constructions of recursively saturated and resplendent models from the point of view (...) of a model of arithmetic. These internal arguments are used in conjunction with Pabion’s theorem that ensures that certain oracles are coded in a sufficiently saturated model of arithmetic. Examples of applications are provided for the theories of dense linear orders and of discrete linear orders. These results are then generalised to other ω-categorical theories and theories with a unique countable recursively saturated model. (shrink)

In this article we find some sufficient and some necessary ${\Sigma^1_1}$ -conditions with oracles for a model to be resplendent or chronically resplendent. The main tool of our proofs is internal arguments, that is analogues of classical theorems and model-theoretic constructions conducted inside a model of first-order Peano Arithmetic: arithmetised back-and-forth constructions and versions of the arithmetised completeness theorem, namely constructions of recursively saturated and resplendent models from the point of view of a model of arithmetic. These internal arguments are (...) used in conjunction with Pabion’s theorem that ensures that certain oracles are coded in a sufficiently saturated model of arithmetic. Examples of applications are provided for the theories of dense linear orders and of discrete linear orders. These results are then generalised to other ω-categorical theories and theories with a unique countable recursively saturated model. (shrink)

In the the passage just quoted from theDialogues concerning Natural Religion, David Hume developed a thought-experiment that contravened his better-known views about chance expressed in hisTreatise and firstEnquiry.For among other consequences of the eternal-recurrence hypothesis Philo proposes in this passage, it may turn out that what the vulgar call cause is nothing but a secret and concealed chance.

In the the passage just quoted from the Dialogues concerning Natural Religion, David Hume developed a thought-experiment that contravened his better-known views about "chance" expressed in his Treatise and first Enquiry. For among other consequences of the 'eternal-recurrence' hypothesis Philo proposes in this passage, it may turn out that what the vulgar call cause is nothing but a secret and concealed chance. (In this sentence, I have simply reversed "cause" and "chance" in a well-known passage from Hume's Treatise, p. 130). (...) In the first eight sections of this essay, I develop one topological and model-theoretic analogue of Hume's thought-experiment, in which 'most' ('A-generic') models M of a 'scientific' theory U are both 'eternally recurrent' and topologically random (in a sense which will be made precise), even though they are 'inductively' defined, via a step-by-step ('empirical'?) procedure that Hume might have been inclined to endorse. The last aspect of this model-theoretic thought-experiment also serves to distinguish it from simpler measure-theoretic prototypes that are known to follow from Kolmogorov's Zero-One Law (cf. the Introduction, 5.2, 6.1 and 6.7 below). In the last three sections, I will argue more informally (1) that the metamathematical thought-experiments just mentioned do have a genuine metaphysical relevance, and that this relevance is predominantly skeptical in its implications; (2) that such 'nonstandard' instances of semantic underdetermination and 'pathology' seem to be the metatheoretic rule rather than the exception; and therefore, (3) that metamathematical and metatheoretic 'malign-genius' arguments are quite coherent, contrary (e.g.) to assertions such as that of Putnam (1980), pp. 7-8. In the essay's conclusion, finally, I assimilate (2) and (3) to the familiar datum that 'simplicity', rather than 'pathology', has more often than not turned out to be an anomalous 'special case' in the historical development of scientific and mathematical ontology. (shrink)

What particular privilege has this little Agitation of the Brain which we call Thought, that we must make it the Model of the whole Universe? (Hume, Dialogues Concerning Natural Religion, 1976, p. 168)******...at once it struck me, what quality went to form a Man (sic) of Achievement especially in Literature and which Shakespeare possessed so enormously—I mean Negative Capability, that is when someone is capable of being in uncertainties, Mysteries, doubts without any irritable reaching after fact and reason. (Keats 1959, (...) p. 261)******Die menschliche Vernunft hat das besondere Schicksal in ihrer Gattung ihrer Erkenntnisse: dass sie durch Fragen belästigt wird, die sie nicht abweisen kann; denn sie sind ihr durch die Natur der Vernunft selbst aufgegeben, die sie aber auch nicht beantworten kann; denn sie übersteigen alles Vermögen der menschlichen Vernunft. (Opening lines of the Kritik der reinen Vernunft (1956), A VII; the italics in the text are mine)Human reason has the particular fa .. (shrink)

A ground-motive for this study of some historical and metaphysical implications of the diagonal lemmas of Cantor and Gödel is Cantor's insightful remark to Dedekind in 1899 that the Inbegriff alles Denkbaren (aggregate of everything thinkable) might, like some class-theoretic entities, be inkonsistent. In the essay's opening sections, I trace some recent antecedents of Cantor's observation in logical writings of Bolzano and Dedekind (more remote counterparts of his language appear in the First Critique), then attempt to relativize the notion of (...) Inkonsistenz to self-sufficient theories T which interpret themselves. In effect, I argue that Gödel's diagonal lemma suggests a sense in which metatheoretic notions of proof, well-foundeness and satisfaction are object-theoretically inkonsistent. With respect to Cantor's Inbegriff, for example, the lemma yields that any object-theoretic reconstruction of thinkability generates an antidiagonal sentence , which one can paraphrase asSelf-referential application of the assertion that. (shrink)

We present a semi-formal foundational theory of sorts, akin to sets, named librationism because of its way of dealing with paradoxes. Its semantics is related to Herzberger’s semi inductive approach, it is negation complete and free variables (noemata) name sorts. Librationism deals with paradoxes in a novel way related to paraconsistent dialetheic approaches, but we think of it as bialethic and parasistent. Classical logical theorems are retained, and none contradicted. Novel inferential principles make recourse to theoremhood and failure of theoremhood. (...) Identity is introduced à la Leibniz-Russell, and librationism is highly non-extensional. Π 1 1 -comprehension with ordinary Bar-Induction is accounted for (to be lifted). Power sorts are generally paradoxical, and Cantor’s Theorem is blocked as a camouflaged premise is naturally discarded. (shrink)

The relation between logic and philosophy of science, often taken for granted, is in fact problematic. Although current fashionable criticisms of the usefulness of logic are usually mistaken, there are indeed difficulties which should be taken seriously — having to do, amongst other things, with different scientific mentalities in the two disciplines (section 1). Nevertheless, logic is, or should be, a vital part of the theory of science. To make this clear, the bulk of this paper is devoted to the (...) key notion of a scientific theory in a logical perspective. First, various formal explications of this notion are reviewed (section 2), then their further logical theory is discussed (section 3). In the absence of grand inspiring programs like those of Klein in mathematics or Hilbert in metamathematics, this preparatory ground-work is the best one can do here. The paper ends on a philosophical note, discussing applicability and merits of the formal approach to the study of science (section 4). (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 deal with the fragment of modal logic consisting of implications of formulas built up from the variables and the constant ‘true’ by conjunction and diamonds only. The weaker language allows one to interpret the diamonds as the uniform reflection schemata in arithmetic, possibly of unrestricted logical complexity. We formulate an arithmetically complete calculus with modalities labeled by natural numbers and ω, where ω corresponds to the full uniform reflection schema, whereas n<ω corresponds to its restriction to arithmetical Πn+1-formulas. This (...) calculus is shown to be complete w.r.t. a suitable class of finite Kripke models and to be decidable in polynomial time. (shrink)

For “natural enough” systems of ordinal notation we show that α times iterated local reflection schema over a sufficiently strong arithmetic T proves the same Π 1 0 -sentences as ω α times iterated consistency. A corollary is that the two hierarchies catch up modulo relative interpretability exactly at ε-numbers. We also derive the following more general “mixed” formulas estimating the consistency strength of iterated local reflection: for all ordinals α ⩾ 1 and all β, β ≡ Π 1 0 (...) T ω α · , α ≡ Π 1 0 T β + ω α . Here T α stands for α times iterated local reflection over T , T β stands for β times iterated consistency, and ≡ Π 1 0 denotes mutual Π 1 0 -conservativity. In an appendix to this paper we develop our notion of “natural enough” system of ordinal notation and show that such systems do exist for every recursive ordinal. (shrink)

A well-known result states that, over basic Kalmar elementary arithmetic EA, the induction schema for ∑n formulas is equivalent to the uniform reflection principle for ∑n + 1 formulas . We show that fragments of arithmetic axiomatized by various forms of induction rules admit a precise axiomatization in terms of reflection principles as well. Thus, the closure of EA under the induction rule for ∑n formulas is equivalent to ω times iterated ∑n reflection principle. Moreover, for k < ω, k (...) times iterated ∑n reflection principle over EA precisely corresponds to the extension of EA by k nested applications of ∑n induction rule.The above relationship holds in greater generality than just stated. In fact, we give general formulas characterizing in terms of iterated reflection principles the extension of any given theory by k nested applications of ∑n or Πn induction rules. In particular, the closure of a theory T under just one application of ∑1 induction rule is equivalent to T together with ∑1 reflection principle for each finite Π2 axiomatized subtheory of T.These results have closely parallel ones in the theory of subrecursive function classes. The rules under study correspond, in a canonical way, to natural closure operators on the classes of provably recursive functions. Thus, ∑1 induction rule precisely corresponds to the primitive recursive closure operator, and ∑1 collection rule, introduced below, corresponds to the elementary closure operator. (shrink)

We gather the following miscellaneous results in proof theory from the attic.1. 1. A provably well-founded elementary ordering admits an elementary order preserving map.2. 2. A simple proof of an elementary bound for cut elimination in propositional calculus and its applications to separation problem in relativized bounded arithmetic below S21.3. 3. Equivalents for Bar Induction, e.g., reflection schema for ω logic.4. 4. Direct computations in an equational calculus PRE and a decidability problem for provable inequations in PRE.5. 5. Intuitionistic fixed (...) point theories which are conservative extensions of HA.6. 6. Proof theoretic strengths of classical fixed points theories.7. 7. An equivalence between transfinite induction rule and iterated reflection schema over IΣn.8. 8. Derivation lengths of finite rewrite rules reducing under lexicographic path orders and multiply recursive functions.Each section can be read separately in principle. (shrink)

We demonstrate that, in itself and in the absence of extra premises, the following argument scheme is fallacious: The sentence A says about itself that it has a property F, and A does in fact have the property F; therefore A is true. We then examine an argument of this form in the informal introduction of Gödel’s classic (1931) and examine some auxiliary premises which might have been at work in that context. Philosophically significant as it may be, that particular (...) informal argument plays no rôle in Gödel’s technical results. Going deeper into the issue and investigating truth conditions of Gödelian sentences (i.e., those sentences which are provably equivalent to their own unprovability) will provide us with insights regarding the philosophical debate on the truth of Gödelian sentences of systems—a debate which goes back to Dummett (1963). (shrink)

In this paper we explain our pretense account of truth-talk and apply it in a diagnosis and treatment of the Liar Paradox. We begin by assuming that some form of deflationism is the correct approach to the topic of truth. We then briefly motivate the idea that all T-deflationists should endorse a fictionalist view of truth-talk, and, after distinguishing pretense-involving fictionalism (PIF) from error- theoretic fictionalism (ETF), explain the merits of the former over the latter. After presenting the basic framework (...) of our PIF account of truth-talk, we demonstrate a few advantages it offers over T-deflationist accounts that do not explicitly acknowledge pretense at work in the discourse. In turning to the Liar Paradox, we explain how the quasi-anaphoric functioning that our account attributes to truth-talk provides a diagnosis of the Liar Paradox (and other instances of semantic pathology) as having no content—in the sense of not specifying any of what we call M-conditions. At the same time, however, we vindicate the intuition that we can understand liar sentences, thereby avoiding one standard objection to “meaningless strategy” responses to the Liar Paradox. With this diagnosis in place, we then, by way of treatment, introduce a new predicate, ‘semantically defective’, and show how the explanation we give for its application allows for a consistent, yet revenge-immune, (dis)solution of the Liar Paradox, and semantic pathology generally. (shrink)

This book attempts to explicate and expand upon Frank Ramsey's notion of the realistic spirit. In so doing, it provides a systematic reading of his work, and demonstrates the extent of Ramsey's genius as evinced by both his responses to the Tractatus Logico-Philosophicus , and the impact he had on Wittgenstein's later philosophical insights.

This paper proposes substitutional definitions of logical truth and consequence in terms of relative interpretations that are extensionally equivalent to the model-theoretic definitions for any relational first-order language. Our philosophical motivation to consider substitutional definitions is based on the hope to simplify the meta-theory of logical consequence. We discuss to what extent our definitions can contribute to that.

In his book Shadows of the Mind: A search for the missing science of con- sciousness [SM below], Roger Penrose has turned in another bravura perfor- mance, the kind we have come to expect ever since The Emperor’s New Mind [ENM ] appeared. In the service of advancing his deep convictions and daring conjectures about the nature of human thought and consciousness, Penrose has once more drawn a wide swath through such topics as logic, computa- tion, artificial intelligence, quantum physics (...) and the neuro-physiology of the brain, and has produced along the way many gems of exposition of difficult mathematical and scientific ideas, without condescension, yet which should be broadly appealing. 1 While the aims and a number of the topics in SM are the same as in ENM, the focus now is much more on the two axes that Pen- rose grinds in earnest. Namely, in the first part of SM he argues anew and at great length against computational models of the mind and more specifi- cally against any account of mathematical thought in computational terms. Then in the second part, he argues that there must be a scientific account of consciousness but that will require a (still to be found) non-computational extension or modification of present-day quantum physics. (shrink)

We give a new proof for Godel's second incompleteness theorem, based on Kolmogorov complexity, Chaitin's incompleteness theorem, and an argument that resembles the surprise examination paradox. We then go the other way around and suggest that the second incompleteness theorem gives a possible resolution of the surprise examination paradox. Roughly speaking, we argue that the flaw in the derivation of the paradox is that it contains a hidden assumption that one can prove the consistency of the mathematical theory in which (...) the derivation is done; which is impossible by the second incompleteness theorem. (shrink)

Gödel's two incompleteness theorems are among the most important results in modern logic, and have deep implications for various issues. They concern the limits of provability in formal axiomatic theories. The first incompleteness theorem states that in any consistent formal system F within which a certain amount of arithmetic can be carried out, there are statements of the language of F which can neither be proved nor disproved in F. According to the second incompleteness theorem, such a formal system cannot (...) prove that the system itself is consistent (assuming it is indeed consistent). These results have had a great impact on the philosophy of mathematics and logic. There have been attempts to apply the results also in other areas of philosophy such as the philosophy of mind, but these attempted applications are more controversial. The present entry surveys the two incompleteness theorems and various issues surrounding them. (shrink)

A notion of finitary inductively presented (f.i.p.) logic is proposed here, which includes all syntactically described logics (formal systems)met in practice. A f.i.p. theory FS0 is set up which is universal for all f.i.p. logics; though formulated as a theory of functions and classes of expressions, FS0 is a conservative extension of PRA. The aims of this work are (i)conceptual, (ii)pedagogical and (iii)practical. The system FS0 serves under (i)and (ii)as a theoretical framework for the formalization of metamathematics. The general approach (...) may be used under (iii)for the computer implementation of logics. In all cases, the work aims to make the details manageable in a natural and direct way. (shrink)