The Gödelian symphony -- Foundations and paradoxes -- This sentence is false -- The liar and Gödel -- Language and metalanguage -- The axiomatic method or how to get the non-obvious out of the obvious -- Peano's axioms -- And the unsatisfied logicists, Frege and Russell -- Bits of set theory -- The abstraction principle -- Bytes of set theory -- Properties, relations, functions, that is, sets again -- Calculating, computing, enumerating, that is, the notion of algorithm -- Taking numbers (...) as sets of sets -- It's raining paradoxes -- Cantor's diagonal argument -- Self-reference and paradoxes -- Hilbert -- Strings of symbols -- In mathematics there is no ignorabimus -- Gödel on stage -- Our first encounter with the incompleteness theorem -- And some provisos -- Gödelization, or say it with numbers! -- TNT -- The arithmetical axioms of tnt and the standard model N -- The fundamental property of formal systems -- The Gödel numbering -- And the arithmetization of syntax -- Bits of recursive arithmetic -- Making algorithms precise -- Bits of recursion theory -- Church's thesis -- The recursiveness of predicates, sets, properties, and relations -- And how it is represented in typographical number theory -- Introspection and representation -- The representability of properties, relations, and functions -- And the Gödelian loop -- I am not provable -- Proof pairs -- The property of being a theorem of TNI (is not recursive!) -- Arithmetizing substitution -- How can a TNT sentence refer to itself? -- Fixed point -- Consistency and omega-consistency -- Proving G1 -- Rosser's proof -- The unprovability of consistency and the immediate consequences of G1 and -- G2 -- Technical interlude -- Immediate consequences of G1 and G2 -- Undecidable1 and undecidable 2 -- Essential incompleteness, or the syndicate of mathematicians -- Robinson arithmetic -- How general are Gödel's results? -- Bits of turing machine -- G1 and G2 in general -- Unexpected fish in the formal net -- Supernatural numbers -- The culpability of the induction scheme -- Bits of truth (not too much of it, though) -- The world after Gödel -- Bourgeois mathematicians! : the postmodern interpretations -- What is postmodernism? -- From Gödel to Lenin -- Is biblical proof decidable? -- Speaking of the totality -- Bourgeois teachers! -- (un)interesting bifurcations -- A footnote to Plato -- Explorers in the realm of numbers -- The essence of a life -- The philosophical prejudices of our times -- From Gödel to Tarski -- Human, too human -- Mathematical faith -- I'm not crazy! -- Qualified doubts -- From gentzen to the dialectica interpretation -- Mathematicians are people of faith -- Mind versus computer : Gödel and artificial intelligence -- Is mind (just) a program? -- Seeing the truth and going outside the system -- The basic mistake -- In the haze of the transfinite -- Know thyself : Socrates and the inexhaustibility of mathematics -- Gödel versus wittgenstein and the paraconsistent interpretation -- When geniuses meet -- The implausible Wittgenstein -- There is no metamathematics -- Proof and prose -- The single argument -- But how can arithmetic be inconsistent? -- The costs and benefits of making Wittgenstein plausible. (shrink)
In a recent paper S. McCall adds another link to a chain of attempts to enlist Gödel’s incompleteness result as an argument for the thesis that human reasoning cannot be construed as being carried out by a computer.1 McCall’s paper is undermined by a technical oversight. My concern however is not with the technical point. The argument from Gödel’s result to the no-computer thesis can be made without following McCall’s route; it is then straighter and more forceful. Yet the (...) argument fails in an interesting and revealing way. And it leaves a remainder: if some computer does in fact simulate all our mathematical reasoning, then, in principle, we cannot fully grasp how it works. Gödel’s result also points out a certain essential limitation of self-reflection. The resulting picture parallels, not accidentally, Davidson’s view of psychology, as a science that in principle must remain “imprecise”, not fully spelt out. What is intended here by “fully grasp”, and how all this is related to self-reflection, will become clear at the end of this comment. (shrink)
I define T-schema deflationism as the thesis that a theory of truth for our language can simply take the form of certain instances of Tarski's schema (T). I show that any effective enumeration of these instances will yield as a dividend an effective enumeration of all truths of our language. But that contradicts Gödel's First Incompleteness Theorem. So the instances of (T) constituting the T-Schema deflationist's theory of truth are not effectively enumerable, which casts doubt on the idea that (...) the T-schema deflationist in any sense has a theory of truth. (The argument in section 2 of "Semantics for Deflationists" supercedes this paper.). (shrink)
This paper is a summary of a lecture in which I presented some remarks on Gödel’s incompleteness theorems and their meaning for the foundations of physics. The entire lecture will appear elsewhere. doi: http://dx.doi.org/ 10.5007 / 1808-1711.2011v15n3p453.
This paper shows that some classes of multimodal paraconsistent logics endowed with weak forms of negation are incompletable with respect to Kripke semantics. The reach of such incompleteness is discussed, and we argue that this shortcoming, more than just a logical predicament, may be relevant for attempts to characterize quantum logics and to handle quantum information and quantum computation.
Gödel began his 1951 Gibbs Lecture by stating: “Research in the foundations of mathematics during the past few decades has produced some results which seem to me of interest, not only in themselves, but also with regard to their implications for the traditional philosophical problems about the nature of mathematics.” (Gödel 1951) Gödel is referring here especially to his own incompleteness theorems (Gödel 1931). Gödel’s first incompleteness theorem (as improved by Rosser (1936)) says that for any consistent formalized (...) system F, which contains elementary arithmetic, there exists a sentence GF of the language of the system which is true but unprovable in that system. Gödel’s second incompleteness theorem states that no consistent formal system can prove its own consistency. (shrink)
Kurt Godel, the greatest logician of our time, startled the world of mathematics in 1931 with his Theorem of Undecidability, which showed that some statements in mathematics are inherently "undecidable." His work on the completeness of logic, the incompleteness of number theory, and the consistency of the axiom of choice and the continuum theory brought him further worldwide fame. In this introductory volume, Raymond Smullyan, himself a well-known logician, guides the reader through the fascinating world of Godel's incompleteness (...) theorems. The level of presentation is suitable for anyone with a basic acquaintance with mathematical logic. As a clear, concise introduction to a difficult but essential subject, the book will appeal to mathematicians, philosophers, and computer scientists. (shrink)
This article shows that in two respects, Gödel's incompleteness theorem strongly supports the arguments of Edgar Morin's complexity paradigm. First, from the viewpoint of the content of Gödel's theorem, the latter justifies the basic view of complexity paradigm according to which knowledge is a dynamic, unfinished process, and develops by way of self-criticism and self-transcendence. Second, from the viewpoint of the proof procedure of Gödel's theorem, the latter confirms the complexity paradigm's circular line of inference through which is formed (...) the all-round knowledge of a concrete object. (shrink)
According to Field’s influential incompleteness objection, Tarski’s semantic theory of truth is unsatisfactory since the definition that forms its basis is incomplete in two distinct senses: (1) it is physicalistically inadequate, and for this reason, (2) it is conceptually deficient. In this paper, I defend the semantic theory of truth against the incompleteness objection by conceding (1) but rejecting (2). After arguing that Davidson and McDowell’s reply to the incompleteness objection fails to pass muster, I argue that, (...) within the constraints of a non-reductive physicalism and a holism concerning the concepts of truth, reference and meaning, conceding Field’s physicalistic inadequacy conclusion while rejecting his conceptual deficiency conclusion is a promising reply to the incompleteness objection. (shrink)
Natural deduction systems were motivated by the desire to define the meaning of each connective by specifying how it is introduced and eliminated from inference. In one sense, this attempt fails, for it is well known that propositional logic rules (however formulated) underdetermine the classical truth tables. Natural deduction rules are too weak to enforce the intended readings of the connectives; they allow non-standard models. Two reactions to this phenomenon appear in the literature. One is to try to restore the (...) standard readings, for example by adopting sequent rules with multiple conclusions. Another is to explore what readings the natural deduction rules do enforce. When the notion of a model of a rule is generalized, it is found that natural deduction rules express “intuitionistic” readings of their connectives. A third approach is presented here. The intuitionistic readings emerge when models of rules are defined globally, but the notion of a local model of a rule is also natural. Using this benchmark, natural deduction rules enforce exactly the classical readings of the connectives, while this is not true of axiomatic systems. This vindicates the historical motivation for natural deduction rules. One odd consequence of using the local model benchmark is that some systems of propositional logic are not complete for the semantics that their rules express. Parallels are drawn with incompleteness results in modal logic to help make sense of this. (shrink)
A common objection to Russell's theory of descriptions concerns incomplete definite descriptions: uses of (for example) ‘the book is overdue’ in contexts where there is clearly more than one book. Many contemporary Russellians hold that such utterances will invariably convey a contextually determined complete proposition, for example, that the book in your briefcase is overdue. But according to the objection this gets things wrong: typically, when a speaker utters such a sentence, no facts about the context or the speaker's communicative (...) intentions single out a particular description-theoretic proposition as the proposition expressed. However, this is an objection only if it is assumed that successful linguistic communication requires the hearer to identify a proposition uniquely intended by the speaker. We argue that this assumption is mistaken. On our view, no proposition, descriptive or referential, is uniquely intended in such a context; thus, no proposition can nor need be identified as the proposition expressed. One significant upshot is that, once the aforementioned assumption is rejected, incompleteness no longer poses a threat to Russell's theory of descriptions. (shrink)
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 (...) class='Hi'>incompleteness problem. (shrink)
He argues that the intuitively provable arithmetic sentences constitute a recursively enumerable set, which has a Gödel sentence which is itself intuitively provable. The incompleteness theorem does not apply, since the set of provable arithmetic sentences is not consistent. The purpose of this article is to sharpen Priest's argument, avoiding reference to informal notions, consensus, or Church's thesis. We add Priest's dialetheic semantics to ordinary Peano arithmetic PA, to produce a recursively axiomatized formal system PA that contains its own (...) truth predicate. Whether one is a dialetheist or not, PA is a legitimate, rigorously defined formal system, and one can explore its proof-theoretic properties. The system is inconsistent (but presumably non-trivial), and it proves its own Gödel sentence as well as its own soundness. Although this much is perhaps welcome to the dialetheist, it has some untoward consequences. There are purely arithmetic (indeed, 0) sentences that are both provable and refutable in PA. So if the dialetheist maintains that PA is sound, then he must hold that there are true contradictions in the most elementary language of arithmetic. Moreover, the thorough dialetheist must hold that there is a number g which both is and is not the code of a derivation of the indicated Gödel sentence of PA. For the thorough dialetheist, it follows ordinary PA and even Robinson arithmetic are themselves inconsistent theories. I argue that this is a bitter pill for the dialetheist to swallow. (shrink)
Informal statements of Gödel's Second Incompleteness Theorem, referred to here as Informal Second Incompleteness, are simple and dramatic. However, current versions of Formal Second Incompleteness are complicated and awkward. We present new versions of Formal Second Incompleteness that are simple, and informally imply Informal Second Incompleteness. These results rest on the isolation of simple formal properties shared by consistency statements. Here we do not address any issues concerning proofs of Second Incompleteness.
It is well understood and appreciated that Gödel’s Incompleteness Theorems apply to sufficiently strong, formal deductive systems. In particular, the theorems apply to systems which are adequate for conventional number theory. Less well known is that there exist algorithms which can be applied to such a system to generate a gödel-sentence for that system. Although the generation of a sentence is not equivalent to proving its truth, the present paper argues that the existence of these algorithms, when conjoined with (...) Gödel’s results and accepted theorems of recursion theory, does provide the basis for an apparent paradox. The difficulty arises when such an algorithm is embedded within a computer program of sufficient arithmetic power. The required computer program (an AI system) is described herein, and the paradox is derived. A solution to the paradox is proposed, which, it is argued, illuminates the truth status of axioms in formal models of programs and Turing machines. (shrink)
What were the earliest reactions to Gödel's incompleteness theorems? After a brief summary of previous work in this area I analyse, by means of unpublished archival material, the first reactions in Vienna and Berlin to Gödel's groundbreaking results. In particular, I look at how Carnap, Hempel, von Neumann, Kaufmann, and Chwistek, among others, dealt with the new results.
This short sketch of Gödel’s incompleteness proof shows how it arises naturally from Cantor’s diagonalization method [1891]. It renders Gödel’s proof and its relation to the semantic paradoxes transparent. Some historical details, which are often ignored, are pointed out. We also make some observations on circularity and draw brief comparisons with natural language. The sketch does not include the messy details of the arithmetization of the language, but the motives for it are made obvious. We suggest this as a (...) more efficient way to teach the topic than what is found in the standard textbooks. For the sake of self–containment Cantor’s original diagonalization is included. A broader and more technical perspective on diagonalization is given in [Gaifman 2005]. In [1891] Cantor presented a new type of argument that shows that the set of all binary sequences (sequences of the form a0, a1,…,an,…, where each ai is either 0 or 1) is not denumerable ─ that is, cannot be arranged in a sequence, where the index ranges over the natural numbers. Let A0, A2,…An, … be a sequence of binary sequences. Say An = an,0, an,1, …, an,i, … . Define a new sequence A* = b0, b1,…,bn,… , by putting. (shrink)
How do we prove true but unprovable propositions? Gödel produced a statement whose undecidability derives from its ad hoc construction. Concrete or mathematical incompleteness results are interesting unprovable statements of formal arithmetic. We point out where exactly the unprovability lies in the ordinary ‘mathematical’ proofs of two interesting formally unprovable propositions, the Kruskal-Friedman theorem on trees and Girard's normalization theorem in type theory. Their validity is based on robust cognitive performances, which ground mathematics in our relation to space and (...) time, such as symmetries and order, or on the generality of Herbrand's notion of ‘prototype proof’. (shrink)
In this paper I argue that it is more difficult to see how Godel's incompleteness theorems and related consistency proofs for formal systems are consistent with the views of formalists, mechanists and traditional intuitionists than it is to see how they are consistent with a particular form of mathematical realism. If the incompleteness theorems and consistency proofs are better explained by this form of realism then we can also see how there is room for skepticism about Church's Thesis (...) and the claim that minds are machines. (shrink)
Elizabeth Prior claims that dispositional predicates are incomplete in the sense that they have more than one argument place. To back up this claim, she offers a number of arguments that involve such ordinary dispositional predicates as ‘fragile’, ‘soluble’, and so on. In this paper, I will first demonstrate that one of Prior’s arguments that ‘is fragile’ is an incomplete predicate is mistaken. This, however, does not immediately mean that Prior is wrong that ‘fragile’ is an incomplete predicate. On the (...) contrary, I maintain that she has offered another valid argument that does indeed establish the claim that ‘fragile’ is an incomplete predicate. I will argue further that Prior is right that ‘soluble’ is an incomplete predicate. Then does this mean that all dispositional predicates are incomplete? I don’t think so. I will suggest that there are complete dispositional predicates that have no more than one argument place. Finally, by relying on my discussion of the incompleteness of dispositional predicates, I will attempt to provide a better understanding of the context-dependence and intrinsic nature of dispositional ascriptions. (shrink)
We first state a few previously obtained results that lead to general undecidability and incompleteness theorems in axiomatized theories that range from the theory of finite sets to classical elementary analysis. Out of those results we prove several incompleteness theorems for axiomatic versions of the theory of noncooperative games with Nash equilibria; in particular, we show the existence of finite games whose equilibria cannot be proven to be computable.
In recent years a number of criticisms have been raised against the formal systems of mathematical logic. The latter, qualified as closed systems, have been contrasted with systems of a new kind, called open systems, whose main feature is that they are always subject to unanticipated outcomes in their operation and can receive new information from outside at any time [cf. Hewitt 1991]. While Gödel's incompleteness theorem has been widely used to refute the main contentions of Hilbert's program, it (...) does not seem to have been generally used to point out the inadequacy of a basic ingredient of that program - the concept of formal system as a closed system - and to stress the need to replace it by the concept of formal system as an open system. (shrink)
What Gödel accomplished in the decade of the 1930s before joining the Institute changed the face of mathematical logic and continues to influence its development. As you gather from my title, I’ll be talking about the most famous of his results in that period, but first I want to indulge in some personal reminiscences. In many ways this is a sentimental journey for me. I was a member of the Institute in 1959-60, a couple of years after receiving my PhD (...) at the University of California in Berkeley, where I had worked with Alfred Tarski, another great logician. The subject of my dissertation was directly concerned with the method of arithmetization that Gödel had used to prove his theorems, and my main concern after that was to study systematic ways of overcoming incompleteness. Mathematical logic was going through a period of prodigious development in the 1950s and 1960s, and Berkeley and Princeton were two meccas for researchers in that field. For me, the prospect of meeting with Gödel and drawing on him for guidance and inspiration was particularly exciting. I didn’t know at the time what it took to get invited. Hassler Whitney commented for an obituary notice in 1978 that “it was hard to appoint a new member in logic at the Institute because Gödel could not prove to himself that a number of candidates shouldn’t be members, with the evidence at hand.” That makes it sound like the problem for Gödel was deciding who not to invite. Anyhow, I ended up being one of the lucky few. (shrink)
This paper explores the relationships between Davidson's indeterminacy of interpretation thesis and two semantic properties of sentences that have come to be recognized recently, namely semantic incompleteness and semantic indecision.1 More specifically, I will examine what the indeterminacy thesis entails for sentences of the form 'By sentence S (or word w), agent A means that m' and 'Agent A believes that p.' My primary goal is to shed light on the indeterminacy thesis and its consequences. I will distinguish two (...) kinds of indeterminacy that have very different sources and very different consequences. But this does not purport to be an exhaustive study: there may well be other forms of indeterminacy that this .. (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)
In addition to this being the centenary of Kurt Gödel’s birth, January marked 75 years since the publication (1931) of his stunning incompleteness theorems. Though widely known in one form or another by practicing mathematicians, and generally thought to say something fundamental about the limits and potentialities of mathematical knowledge, the actual importance of these results for mathematics is little understood. Nor is this an isolated example among famous results. For example, not long ago, Philip Davis wrote me about (...) what he calls The Paradox of Irrelevance: “There are many math problems that have achieved the cachet of tremendous significance, e.g. Fermat, 4 color, Kepler’s packing, Gödel, etc. Of Fermat, I have read: ‘the most famous math problem of all time.’ Of Gödel, I have read: ‘the most mathematically significant achievement of the 20th century.’ … Yet, these problems have engaged the attention of relatively few research mathematicians—even in pure math.” What accounts for this disconnect between fame and relevance? Before going into the question for Gödel’s theorems, it should be distinguished in one respect from the other examples mentioned, which in any case form quite a mixed bag. Namely, each of the Fermat, 4 color, and Kepler’s packing problems posed a stand-out challenge following extended efforts to settle them; meeting the challenge in each case required new ideas or approaches and intense work, obviously of different degrees. By contrast, Gödel’s theorems were simply unexpected, and their proofs, though requiring novel techniques, were not difficult on the scale of things. Setting that aside, my view of Gödel’s incompleteness theorems is that their relevance to mathematical logic (and its offspring in the theory of computation) is paramount; further, their philosophical relevance is significant, but in just what way is far from settled; and finally, their mathematical relevance outside of logic is very much unsubstantiated but is the object of ongoing, tantalizing efforts.. (shrink)
In the paper some applications of Gödel's incompleteness theorems to discussions of problems of computer science are presented. In particular the problem of relations between the mind and machine (arguments by J.J.C. Smart and J.R. Lucas) is discussed. Next Gödel's opinion on this issue is studied. Finally some interpretations of Gödel's incompleteness theorems from the point of view of the information theory are presented.
Like Heisenberg’s uncertainty principle, Gödel’s incompleteness theorem has captured the public imagination, supposedly demonstrating that there are absolute limits to what can be known. More specifically, it is thought to tell us that there are mathematical truths which can never be proved. These are among the many misconceptions and misuses of Gödel’s theorem and its consequences. Incompleteness has been held to show, for example, that there cannot be a Theory of Everything, the so-called holy grail of modern physics. (...) Some philosophers and mathematicians say it proves that minds can’t be modelled by machines, while others argue that they can be modelled but that Gödel’s theorem shows we can’t know it. Postmodernists have claimed to find support in it for the view that objective truth is chimerical. And in the Bibliography of Christianity and Mathematics (yes, there is such a publication) it is asserted that ‘theologians can be comforted in their failure to systematize revealed truth because mathematicians cannot grasp all mathematical truths in their systems either.’ Not only that, the incompleteness theorem is held to imply the existence of God, since only He can decide all truths. Even Rebecca Goldstein’s book, whose laudable aim is to provide non-technical expositions of the incompleteness theorems (there are two) for a general audience and place them in their historical and biographical context, makes extravagant claims and distorts their significance. As Goldstein sees it, Gödel’s theorems are ‘the most prolix theorems in the history of mathematics’ and address themselves ‘to the central question of the humanities – ‘what is it to be human?’ – since they involve ‘such vast and messy areas as the nature of truth and knowledge and certainty’. Unfortunately, these weighty claims disintegrate under closer examination, while the book as a whole is marred by a number of disturbing conceptual and historical errors. On the face of it, Goldstein would appear to have been an ideal choice to present Gödel’s work: she received a PhD in Philosophy from Princeton University in 1977 and since then has taught philosophy of science and philosophy of mind at several.... (shrink)
Gödel’s incompleteness applies to any system with recursively enumerable axioms and rules of inference. Chaitin’s approach to Gödel’s incompleteness relates the incompleteness to the amount of information contained in the axioms. Zurek’s quantum Darwinism attempts the physical description of the universe using information as one of its major components. The capacity of quantum Darwinism to describe quantum measurement in great detail without requiring ad-hoc non-unitary evolution makes it a good candidate for describing the transition from quantum to (...) classical. A baby-universe diffusion model of cosmic inflation is analyzed using quantum Darwinism. In this model cosmic inflation can be approximated as Brownian motion of a quantum field, and quantum Darwinism implies that molecular interaction during Brownian motion will make the quantum field decohere. The quantum Darwinism approach to decoherence in the baby-universe cosmic-inflation model yields the decoherence times of the baby-universes. The result is the equation relating the baby-universe’s decoherence time with the Hubble parameter, and that the decoherence time is considerably shorter than the cosmic inflation period. (shrink)
• How to construct a ‘canonical’ Gödel sentence • If PA is sound, it is negation imcomplete • Generalizing that result to sound p.r. axiomatized theories whose language extends LA • ω-incompleteness, ω-inconsistency • If PA is ω-consistent, it is negation imcomplete • Generalizing that result to ω-consistent p.r. axiomatized theories which extend Q..
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)
In Episode 1, we introduced the very idea of a negation-incomplete formalized theory T . We noted that if we aim to construct a theory of basic arithmetic, we’ll ideally like the theory to be able to prove all the truths expressible in the language of basic arithmetic, and hence to be negation complete. But Gödel’s First Incompleteness Theorem says, very roughly, that a nice theory T containing enough arithmetic will always be negation incomplete. Now, the Theorem comes in (...) two flavours, depending on whether we cash out the idea of being ‘nice enough’ in terms of (i) the semantic idea of T ’s being a sound theory, or (ii) the idea of odel’s own T ’s being a consistent theory which proves enough arithmetic. And we noted that G¨. (shrink)
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. (shrink)
Following F. William Lawvere, we show that many self-referential paradoxes, incompleteness theorems and fixed point theorems fall out of the same simple scheme. We demonstrate these similarities by showing how this simple scheme encompasses the semantic paradoxes, and how they arise as diagonal arguments and fixed point theorems in logic, computability theory, complexity theory and formal language theory.
ENTIRE BOOK, SINGLE FILE. BOOLEAN RELATION THEORY AND THE INCOMPLETENESS PHENOMENA. 10/30/07 version. Same as 10/01/07 version with Preface added. 568 pages without Appendix B. See above for Appendix B by Francoise Point.
It is not yet clear just what the most illuminating ways of rigorously stating the Incompleteness Theorems are. This is particularly true of the Second. Also I believe that there are more illuminating proofs of the Second that have yet to be uncovered.
The logic of ‘elsewhere,’ i.e., of a sentence operator interpretable as attaching to a formula to yield a formula true at a point in a Kripke model just in case the first formula is true at all other points in the model, has been applied in settings in which the points in question represent spatial positions (explaining the use of the word ‘elsewhere’), as well as in the case in which they represent moments of time. This logic is applied here (...) to the alethic modal case, in which the points are thought of as possible worlds, with the suggestion that its deployment clarifies aspects of a position explored by John Divers un-der the name ‘modal agnosticism.’ In particular, it makes available a logic whose Halldén incompleteness explicitly registers the agnostic element of the position – its neutrality as between modal realism and modal anti-realism. (shrink)
Why these notes? After all, I’ve written An Introduction to Gödel’s Theorems (CUP, heavily corrected fourth printing 2009: henceforth IGT ). Surely that’s more than enough to be going on with? Ah, but there’s the snag. It is more than enough. In the writing, as is the way with these things, the book grew far beyond the scope of the lecture notes from which it started. And while I hope the result is still pretty accessible to someone prepared to (...) put in the time and effort, there’s a lot more in the book than is really needed by philosophers meeting the incompleteness theorems for the first time. After all, you might want to get your heads around only those technical basics which are actually needed for understanding philosophical discussions about incompleteness. So you need a cut-down version of the book – an introduction to the Introduction! Well, isn’t that what lectures are for? Indeed. But there’s another snag. I haven’t got many lectures to play with. So either (A) I crack on at quite a fast pace (hard-core mathmo style), cover those basics, but perhaps leave too many people puzzled and alarmed. Or (B) I do relaxed talk’n’chalk, highlighting the really Big Ideas, making sure everyone is grasping them as we go along, but inevitably omit important stuff and leave quite a gap between what happens in the lectures and what happens in the book. What to do? I’m going for plan (B). But then I still need to do something to fill that gap between lectures and book. Hence these notes. The idea, then, is to give relaxed lectures, highlighting Big Ideas, not worrying too much about depth or fine-detail (or even about getting through all of the day’s intended menu of topics). Then after the lecture, I’ll write up notes that expand things just enough, and then give pointers to relevant chunks of IGT. The idea, however, is for the notes to be more or less stand-alone, and to tell a brief but coherent story read by themselves. So occasionally I’ll copy a paragraph or two from the book, rather than just refer to them. Warning: just occasionally in these notes, I’ll no doubt apply that good maxim ‘Where it doesn’t itch, don’t scratch’.. (shrink)
According to several commentators, Kurt Godel's incompleteness discoveries were assimilated promptly and almost without objection by his contemporaries - - a circumstance remarkable enough to call for explanation. Careful examination reveals, however, that there were doubters and critics, as well as defenders and rival claimants to priority. In particular, the reactions of Carnap, Bernays, Zermelo, Post, Finsler, and Russell, among others, are considered in detail. Documentary sources include unpublished correspondence from Godel's Nachlass.
It has been suggested by Clark Glymour that the spatio-temporal structure of the universe might be underdetermined by all observational data that could ever, theoretically, be gathered. It is possible for two spacetimes to be observationally indistinguishable (OI) yet topologically distinct. David Malament extended the argument for the underdetermination of spacetime structure by showing that under quite general conditions (such as the absence of any closed timelike curves) a spacetime will always have an OI counterpart (at least in weak sense). (...) Because the plight of the cosmologist seemed to be so discouraging in this regard, Malament considered the relationship between global properties and OI spacetimes. This information is helpful to the cosmologist. It allows, in principle, one to reject some spacetime models based on observational evidence. In this paper, I consider the relationship between variants of geodesic incompleteness and different senses (some old and some new) of OI. In light of the findings, it seems that (for the most part) the predicament of the cosmologist is not good. Quite generally, versions of geodesic incompleteness are not conserved even under the strongest formulations of OI. (shrink)
Many different but related arguments developed in the Caritas in Veritate converge on one central, yet not clearly stated, conclusion or thesis: economic and business activities are ‘incomplete’. This article will explore the above-mentioned ‘incompleteness’ thesis or argument from three different perspectives: the role, the practice and the purpose of economic and business activities in contemporary societies. In doing so, the paper will heavily draw on questions and, still not fully learned, lessons derived from the present financial and economic (...) crisis. Caritas in Veritate provides an appealing moral framework in which many of these lessons take a deeper sense and a more comprehensive meaning. The notion of ‘incompleteness’ is applied here to economic and business theory and practice in the sense derived from Gödel’s theorems. They state in terms of logical and mathematical demonstrations that no system of axiomatic statements can provide a proof of its own consistency. Such a proof requires the use of statements belonging to another (higher) level system. In the case of economics or business theory and practice these ‘higher level’ statements are value judgments. By stressing the importance of ethics and moral philosophy for daily life, Caritas in Veritate strongly reminds us that neither economy nor business are self-sufficient either in organisational and social, practical or moral terms. (shrink)
We prove that any 1-closed (see def 1.1) model of the Π 2 consequences of PA satisfies ¬Cons PA which gives a proof of the second Godel incompleteness theorem without the use of the Godel diagonal lemma. We prove a few other theorems by the same method.
A proof is presented that a form of incompleteness in Quantum Mechanics follows directly from the use of unbounded operators. It is then shown that the problems that arise for such operators are not connected to the non- commutativity of many pairs of operators in Quantum Mechanics and hence are an additional source of incompleteness to that which allegedly flows from the..
In this paper we formulate a version of Second Incompleteness Theorem. The idea is that a sequential sentence has ‘consistency power’ over a theory if it enables us to construct a bounded interpretation of that theory. An interpretation of V in U is bounded if, for some n , all translations of V -sentences are U -provably equivalent to sentences of complexity less than n . We call a sequential sentence with consistency power over T a pro-consistency statement for (...) T . We study pro-consistency statements. We provide an example of a pro-consistency statement for a sequential sentence A that is weaker than an ordinary consistency statement for A . We show that, if A is $${{\sf S}^{1}_{2}}$$ , this sentence has some further appealing properties, specifically that it is an Orey sentence for EA . The basic ideas of the paper essentially involve sequential theories. We have a brief look at the wider environment of the results, to wit the case of theories with pairing. (shrink)
We will study several weak axiom systems that use the Subtraction and Division primitives (rather than Addition and Multiplication) to formally encode the theorems of Arithmetic. Provided such axiom systems do not recognize Multiplication as a total function, we will show that it is feasible for them to verify their Semantic Tableaux, Herbrand, and Cut-Free consistencies. If our axiom systems additionally do not recognize Addition as a total function, they will be capable of recognizing the consistency of their Hilbert-style deductive (...) proofs. Our axiom systems will not be strong enough to recognize their Canonical Reflection principle, but they will be capable of recognizing an approximation of it, called the "Tangibility Reflection Principle". We will also prove some new versions of the Second Incompleteness Theorem stating essentially that it is not possible to extend our exceptions to the Incompleteness Theorem much further. (shrink)
Gödel's Incompleteness Theorems have the same scientific status as Einstein's principle of relativity, Heisenberg's uncertainty principle, and Watson and Crick's double helix model of DNA. Our aim is to discuss some new faces of the incompleteness phenomenon unveiled by an information-theoretic approach to randomness and recent developments in quantum computing.
We present some recent technical results of us on the incompleteness of classical analysis and then discuss our work on the Arnol'd decision problems for the stability of fixed points of dynamical systems.
We begin by considering two principles, each having the form causal completeness ergo screening-off . The first concerns a common cause of two or more effects; the second describes an intermediate link in a causal chain. They are logically independent of each other, each is independent of Reichenbach's principle of the common cause, and each is a consequence of the causal Markov condition. Simple examples show that causal incompleteness means that screening-off may fail to obtain. We derive a stronger (...) result: in a rather general setting, if the composite cause C 1 & C 2 & ... & C n screens-off one event from another, then each of the n component causes C 1 , C 2 , ..., C n must fail to screen-off. The idea that a cause may be ordinally invariant in its impact on different effects is defined; it plays an important role in establishing this no-go theorem. Along the way, we describe how composite and component causes can all screen-off when ordinal invariance fails. We argue that this theorem is relevant to assessing the plausibility of the two screening-off principles. The discovery of incomplete causes that screen-off is not evidence that causal completeness must engender screening-off. Formal and epistemic analogies between screening-off and determinism are discussed. (shrink)
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. (shrink)
The paper studies two formal schemes related to -completeness.LetS be a suitable formal theory containing primitive recursive arithmetic and letT be a formal extension ofS. Denoted by (a), (b) and (c), respectively, are the following three propositions (where (x) is a formula with the only free variable x): (a) (for anyn) ( T (n)), (b) T x Pr T (–(x)–) and (c) T x(x) (the notational conventions are those of Smoryski [3]). The aim of this paper is to examine the (...) meaning of the schemes which result from the formalizations, over the base theoryS, of the implications (b) (c) and (a) (b), where ranges over all formulae. The analysis yields two results overS : 1. the schema corresponding to (b) (c) is equivalent to ¬Cons T and 2. the schema corresponding to (a) (b) is not consistent with 1-CON T. The former result follows from a simple adaptation of the -incompleteness proof; the second is new and is based on a particular application of the diagonalization lemma. (shrink)
In "Virtue and Right" Robert Johnson argues that virtue ethics that accept standards such as Virtuous Agent (A's x-ing is right in circumstances c iff a fully virtuous agent would x in c) are incomplete, since they cannot account for duties of moral self-improvement. This paper offers four solutions to the problem of incompleteness: the first discards Virtuous Agent and counts actions as wrong iff a vicious person would perform them; the second retains Virtuous Agent but counts self-improving actions (...) as countererogatory: wrong but nonetheless good to do; the third replaces Virtuous Agent with a standard appealing to the Mengzian virtue of righteousness, understood as situational appropriateness; the fourth replaces Virtuous Agent with a standard that holds an action right if it promotes the agent's virtue. Each solution accommodates duties of moral self-improvement, so a virtue ethics embracing any of them would not be incomplete. (shrink)
Recently, Dollimore criticized our claim that Organizational Ecology is not a Darwinian research program. She argued that Organizational Ecology is merely an incomplete Darwinian program and provided a suggestion as to how this incompleteness could be remedied. Here, we argue that Dollimore’s suggestion fails to remedy the principal problem that Organizational Ecology faces and that there are good reasons to think of the program as deeply incompatible with Darwinian thinking.
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)
We present some recent technical results of us on the incompleteness of classical analysis and then discuss our work on the Arnol'd decision problems for the stability of fixed points of dynamical systems.
Plausibility Logic was introduced by Daniel Lehmann. We show—among some other results—completeness of a subset of Plausibility Logic for Preferential Models, and incompleteness of full Plausibility Logic for smooth Preferential Models.
We generalize the incompleteness proof of the modal predicate logic Q-S4+ p p + BF described in Hughes-Cresswell [6]. As a corollary, we show that, for every subframe logic Lcontaining S4, Kripke completeness of Q-L+ BF implies the finite embedding property of L.
Let us recall that Raphael Robinson's Arithmetic Q is an axiom system that differs from Peano Arithmetic essentially by containing no Induction axioms [13], [18]. We will generalize the semantic-tableaux version of the Second Incompleteness Theorem almost to the level of System Q. We will prove that there exists a single rather long Π 1 sentence, valid in the standard model of the Natural Numbers and denoted as V, such that if α is any finite consistent extension of Q (...) + V then α will be unable to prove its Semantic Tableaux consistency. The same result will also apply to axiom systems α with infinite cardinality when these infinite-sized axiom systems satisfy a minor additional constraint, called the Conventional Encoding Property. Our formalism will also imply that the semantic-tableaux version of the Second Incompleteness Theorem generalizes for the axiom system IΣ 0 , as well as for all its natural extensions. (This answers an open question raised twenty years ago by Paris and Wilkie [15].). (shrink)
Kurt Godel’s “Incompleteness Theorem” is generally seen as one of the three main achievements of modern logic in philosophy. However, in this article, three fundamental flaws in the theorem will be exposed about its concept, judgment and reasoning parts by analyzing the setting of the theorem, the process of demonstration and the extension of its conclusions. Thus through the analysis of the essence significance of the theorem, I think the theorem should be classified as "liar paradox" or something like (...) that. Therefore, the theorem is not reliable and then the content of the theorem itself is questionable. At the same time, please note, the root of the problem exposed in Godel's “Incompleteness Theorem” is a typical example o f existing loopholes in traditional logic. (shrink)
According to John Rawls's ideal of liberal public reason, comprehensive moral, religious and philosophical doctrines should play no more than an auxiliary or marginal role in the political life of constitutional democracies. David Reidy has recently claimed that since liberal public reason is incomplete, comprehensive doctrines, and non-public reasons, must play a wider role than Rawls admits. In response, I argue that Reidy's arguments do not establish that liberal public reason is incomplete. Furthermore, even if the substantive values embodied in (...) liberal public reason were insufficient to determine certain fundamental decisions, such indeterminacy need not be eliminated by recourse to comprehensive doctrines. (shrink)
Luck egalitarianism makes a fundamental distinction between inequalities for which agents are responsible and inequalities stemming from luck. I give several reasons to find luck egalitarianism a compelling view of distributive justice. I then argue that it is an incomplete theory of equality. Luck egalitarianism lacks the normative resources to achieve its ends. It is unable to specify the prior conditions under which persons are situated equivalently such that their choices can bear this tremendous weight. This means that luck egalitarians (...) need to become pluralists who understand equality not merely in terms of choice, luck, and responsibility. After developing my critical argument that luck egalitarianism is incomplete, I sketch a strategy for rehabilitating and filling out the theory. (shrink)
'God needs no instruments to act', Malebranche writes in Search 6.2.3; 'it suffices that He wills in order that a thing be, because it is a contradiction that He should will and that what He wills should not happen. Therefore, His power is His will' (450). After nearly identical language in Treatise 1.12, Malebranche writes that '[God's] wills are necessarily efficacious ... [H]is power differs not at all from [H]is will' (116). God's causal power, here, clearly traces only to His (...) volitions - not merely to the fact that He wills, but specifically to the content of His volitions ('"what" He wills'). Yet despite the obviously key role the ordinary notion of volitional content plays for Malebranche, recent writers have paid surprisingly little attention either to it or its exegetical implications. I hope to rectify this situation here. The plan of this paper is this: first, to borrow current work in the philosophy of mind to sketch the notion of an incomplete volition, i.e. one whose content is 'incomplete' in a sense to be explained; second, to show that Malebranche clearly allows and uses something like this notion; third, to apply the notion to Malebranche's doctrine of human freedom. In so doing, I believe, we can understand this doctrine in a new way, and one which: (i) is clearly consistent with his texts, and (ii) unlike other interpretations makes coherent sense out of the conflicting streams in his heroic attempt to reconcile his occasionalism - the doctrine that no finite substances have genuine causal powers - with our freedom; fourth, Contrast my interpretation with those of two recent writers: Sleigh et al. (1998) and Schmaltz (1996); and Fifth, Summarize the major results. (shrink)
The causal power of Malebranche's God is a function of the content of His will. Yet despite its significance for Malebranche, little exegetical attention has been paid to his notion of volitional content. In this paper I develop the notion of an 'incomplete' volition, note that Malebranche accepted and used something like it, and then examine Malebranche's natural theodicy in its light. This yields a new interpretation in which, unlike previous interpretations, Malebranche actually succeeds in reconciling his seemingly incompatible beliefs (...) that: (1) God alone is causally responsible for all natural states of affairs; (2) God's power is His will; (3) God wills to produce only goods; and yet (4) genuine evils exist. (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.
whole numbers that manages to assert that it itself is unprovable (from a given finite set F of axioms using formal logic). (Gödel's paper is included in the well-known anthology [1].) GF : ``GF cannot be proved from the finite set of axioms F.'' This assertion GF is therefore true if and only if it is unprovable, and the formal axiomatic system F in question either proves falsehoods (because it enables us to prove GF) or fails to prove a true (...) assertion (because it does not enable us to prove GF). If we assume that the former situation is impossible, we conclude that F is necessarily incomplete since it does not permit us to establish the true statement GF. (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)
An interpretation of Wittgenstein’s much criticized remarks on Gödel’s First Incompleteness Theorem is provided in the light of paraconsistent arithmetic: in taking Gödel’s proof as a paradoxical derivation, Wittgenstein was drawing the consequences of his deliberate rejection of the standard distinction between theory and metatheory. The reasoning behind the proof of the truth of the Gödel sentence is then performed within the formal system itself, which turns out to be inconsistent. It is shown that the features of paraconsistent arithmetics (...) match with some intuitions underlying Wittgenstein’s philosophy of mathematics, such as its strict finitism and the insistence on the decidability of any mathematical question. (shrink)
In this paper it is argued that the opposition between the two main methods of mathematics, the axiomatic and the analytic method, is first of all an opposition between intuition and <span class='Hi'>discourse</span>, and, in addition, an opposition between the socalled demonstrative and non-demonstrative reasoning. These two methods, however, are not on a par because the view that the method of mathematics is the axiomatic method is refuted by Goedel's incompleteness results, which on the contrary do not affect the (...) view that the method of mathematics is the analytic method. (shrink)
Roger Penrose is justly famous for his work in physics and mathematics but he is _notorious_ for his endorsement of the Gödel argument (see his 1989, 1994, 1997). This argument, first advanced by J. R. Lucas (in 1961), attempts to show that Gödel’s (first) incompleteness theorem can be seen to reveal that the human mind transcends all algorithmic models of it1. Penrose's version of the argument has been seen to fall victim to the original objections raised against Lucas (see (...) Boolos (1990) and for a particularly intemperate review, Putnam (1994)). Yet I believe that more can and should be said about the argument. Only a brief review is necessary here although I wish to present the argument in a somewhat peculiar form. (shrink)
Preface 1 The First Theorem revisited 1.1 Notational preliminaries 1.2 Definitional preliminaries 1.3 A general version of G¨ odel’s First Theorem 1.4 Giving the First Theorem bite 1.5 Generic G¨ odel sentences and arithmetic truth 1.6 Canonical and standard G¨ odel sentences 2 The Second Theorem revisited 2.1 Definitional preliminaries 2.2 Towards G¨ odel’s Second Theorem 2.3 A general version of G¨ odel’s Second Theorem 2.4 Giving the Second Theorem bite 2.5 Comparisons 2.6 Further results about provability predicates 2.7 Back (...) to the First Theorem 2.8 Introducing Rosserized provability predicates.. (shrink)
Aiming to unravel the mystery of quantum mechanics, this book is concerned with questions about action-at-a-distance, holism, and whether quantum mechanics gives a complete account of microphysical reality. With rigorous arguments and clear thinking, the author provides an introduction to the philosophy of physics.
Fitch’s paradox of knowability is an apparently valid reasoning from the assumption (typical of semantic anti-realism) that every true proposition is knowable to the unacceptable conclusion that every true proposition is known. The paper develops a critical dialectic wrt one of the best motivated solutions to the paradox which have been proposed on behalf of semantic anti-realism—namely, the intuitionistic solution. The solution consists, on the one hand, in accepting the intuitionistically valid part of Fitch’s reasoning while, on the other hand, (...) exploiting the characteristic weakness of intuitionistic logic in order to preserve the consistency of such acceptance with the denial of omniscience. It is first remarked how the solution still commits one to acceptance of modal claims which are unwarranted even by the lights of standard intuitionistic semantics. A novel form of the paradox is then introduced, which focuses on infallibility rather than omniscience and derives, from semantic anti-realism and a highly plausible constraint on knowledge, that every believed proposition is not untrue. Because of the logical form of this conclusion, an analogue of the intuitionistic solution for the novel form of the paradox would require drawing the characteristic intuitionistic distinctions wrt decidable propositions, which cannot be done. Semantic anti-realism still intuitionistically entails the unacceptable conclusion that every believed (decidable) proposition is true. (shrink)
It is often claimed that the conclusion of a deductively valid argument is contained in its premises. Popper refuted this claim when he showed that an empirical theory can be expected always to have logical consequences that transcend the current understanding of the theory. This implies that no formalisation of an empirical theory will enable the derivation of all its logical consequences. I call this result ‘Popper-incompleteness.’ This result appears to be consistent with the view of deductive reasoning as (...) a process of unfurling the content of the premises; but I suggest that the result about validity impugns this theory of reasoning. (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)
This title introduces students to non-classical logic, syllogistic, to quantificational and modal logic. The book includes exercises throughout and a glossary of terms and symbols. Taking students beyond classical mathematical logic, "Philosophical Logic" is a wide-ranging introduction to more advanced topics in the study of philosophical logic. Starting by contrasting familiar classical logic with constructivist or intuitionist logic, the book goes on to offer concise but easy-to-read introductions to such subjects as quantificational and syllogistic logic, modal logic and set theory. (...) Chapters of this title include: Sentential Logic; Quantificational Logic; Sentential Modal Logic; Quantification and Modality; Set Theory; Incompleteness; An Introduction to Term Logic; and, Modal Term Logic. In addition, the book includes a list of symbols and a glossary of terms for ease of reference and exercises throughout help students master the topics covered in the book. (shrink)
In "Remarks on the Foundations of Mathematics" Wittgenstein discusses an argument that goes from Gödel’s incompleteness result to the conclusion that some truths of mathematics are unprovable. Wittgenstein takes issue with this argument. Wittgenstein’s remarks in this connection have received very negative reaction from some very prominent people, for example, Gödel and Dummett. The paper is a defense of what Wittgenstein has to say about the argument in question.
While Gödel's (first) incompleteness theorem has been used to refute the main contentions of Hilbert's program, it does not seem to have been generally used to stress that a basic ingredient of that program, the concept of formal system as a closed system - as well as the underlying view, embodied in the axiomatic method, that mathematical theories are deductions from first principles must be abandoned. Indeed the logical community has generally failed to learn Gödel's lesson that Hilbert's concept (...) of formal system as a closed system is inadequate and continues to use it as if there were no incompleteness theorem. In this paper I will stress the role of Gödel's incompleteness theorem in showing the inadequacy of such a concept of formal system and the need for a more articulated view of mathematical theories. More generally I will argue that Gödel's result entails that, as an alternative to mathematical logic, a new concept of logic is required: logic as the theory of communicating inference processes. (shrink)
Given any simply consistent formal theory F of the state complexity L(S) of finite binary sequences S as computed by 3-tape-symbol Turing machines, there exists a natural number L(F ) such that L(S) > n is provable in F only if n < L(F ). On the other hand, almost all finite binary sequences S satisfy L(S) > L(F ). The proof resembles Berry’s..
Richard Dagger (in this issue) provides perhaps the most persuasive version of a ‘fair play’ theory of criminal punishment, grounded in an attractive liberal republican political theory. But, I argue, his version of the theory still faces serious objections: that its explanation of why some central mala in se are properly criminalised is still distorting, despite his appeal to the burdens of ‘general compliance’; and that it cannot adequately explain (as it should explain) the differential seriousness and wrongfulness of different (...) kinds of crime. (shrink)
We examine some of Connes’ criticisms of Robinson’s infinitesimals starting in 1995. Connes sought to exploit the Solovay model S as ammunition against non-standard analysis, but the model tends to boomerang, undercutting Connes’ own earlier work in functional analysis. Connes described the hyperreals as both a “virtual theory” and a “chimera”, yet acknowledged that his argument relies on the transfer principle. We analyze Connes’ “dart-throwing” thought experiment, but reach an opposite conclusion. In S , all definable sets of reals are (...) Lebesgue measurable, suggesting that Connes views a theory as being “virtual” if it is not definable in a suitable model of ZFC. If so, Connes’ claim that a theory of the hyperreals is “virtual” is refuted by the existence of a definable model of the hyperreal field due to Kanovei and Shelah. Free ultrafilters aren’t definable, yet Connes exploited such ultrafilters both in his own earlier work on the classification of factors in the 1970s and 80s, and in Noncommutative Geometry, raising the question whether the latter may not be vulnerable to Connes’ criticism of virtuality. We analyze the philosophical underpinnings of Connes’ argument based on Gödel’s incompleteness theorem, and detect an apparent circularity in Connes’ logic. We document the reliance on non-constructive foundational material, and specifically on the Dixmier trace −∫ (featured on the front cover of Connes’ magnum opus) and the Hahn–Banach theorem, in Connes’ own framework. We also note an inaccuracy in Machover’s critique of infinitesimal-based pedagogy. (shrink)
Normal mathematical culture is overwhelmingly concerned with finite structures, finitely generated structures, discrete structures (countably infinite), continuous and piecewise continuous functions between complete separable metric spaces, with lesser consideration of pointwise limits of sequences of such functions, and Borel measurable functions between complete separable metric spaces.
The “DNA is a program” metaphor is still widely used in Molecular Biology and its popularization. There are good historical reasons for the use of such a metaphor or theoretical model. Yet we argue that both the metaphor and the model are essentially inadequate also from the point of view of Physics and Computer Science. Relevant work has already been done, in Biology, criticizing the programming paradigm. We will refer to empirical evidence and theoretical writings in Biology, although our arguments (...) will be mostly based on a comparison with the use of differential methods (in Molecular Biology: a mutation or alike is observed or induced and its phenotypic consequences are observed) as applied in Computer Science and in Physics, where this fundamental tool for empirical investigation originated and acquired a well-justified status. In particular, as we will argue, the programming paradigm is not theoretically sound as a causal(as in Physics) or deductive(as in Programming) framework for relating the genome to the phenotype, in contrast to the physicalist and computational grounds that this paradigm claims to propose. (shrink)
