University:
Massachusetts Institute of Technology
Course:
24.242 | Logic II
Academic year:

2023
Views:

118

Pages:

8
Author:

Rebecca Chaney

Godel's First Incompleteness Theorem First Incompleteness Theorem. If I? is a consistent x set of axioms that includes Q, then there is a true sentence that isn't provable in r . Proof: By Craig's Theorem, we may assume I? is A. Use the Self-referential Lemma to find a sentence @ such that Q I(@ - - Bewr([ r@l))- If @ were provable in r , then Bewr([r@]) would be a true hence provable in r . But also, since @ and (@ ~ewr([r@])is provable in -- x sentence, hence provable in Q, Bewr([r@])) are both provable in r , - r.This contradicts the consistency of r. - Since @ isn't provable in r , Bewr(r@) is false. Hence Bewr(r@) is true, and @ is true. !H Corollary. Any x set of axioms that includes Q and in a-consistent is incomplete, that is, there are sentences that are neither provable nor refutable in the theory. Proof: As before, we may take our set I? of axioms to be A. Let @ be the sentence constructed in the proof of the first incompleteness theorem. We saw already that @ isn't provable in r.Hence, for each m, m is not the code of a proof in I? of r@. Since the formula Br strongly represents {: x is the code of a proof of y in r } in Q, - [m] Br [ r@] is provable in Q, hence provable r.Since I? is a-consistent, (3y) y Br [ r@] isn't provable in r.That is, Bewr([r@]) isn't provable in r and so - @ isn't provable in r.!H in Because @ isn't provable in r , -@ consistent with r , even though, for each m, is consistent with r , and hence (3y)y Br [ r@] is - [m] Br [ r@] is a consequence of I? u {(3y)y Br [r@]} is an example of a consistent, a-inconsistent theory. r.Consequently, Self-reference Lemma, p. 2 Shortly after Godel's proof, Barclay Rosser recognized that the hypothesis of 0consistency was stronger than needed. Stronger Corollary (Rosser). Any x set of axioms that includes Q and is consistent is incomplete. Rosser proved this by constructing a sentence o that is provably equivalent to: ( ~ Y ) (Br Y [ 'oll + (32 < Y)z Br [" 0 '1). The proof looks a lot like the proof that every A set is strongly representable and the proof that every x total function is functionally representable. Indeed, the idea of these proofs originated with Rosser's proof. Since we have used Rosser's idea to prove the every A set is strongly representable, we can prove a Still Stronger Corollary (Tarski, Mostowski, and Robinson). There isn't any A set that includes the sentences provable in Q and excludes the sentences refutable. Note that this implies Rosser's result, since, if I? were complete, then the set of consequences of I? would be x , and the complement of the set of consequences of I?, which is {nonsentences) u {sentences 0: -0 is a consequence of I?), would also be x.. Proof: Suppose D were a A set that includes the sentences provable in Q and excludes the sentences refutable. Let 6(x) strongly represent D in Q, and use the Self-Referential Lemma to find a sentence q with Q If tn - - rqll)). is in D, then 6([ T I ) is provable in Q, and so q is refutable in Q, contrary to the hypothesis that D excludes the sentences refutable in Q. So 'ql must not be in D. Then -6([ rql) is provable Self-reference Lemma, p. 3 in Q, and so q is provable in Q, contrary to the hypothesis that D includes the sentences provable in Q. Contradiction.H A theory is said to be decidable iff the set of it's consequences is A. This usage is confbsing. If you say that Peano Arithmetic is decidable, you might be making the true statement that there is an algorithm for determining whether a sentence is an axiom of PA, or you might be making the false statement that there's an algorithm for determining whether a sentence is a consequence of the axioms of PA. The established practice is to accept the latter reading, but it's a practice that makes for easy mix-ups. It's the result of a common failure to make it clear whether by a "theory" one means a set of axioms or the set of consequences of a set of axioms. Indulging in the unfortunate usage, we have the following: Theorem. No decidable theory is consistent with Q. Proof: This is where we use the fact that Q, unlike PA, can be written down as a single sentence. If !a were a decidable theory consistent with Q, then {sentences 4: (Q - 4) is a consequence of !a) would be a A set that includes the consequences of Q and excludes the sentences refutable in Q.H Church's Theorem. The set of sentences valid in the predicate calculus isn't A. Proof: The set of valid sentences is consistent with Q, so it better not be a decidable the0ry.H If 4 is the Godel sentence for PA - the sentence that asserts, "I am not provable in PA" then we can recognize 4 as true, even though 4 isn't provable in PA. Consequently, PA doesn't include everything we can recognize as true. There is nothing special about PA in this. Replace PA by your favorite true theory, and you'll get the same answer. Self-reference Lemma, p. 4 Let's see what happens if we take I? to be the set of sentences of the language of arithmetic that we can recognize as true. By this, I don't mean merely the sentences we are able to prove in formal system. I mean the sentences we are capable of recognizing as true by any cognitive methods available to us. One of those cognitive methods is proof, and indeed we'll count a sentence as recognizably true if it is in principle derivable from other sentences that are recognizably true, even if the derivation is too complicated for us to carry it out in practice. Assuming that I? is x , we can form the Godel sentence for r.We can recognize that 4 is true, even though 4 isn't derivable from I?. But wait a minute. I? was supposed to include everything we could recognize as true, yet 4 is a sentence we can recognize as true, even though it's not a consequence of r. The conclusion J. R. Lucasl wants us to draw from this is that the set of arithmetical sentences we can recognize as true isn't x. This is a philosophically important conclusion. It's fatal for the computational model of mind, which has it that the way to understand the human mind is to regard it as a gigantic computing machine. But the consequences go farther than that. The workings of the human mind can't even be simulated by a Turing machine. Now the operation of any ordinary mechanical device that takes symbolic inputs and yields symbolic outputs can be simulated by a Turing machine. This includes mechanical devices made of flesh and blood, with a carbon-based central processing unit, as well as devices made of steel and 1. "Minds, Machines, and Godel," Philosophy 36 (1961): 120-24. The argument is taken up by Roger Penrose, The Emperor's New Mind (New York and Oxford: Oxford University Press, 1989). Self-reference Lemma, p. 5 plastic with a silicon-based CPU. The human mind has within it some spark of divinity that cannot be mimicked by any merely mechanical system. Most philosophers have wanted to resist Lucas's conclusion, but there has been no consensus what part of the argument to reject. One countervailing idea is this: The mere existence of the Godel sentence has no surprising consequences. What makes the Lucas argument go is that we can explicitly write down the Godel sentence, and once we have written it down, we can recognize its truth. In order for us to write down such a Godel sentence, it is not enough that there exist a X set of sentences whose consequences are all the arithmetical sentences we can recognize as true. We have to be able to explicitly specify the set. The conclusion to be drawn fiom the Lucas argument isn't that there isn't a computer program that simulates the operation of the human mind (or, at least, that part of human mental activity that is concerned with arithmetic). It's that, if there is such a program, we can't say what it is, or can't say with enough precision to write down the program and its Godel sentence. While this response resists Lucas's conclusion, it nonetheless takes us some distance down the path Lucas has pointed us. If you take an ordinary mechanical device, like a clock or an adding machine, we see that it' possible to find out exactly how the de vice works. Simply unscrew the back and examine it closely. The practical difficulties that stand in the way of doing the same thing for a hum being are immense. But before Godel's theorem we wouldn't have thought that in principle it was impossible for a human being to know her own program. It turns out, however, that a human being is fundamentally different fiom a mere mechanical device in that it isn't possible even in theory for a human being to know her own program, whereas it is Self-reference Lemma, p. 6 possible, at least in theory, to know in detail how a mechanical device works. The spark of divinity is still there, albeit in embers. One thing to say in response is that, to know what sentences an agent is able to recognize as true, it is not enough to know in detail how the agent's mind works. We also have to know which arithmetical sentences are true, since in order to recognize a sentence as true, it has to be true. The most we can hope to determine just by examining an agent's mental state is what sentences the agent regards as true, that is, which sentences she believes. To say which of these regardings of a sentence as true ought to count as recognitions of true, we have to know about the natural number system as well as about the agent's inner states. For the Lucas argument to even get started, we have to take I ' be the set of sentences the agent's belief-forming processes permit her to regard as true, rather than those she is able to recognize as true. But with that emendation, does not the Lucas argument show that, even though it is in principle possible to specify the outputs of a purely mechanical system by examining it closely, it isn't possible to do the same for the outputs of the human mind? Perhaps not. What the First Incompleteness Theorem shows is that, if I? is consistent, then the Godel sentence for I? is true. But how do we know that the set of arithmetical sentences we regard as true is consistent? Of course, we'd like to hope it's consistent, but you can't expect to tell by examining the belief-forming mechanism whether it ever generates a contradiction, for the same reason that you can't tell by examining it's program whether a given Turing machine will halt. As we shall see in detail when we turn to the Second Incompleteness Theorem, consisntent arithmetical theories can't prove their own consistency. We can't be sure that our Self-reference Lemma, p. 7 Godel sentence is true because we can't be sure that our beliefs are consistent. What we get in the end is not a spark of divinity but a counsel to humility. Another place that Godel's theorem has caused philosophical consternation is more directly concerned with the foundations of mathematics. Before the nineteenth century, mathrnaticians weren't insecure about what they were doing. What geometers studied was the structure of space (although the extend to which that structure was independent of our ways of representing space was controversial). After the advent of non-Euclidean geometry, this way of thinking was no longer tenable. Geometers studies many different, mutually incompatible systems, and they can't all describe the structure of reality. The traditional attitude toward geometry was a version of Aristotelean, as opposed to Platonic, realism. According to Plato, mathematical entities exist eternally in a pure realm all to themselves, free of the vicissitudes of bodies and sensations. Before birth, our uncorrupted minds could perceive them directly, but, now that we are embodied, our mathematical understanding consists in recollecting what before we could plainly see. Modem thinkers find this account of how mathematical knowledge is acquired implausible, so a central difficulty for mathematical Platonists -people who believe that mathematicians study actually existing things that are beyond the reach of space and time -is, How can we know about such things, when they don't affect us? Also, why are they so usehl scientifically, when they are causally inert? Aristotle's version or realism avoided this difficulty. The sense in which Aristotle's mathematical objects were "abstract' was different from the sense in which Plato's were. According to Aristotle, geometers studied ordinary physical things, regarding them from a "abstract"point of view that pays attention to size, shape, and position, but ignores color, texture, Self-reference Lemma, p. 8 weight, smell, and taste. The attraction of such a viewpoint faded dramatically with the advent of non-Euclidean geometry. Toward the end of the nineteenth century, an alternative conception of what mathematicians were doing became prominent. Mathematics isn't "about" anything. What mathematicians do is develop the consequences of systems of axioms. Which of those axioms are actually useful in describing material reality isn't a question for the mathematician; it's a question for the physicist. If there are any ways of interpreting the mathematical language so as to make the axioms true, we can be assured that the same interpretation will also satisfy the theorems. But whether there are such interpretations is not the mathematician's concern. This "formalist" perspective accurately describes what algebraists do. A "group" is anything that satisfies the axioms of group theory, and what a group theorist does is to discover the properties true of everything that satisfies the axioms. The picture doesn't fit what number theorists do. Whatever we take the axioms of number theory to be, there will be further statements we can recognize as true -true, that is, in the "intended model" of the language that aren't consequences of the axioms. By showing this is so, the First Incompleteness Theorem makes the formalist position difficult to maintain.

Gödel’s First Incompleteness Theorem

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock