X-Message-Number: 4146 Date: Tue, 04 Apr 95 04:48:38 From: mike <> Subject: SCI.CRYONICS Goedel This is a comment on Bob Ettinger's posting #4135, relating to Goedel's incompleteness results, and more specifically, his contention that "the incompleteness theorems are phony." First, it is worth remarking that this may not seem much related to cryonics, yet perhaps it has some relevance. Some people, e.g. Roger Penrose, have used the Goedel results as an argument against strong AI, in that there are (supposedly) things that are knowable to a human that are unknowable to a device that operates via a known set of rules, i.e., a machine. In cryonics, however, we say that essentially the human organism *is* a machine of a certain type and can be repaired from the frozen state as such, and made to functon again. It seems farfetched to me that Goedel's incompleteness result will ever pose an insurmountable barrier to the resusciation of cryonics patients, yet I suppose some people will worry over this issue, since they worry over every other conceivable obstacle to cryonics. (In fact many people act as if it is very important that they *find* objections to cryonics, so they can more easily dismiss it.) Anyway, to go on to the main issues, we recall that Goedel's principal results had to do with properties of certain formal mathematical systems, the kind in which results are expressed in the form of theorems that are proved. More specifically, the kind of mathematical systems Goedel dealt with were the comprehensive sort that can express all of ordinary mathematics including such topics as the arithmetic of whole or decimal numbers, Euclidean geometry, algebra, and the various mathematical constructs that are used in physics. It's great to have a comprehensive, more-or-less all-inclusive system of this sort, in which so many different results can be expressed. You are pushing toward a mathematician's Theory of Everything. But, there is a big danger with pushing too far. That is, your theory, whatever it is, must be based on starting assumptions or axioms that cannot be proved but must be accepted on faith. More or less, the more comprehensive or powerful you want your theory to be, the more axioms you have to assume. If you assume too many or too much, however, you find that, following one train of reasoning, you can prove some proposition P, whereas with some other approach you prove not-P, i.e. your system is inconsistent. A basic principle of logic, which essentially all useful mathematical systems incorporate, is "P implies that not-P implies Q" where Q is any other proposition whatever. In other words, in an inconsistent, formal system, any proposition that can be stated in the system becomes provable, which reduces everything to triviality. For a system to be useful, then, it is very important that it be consistent. Something of the seriousness of this problem can be gathered by considering a little mathematical history. In the 19th century there was great interest in putting mathematics on a firm logical footing, which involved finding simple underlying principles from which it was hoped that all or a very large part of mathematics could be derived. One of the pioneers of this effort was the logician Gottlob Frege (1848-1925). Frege (pronounced FRAY-guh) worked for 20 years to construct, in essence, the first comprehensive mathematical system, a near Theory of Everything. It was all based on a few relatively simple concepts, a very important one being the notion of set. More or less, almost everything in mathematics can be defined as some sort of set. For example, one definition of the number one is "the set of all singletons" where a singleton is a set having just one member or element. (This is not a circular definition, because "x has one member" means "there exists y such that y is a member of x, and for all z, if z is a member of x then z=y"; i.e. x's having one member can be defined without already having a definition of "one.") To make your theory as comprehensive and powerful as possible, then, it is desirable to have as many different sets as possible. Frege boldly rushed in and, in his theory, essentially allowed a set to be associated to every statable, mathematical property whatever. However, this led to inconsistency. Consider "the set of all sets that are not members of themselves." This set is a member of itself if and only if it is not a member of itself. Frege's system was inconsistent, and as it stood, mathematically worthless, a magnificent airplane that wouldn't quite fly. At this point we might raise the question, along the lines of Bob's posting, whether such a "set" is essentially meaningless. To me, however, it seems there is some meaning here. In general, many of the things I would think of as "sets" are not members of themselves. The set of prime numbers is not a prime number, for example. It seems reasonable, at first glance, that a set would either be a member of itself or not. And it seems reasonable, again at first glance, that I could form the collection of all those sets which do not happen to be members of themselves. "Collection" on the other hand, seems just another word for "set." Why not talk about the collection of all possible sets whatever? That very large collection (set), it would seem, contrary to many other sets, *is* required to be a member of itself. In any case, the existence of the inconsistency shows we are too general in what we allow to be a "set." Efforts at fixing the problem thus centered on how to restrict the notion of set, and still end up with essentially all of mathematics. Frege himself tried to devise such a fix, but his new system was again shown inconsistent. The first real success (we think) was had by Russell and Whitehead, whose system, Principia Mathematica or PM, was published in 3 volumes, 1910-13. PM can derive essentially all of mathematics, but it is cumbersome. Later some other, simpler systems of mathematical logic were devised that better met the intended needs and have not yet been shown to be inconsistent. Just because they have not been *shown* to be inconsistent doesn't mean they are consistent, however. Mathematicians such as David Hilbert, early in this century, worried over this problem. What you'd really like to do is *prove* such a system is consistent. Then (maybe) you could quit worrying, or at least not worry as much. Ideally, you'd start with some system, say PM, and prove *within PM itself* that PM is consistent. This would avoid the problem that, if you had to use some more comprehensive system, say PM*, to prove PM is consistent, it would still leave open the question whether PM* is consistent. (If PM* were inconsistent, then, as noted above, anything you like would be provable within it, and consequently its theorems would be untrustworthy.) On the other hand, though, even if you did prove PM was consistent, within PM, it still wouldn't "really" show PM is consistent. The reason for this is that PM is comprehensive enough that "PM is consistent" is one of the statable propositions within PM. Thus if PM is inconsistent you can prove "PM is consistent." And this property holds with all the other comprehensive systems I referred to, that were devised as improvements of PM. Still, mathematicians agreed, it would be interesting if you *could* prove consistency, even if you couldn't quite trust the result. Goedel showed, however, that *if PM is consistent*, it is impossible to prove that within PM. And this sort of proof carries over, straightforwardly, to the other logical systems I've referred to. Goedel's proof is closely related to another result, his incompleteness theorems. Within PM and related systems, there is a class of statements, the "closed well-formed formulas" or CWFFs, essentially just the statable propositions, expressed in a formal way, that is, according to specified rules. An example is "for all x, there exists y such that y is a member of x." This statement happens to be false, since if x is the empty set (a construct allowed in all these systems) there is no y that is a member of x. Let's call this statement S. Then not-S has the form "there exists x such that for all y, y is not a member of x." Not-S is true. In general, if S is a CWFF then either S or not-S is true. One important class of CWFFs is the *theorems,* which are statements obtainable by applying rules of inference to initial statements or axioms. Basically, every theorem is a *true* CWFF, *provided your system is consistent.* This means that, if S is a theorem, then not-S is *not* a theorem--again, if your system is consistent. The system is said to be *complete* on the other hand, if, for any CWFF S, either S *or* not-S is a theorem. What this means, essentially, is that the complete logical system is able to decide the truth or falsity of all applicable statements we can make within it. If we had enough time, in fact, we could start with any CWFF S, and search exhaustively for proofs, of both S and not-S. PM and the other systems are constructed so that this process can be mechanized. In this way then, a computer must eventually find either a proof of S, which would establish that S is true within the system, or a proof of not-S. (Any such proof would be expressible as a finite string of symbols.) If it ever found a proof of S, on the other hand, this would be a guarantee that it could *never* find a proof of not-S, and vice versa. All this would be the case, however, *only* if PM is *both* complete and consistent. If PM is consistent but not complete, for instance, there would be some CWFF S such that *neither* a proof of S nor of not-S could be obtained by exhaustively searching. What Goedel showed was that, in fact, PM and related systems, *if consistent*, are all incomplete. He did this by constructing a statement S for which he could show that both S and not-S are unprovable. S has the form, roughly, of "This statement is not provable within PM" (with analogous statements for the other systems). Then, if S actually *is* provable, the contradiction leads to the inconsistency of PM, while if not-S is provable that amounts to proving "This statement *is* provable within PM," which is again a contradiction and results in inconsistency. It is worth remarking that this result establishes the impossibility of proving the consistency of PM within PM. Such a proof would *prove* that neither S nor not-S is provable, for the reasons I've just outlined, and thus that S is true within the system, which would amount to a proof of S. Another point worth making is that Goedel's argument establishes that it is S, rather than not-S, that is true in PM. To establish this, however, it is clear we must use arguments *not* entirely formalizable within PM, or otherwise S would be a theorem. However, these extra arguments can all be reduced to the one property, that PM is consistent! This, really, is all the "extra" knowledge we need, other than what is contained in PM itself. Anyway, we can now consider what appears to be Bob's main gripe, that S is more-or-less meaningless, by virtue of self- reference, etc. My feeling is that S would seem more meaningful if we considered a closer approximation of the real statement S, rather than just our fuzzy English version. (See, for example, W. V. Quine's treatment in *Mathematical Logic,* Revised Ed., starting p. 307.) S is not simply "This statement is unprovable" but carefully and legitimately makes an assertion that a certain CWFF is not a theorem, in such a way that S itself *is* that very CWFF--a most remarkable achievement (especially given the cumbersome symbolism Goedel had to use in that pre-LISP era). To my thinking, it is meaningful to assert that any given CWFF is (or is not) a theorem, hence S itself is meaningful. A statement like, "This statement is false" does not seem so meaningful, because truth is not formalizable in the same sense as provability. However, I think this is not really the most important issue. For a logical system like PM, we would really like to know whether some statements within the system are true but unprovable. The incompleteness results establish this, in the sense that there are undecidable propositions like S. An objection might be raised that S is highly contrived and basically meaningless. However we have noted that another such proposition, whose undecidability follows from incompleteness, is the highly meaningful one, "the system is consistent." To my thinking, the incompleteness results deserve to be taken seriously. Mike Perry Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=4146