Insert non-formatted text here<The following treatise has been written some 25 years ago by a non-expert for non-experts, e.g. the enthusiastic readers of Hofstadters `Gödel, Escher, Bach` and similars. Continued reproaches from stubbornly resisting experts lead me to go into ever more details, so it all became a quite lengthy affair. Sorry for that!
Insert non-formatted text here
The following treatise has been written some 25 years ago by a non-expert for non-experts, e.g. the enthusiastic readers of Hofstadters `Gödel, Escher, Bach` and similars. Continued reproaches from stubbornly resisting experts lead me to go into ever more details, so it all became a quite lengthy affair. Sorry for that!
Just an initial remark: Every selfreferent sentence (formula) is based on identifying the subject with the
whole sentence, i.e. the TWO words 'this sentence' with the FOUR words ' this sentence is false', so mathematically speaking, it is based on the nonsensical equation 2 = 4 ! Why the hell do mathematicians take such nonsense so serious ? Gino ~~ ----
Selfreference, Sense or Nonsense?
A critical analysis of Logical Antinomies kung ikaw malibang adto lng sa ila kah wiling .. pag aron mag pa ilo ..... hahahahha hahahha .. !!
Cantor's Diagonal Argument
and
Goedel's Incompleteness Proof
by
Eginhart Biedermann
July 1984, revised in 2007
Contents
Page
I Introduction 2 II Principles of Foundations of Mathematics 3 III Counter theses 4 IV Selfreference in Natural Language 4 ………Selfreferent sentences 4 ………Selfreferent definitions 9 ………Selfreferent Predicates, Grellings Paradox 10 V The Impredicative Definition 11 ……The Unit Element The Dedekind Cut The Set that contains itself VI Cantor's Diagonal Method 15 ……Enumerable Infinity 15 ……Non-enumerable Infinity 16 ……Not effectively calculable Functions 17 ……Richard's Paradox . 18 ……The Three Modes of Diagonal Argument 18 …....Counter Arguments 19 ……A List of All Real Numbers between 0 and 1 22 ……Cantor's original version of Diagonal Argument 23
VII The Berry Paradox 25 VIII The Barber's Paradox 26 IX The Formal System P and Recursive Definitions 26 X Goedel's Incompleteness Theorem 29 XI The Halting Problem 33 XII Conclusions 36 ……………………Bib1iography 38
I Introduction
Since the appearance of the 'Liar's Paradox' in the discussion among Greek philosophers about 2500 years ago, selfreferent constructs have ever again been the subject of philosophical argumentation. Since about one century, with the advent of Cantor's set theory, mathematicians have joined this dis- cussion, mostly by advancing ever more 'paradoxa' or 'antinomies' which all are based somehow on selfreference, and which often were claimed to result from sound logical reasoning. The culmination in this discussion undoubtedly has been reached, now five decades ago, with Goedel's proof of the incompleteness of Formal Systems. However, as to the overall role and importance of selfreference in mathematics, we may justly repeat today what Hilbert formulated back in 1925: 'Let us admit that the situation in which we presently find ourselves with respect to the paradoxes is in the long run intolerable. Just think: in mathematics, this paragon of reliability and truth, the very notions and inferences, as everyone learns, teaches and uses them, lead to absurdities.' On the one hand, selfreference leads to antinomies, on the other hand, a self- referent argumentation is at the core of Goedel's famous Incompleteness Theorem. In the following treatise a clarification of this unsatisfactory situation will be attempted. Since the author finds himself in total opposition to a series of basic assumptions that underlie today's theory on the foundations of mathematics, the most prominent of these are quoted in Chapter II, to be confronted in Chapter III with the author’s counter-theses. These will then be defended in detail in Chapters IV to XI. In summary, the argumentation will demonstrate that genuine self- reference, whether in the self ascertaining or in the self contradicting mode, cannot be claimed to be of any good use, meaning or 'importance', whether mathematical or philosophical. To avoid misunderstandings: The here incriminated self-reference occurs only where 'elements of language' like predicates, sentences, definitions, arithmetic formulae or computer programs are intended to refer to themselves. This genuine selfreference has clearly to be differentiated from such formulations as 'I say', 'it has been shown in this paper', or the computer instruction 'go to instruction 17' (of the presently running program) , etc. None of these sentences takes reference to itself, and there is no objection to their use wherever appropriate.
Principles of Foundations of Mathematics
Since decades much work on the logical foundation of mathematics has been based, among others, on the following assumptions: 1) Selfreferent sentences and definitions do not constitute a violation of logic. There exist true, meaningful sentences that contain a self-reference. 2) A substantial part of the branch of mathematics called 'analysis' is founded on selfreferent, so-called 'impredicative' definitions, and no logical inconsistencies are generated thereby. 3) The theory of recursive functions is founded on self-reference. 4) Logically unobjectionable deductions can lead, in natural language as well as in mathematics, to logical inconsistencies, or 'logical paradoxes'. Although indeed all these paradoxes result from the same type of selfreference, due to 1), 2) and 3) it is not recommendable to avoid them simply by vetoing selfreference, since essential parts of mathematics would be lost thereby. 5) Cantor's diagonal method, making reference to all elements of infinite totalities, is an appropriate technique to prove the nonenumerability of such sets as the real numbers or the recursive functions, or to prove the existence of not effectively calculable functions etc. 6) The proper way to avoid the mathematical paradoxes is by imposing restrictions on several types of intuitively correct logical reasoning. Russell’s theory of types, 'mathematical constructivism' and various 'formalized systems' have been proposed to this end.
7) Goedel has proved, by an ingenious construction of a self- referent formula, that in any sufficiently rich formalized system there are infinitely many true arithmetical formulae that cannot be proved, i.e. they cannot be derived from any set of axioms, if that system is assumed to be consistent. Therefore, arithmetic is said to be 'incomplete'. 8) There can be no 'Halting Program', i.e. no computing procedure that would allow to determine whether a computer running on a given computer program with a given data input will ever come to a halt or run forever. This fact can be used for simple proofs of Goedel's Incompleteness Theorem. III The Counter Theses The following counter theses will be defended in chapters IV - XI. 1) In natural language all selfreferent (S.R.) sentences violate quite generally accepted and everywhere applied rules for a meaningful use of propositional sentences. No S.R. sentences are needed anywhere for the prime purpose of language, a meaningful and effective communication between individuals, including the formulation of scientific statements, arguments or conclusions. 2) In mathematics, the concept of 'impredicative definition' leads to an unfortunate mix-up of three logically different types of definition: non-self-referential, tautological and self-contradictory ones. At least the latter ones should be dismissed from mathematics to assure its consistency. 3) No selfreferent definitions are needed in the foundation of analysis, and no real number can be defined through the self- referent construct of a Dedekind cut on the rational numbers. 4) Recursive functions or definitions are not based on self- reference. 5) Cantor's Diagonal Method is inadequate to prove the set of all real numbers (or any other set) to be non-enumerably infinite, i.e. to be of higher infinity, of higher Cardinality than the natural numbers. As yet, no valid proof has ever been proffered that there could ‘exist’ more real numbers than the ‘infinitely many’ natural numbers. 6) The selfreference in Goedel's formula is achieved through an inconsistent application of a variable in two different identities. Therefore, the proper interpretation of that formula is rather: 'This formula is not correctly constructed, and (therefore) it is not derivable from a consistent set of axioms'. Consequently, that formula is not an undecidable formula within System P, and it does not prove the incompleteness of arithmetic. 7) The proof that there can be no 'Halting Program' is based on a selfreferent construct similar to the Liar Paradox. It appears to be based on the construction of a STOP-and-GO computer program. This proof is inconclusive, to say the least. 8) All so-called paradoxes arise from either genuine, intuitively nonsensical S.R. sentences or from self-contradictory definitions, and not one of them contains an inconsistency that could be claimed to 'results' from logical deduction.
IV Selfreference in Natural Language Three readily discernible types of selfreference can be construed in natural language, and in corresponding form we encounter them in mathematics as well: The propositional sentence that takes reference to itself, the selfreferent definition (of a concept), and the predicate that takes reference to itself. We begin here with the simple propositional sentence, consisting of subject and predicate only. To make it quite clear: The truth or falsity of 'if-then clauses', i.e. the question what conclusions can be drawn from given premises by logical reasoning, the subject of so many treatises on 'logics', is not the subject of the following considerations. Here we will rather be concerned with: What are meaningful premises? Everybody is well aware that we are able to formulate true and false, meaningful as well as meaningless sentences. Although thick volumes have been written by philosophers of all times about these four concepts, the most simplistic definition of them will here serve our purpose to avoid misunderstandings and inconsistencies, and the reader will easily convince himself that most of us make use of exactly this definition in our daily use of language. The prerequisites that have to be fulfilled in order to make a propositional sentence (i.e. one that makes a statement about some subject) qualifiable as 'meaningful' and 'true', are: 1) The subject word in the sentence has to identify unmistakably the item (given in some type of 'reality') that it is meant to address. This can be done in essentially three different ways: a) by using a demonstrative pronoun, and if possible pointing simultaneously at the addressed item: 'this book', 'this sentence' (the preceding one), 'this idea' (that has just been exposed) etc. b) by first assigning 'names' to the somehow indicated or described items and then using these names as subject words in the sentences: 'The Bible', 'Sentence 1', 'Goedel's Proof', etc. c) by an identifying description, e.g. by using subject attributes: 'The oldest book of mankind', 'The first sentence of chapter III', 'The formula proposed by Goedel to say of itself that it cannot be proved' etc. 2) The predicate of the sentence must equally be explained or defined somehow, e.g. 'is red' may be explained by showing several red things, in contrast to other, differently coloured things. 3) The item addressed by the subject word must belong to a category of 'things' to which the predicate of the sentence is applicable, or relative to which the predicate has been defined. 4) It must be possible to determine by perception or logical deduction that the item identified by the subject really has the property described by the predicate of the sentence. If any one of the first three requirements is not fulfilled, a sentence has to be classified as meaningless and there can be no examination of whether it is 'true' or 'false'. Thus, the sentence 'the apple is true' is meaningless for two reasons: It leaves entirely undetermined which apple is talked about, and the predicate 'is true' is not applicable to apples, i.e.: as yet it has never been defined relative to apples. If requirements 1) to 3) are fulfilled, then, and only then, can we concede the quality 'meaningful' to a sentence, and only then may we proceed to the examination whether it is 'true' or 'false', i.e. whether it is in accordance with the addressed 'reality' or not.
With these preliminaries we can now proceed to the subject proper of this chapter, the selfreferent sentences. 'This sentence is short' is readily cited as an example for a true S.R. sentence by those who believe S.R. sentences to be logically correct and unobjectionable constructions. And indeed, there can be no doubt that we can concede a certain amount of 'truth' to this sentence since it really is short. Many similar S.R. sentences can be formulated: 'This sentence appears on page 6' 'THIS SENTENCE IS PRINTED IN CAPITAL LETTERS', 'This sentence contains five words', 'This sentence contains two nouns', 'This sentence ends with the word 'you-name-it’. All these sentences are equally 'true' or 'correct' as 'This sentence is short', and certainly none of them is as false as 'This sentence is long' or 'This sentence contains four words'. And yet they all are sentences as they never occur in the normal use of natural language. They all violate the universally accepted rules for the usage of the demonstrative pronoun: In the moment of formulation of this 'This sentence' the respective sentences are not in existence so that one could point to them simultaneously. This self-referential usage of the pronoun 'this' is so unusual and deviating from the normal use of language that, to any unprepared reader who is confronted with one of these sentences for the first time, it has to be explained in an additional commentary that this 'This sentence' is intended to refer to nothing else but to just that sentence itself that begins with 'This sentence'. On the other hand, all these S.R. sentences have in common that their predicate refers to their printed appearance, their structure or their position on a page, that is, to particulars that at least become established during the formulation or with completion of these sentences, so that indeed the 'truth' of these statements may finally be examined. Everyone with some sensitivity for an unmistakable and unambiguous use of language will experience an increasing uneasiness when proceeding through the above sequence of S.R. sentences. This is due to the establishment of the addressed facts being ever more delayed in the course of sentence formation when we proceed through that list. That the first of them appears on page 6 is evident before we insert the "6". The situation with "CAPITAL LETTERS" is similar. In the third example, however, nothing is contained five times before we complete the sentence with "words" (another choice would have been: n's or S's!). In the fourth example a more confusing choice instead of the "nouns" would be: This sentence contains two sentences'. I can hardly imagine that any reader would classify this one as a meaningful and true sentence. In that respect, the last of the above examples is much nicer: It will always end with whatever word you insert instead of "you-name-it". This is one of the most universally self-fulfilling constructs that can be thought of.
And yet, even if we should be willing to accept such S.R. sentences as meaningful despite the misusage of the pronoun "this", we are confronted with the question what purpose such sentences could serve that produce the facts that they are to address with their own formulation only. In any case, these sentences indulge in a totally useless kind of self-satisfaction. Whereas normal statements in natural language may always be thought of in context with and as an answer to some earlier formulated question, this is not possible with these S.R.- sentences. And yet, it is only such a context that makes a propositional sentence meaningful as well as useful. Much worse is the situation with the two following S.R. sentences: "This sentence is true" and "This sentence is false". They are meaningless to a still higher degree than the preceding ones, because they contain predicates for whose meaningful, not selfreferent, application the necessary requirements are not fulfilled in two ways: Neither a "somehow existing reality" is given, nor a propositional sentence that addresses that reality, and referring to which, after appropriate examination, we could meaningfully formulate: "This propositional sentence is in accordance with the reality addressed by it, this sentence is true" or "it is in disaccord with that reality, it is false". So, in selfreferent application both "this sentence is true" and "this sentence is false" are equally nonsensical word sequences, constructed in flagrant violation of all good common sense. And never can "this sentence is false" be used as a proof for the inconsistency of our logic, as some logicians will have us believe, when they formulate that this sentence would be true, if it were false, and false, if it were true. Of course the same holds for such formulations as: "I am now lying", or the ancient version of the "liar's paradox" in which a Cretan is claimed to have said "all Cretans are always lying". And this has been realized more than 2300 years ago by the ancient Greeks themselves! I could not give a better description than the one ascribed to Chrysippos (280 - 208): "Those people who formulate the liar paradox, stray wholly from word meanings; they only produce sounds, without expressing anything". (see also footnote No 2 on page 11)
Let us now turn to the second type of subject identification, the use of names. Such S.R.-sentences will at least not contain the misused demonstrative pronoun. As we want to discuss sentences, we attach ‘names’ to them in the form of the capital letters: A: "Goedel was a great mathematician" B: "The sentence A contains ten words" C: "The sentence B is false" D: "The sentence C is true" Each of the sentences B, C, and D makes a statement about a preceding sentence and so derives its meaning from our knowledge of these, which we still remember and which we may substitute for their names in the subsequent sentences to obtain: B: "The sentence "Goedel was a great mathematician" contains ten words" or: C: "The sentence "the sentence "Goedel was a great mathematician" contains ten words" is false" Although a very ugly construction, such a nested sentence certainly is logically correct and it exhibits the phenomenon to be "self-sufficiently meaningful". At the beginning of this chapter the possibility of such a self-sufficiency was not addressed since this phenomenon cannot occur in propositional sentences in general. It is confined to statements about letters, words or word sequences. Only these three types of items, being the elements of language, can themselves be inserted instead of their names as subject attributes into sentences, so that these sentences can be meaningful without referring to some reality that were exterior to them ( such self-sufficiency will be encountered in mathematical formulae again). With this in mind we now turn to the S.R. sentences: E: "The sentence E contains six words" ; F: "The sentence F is true" K: "The sentence K is false". To some readers S.R. sentences of this form may at first sight appear somewhat less confusing than those constructed with the demonstrative pronoun, and yet we had to take recourse to an equally unusual procedure as with the use of the demonstrative pronoun that pointed to a nonexistent sentence. In fact, we had to violate a well established general rule saying that the name which I want to ascribe to an item must not change that item. This rule clearly precludes using the subject of a sentence as name for this same sentence. The meaning of "the sentence F is true" is totally independent of whether we call it "A", "B", "17" or "Jonny"; all these names are deliberately interchangeable. Not so the letter "F". When using F as name for "the sentence F is true" an entirely different construct results: When trying to obtain a self-sufficiently meaningful sentence by inserting sentence F in place of its name, we get: "The sentence "the sentence F is true" is true". We may repeat this operation indefinitely and yet will never get rid of that F, and we will never know what sentence is here claimed to be true, or more precisely, which sentence is assumed to be in accordance with what 'reality'. All we arrive at is the entirely nonsensical infinite nesting: 'The sentence, the sentence, the sentence …… is true, is true, is true', which certainly is in no way any more meaningful than our sentence K, which, upon insertion into itself, yields: K: 'The sentence 'the sentence K is false' is false' thus yielding quite automatically the self-contradiction that we had to derive from 'this sentence is false' by logical deduction. Again this can be no proof for the claim that 'logic leads to contradiction'. All we really can conclude is that this sentence is neither false nor true, but instead quite meaningless, since in its construction the second above-mentioned prerequisite was neglected: as yet nobody has succeeded in defining what 'is false' should mean in an S.R. sentence, where there is no possibility whatsoever for any reference to a 'somehow given reality'.
In no way better in this respect are sentences like: L: 'the sentence L is incomprehensible' or M: 'sentence M is self-contradictory' or N: 'sentence N is self-referential'. Certainly no reader could be talked into accepting them as a meaningful piece of information. A special example of such word sequences is: G: 'the sentence G cannot be proven to be true’. The best thing to do with such 'sentences' certainly were not to waste any more intellectual efforts on their analysis and to dismiss them forever from further scientific investigations, just for the simple reason that they have not been correctly named. However, the mathematical equivalent to the last one will be encountered in Chapter X at the core of Goedel's famous Incompleteness Theorem.
Selfreferent Definitions
We all experience rather early in life of what little help such definitions are as: 'red is red' and 'green is green'. Fortunately we have better means to learn differentiating the various colours. Due to this simple evidence of their uselessness, such definitions have never found acceptance to our everyday use of language (for the purpose of objective and unambiguous communication) , nor to the language of the natural sciences. In mathematics, however, selfreferent definitions have found quite widespread application in generating rather artificial problems. We will see that later.
Selfreferent Predicates, Grellings Paradox
In the intent to circumvent the grammatical problems encountered in the construction of selfreferent sentences, various logicians and mathematicians turned to the construct of 'selfreferent predicates'. We may raise the question whether such predicates as 'is short', 'is English', 'has five syllables' or 'is long', 'is German', 'contains four words' do share the property described by them, i.e. whether they are 'self-descriptive' or not (the first three are, the others not). The question whether the predicate 'is non-self-descriptive' is self-descriptive or not, is then said to lead to 'Grellings paradox' since, if it were self-descriptive, then it were non- self-descriptive, and vice versa. Clearly we are caught here in logic trap. To come to grips with the problem, we better omit the negation and ask whether the word sequence "does have the property which it describes" does have the property which it describes. It is immediately clear that the property here talked about between the quotation marks remains totally undefined. But to ask whether something has an undefined property is an utterly meaningless undertaking. The trick with Grellings Paradox evidently lies in that inconspicuous yet indefinite little 'it', which becomes meaningful only when preceded by something it can refer to. Yet, the 'it' in the above construct within the quotation marks is not preceded by anything the like. The additional introduction of the negation in the case of 'non-self-descriptive' does in no way improve on the meaninglessness of these formulations. Any variation in the wording, such as Hofstadter's '"yields falsehood when preceded by its quotation" "yields falsehood when preceded by its quotation"' does not bring any more meaning into the self generated verbal confusion. The only way out of these nonsense-loops is to stick to our common-sense rule to take reference only to subjects that have been exhibited or defined before, or that, at least, can be defined separately. Still, one could claim that all difficulties are avoided and a perfect, self sufficiently meaningful and true sentence were obtained when, instead of using demonstrative pronouns or sentence names in selfreferent intent, an identifying attribute is introduced to form the following 'last sentence of Chapter IV': 'The last sentence of Chapter IV does not refer to anything external to itself'. Footnote No 1 : Please do not consider this footnote to be part of Chapter IV. This would seriously impact the meaning and truth of 'the last sentence of Chapter IV', since then it would no longer refer to itself! But: is that really a good, self sufficiently meaningful sentence that depends in its truth so sensitively on changes in its surroundings? And does it, or does it not, refer to something external to itself? Is it not just another rather absurd example of a nonsensical word sequence, engaged in useless self-satisfaction, that has been invented for no better purpose than to irritate a confused and helpless audience? Footnote No 2: The nonsense of the self-referentially misused demonstrative pronoun is further enhanced when used in 'stand-alone' mode, to arrive at such S.R. sentences as: 'This is a sentence', 'This is a word', 'This is a letter', 'This is this', 'This is nonsense' etc. etc. The inclined reader may meditate on the philosophical profoundness of these 'sentences', or just forget them. It was the intent of this rather lengthy discussion to demonstrate that we certainly are able to produce nonsensical word sequences, but that natural language will not lose any of its capabilities and its value for a meaningful exchange of information when these selfreferent constructs are banned from it once and for all. In the following chapters, it will be shown that in mathematics selfreference serves no better purpose whatsoever.
V The Impredicative Definition and its application in Analysis:
the Unit element, the Dedekind cut, the Set that contains itself
Impredicative definitions are defined as such in which 'the definiens comprises totalities, of which the definiendum is a part'. Under this definition of impredicativity quite harmless definitions may get mixed up with pathological ones. The unit element A certainly harmless case is the definition of the unit element in a group as 'the element x for which, with any element y from the group, 'x ∙ y = y' is a true statement'. This is regarded as an impredicative definition since the unit element of the group is one of all the elements y in this group. At a closer look, however, this definition turns out not to be self-referential at all, since, for the definition of the unit element x, it is sufficient that for any element y (with: y # x) is valid: x ∙ y = y. An additional claim that also x ∙ x = x is not suited to define the unit element since it is fulfilled by x = 0 as well. This is about the same situation as when I write 'in this paper', where, without any self-reference, other sentences are addressed than the one I just formulate. The least upper bound An exemplary specimen of really self-referential impredicative definition that is thought to be needed in the foundation of analysis is the definition of 'the least upper bound B of a given bounded set S of real numbers', as was discussed by Weyl. In this context, the real numbers are treated as Dedekind cuts in the realm of the rational numbers and B is defined as the union of all the Dedekind cuts that belong to S. This union B is also a Dedekind cut and therefore a real number and it evidently has been defined on the basis of the set of all real numbers, of which it is an element itself. No doubt, this is again an Impredicative definition. And yet, it is quite decisively different from the definition of the unit element. Whereas there any single element y whatever was sufficient for the definition of x, any element z whatever out of S is quite useless for the definition of B. Either S contains a determinable largest element, then B is defined through this element (and this element alone!), or S does not contain a largest element, but then we can determine to each element z´ in S another element z´´ > z´ , that, taken alone, is a better approximation to B than the entire union of all the infinitely many elements z in S which are smaller than z´. So, they all together are useless for the definition of B. In general, however, in the process of the above definition we will even not be able to decide whether a given real number belongs to S or not, as long as B is not determined. So, the above definition tries in total self-reference to define B through B, and thereby it turns out to be of no use whatsoever. Here we are left with the question whether there is a need at all for such an existence proof for the least upper bound of a given bounded set of real numbers, or whether the entire formulation of the problem is based on a fundamental misunderstanding. To clarify this, we first have to reach an understanding on what a 'given bounded set S of real numbers' really is. By just formulating the sentence 'a set S be given' such a set certainly is still far from 'being given'. It cannot make any sense whatever to consider a set S as 'given' as long as it has not properly been defined! ‘Define a bounded set of real numbers’ can be done in two essentially different ways: 1.) through direct definition of it’s upper bound, e.g.: S = all z < e or T = all z <_ 1 etc. evidently S has no least upper bound, the least upper bound of T is 1. 2.) through some functional relation like:
S = all Z(r) with Z(r) = 1 – 1/e(exp)r with r = 1, 2, 3, ….. or
T = all Z(r) with Z(r) = π - 1√r with r = 1, 2, 3, ….
in none of these cases arises any doubt whether these sets S have some least upper bound B or not. In each case, the definition of S also contains the definition of B, and B may be an irrational, a rational or even a natural number, just as it has been defined, and in no case do we encounter a need to introduce a self-referential existence proof for B, or, to cite Weyl, 'real numbers of second level'. But it is not only in the discussion of this upper bound that we find such superfluous and useless self-referential definitions: Already the much more fundamental definition of the real number as a 'Dedekind cut' is by no means better.
The Dedekind Cut In Weyl's much cited book (p. 22) we read: 'under a real number a we understand the set of all rational numbers r which are smaller than a '!
No doubt, this is a totally self-referential formulation, and certainly, nobody has ever succeeded in defining a real number in this way. Wherever a real number is defined, this is done in the form of some functional relation on the basis of the natural or the rational numbers, just as the rationals are defined by the functional relation r = p/q. To just name a few of the most well-known: a = √2 or a x a = 2 or
e = 1+1/1!+1/2!+1/3!+ …. or π/4 = 1-1/3+1/5-1/7…..
Based on such definitions, each of these real numbers may be determined to any desired precision and exhibited as a broken- up decimal number. Thus, and only thus, can real numbers be defined, and as their definitions can lexicographically be ordered, they are countably infinite, just as the rationals. On top of all that: the definition of the reals as Dedekind Cuts on the rationals assures the smallest possible difference between two adjacent reals a’ and a’’ to be just one rational that belongs to a’ but not to a’’, so there cannot be more reals than there are rationals. Finally: in case the 'real number a' in Weyl’s definition should by chance be itself a rational number (the rationals are a subset of the reals!) this definition turns to the absurdity that the rational number a is no more itself, but instead identical to 'all rationals that are smaller than itself' ! On the basis of all this, no good argument can be found anywhere to convince us that impredicative definitions or any other Selfreference should or could be needed in the foundation of analysis. The Set that contains itself as Element The next example of impredicative definition to be discussed here, is taken from set theory. Set theorists like to start from the assumption that, to any property whatsoever that can somehow be described in some language or by a mathematical formula, the 'existence in reality' is established for the set of all 'things' that do have this property. In this context we need not discuss the problem what this 'existence in reality' could really mean, we may here content ourselves with the assumption that we can form, in our imagination, a mental conception of such a set. This then is intuitively quite a sound assumption as long as we assure that the definitions of the respective properties are perfectly unambiguous, and as long as we agree to understand by 'all things' all those 'things' of which we are able to have some mental conception before we start to check whether a given thing has one of these properties, or not. So we can easily conceive of the 'set of all those things that are fingers of our left hand' or 'the set of all those sentences in this treatise that contain more than ten words' or 'the set of all those natural numbers that are multiples of 17 and smaller than 10000' etc. etc. The affair becomes more dubious with the 'set of all primes between 10exp10exp10 and 10exp10exp11 , since nobody in our universe with it’s much less than 10¹ºº elementary particles will ever be able to determine such primes in the sense that he could write one of them down in, say, our decimal notation. Yet, most mathematicians even claim that they can conceive of the 'set of all primes' or of 'all natural numbers'. Honestly, I have no idea of how mathematicians manage to do that, and not one of them has ever given a reasonable explanation on what he does when he believes to imagine in his finite small brain such an infinite sequence in its totality. The usual argument 'but we can imagine to count up to any given natural number N, however large that N may be' certainly cannot serve the purpose, since the length of the sequence of the natural numbers up to any large N always remains Zero relative to the length of the sequence of all natural numbers. We all were taught that N/∞ = 0, no matter how large that number N may be. In spite of such difficulties to imagine infinite sets as 'given', a great variety of mathematical arguments has been based on the assumption that some specific infinite set be given (through the definition of the property common to all its elements). Then, by taking reference to 'all' the elements of this set, a further element is defined in such a way as to share the defining property with those elements. Whenever then it is claimed that this element be one of all of the elements on the basis of which it has been defined, this evidently is a case of impredicative definition, and invariably this procedure leads into confusion. The most prominent example of such reasoning is when set-theorists define 'the set of all sets', which, being itself a set, is then claimed, in neglect of the above-stated requirement for 'prior existence' to contain itself as element. The unavoidable consequence of this assumption is that this element of the set of all sets also has to contain itself as an element, which contains itself as element, which... etc., etc. We easily see that this unpronounceable infinite nesting results from the attempt to identify two contradictory concepts with each other, two concepts that, by definition, cannot be identical, i.e. a 'totality' and one of its 'elements'. It is in this category that we find one of the most famous 'mathematicians paradoxa', the one invented by Russell in 1902, who started by defining 'the set of all those sets that do not contain themselves as element' and of which he then claims that it would have to contain itself as element if it did not contain itself as element, and vice versa. A few more such 'definitions' may be listed here: 'The set of all mental concepts' 'The set of all inconceivable and unimaginable things' or, the one I like most of all: 'The set of all useless selfreferent mathematico-philosophical concepts'. I am rather inclined to say that the only paradox in context with such linguistic constructs is that we still find in modern textbooks on the foundations of mathematics such statements as: These paradoxes result from methods of reasoning and ways of thinking that do not appear to be intuitively unjustifiable. To come to the conclusion of this chapter: It has been shown that the concept of 'impredicative definition' leads to a confusing mix-up of selfreferent and non-selfreferent definitions. The selfreferent ones may be as useless as they are harmless when they are tautological, or when they correlate two non-contradictory concepts to each other, as are real numbers and Dedekind cuts. They lead into confusion and contradiction, however, as soon as, in violation of all good common sense, two contradictory entities are identified with each other, as it is done in the definition of the 'set of all sets' and any other set that is to 'contain itself as element!’
VI Cantor's Diagonal Method Since its introduction by Cantor in 1874 the Diagonal Method has found wide application for a variety of proofs all of which contain a certain amount of circularity in the sequence of arguments, and most of which were found to lead to some kind of paradox or antinomy. Therefore, this method and its various applications have to be discussed in all detail. The gist of the discussion will be to demonstrate that the underlying assumptions of this method lead to contradiction and should therefore be dismissed from mathematics. ……………………………….The Enumerable Infinity The definition of 'enumerable infinity' reads: The totality of all natural numbers is said to be an 'enumerably' or 'countably' infinite set since, by counting, we can reach any given natural number n, i.e. any element of this infinite set. The counting procedure determines the sequence 1, 2, 3, 4, ..., such that every element in this set, every natural number, has its predetermined place in that sequence. Any other infinite set, for the members of which a 1-1 mapping to the natural numbers exists, is equally said to be enumerably infinite and, by consequence, to be of the same infinite size as the set of the natural numbers. The most simple of such sets are 'all even numbers', 'all multiples of a given natural number n', 'all square numbers m = nexp2', 'all m = 2n, or 'all m = nexpn, etc, etc. By this definition of „enumerability“, it can also be shown that the set of all rationals x = p/q (with p < q) in the interval 0 < x < 1 is enumerably infinite, the arrangement in the sequence being such that p/q comes before r/s if (p+q)<(r+s), and in the case of (p+q)=(r+s), if p < r. When this sequence is 'extended to infinity', it will clearly comprise 'all' the rationals in the interval 0 < x < 1, and each one has its clearly defined place in the sequence, so the 1-1 mapping to the sequence of the natural numbers is assured. - …………….The Non-enumerable Infinity The first important application of Cantor's diagonal method was the surprising claim that the set of all real numbers r (i.e. “infinite decimal sequences”) in the interval 0 < r < 1 be not enumerable, meaning that there should be more, in fact infinitely more, irrationals than the infinitely many rationals in that interval. The proof runs as follows, and to avoid any mistake, I just copy the wording as given in S.C. Kleene, “Introduction to Metamathematics”: Suppose Xo' X1' X2' X3' ... to be an infinite list or enumeration of some but not necessarily all of the real numbers belonging to the interval. Write down one below the other their respective non-terminating decimal fractions. .Xoo Xo1 Xo2 Xo3 …. Select the diagonal fraction .X1o X11 X12 X13 ….. Xoo X11 X22 X33 …..and .X2o X21 X22 X23 …. change each of the successive digits .X3o X31 X32 X33 …. Xnn to a different digit X`nn, but …. .… …. …. avoid producing a terminating fraction. Say, let X`nn = 5 if Xnn is not = 5, and X`nn = 6 if Xnn = 5 The resulting fraction .X`oo X`11 X`22 X`33 ... represents a real number x which belongs to the interval but not to the enumeration. For the fraction differs from the first of the given fractions in the first (tenths) place, from the second in the second (hundredths) place, from the third in the third (thousandths) place, and so on. Hence the given enumeration is not an enumeration of all the real numbers in the interval. An enumeration of all the real numbers in the interval is non-existent. It is clear that an essential difference has been revealed between the set of the rational numbers on the one hand and the set of the real numbers on the other. The reals are not enumerable. So far S.C.Kleene. Let us shortly summarize the train of thought in this proof: First, an infinite list of infinite decimal fractions is assumed to be given, then, by taking reference to each one of the infinitely many decimal fractions, a new element is defined that, no doubt, is again an infinite decimal fraction, but different from all those in the list. This is assumed to prove that there exist more infinite decimal fractions, i.e. more real numbers in the interval 0 < x < 1 than can be enumerated in any infinite list. Therefrom results as the most outstanding claim that there be substantially more real numbers than rational numbers in that interval. This is rather hard to imagine since, as we all have learned, the rationals already lie so densely that between any two of them, they may be as close to each other as they ever want, there are infinitely many more others in between. Still another argument should make us skeptical against Cantor's claim: With Dedekind's definition of a real number r as 'the set of all rationals that are smaller than r', the smallest possible difference between two real numbers r1 and r2 consists of at least one rational number that belongs to r2 but not to r1. So, we certainly cannot differentiate between more reals than there are rationals in the 0 to 1 interval. We will come back to that after several other modes of Diagonal Argument have been presented. …………………The not effectively calculable functions A rather contrary use is made of the diagonal method to prove that there exist well defined, yet 'not effectively calculable' functions. We follow the argumentation as given by M. Davis (Computability and Insolvability p. XVII): We consider functions of a single variable f(x), defined on the positive integers (that is, for x = 1, 2, 3, etc.) and whose values are positive integers. Examples of such functions are xexp2, 2expx, `the xth digit in the decimal expansion of π' etc. We shall say that such a function f(x) is effectively calculable if there exists a definite algorithm that enables us to compute the functional value corresponding to any given value of x. Let us assure that such an algorithm can be expressed as a set of instructions in the English language. Furthermore, let us imagine all such sets of instructions ordered according to the number of letters they contain: first, those (if any) that consist of a single letter: then those that employ two letters: etc. Where there is more than one set of instructions consisting of the same number of letters, they are to be ordered among themselves, alphabetically, like the entries in a dictionary. Thus, there will be a first set of instructions, a second set of instructions, a third, etc. With each positive integer i, there is associated the ith set of instructions in this list, Ei, which tells us how to compute the values of some function. The function associated in this way with Ei we will call fi(x). Now let
g(x)=fx(x)+1. (2)
Then, g(x) is a perfectly good function. Its value for a given integer x is obtained by finding the xth set of instructions Ex, then applying it to the number x as argument, and finally increasing this result by 1. We have: I.) For no value of i is it the case that g(x) = fi(x). PROOF. Suppose that g(x) = fio(x) = for some integer io Then, by (2), fio(x) = f x(x) + 1 for all values of x. In particular, this equation would have to hold for x = io yielding fio(io) = fio(io) + 1. But this is a contradiction. Now, from the manner of choice of the Ei, the functions fi(x) were to include all effectively calculable functions. This yields: II.) g(x) is 'not effectively calculable'. So much from M. Davis. We will come back to that further down.
………………………… Richard's Paradox
Richard, in his 1905 paper, chose yet another mode of Diagonal argument to end up with a contradiction, a 'paradox'. The Ei are now assumed to constitute the list of all English word sequences that define a number, again in their lexicographical order. On the basis of the decimal expansions of these numbers we can then define an anti-diagonal sequence. This sequence represents a real number, and its definition is an English word sequence of finite length. So this definition must be one of the Ei, with a predetermined place in that list, due to the lexicographical ordering. Yet, due to its definition, this anti-diagonal number is different from all numbers in our list. So we have a contradiction.
………………..The three modes of Diagonal Argument
We summarize shortly the three different modes of 'diagonal', or better 'anti-diagonal argumentation' that we encountered:
For the proof of the non-enumerability of the real numbers the anti-diagonal was argued to be an additional sequence of the same species as the horizontal sequences in the infinite matrix.
For the not-effectively calculable function g(x), the anti-diagonal was concluded to be a new function of an essentially different type than the functions fi(x),
and, to arrive at the 'paradox', the anti-diagonal sequence was identified with one of the horizontal
sequences of the xij-matrix, thus producing the contradictory self-reference.
The origin of these variations is rather obvious. In the first case, the anti-diagonal non-terminating sequence of integers is as indisputably the representation of a real number as are all the horizontal sequences in the xij-matrix. On the other hand, the definition of that matrix was kept rather vague, it was just 'assumed to be infinite', and no word was lost on the question of what happened to an infinite xij-matrix when we try to add another line to it. Any such discussion was suppressed by the claim: 'evidently there are more than enumerably many real numbers'.
In the second case it was ascertained unambiguously that our list contained all the functions fi(x), whereas their property to be 'effectively calculable' was left vague enough so that we could content ourselves with the answer that the 'anti-diagonal function' g(x) be, although well defined, not effectively calculable, whatever that might mean.
In the third case, finally, it was again ascertained that our list contained all numbers that can be defined by finitely many English words, and the anti-diagonal equally turned out to be a number that also was defined by finitely many English words. So we had no other escape but to admit the 'contradiction'.
……………………Counter-Arguments Critical analysis will show that in none of the afore-mentioned three modes of Diagonal Argument do we have inevitably to follow the chosen way of reasoning. With the real numbers we have the choice between two counter- arguments. The most simple is to follow Cantor’s reasoning up to the conclusion: 'An enumeration of all the real numbers in the interval is nonexistent'. Instead of claiming that there be more real numbers than can be accommodated in any completed infinite list, however, we conclude: Certainly, there can be no complete infinite list of all real numbers, since no infinite list can ever be completed! This conception is a self-contradiction from the beginning! This leads to the second counter-argument where we question: What is it to mean when Cantor-Davis start by saying: 'Suppose that xo, x1, x2, ... is an infinite list of real numbers' and 'write down their respective non-terminating decimal fractions'? Nobody has ever succeeded in writing down a single non-terminating decimal fraction. All that can be written down are finite initial pieces of non- terminating decimal fractions. Real numbers, and here we mean essentially the irrationals, cannot be 'given' or defined by anything else but by algorithms or descriptions that yield resp. describe non-terminating decimal fractions. These algorithms and descriptions have to be formulated in some language, say in English, enriched by a series of mathematical symbols. This yields the chance, at least to start, to generate the lexicographically ordered infinite enumeration of 'all' finite definitions of real numbers, just as Richard assumed that the list of 'all' finite number definitions in general could be generated. The word 'all' is put in quotation marks here to indicate that it is not implied that this process could ever be terminated. To assure no to miss a single such definition, we follow J. Richard (1905) and start off with a lexicographically ordered enumeration of 'all' possible permutations (with repetitions) of our enlarged English alphabet, to eliminate, after careful examination, one after the other, all those permutations that do not define a real number. In the course of this examination we will rather early, say after the acceptance of k definitions of real numbers, run into the wording: 'Take the diagonal sequence from the xij-matrix that is defined by the lexicographically ordered sequence of all definitions of real numbers', and a little further down we will encounter something like: 'Take an anti-diagonal sequence to the xij-matrix that ...'. It is evident that the first of these wordings defines at best k decimals, and not one more! The (k+1)th decimal remains undefined with its selfreferent definition: the (k+1)th decimal is equal to the (k+1)th decimal of the (k+1)th sequence. This is just as unfit to define anything as the 'red is red' that was discussed earlier. And certainly all further decimals of this 'diagonal' are equally undefined since the xij-matrix from which they should be taken is not in existence yet. The anti-diagonal definition, showing up in our list after the acceptance of r correct real number definitions, certainly not better than the diagonal one, but not much worse either, is equally unfit to define a real number. The add-on of a self-contradiction in the definition of the (r+1)th decimal does not make much of a change. No doubt, we have to eliminate the diagonal, as well as the anti- diagonal definition once and for all from the infinite enumeration of the real number definitions. Based on this argumentation, Richard himself concluded back in 1905: 'therefore, there is no contradiction'. There is not much to add after 78 years. Cantor's Diagonal Argument and his non-enumerable infinity of the set of the real numbers cannot be recovered without the schizophrenic claim that we should and could first complete the infinite enumeration of all real number definitions and then reanimate the anti-diagonal definition that we had rejected before. Yet we have to keep it well apart from our infinite list, although it has its predetermined place there in the lexicographical order! So, through this resurrection we have maneuvered ourselves into the absurd situation that we try to define a real number by a sentence that does not define a real number as long as we consider it to be a definition of a real number. This absurdity, however, is most simply eliminated when we admit that the outstanding property of any infinite enumeration is that it can never be completed, not even imagined to be completed. So, the anti-diagonal definition will never become a valid definition of a real number. Confronted with these arguments, some mathematicians will tell you: 'Well, accepted that there cannot be more than enumerably many definitions of real numbers. The great majority of the real numbers, the non-enumerable ones, then are the “indefinable” real numbers'. It certainly cannot be questioned that we cannot enumerate what we cannot define. We cannot even discern two indefinable numbers from each other, just as we cannot attribute any meaning to the concept of the 'existence' of one sole indefinable number! But Cantor's whole paradise of transfinite numbers is based on the belief in the non-enumerable quantity of these numbers! The situation with the not-effectively calculable functions is quite similar. Since we will never manage to complete the list of all functions fi(x), the definition of g(x) will never become a well defined function for all values of x, but it certainly will be effectively calculable for every value of i respectively x, as far as the fi(x) have been defined before! Another, equally valid, argument against the not-effectively calculable function g(x) runs as follows: The infinite list of functions of one variable fi(x) yields a two-dimensional matrix of function values. Each such two-dimensional matrix represents basically a function of two variables g(x,y). The diagonal of this matrix, just as any anti-diagonal, is then correctly defined not as a function of one variable but as function of two variables g(x,y), with x = y = 1, 2, 3 and there will never surface the question whether this g(x,y) could be one of the f(x) or not, and there will be no basis for the claim that g(x,y) could be 'not-effectively calculable'.
Apart from this general criticism of the diagonal method, Davis's argumentation for the not effectively calculable function g(x) can be refuted on a much simpler basis: From the choice of the Ei, the set of functions fi(x) is assumed to comprise all effectively calculable functions the computing procedure for which is expressible in the English language. Then these functions are denominated by 'names'. To avoid nonsense and contradictions, these names must be symbols or words that do not belong to the English vocabulary as used in the formulation of the computing procedures Ei. Davis chose the symbols fi(x) for that purpose, which certainly are not part of the English vocabulary. When he then defines g(x) = fx(x) + 1 and calls g(x) a perfectly good function, he may be quite right. However, this g(x) certainly is not formulated in the English language! Neither the symbols fi, nor fx with its variable index belong to it. Therefore, it is unjustified to expect g(x) to be equal to one of the fi’s, or, otherwise, to conclude that it be 'not effectively calculable', since it is not equal to any one fi. g(x), not being definable with the English vocabulary that was used for the Ei is very well and effectively calculable as soon and as far as the symbols fi(x) are explained in English! So, there is no contradiction anywhere and nothing undecidable either. The only way to formulate the computing procedure for g(x) in the same language as used for the computing procedures Ei is the infinite sentence: If x equals 1 then follow the procedure ….. (these dots stand for the full length English formulation of E1) and if x equals 2 then follow the procedure….. (these dots stand for the full length formulation of E2) and if etc. etc. Yet this sentence can never be completed, so g(x) does not have a finite definition in the English language. It has to be emphasized here that the first two of our three versions of the Diagonal Argument are based on the fundamental assumption that an infinite list be first completed before the anti-diagonal is derived from it. Most surprisingly, most mathematicians accept this to be an 'intuitively justifiable' assumption although, as of today, nobody has ever succeeded in advancing another definition of an 'infinite sequence' that were not synonymous with 'a sequence that can NOT be finished'. This is precisely the same situation as with the conception of 'the set of all natural numbers', mathematicians claiming, without offering any proof or demonstration thereof, to dispose of an imaginative capability that appears intuitively absurd to most non-mathematicians. Certainly, there were also a few mathematicians who repudiated Cantor's mode of operating in and beyond the infinite (Kronecker, Brower), yet the overwhelming majority decided with Hilbert that 'no one shall be able to drive us from the paradise that Cantor created for us'. It must have been this enthusiasm for Cantor's paradise of ever higher infinites that forbade mathematicians to realize how easily a contradiction can be derived from Cantor's assumption that an infinite matrix could be completed. This will be shown in the next section.
………………… A list of all real numbers between 0 and 1
The most simplistic reasoning yields a 'proof' that the set of all real numbers x in the interval 0 < x < 1 is of exactly the same infinite size as the set of the natural numbers, as long as this set is assumed, as Cantor does, that it could be 'complete' and 'given' : For this proof we generate, starting with 0, the infinite list of the natural numbers, one below the other, for simplicity reasons in binary notation, by the following 'program':
Step 1: generate 0
1
Step n: put a copy of stage n-1 below stage n-1, put a vertical row of 0's to the left of stage n-1 and a row of 1's to the left of its copy. The n-th stage of this expanding matrix is a list of all natural numbers from zero to 2n-1 in binary notation, respectively a list of all possible 0-1-sequences of length n. The first three stages in this expansion are shown here: 0 00 000 Evidently, the application of Cantor’s Diagonal Method to any stage of this list 1 01 001 can never yield an 0 – 1 sequence that were not contained already in that list.
10 010
11 011
100
101
110
111
Now, if we want our list to comprise all natural numbers (in binary notation), we certainly are not allowed to interrupt its expansion at any finite step N, i.e. at any finite length of the horizontal 0-1-sequences. The complete infinite list of all natural numbers, the existence of which Cantor has succeeded to convince so many of, thus becomes inevitably an infinite xij-matrix which, in contrast to Cantor's xij-matrix, grows much faster in the vertical than in the horizontal direction. And yet, it grows in both directions to the same enumerable infinity. We all were taught the 1-1 mapping argument to make us believe that the set of all numbers m with m = 2expn is of equal infinite size (of cardinality No in the language of Cantor) as the set of all natural numbers n. But, when counted from right to left, the n-th row in our list of the natural numbers is precisely meant to correlate to the value 2expn. So, the set of all those rows is certainly of equal cardinality as the set of all numbers m = 2expn with n = 1, 2, 3, …. On the other hand, after the n-th program step our matrix consists of n rows and 2expn lines. So, it is equally justified to say that in our infinite xij-matrix, the set of all rows is of cardinality No, whereas the set of all lines is of cardinality 2expNo. Inevitably, cardinality 2expNo must be equal to cardinality No ! Cantor and all set-theorists, however, claim that 2expNo » No ! The assumedly 'complete', infinite xij-matrix which we obtained in the effort to generate a complete list of all natural numbers quite obviously is a list of all possible infinite 0-1-sequences. We are free to interpret any infinite 0-1-sequence as a real number in the interval {0,1} . So, unavoidably, our xij-matrix can be understood to be a list of all real numbers in that interval. Yet, this identity of the list of all natural numbers with the list of all real numbers in the {0,1}-interval is in contrast to Cantor's claim of the nonenumerability of the set of all real numbers in {o,1}. The origin of this contradiction clearly resides in the use of the concept 'complete infinite list'. In general, mathematicians do not tolerate concepts or assumptions which lead to contradiction. So let us stick to this principle, which has proved so successful everywhere else! We better admit that the list of 0-1-sequences can never become anything else but a finite list of 0-1-sequences of finite length N, no matter how large that N may be, respectively a list of just the first 2expN natural numbers, which is nothing compared to a list of 'all natural numbers'. And we have equally to admit that we are totally unable to develop in our mind something like a mental concept of a complete infinite list of real numbers in the form of complete infinite 0-1-sequences, from which we could gain another real number by Cantor's Diagonal Method. This honest confession is evidently the only possible way to avoid the above contradiction..
Cantor's original version of Diagonal Argument This discussion of Cantor's Diagonal Argument should not be terminated without mentioning his original version in his 1873 letter to Dedekind. I try to translate from Meschkowski: Assume that all points P in the interval 0 - 1 could somehow be enumerated. We then can select an interval [A1, B1] of length 1/3 that lies within the 0 - 1 interval and that does not contain point P1. The second point P2 in the enumeration may then be either outside of or within [A1, B1]. In either case, however, we can choose an interval [A2, B2] that has 1/3 the length of [A1, B1], that lies totally within [A1, B1], and that does not contain the point P2, and so on. We thus obtain a sequence of intervals [An , Bn ] with the following properties: 1.) [An+1, Bn+1] is contained within [An, Bn] 2.) the length of [A , B ] is 1/3expn 3.) the points P1, P2, P3, ……Pn are not contained in [An , Bn ] It follows from 1.) and 2.) that our sequence of intervals has the character of an 'Intervallschachtelung'. Therefore, there exists one point P which is contained in all intervals of the sequence. This point cannot be equal to any one of the points Pn, since P = Pm would lead to the contradiction: a) P lies within all intervals of the sequence, so it is also within [Am , Bm ] b) from 3.) follows that P = Pm is not within [Am, Bm ] From this contradiction Cantor concludes that the assumption must have been wrong that the points of the 0 - 1 -interval could be enumerated. This argument sounds quite reasonable, yet it ignores another important fact that we are taught in set theory: The mapping x → y = A1 + ⅓ x establishes a one-one mapping between the set of all real numbers in the 0 - 1 -interval to the set of the real numbers in [A1, B1]. A similar one-one mapping exists between all the points of any two successive intervals [An , Bn ] and [An+1,Bn+1] . How then can we believe that by repeating this mapping process over and over again we could ever manage to define one singular point? Let us assume our initial enumeration of points Pn to be the enumeration of the rational points between 0 and 1. The repeated mapping process then teaches us that each of the intervals [An , Bn ] contains just as many, and that is enumerably infinitely many, rational numbers as the 0 - 1 -interval, and each of the rational numbers in [An , Bn ] is also contained in the initial enumeration of the Pn . So, how can we, by this process, ever arrive at the definition of one singular number P that is not contained among the Pn ? We have seen that Cantor's Diagonal Argument is based on the result of the (assumed) execution of infinitely many steps of some mathematical procedure as a valid mathematical concept. Let us conclude this sad story with the most simple proof that this concept leads to contradiction: Assume the set N of all natural numbers, as well as an empty bag B as given. We transfer in step 1 of our infinite procedure first the numbers 1 and 2 to the bag B and then we return the number 1 to set N. The n-th step of this procedure is: transfer numbers 2n-1 and 2n to hag B and return number n to set N. The question is: How many numbers are in bag B after the (assumed) execution of 'infinitely many' steps. We answer with Cantor: There can be no number in the bag since any number ni that we might name has been removed from the bag in the ni-th step. And yet we know that the content of the bag has been augmented by one number with each of the infinitely many steps of our procedure. This simple contradiction should suffice to every sincere mathematician never again to fall back on the concept 'after infinitely many steps’.
VII The Berry Paradox
In the endeavour in Chapter VI to eliminate all those letter permutations from Richard's list that do not define a number we will encounter, apart from the diagonal and anti-diagonal definitions, many more letter sequences which superficially share the appearance of number-definitions, which, however, will have to be discarded for various quite evident reasons. A prominent group of unfit definitions are all those that take reference to some as yet unknown number definitions, i.e. to all those definitions that come later in the lexicographical order. A subgroup of these unfit definitions are all those that take reference to themselves. This selfreference may be accomplished in any one of the three modes that were discussed in Chapter IV, and it is quite immaterial whether these constructs are of the self-ascertaining or the self-contradicting type. A typical selection of such unfit 'number-definitions' is: No.m The number defined by this definition No.n Twice the number defined by definition No.n No.p The number defined by the third definition on page 25 of the treatise 'Selfreference, Sense or Nonsense' No.q One more than the number defined by the next definition No.r The sum of all numbers defined by definitions No.1 to No.r No.s Twice the largest number definable by 61 letters respectively numerals No.t The least integer not nameable in fewer than nineteen syllables It is quite obvious that none of these 'definitions' is fit to define a number. They all have to be eliminated from the list (or set) of number-definitions due to one and the same easily discernible deficiency: to take reference to themselves. Even the reference to 'the next definition' is unacceptable since this 'next definition' is as yet undefined, and might read: one more than the preceding definition. In the latter two, No.s and No.t, the selfreference is somewhat better camouflaged than in the former ones. No.s consists of 61 letters and numerals respectively, so it refers, among other definitions, also to itself. So does No.t, which consists of 18 syllables. This last formulation, which here appears as just one nonsense formula among many similarly constructed ones, has been introduced into the mathematical literature by Bertrand Russell in his version of 'Berry's Paradox', which runs like this: The expression: 'the least integer not nameable in fewer than nineteen syllables' must denote a definite integer; in fact, it denotes 111,777. But 'the least integer not nameable in fewer than nineteen syllables' is itself a name consisting of eighteen syllables; hence the least integer not nameable in fewer than nineteen syllables can be named in eighteen syllables, which is a contradiction! The fact that No.t is just one out of an infinite multitude of selfreferent constructs that have to be eliminated from the list of number-definitions, is thoroughly ignored in this discussion. So, instead of admitting that all these 'definitions' are man-made nonsense, modern mathematicians, like R. Rucker, derive from them such conclusions as 'paradoxes are compact energy sources' or 'The very existence of a paradox like this can be used to derive interesting facts about the relationship between the mind and the universe', or 'the paradoxes indicate that the rational world is incomplete'. Evidently, it provides more self-comfort to assume the world to be incomplete than to suspect one's own training in rational thinking of such a deficiency.
………………………VIII The Barber's Paradox
In the so-called 'Barber's paradox', a village barber is brought into trouble by the order to shave all those male villagers and only those who do not shave themselves. Evidently, with this order, the poor barber cannot decide whether he should shave himself or not. In both cases he violates the order. As realists with some common sense, we easily locate the problem in this story: A shaving barber is a physical phenomenon in space and time. It is a logician's arbitrariness to describe this phenomenon in a purely logical phrase, under elimination of space and time. With a physicist's order, our barber is better off: He is to shave in his shop between 9 a.m. and 11 a.m. all those and only those who do not shave themselves earlier in the morning at home.
This suppression of the parameter time in the description of physical phenomena is at the core of many erroneous claims that selfreference be a widespread phenomenon in our world. One prominent such claim is that every control system with its feedback loops be subject to Goedel’s undecidability problem, due to its built-in selfreference. Every engineer, however, knows about the importance of the time lag which is inherent to any feedback loop: reference is always made not 'to itself' but to an earlier state of the system. And we all are familiar with the most widespread technical 'if on then off and if off then on'- system: the electric door-bell. A second example of the same type of misunderstanding appears in many discussions on what happens when we reflect on our own mind. Again, there is no danger to get caught in a selfreferent loop: when we reflect on our mind, we invariably reflect on earlier states of our mind. A minimum time lag of about one second seems to be a reasonable estimate.
IX ……………… The Formal System P and Recursive Definitions
In defending the application of selfreference in general, it is often claimed by mathematicians that the entire theory of Recursive Functions be based on selfreference. It will be shown here that this is not the case. For this discussion, the concept of 'Formal System' has first to be introduced. We choose here the System P of Principia Mathematica, as it was used by Goedel for the formulation of the proof of his Incompleteness Theorem, to ∙be discussed in the next chapter. Whereas we all did our arithmetic at school with the help of the ten numerals 0, 1, 2,...9 and a variety of function symbols (addition +, subtraction -, multiplication ∙ , division : , faculty! etc.), plus a sequence of variable-symbols (x,y,z...), the Formalists tried around the beginning of this century to reduce arithmetic, in a sense, to its 'atoms'. The intent was to find a minimum number of interpreted symbols, so that, together with a set of rules for the formation of well-formed formulae, all arithmetical propositions could be expressed as such formulae, and vice versa, that all well-formed formulae would yield, when read from left to right, with the given interpretations of the individual symbols, arithmetical propositions. It was further hoped that, with the proper choice of a few well-formed formulae as 'axioms', and the definition of some transformation or derivation rules, all formulae that are 'derivable form the axioms' would yield, when 'interpreted', true arithmetic propositions. It is the totality of all these symbols, axioms, rules of formation and derivation, plus all possible well-formed formulae that are summarized under the concept 'Formal System'. Such a Formal System is called 'consistent' when for no formula A, this formula as well as its negation can be derived from the axioms. The System is called 'complete' when the set of all derivable formulae, 1when read from left to right with proper interpretation of the symbols, yields the set of all true arithmetic propositions.
For our discussion, the following set of basic symbols will serve the purpose: ~ not, v or, A and, > implies, 3 it exists a, = is equal to, 0 = zero, f follower of, (x) for all x is, x, y, z, v... an unlimited number of variable-symbols. A simple example of a formula then is: (x) ~ (fx = 0) with the interpretation: 'for all x it is not (true) that the follower of x equals zero'. This vocabulary might at first sight appear rather scanty, most of all since it contains but one arithmetic function symbol, the follower f. This allows us just to form the sequence of the natural numbers in the form 1= f0, 2 = ff0, 3 = fff0 etc. It is only through the introduction of the recursive definitions of the higher arithmetic functions that our system obtains the necessary strength. In its essence, this is nothing different than the mode in which we learned as children first the addition as 'counting-on', i.e. as a repeated taking of the follower, multiplication as a repeated addition and “faculty” as repeated multiplication. With the more familiar symbols a, b, 0, 1, +, ∙ , !, these processes can be generalized and expressed through the following formulae: a + 0 = a and a + (b+1) = (a+b) + 1 for b = 0, 1, 2, 3,... a ∙ 0 = 0 and a ∙ (b+1) = a ∙ b + a for b = 0, 1, 2, 3,... 0! = 1 and (b+1)! = (b+1) ∙ b! for b = 0, 1, 2, 3,... Successive substitution of the rising sequence of the numbers 0, 1, 2, 3, ... for b gives us our 'childrens arithmetic': a+0 = a, a+1 = a+1, a+2 = a+1+1 a+3 = a+1+1+1 a∙0 = 0, a∙1 = 0+a, a∙2 = 0+a+a, a∙3 = 0+a+a+a etc. 0! = 1, 1! = 1x1 2! = 2 ∙ 1! 3! = 3 ∙ 2! ∙ 1 4! = 4 ∙ 3! = 4 ∙ 3 ∙ 2! ∙ 1 etc. It is only after execution of these successive steps and then forgetting about them, that we can claim that e.g. 4! = 24, i.e. the result of adding 24 numbers “1” one to another , with no need for the function symbols for Faculty, Product and Sum . All this leaves us however with the question of “what IS “y!”” in the same sense as 4! IS (claimed to be) 24, here, where we cannot execute any such successive substitutions? Evidently, it cannot be defined other then by “ y!” plus the above definitions for the symbols “!”, “∙“, and “+”.
In all this, no selfreference can be found anywhere: the first element of the respective sequences is clearly defined, and so is the operation of how to derive the second from the first, the third from the second etc. etc. It is but a plain misunderstanding if a selfreference is interpreted into these definitions by the claim that, e.g. in (b+1)! = (b+1) ∙ b!, the exclamation mark on the one side be defined through the exclamation mark on the other side of that equation. In fact it is one number with the name '(b+1)!' that is explained on the basis of two other numbers, the names of which are '(b+1)' and 'b!'. And that's it! In System P, everything looks much more confusing; the basic logical structure, however, remains the same. Instead of our familiar function symbols (+ , ∙ , !), we have now to use variable symbols as 'function variables'. As recursive definitions for addition, multiplication and faculty we then get the formulae: ………. v1 = x1(y,u) Λ x1(y,0)= y Λ (z)(x1(y,fz) = fx1(y,z)) ……… v2 = x2(y,u) Λ x2(y,0)=0 Λ (z)(x2(y,fz) = x1(x2(y,z),y)) ………. v3 = x3(u) Λ x3(0)=f0 Λ (z)(x3(fz) = x2(x3(z),fz)) After substitution of specific numbers for the free variables y and u, say 3=fff0 for y, and ffff0 for u, these formulae are then considered to be valid representations in System P of the numbers v1= 7 (=3+4), v2 = 12 (= 3x4) and v3 = 24 (= 4!), in the form of recursive definitions. Again, to obtain the result “v3 = 24” we have to take recourse to above definitions for v3, v2, v1 and run through the same long sequence of substitutions as with “4!”. And what we mean by “y!”, here “u!” could not be anything but the combination of these three definitions!
The essential conclusion for us is that in all these constructs no use of selfreference is made anywhere.
X Goedel's Incompleteness Theorem
During the first three decades of this century, all the experience with System P never led to contradictory results, so, the consistency of the system seemed to be fairly well warranted. On the other hand, a series of arithmetical problems was known, which to solve all efforts had as yet
been in vain, problems which could however be formulated in System P (e.g. whether there is a largest prime-pair, like 17-19). So, the completeness of System P appeared less certain, i.e. whether all formulae the interpretation of which is a true arithmetical proposition, could be derived from the axioms. Consequently, it was a basic concern for theoretical mathematicians whether consistency and completeness of System P could not somehow be proved.
In this situation, in 1931, Kurt Goedel published his now famous paper in which he proved the incompleteness of System P by exhibiting a formula (G) that cannot be derived from the axioms of System P and yet has a 'true' interpretation, i.e. “that it cannot be derived from the axioms”!.
The decisive importance attributed to this result until today may here be reflected by the citation of some comments, articles and books that all have Goedel's proof as subject:
- 'Goedel's paper was destined to blow Hilbert's hopes and program sky high' G. Whitrow, 1978
- 'Goedel's work demonstrated that the resources of the human intellect can never be fully formalized, its structure and power being far more complex and subtle than those of any computer...'
G. Whitrow, 1978
- 'The foundations of mathematics appear to be fundamentally problematical...' J. Little, 1980
- 'Mathematics has been shorn of its truth' M. Kline, 1980
- 'The Incompleteness Theorem of Goedel governs control systems as well' A. P. Sage, 1981
- 'Goedel's Theorem points to God: the name of final closure' St. Beer, 1980
- Mind, Machines and Goedel: J.R. Lucas 1958
- God, the Devil, and Goedel: P. Benacerraf, 1967
- Goedel, Escher, Bach: D.G. Hofstadter 1979
In the face of such tremendous attention being paid to Goedel's proof, perhaps even more by philosophers than by mathematicians, and considering the fact that the 'true' interpretation of Goedel's formula (G) is a selfreferent and self-fulfilling construct that says of itself: 'This formula cannot be derived from the axioms', it appears worthwhile to take a very close look at the construction of this formula. With all our prior experience with selfreferent constructs it would not be too surprising to find some defect therein, that would, at least, cast some doubt on the validity or stringency of this 'Proof of Incompleteness'.
For this discussion, we refer here to the booklet 'Goedel's Proof' by E. Nagel and J.R. Newman which gives a fairly comprehensible presentation of this subject even for the mathematically untrained reader. Those familiar with Goedel's Proof may jump from here to page 31.
To enable formulae of System P to refer to 'axioms' and to 'formulae' and finally to 'itself' (these are all strings of the elementary symbols of System P) Goedel introduced specific numbers as names of such strings of symbols, since numbers are the only subjects that can be referred to in arithmetic formulae. To this end, the numbers 1, 2, 3,... are attributed as names, as 'Goedel-numbers', to the individual symbols:
~ v > 3 = 0 f ... x y z...,
1 2 3 4 5 6 7…. 11 19 17..., all further primes being
reserved for the unlimited supply of variable-symbols. On this basis the Goedel-number of a formula is defined to be the product of the rising sequence of primes, beginning with 2, with the i-th prime raised to the power indicated by the Goedel- number of the i-th symbol in that formula. Thus, the Goedel-number of the formula “0 = 0” becomes 2exp6 x 3exp5 x 5exp6 = 243 000 000.
Goedel has shown that, due to this formation procedure, the Goedel-numbers of well-formed formulae share a common arithmetical property that can recursively be described in the symbols of P. On the other hand, we can establish a long list of arithmetical properties that cannot be shared by Goedel-numbers of well-formed formulae, properties that result from meaningless symbol- sequences like '...(f)...' or '. ..=' etc. etc. The demonstration that the Goedel-number of a certain formula shares one such property will then be proof that this formula cannot be derived from the axioms, since our derivation rules warrant that only well-formed formulae can be derived from the axioms. As the next step, the Goedel-number of a proof, which is a sequence of, say, n formulae, is defined to be the product of the first n primes, the i-th prime having the Goedel-number of the i-th formula as exponent. From this construction it is evident that there exists some arithmetical relation between the Goedel-number x of a proof and the Goedel-number z of the last formula of that proof.
An essential part of Goedel's paper is to demonstrate how this relation can be expressed in System P in the shape of a recursive definition, i.e. as a long string of nothing but the elementary symbols of P. With the abbreviation Dem(x,z) for this relation, the formula (x)~Dem(x,z) then has the interpretation: 'For all numbers x it is not that x has the proof-relation to the number z' or 'there is no proof for the formula with Goedel-number z'.
One might suppose that all we have to do to obtain the self- referent formula (G) that says of itself that it cannot be proved, were to substitute in (x)~Dem(x,z) the Goedel-number of this formula for the variable z. Yet, here we encounter a twofold problem: For one, it is evident from the above definitions that the standard representation fff...0 of the Goedel-number of a formula must be much longer than that formula, so it can never be contained in it. Secondly, we run into the chicken-and-egg problem:
A definition of the Goedel-number of this formula cannot be formulated before that formula is completely formulated, and vice versa. After all the problems we encountered with self-referent constructs in natural language, it is not too surprising to see such difficulties in arithmetic as well.
To overcome this obstacle, Goedel invented his ingenious, recursively defined, 'substitution function' sub(m,19,Z(n)), the interpretation of which is: the number which results from number “m” through substitution (a very complicated arithmetical operation) of the “19” by the Gödel number of the number “n”, or , assuming “m” to be the Gödel number of some symbol sequence SS (symbols of the Formal System) “the SS that results from the SS with GN “m” through substitution (normal substitution) of the variable “y” by the numeral “n”.
By combining the proof relation Dem with this substitution function Goedel introduces the formula
(1) (x)~Dem(x,sub(y,19,Z(y)))
the GN of which be n. By substitution of (the representation ff..o of) this n for the variable y in (1) he finally arrives at the formula
(G) (x)~Dem(x,sub(n,19,Z(n)))
with the interpretation 'no x is GN of a proof for the formula with the GN sub(n,19,Z(n)) '. Yet sub(n,19,Z(n)) is (claimed to be) GN of formula (G), since (G) was obtained from (1) through substitution of n for y. So, formula G (is claimed to say) says of itself that it cannot be proved.
To prove the incompleteness of System P, Goedel then concludes - outside of System P - that (G) is a correct arithmetical statement since what it says must be true (if P is consistent), since other-wise it would prove a falsity. So far, so good! The success of the substitution function in generating a selfreferent and true formula appears to be perfect.
However, at a closer look, it is easily seen that, just as we had to violate well-established rules to obtain selfreference in natural language, so had Gödel to violate well-established mathematical rules to obtain his selfreferent formula.
reveals
A first questionable aspect of Gödel’s reasoning shows up in the word-for-word definition of what the abbreviation sub(y,19,Z(y)) is standing for: let us spell out its definition in detail: It reads (in parallel to the interpretation of ‘sub (n, 19, Z(n)’) : 'sub(y,19,Z(y)) is the GN of that formula that is obtained from the formula with GN y by substitution of the free variable y, (the GN of which is 19) by some symbol sequence y, the GN of which being defined by Z(y)’. Unmistakably, the symbol 'y' is here used in one context for two quite different entities: once for the free variable in some formula F(y), and secondly as name for the GN of just that formula (or, more generally, for a variable that ranges over the set of Goedel-numbers of well-formed formulae F(y)!).
It is not the first time in this treatise on selfreferent constructs that we encounter this operation: a more or less well camouflaged identification of two, by definition different, entities with each other! And here it is a quite obvious violation of a well-established rule in mathematics for the handling of variables, at least so long as consistent results are expected. On page 1 of Chapter I of Principia Mathematica, which is as much as the Bible for the theory of Formal Systems, Whitehead and Russell formulate the requirement that a chosen variable 'preserves a recognizable identity throughout the same context'.
The presumably 'true' interpretation of formula (G) is based on the context with formula (1), and the interpretation of formula (1) is based on the assumed existence of some formula F(y), which is addressed in (1) by its GN y. So, we have one context from F(y) through (1) to (G), and unquestionably the identity of the variable y is broken in this context.
So, the correct interpretation of formula (G) reads rather like: 'The formula with GN sub(n,19, Z(n)) has been constructed via an inconsistent application of the symbol 'y', and, therefore, that formula cannot be derived from a consistent set of axioms'.
A second concern arises with the question of what is the above term Z(y) in the symbols of the System? In the long sequence of the some 40 definitions which Gödel introduced for the construction of his Improvable Formula, we find under numbers 16. - 17. the recursive definition of Z(n) : 16. 0 N x = x, and (n + 1) N x = R(3)*n N x n N x corresponds to the operation of “putting the sign “f” n times in front of x” 17. Z(n) = n N [ R (1)] , Z(n) is the Numeral (the Gödel number for the numeral) denoting the number n . We encounter here exactly the same situation as was discussed above with the recursive definition for n! respectively v3. Only a long sequence of similar substitutions leads from e.g. Z(4) = 4 N [ R (1)] to the result “Gödel number of ffff0” (this claim being due to the above attribution of “1” and ”3” as Gödel numbers for the symbols “0” and “f”) However: what is Z(y)? Whereas Gödel takes the pain to tell us expressis verbis that Z(n) IS the Gödel number of the numeral for n, he does not make any remark on what he wants Z(y) to BE! It certainly is NOT the Gödel number for “y”, the number “19”, as would be required for the self referent interpretation of formula (G). And equally it can certainly not be the “Gödel-number of the (not existing) symbol-sequence that results from “putting the sign “f” y times in front of 0”. Unquestionably, Z(y) cannot be anything else but that entire recursive definition 16 + 17 (rewritten in the symbols of the system) with all occurrences of “n” being replaced by “y”. But then, the formula (G), with Z(n) BEING the Gödel number for “n”, certainly cannot be claimed to be derived from formula (1) through “substitution of “n” for “y””! So, the selfreferent interpretation of formula (G) is lost! No better result is obtained from assuming Z(n) not to BE the Gödel number for “n”, but, in parallel to the definition of Z(y), to be the definition 16 + 17 with argument “n” (n = Gödel number of formula (1)). Now formula (G) evidently results from (1) through “substitution of n for y”, but (G) no more says of itself to be obtained from (1) through “substitution of n for y”! Again, no selfreferent interpretation is obtained! That is, what I would like to call:
GÖDEL’S INCONSISTENCY
In the last decades, a variety of other notations for Goedel's proof have been proposed. In the zeal for abstract abbreviations, in all generality the substitution function has either silently been suppressed altogether or at least reduced to something like 's(v1,v1) '. So, the variable that is to be substituted is denied any visible appearance in these formulations. A scrupulous analysis, however, easily reveals that they all suffer from the same malady, the disregard of the first page of Principia Mathematica. The easiest way to get an idea of what must be wrong with Gödel’s invention is anyway just to enlarge the Formal System by the capability to accept symbol sequences in general as arguments, not just those representing numbers. So the need for Gödelization disappears and Gödel’s term ‘sub(y,19,Z(y))’ reduces to the simple Sub(y,y,y) = ‘the symbol sequence resulting from the symbol sequence y via substitution of the free variable y by the symbol sequence y’. No doubt, the symbol y appears here in two different identities! Concluding this chapter, it appears that we have to admit that the vast amount of mathematico-philosophical works and speculations that have by now been generated around Goedel's Theorem during five decades are all founded on a simple violation of Russell Whiteheads rule and on the dubious interpretation of the term Z(y). A last nasty remark may be permitted as to the existence of formula (G) in the Formal System: the Gödel number n of formula (1), and much more yet the Gödel number of this n would be fffff…..0 - sequences with many more symbols f then is the number of elementary particles in this universe, so there is no danger to ever encounter such a monster, at least not in this universe!
XI The Halting Problem A last section must be devoted to the so-called 'Halting Problem' since this is occasionally claimed to offer a basis for a simplified proof of Goedel's Incompleteness Theorem. No doubt, at the core of this argument, we will again find a selfreferent construct. It is based on the following concepts and assumptions: A 'Turing machine' is a (theoretical) version of a rather simple general purpose computer which operates, writes, reads or erases 0's or 1's on the central portion of a one-dimensional tape of, to both sides, unlimited length. 'Data-input' is the tape content (0 - 1 sequence) on which a program starts to operate. 'Data-output' is the tape content after a program comes to a halt by executing the instruction 'Halt and display the tape content'. There is a 'Doubling Program' which doubles the tape content on which it is set to operate, i.e. with a sequence of seven 1's as input, this program generates a sequence of fourteen 1's as output. Programs can be encoded in the form of (0 – 1)- sequences and written onto the tape. There is a 'Universal Program' which enables the Turing Machine to read, decode and execute any such encoded program. So, given 'code(P)v' as input, this program would simulate what would happen if we run program P on the input v. The Halting Problem then consists in the claim that there can be no algorithm, i.e. no program, that would allow to detemine whether a given program, when operating on a given data input, will ever come to a halt or run forever. This claim seems rather surprising since we are all familiar with a series of characteristics from which we can very well tell whether a program will run forever or not, e.g. whether it gets caught in a repeating loop, etc. As proof for that claim the formulation by Martin Davis be reproduced here: Suppose we possess a computing procedure which solves the halting problem for the universal program U. Then we can imagine more complicated procedures of which this supposed procedure is a part. Specifically, we consider the following procedure which begins with a string v of zeros and ones: 1. Try to decode v as the code for a Post-Turing program, i.e., try to find P with code(P) = v. If there is no such P, go back to the beginning of Step 1; otherwise go on to Step 2. 2. Make a copy of v and place it to the right of v getting a longer string which we can write as vv (or equivalently as code(P)v since code(P) = v). 3. Use our (pretended) halting problem procedure to find out whether or not the universal program U will eventually halt if it begins with this string vv as the nonblank portion of the tape, scanning the leftmost symbol. If U will eventually halt, go back to the beginning of Step 3; otherwise stop. This proposed procedure would eventually stop if, first, v = code(P) for some Turing - Post program P (so we will leave Step 1 and go on to Step 2), and, second, if also U will never halt if it begins to scan the leftmost symbol of vv. Since U beginning with code(P)v simulates the behavior of P beginning with v, we conclude that our supposed procedure applied to the string v will eventually stop if and only if v = code(P) where P is a computing procedure that will never stop beginning with v on its tape. By Turing's analysis, there should be a Turing-Post program Po which carries out this very procedure. That is, P will eventually halt beginning with the input v if and only if U will never halt beginning with the input vv. Now let vo = code(Po ). Does U eventually halt beginning with the input vovo? By what we have just said, P eventually halts beginning with the input v if and only if U will never halt beginning with the input vv . But, as we will show, this contradicts our explanation of how U works as a universal program. Since vo = code(Po), U will act, given the input vovo , to simulate the behavior of P when begun on input vo. So U will eventually halt beginning with the input vovo if and only if Po will eventually halt beginning with the input vo . But this contradicts the previous italicized statement. The only way out of this contradiction is to conclude that what we were pretending is untenable. In other words, the halting problem for U is not solvable. (so far Martin Davis) There is quite a sequence of inconsistencies in this 'proof'. We restrict, however, our critical comment on just two of them. The first runs like this: The presumed program which carries out the procedure which solves the halting problem for the universal program U be designated 'program H'. This program must be capable to 'tell' the human operator whether it has succeeded to determine that U, operating on some 'code(P)v'-input, will or will never come to a halt. The only way to do this is by halting and displaying a predetermined symbol, say a 0 for 'will halt' or a 1 for 'will never halt'. So, the program H must of necessity contain two branches which both end with a STOP instruction. When Davis then constructs his procedure Po around the program H with the instruction: 'if U will eventually halt, go back to Step 3' it is implied that, first, program H, as internal part of Po, comes to a Halt and displays a '0', and that after this Halt, program P continues with 'go back to STEP 3'. So, the simple trick with this 'proof' is to sell us a program that will run into a STOP and GO-mode! To protect us from such cheating, we had better replace the simple 'STOP'-instruction by 'STOP and Blow the Fuse'! This will help everyone to realize when a program has come to a STOP! The second argument against this 'proof' is probably more critical yet: Turing claims to have shown that everything computable can be computed by a Turing-Post program P that operates on an appropriate data input v on the tape of a Turing machine. Of necessity, all these programs P must be totally independent of whether we ever consider to 'encode' some of them by translating each instruction into a specific 0-1-sequence or not. Let us call all these programs 'level-1- programs'. A totally different thing is a universal program U that is expected to simulate a program P when operating on the input 'code(P) '! This program U must depend on the specific code that was chosen to encode P! It just has to contain the appropriate 'decoder'. This type of program be called a level-2-program. Logically, just as in Russell's Theory of Types, any program that we expect to simulate the level-2-program U when operating on the input 'code(U) code(P)v', would have to be a level-3-program with the capability to decode the decoder of the level-2-program U etc. etc.
Now, to solve the halting problem in all generality, it suffices entirely to have a procedure, i.e. a program H that solves the halting problem for level-1-programs P. Since this H is to operate on data input 'code(P)v', it certainly has to contain the appropriate decoder. So it is a level-2-program, just as U . But it would be quite unfair to require this H also to solve the halting problem for the level-2-program U if given 'code(U) code(P)v' as input! Davis in his 'proof', however, operates with such an H as part of his level-3-program Po' and, by totally neglecting the various program levels, he then feeds 'code(U) code (Po)’ as input to program Po . So, if Davis proves anything, it is that there can be no procedure that solves the halting problem for the universal program U with it’s built-in decoder. But this is no proof that there could be no procedure that solves the halting problem or every decoder-free level-1-program P ! It is not even a proof that there can be no procedure H that solves the halting problem for the universal program U, provided the program P in the input 'code(P)v', on which U is assumed to operate, does not contain a decoder. And by inserting into H the instruction 'blow the fuse if you find in your input 'code(U) code(P)v' the code of a program P that contains a decoder, we can easily protect ourselves from running with Davis into the infinite double-decode-execute- double-decode-execute... sequence, where we will never find an ultimate decoder-free program which were to be checked whether it will ever halt, just as in Chapter IV with the infinitely nested 'the sentence, the sentence...', where we never found out which sentence should be claimed to be false.
XII Conclusion The starting point of the here-presented considerations was originally a rather vague uneasiness in face of the observation that, on the one hand, two of the most prominent mathematical conceptions of the last hundred years, i.e. Cantor's 'transfinite paradise' and Goedel's Incompleteness Proof, and, on the other hand, the whole series of rather nonsensical 'logical antinomies and paradoxes' are based on essentially the same two types of construct: either a selfreference or a reference to an assumedly complete infinite multitude. Furthermore, the author admits that he has always felt totally incapable to follow his math teachers in their haughty claim to be able to 'see' such a multitude like the set of all natural numbers as one completed totality. A third motive behind the here-exposed considerations was the observation that, in sharp contrast to so many other branches of mathematics, from Cantor's transfinite paradise nothing ever came back to our finite universe that could be claimed to be of any value to the non-mathematical rest of humanity. As it turned out, the investigation had first to concentrate on self-referent constructs in natural language, to show how the so-called 'logical antinomies' are in fact based from the beginning on intuitively nonsensical or self-contradictory suppositions, and that self-referent sentences are really of no value whatsoever for a meaningful application of language. Then, the claim was shown to be untenable that self-reference be required in the foundations of mathematics. Next, the discussion concentrated on a critique of the 'Diagonal Argument', the key to Cantor's 'transfinite paradise', by demonstrating the non-validity of this argument when applied to a potentially infinite list of potentially infinite decimals. In the light of this, it appears quite unclear how the diagonal argument, which is so evident for any finite square of decimals, could ever have been claimed to be just as valid for Cantor's invention of a 'complete' infinite list. Finally, Gödel’s claim to have generated a formula that says of itself, that it cannot be proven, was shown to be unjustified . It cannot be expected that mathematicians, who chose to devote a good part of their lives to cultivating Cantor's paradise, and to speculate about the consequences of Gödel’s invention, will readily take up the here-presented arguments which, in all their simplicity, if not triviality, are hard to believe that they should never have surfaced before. But, quite clearly, they have been ignored so successfully that in no modern text-book on the subject matter any trace of a critical discussion of these aspects of 'infinite' lists and unprovable formulas can be found. Basically, it was tried to sharpen the reader's attention and scepticism towards all types of self-generated pseudo-problems that originate from a careless (or intended?) misuse of language, the favorite pastime of most philosophers since ‘The Liar’ more than 2000 years ago. Clearly, in these days such publications as D.G. Hofstadter's 'Goedel, Escher, Bach', or R.Rucker's 'Infinity and The Mind' are much more 'en vogue' with their trend to rather mystify than to clarify the doings in this branch of mental activity. But how formulated J. von Neumann: 'in mathematics, you don't understand things, you just get used to them!'
B I B L I 0 G RAP H Y
E.W.Beth, Foundations of Mathematics, North Holland 1965
P.W.Bridgman, A Physicists Second Reaction to Mengenlehre, Scripta Mathematica 1934
G.Cantor, Letter to Dedekind, in van Heijenoortf `From Frege to Gödel`
G.J.Chaitin, Göde1’s Theorem and Information, Int.J.Theoret.Physics Vo1.21, No. 12 , 1982 , p. 941
J.W.Dauben, Georg Cantor and the Origins f Transfinite Set Theory, Scientific American ,1983
M.Davis, Computability and Unsolvability, McGraw-Hill, 1958 The Undecidable, Raven Press, 1965
What is a Computation, in L.A.Steen : Mathematics today
L.Fischer, Die Grundlagen der Philosophie und der Mathematik,
F.Meiner Verlag, 1933, p 68 ff
K.Gödel, Über formal unentscheidbare Sätze der Princ. Math. Monatshefte Math. Phys. 38, 1931 ,
P 173-198
W.S.Hatcher, Foundations of Mathematics, Saunders, 1968 J. van Heijenoort, From Frege to Gödel, Harvard Un.Press, 1967
H.Hermes, Aufzäh1barkeit-Entscheidbarkeit, Springer 1961
Einführung in die mathematische Logik, Teubner, 1963
D.Hilbert, P.Bernays, Grundlagen der Mathematik II , Springer 1939 D.R.Hofstadter, Gödel-Escher-Bach, Basic Books, 1979 S.C.Kleene, Introduction to Metamathematics, North Holland 1971 E.Nagel,J.R.Newman, Gödel’s Proof, New York Univers.Press, 1958
J.Richard, The principles of mathematics and the problem of sets,
Revue General des Sciences Pures et Appliquees,1905
B.Rosser, An Informal Exposition of Proofs of Gödel’s Theorems
and Church’s Theorem, J.Symbolic Logic Vol.4, June 1939
R. Rucker , Infinity and the Mind, Birkhäuser 1982 B. Russell, A.N.Whitehead, Principia Mathematica . Cambridge U.P.1910 W. Sierpinski, Cardinal and Ordinal Numbers, Warszawa 1965 R.M.Smullyan, Theory of Formal Systems, Princeton U.P. 1961 L.A.Steen, Mathematics Today, Springer 1978 H. Weyl, Das Kontinuum, Veit & Comp. 1918
Selfreference, Sense or Nonsense?
A critical analysis of Logical Antinomies
Cantor's Diagonal Argument
and
Goedel's Incompleteness Proof
by
Eginhart Biedermann
July 1984, revised in 2007
Contents
Page
I Introduction 2 II Principles of Foundations of Mathematics 3 III Counter theses 4 IV Selfreference in Natural Language 4 ………Selfreferent sentences 4 ………Selfreferent definitions 9 ………Selfreferent Predicates, Grellings Paradox 10 V The Impredicative Definition 11 ……The Unit Element The Dedekind Cut The Set that contains itself VI Cantor's Diagonal Method 15 ……Enumerable Infinity 15 ……Non-enumerable Infinity 16 ……Not effectively calculable Functions 17 ……Richard's Paradox . 18 ……The Three Modes of Diagonal Argument 18 …....Counter Arguments 19 ……A List of All Real Numbers between 0 and 1 22 ……Cantor's original version of Diagonal Argument 23
VII The Berry Paradox 25 VIII The Barber's Paradox 26 IX The Formal System P and Recursive Definitions 26 X Goedel's Incompleteness Theorem 29 XI The Halting Problem 33 XII Conclusions 36 ……………………Bib1iography 38
I Introduction
Since the appearance of the 'Liar's Paradox' in the discussion among Greek philosophers about 2500 years ago, selfreferent constructs have ever again been the subject of philosophical argumentation. Since about one century, with the advent of Cantor's set theory, mathematicians have joined this dis- cussion, mostly by advancing ever more 'paradoxa' or 'antinomies' which all are based somehow on selfreference, and which often were claimed to result from sound logical reasoning. The culmination in this discussion undoubtedly has been reached, now five decades ago, with Goedel's proof of the incompleteness of Formal Systems. However, as to the overall role and importance of selfreference in mathematics, we may justly repeat today what Hilbert formulated back in 1925: 'Let us admit that the situation in which we presently find ourselves with respect to the paradoxes is in the long run intolerable. Just think: in mathematics, this paragon of reliability and truth, the very notions and inferences, as everyone learns, teaches and uses them, lead to absurdities.' On the one hand, selfreference leads to antinomies, on the other hand, a self- referent argumentation is at the core of Goedel's famous Incompleteness Theorem. In the following treatise a clarification of this unsatisfactory situation will be attempted. Since the author finds himself in total opposition to a series of basic assumptions that underlie today's theory on the foundations of mathematics, the most prominent of these are quoted in Chapter II, to be confronted in Chapter III with the author’s counter-theses. These will then be defended in detail in Chapters IV to XI. In summary, the argumentation will demonstrate that genuine self- reference, whether in the self ascertaining or in the self contradicting mode, cannot be claimed to be of any good use, meaning or 'importance', whether mathematical or philosophical. To avoid misunderstandings: The here incriminated self-reference occurs only where 'elements of language' like predicates, sentences, definitions, arithmetic formulae or computer programs are intended to refer to themselves. This genuine selfreference has clearly to be differentiated from such formulations as 'I say', 'it has been shown in this paper', or the computer instruction 'go to instruction 17' (of the presently running program) , etc. None of these sentences takes reference to itself, and there is no objection to their use wherever appropriate.
Principles of Foundations of Mathematics
Since decades much work on the logical foundation of mathematics has been based, among others, on the following assumptions: 1) Selfreferent sentences and definitions do not constitute a violation of logic. There exist true, meaningful sentences that contain a self-reference. 2) A substantial part of the branch of mathematics called 'analysis' is founded on selfreferent, so-called 'impredicative' definitions, and no logical inconsistencies are generated thereby. 3) The theory of recursive functions is founded on self-reference. 4) Logically unobjectionable deductions can lead, in natural language as well as in mathematics, to logical inconsistencies, or 'logical paradoxes'. Although indeed all these paradoxes result from the same type of selfreference, due to 1), 2) and 3) it is not recommendable to avoid them simply by vetoing selfreference, since essential parts of mathematics would be lost thereby. 5) Cantor's diagonal method, making reference to all elements of infinite totalities, is an appropriate technique to prove the nonenumerability of such sets as the real numbers or the recursive functions, or to prove the existence of not effectively calculable functions etc. 6) The proper way to avoid the mathematical paradoxes is by imposing restrictions on several types of intuitively correct logical reasoning. Russell’s theory of types, 'mathematical constructivism' and various 'formalized systems' have been proposed to this end.
7) Goedel has proved, by an ingenious construction of a self- referent formula, that in any sufficiently rich formalized system there are infinitely many true arithmetical formulae that cannot be proved, i.e. they cannot be derived from any set of axioms, if that system is assumed to be consistent. Therefore, arithmetic is said to be 'incomplete'. 8) There can be no 'Halting Program', i.e. no computing procedure that would allow to determine whether a computer running on a given computer program with a given data input will ever come to a halt or run forever. This fact can be used for simple proofs of Goedel's Incompleteness Theorem. III The Counter Theses The following counter theses will be defended in chapters IV - XI. 1) In natural language all selfreferent (S.R.) sentences violate quite generally accepted and everywhere applied rules for a meaningful use of propositional sentences. No S.R. sentences are needed anywhere for the prime purpose of language, a meaningful and effective communication between individuals, including the formulation of scientific statements, arguments or conclusions. 2) In mathematics, the concept of 'impredicative definition' leads to an unfortunate mix-up of three logically different types of definition: non-self-referential, tautological and self-contradictory ones. At least the latter ones should be dismissed from mathematics to assure its consistency. 3) No selfreferent definitions are needed in the foundation of analysis, and no real number can be defined through the self- referent construct of a Dedekind cut on the rational numbers. 4) Recursive functions or definitions are not based on self- reference. 5) Cantor's Diagonal Method is inadequate to prove the set of all real numbers (or any other set) to be non-enumerably infinite, i.e. to be of higher infinity, of higher Cardinality than the natural numbers. As yet, no valid proof has ever been proffered that there could ‘exist’ more real numbers than the ‘infinitely many’ natural numbers. 6) The selfreference in Goedel's formula is achieved through an inconsistent application of a variable in two different identities. Therefore, the proper interpretation of that formula is rather: 'This formula is not correctly constructed, and (therefore) it is not derivable from a consistent set of axioms'. Consequently, that formula is not an undecidable formula within System P, and it does not prove the incompleteness of arithmetic. 7) The proof that there can be no 'Halting Program' is based on a selfreferent construct similar to the Liar Paradox. It appears to be based on the construction of a STOP-and-GO computer program. This proof is inconclusive, to say the least. 8) All so-called paradoxes arise from either genuine, intuitively nonsensical S.R. sentences or from self-contradictory definitions, and not one of them contains an inconsistency that could be claimed to 'results' from logical deduction.
IV Selfreference in Natural Language Three readily discernible types of selfreference can be construed in natural language, and in corresponding form we encounter them in mathematics as well: The propositional sentence that takes reference to itself, the selfreferent definition (of a concept), and the predicate that takes reference to itself. We begin here with the simple propositional sentence, consisting of subject and predicate only. To make it quite clear: The truth or falsity of 'if-then clauses', i.e. the question what conclusions can be drawn from given premises by logical reasoning, the subject of so many treatises on 'logics', is not the subject of the following considerations. Here we will rather be concerned with: What are meaningful premises? Everybody is well aware that we are able to formulate true and false, meaningful as well as meaningless sentences. Although thick volumes have been written by philosophers of all times about these four concepts, the most simplistic definition of them will here serve our purpose to avoid misunderstandings and inconsistencies, and the reader will easily convince himself that most of us make use of exactly this definition in our daily use of language. The prerequisites that have to be fulfilled in order to make a propositional sentence (i.e. one that makes a statement about some subject) qualifiable as 'meaningful' and 'true', are: 1) The subject word in the sentence has to identify unmistakably the item (given in some type of 'reality') that it is meant to address. This can be done in essentially three different ways: a) by using a demonstrative pronoun, and if possible pointing simultaneously at the addressed item: 'this book', 'this sentence' (the preceding one), 'this idea' (that has just been exposed) etc. b) by first assigning 'names' to the somehow indicated or described items and then using these names as subject words in the sentences: 'The Bible', 'Sentence 1', 'Goedel's Proof', etc. c) by an identifying description, e.g. by using subject attributes: 'The oldest book of mankind', 'The first sentence of chapter III', 'The formula proposed by Goedel to say of itself that it cannot be proved' etc. 2) The predicate of the sentence must equally be explained or defined somehow, e.g. 'is red' may be explained by showing several red things, in contrast to other, differently coloured things. 3) The item addressed by the subject word must belong to a category of 'things' to which the predicate of the sentence is applicable, or relative to which the predicate has been defined. 4) It must be possible to determine by perception or logical deduction that the item identified by the subject really has the property described by the predicate of the sentence. If any one of the first three requirements is not fulfilled, a sentence has to be classified as meaningless and there can be no examination of whether it is 'true' or 'false'. Thus, the sentence 'the apple is true' is meaningless for two reasons: It leaves entirely undetermined which apple is talked about, and the predicate 'is true' is not applicable to apples, i.e.: as yet it has never been defined relative to apples. If requirements 1) to 3) are fulfilled, then, and only then, can we concede the quality 'meaningful' to a sentence, and only then may we proceed to the examination whether it is 'true' or 'false', i.e. whether it is in accordance with the addressed 'reality' or not.
With these preliminaries we can now proceed to the subject proper of this chapter, the selfreferent sentences. 'This sentence is short' is readily cited as an example for a true S.R. sentence by those who believe S.R. sentences to be logically correct and unobjectionable constructions. And indeed, there can be no doubt that we can concede a certain amount of 'truth' to this sentence since it really is short. Many similar S.R. sentences can be formulated: 'This sentence appears on page 6' 'THIS SENTENCE IS PRINTED IN CAPITAL LETTERS', 'This sentence contains five words', 'This sentence contains two nouns', 'This sentence ends with the word 'you-name-it’. All these sentences are equally 'true' or 'correct' as 'This sentence is short', and certainly none of them is as false as 'This sentence is long' or 'This sentence contains four words'. And yet they all are sentences as they never occur in the normal use of natural language. They all violate the universally accepted rules for the usage of the demonstrative pronoun: In the moment of formulation of this 'This sentence' the respective sentences are not in existence so that one could point to them simultaneously. This self-referential usage of the pronoun 'this' is so unusual and deviating from the normal use of language that, to any unprepared reader who is confronted with one of these sentences for the first time, it has to be explained in an additional commentary that this 'This sentence' is intended to refer to nothing else but to just that sentence itself that begins with 'This sentence'. On the other hand, all these S.R. sentences have in common that their predicate refers to their printed appearance, their structure or their position on a page, that is, to particulars that at least become established during the formulation or with completion of these sentences, so that indeed the 'truth' of these statements may finally be examined. Everyone with some sensitivity for an unmistakable and unambiguous use of language will experience an increasing uneasiness when proceeding through the above sequence of S.R. sentences. This is due to the establishment of the addressed facts being ever more delayed in the course of sentence formation when we proceed through that list. That the first of them appears on page 6 is evident before we insert the "6". The situation with "CAPITAL LETTERS" is similar. In the third example, however, nothing is contained five times before we complete the sentence with "words" (another choice would have been: n's or S's!). In the fourth example a more confusing choice instead of the "nouns" would be: This sentence contains two sentences'. I can hardly imagine that any reader would classify this one as a meaningful and true sentence. In that respect, the last of the above examples is much nicer: It will always end with whatever word you insert instead of "you-name-it". This is one of the most universally self-fulfilling constructs that can be thought of.
And yet, even if we should be willing to accept such S.R. sentences as meaningful despite the misusage of the pronoun "this", we are confronted with the question what purpose such sentences could serve that produce the facts that they are to address with their own formulation only. In any case, these sentences indulge in a totally useless kind of self-satisfaction. Whereas normal statements in natural language may always be thought of in context with and as an answer to some earlier formulated question, this is not possible with these S.R.- sentences. And yet, it is only such a context that makes a propositional sentence meaningful as well as useful. Much worse is the situation with the two following S.R. sentences: "This sentence is true" and "This sentence is false". They are meaningless to a still higher degree than the preceding ones, because they contain predicates for whose meaningful, not selfreferent, application the necessary requirements are not fulfilled in two ways: Neither a "somehow existing reality" is given, nor a propositional sentence that addresses that reality, and referring to which, after appropriate examination, we could meaningfully formulate: "This propositional sentence is in accordance with the reality addressed by it, this sentence is true" or "it is in disaccord with that reality, it is false". So, in selfreferent application both "this sentence is true" and "this sentence is false" are equally nonsensical word sequences, constructed in flagrant violation of all good common sense. And never can "this sentence is false" be used as a proof for the inconsistency of our logic, as some logicians will have us believe, when they formulate that this sentence would be true, if it were false, and false, if it were true. Of course the same holds for such formulations as: "I am now lying", or the ancient version of the "liar's paradox" in which a Cretan is claimed to have said "all Cretans are always lying". And this has been realized more than 2300 years ago by the ancient Greeks themselves! I could not give a better description than the one ascribed to Chrysippos (280 - 208): "Those people who formulate the liar paradox, stray wholly from word meanings; they only produce sounds, without expressing anything". (see also footnote No 2 on page 11)
Let us now turn to the second type of subject identification, the use of names. Such S.R.-sentences will at least not contain the misused demonstrative pronoun. As we want to discuss sentences, we attach ‘names’ to them in the form of the capital letters: A: "Goedel was a great mathematician" B: "The sentence A contains ten words" C: "The sentence B is false" D: "The sentence C is true" Each of the sentences B, C, and D makes a statement about a preceding sentence and so derives its meaning from our knowledge of these, which we still remember and which we may substitute for their names in the subsequent sentences to obtain: B: "The sentence "Goedel was a great mathematician" contains ten words" or: C: "The sentence "the sentence "Goedel was a great mathematician" contains ten words" is false" Although a very ugly construction, such a nested sentence certainly is logically correct and it exhibits the phenomenon to be "self-sufficiently meaningful". At the beginning of this chapter the possibility of such a self-sufficiency was not addressed since this phenomenon cannot occur in propositional sentences in general. It is confined to statements about letters, words or word sequences. Only these three types of items, being the elements of language, can themselves be inserted instead of their names as subject attributes into sentences, so that these sentences can be meaningful without referring to some reality that were exterior to them ( such self-sufficiency will be encountered in mathematical formulae again). With this in mind we now turn to the S.R. sentences: E: "The sentence E contains six words" ; F: "The sentence F is true" K: "The sentence K is false". To some readers S.R. sentences of this form may at first sight appear somewhat less confusing than those constructed with the demonstrative pronoun, and yet we had to take recourse to an equally unusual procedure as with the use of the demonstrative pronoun that pointed to a nonexistent sentence. In fact, we had to violate a well established general rule saying that the name which I want to ascribe to an item must not change that item. This rule clearly precludes using the subject of a sentence as name for this same sentence. The meaning of "the sentence F is true" is totally independent of whether we call it "A", "B", "17" or "Jonny"; all these names are deliberately interchangeable. Not so the letter "F". When using F as name for "the sentence F is true" an entirely different construct results: When trying to obtain a self-sufficiently meaningful sentence by inserting sentence F in place of its name, we get: "The sentence "the sentence F is true" is true". We may repeat this operation indefinitely and yet will never get rid of that F, and we will never know what sentence is here claimed to be true, or more precisely, which sentence is assumed to be in accordance with what 'reality'. All we arrive at is the entirely nonsensical infinite nesting: 'The sentence, the sentence, the sentence …… is true, is true, is true', which certainly is in no way any more meaningful than our sentence K, which, upon insertion into itself, yields: K: 'The sentence 'the sentence K is false' is false' thus yielding quite automatically the self-contradiction that we had to derive from 'this sentence is false' by logical deduction. Again this can be no proof for the claim that 'logic leads to contradiction'. All we really can conclude is that this sentence is neither false nor true, but instead quite meaningless, since in its construction the second above-mentioned prerequisite was neglected: as yet nobody has succeeded in defining what 'is false' should mean in an S.R. sentence, where there is no possibility whatsoever for any reference to a 'somehow given reality'.
In no way better in this respect are sentences like: L: 'the sentence L is incomprehensible' or M: 'sentence M is self-contradictory' or N: 'sentence N is self-referential'. Certainly no reader could be talked into accepting them as a meaningful piece of information. A special example of such word sequences is: G: 'the sentence G cannot be proven to be true’. The best thing to do with such 'sentences' certainly were not to waste any more intellectual efforts on their analysis and to dismiss them forever from further scientific investigations, just for the simple reason that they have not been correctly named. However, the mathematical equivalent to the last one will be encountered in Chapter X at the core of Goedel's famous Incompleteness Theorem.
Selfreferent Definitions
We all experience rather early in life of what little help such definitions are as: 'red is red' and 'green is green'. Fortunately we have better means to learn differentiating the various colours. Due to this simple evidence of their uselessness, such definitions have never found acceptance to our everyday use of language (for the purpose of objective and unambiguous communication) , nor to the language of the natural sciences. In mathematics, however, selfreferent definitions have found quite widespread application in generating rather artificial problems. We will see that later.
Selfreferent Predicates, Grellings Paradox
In the intent to circumvent the grammatical problems encountered in the construction of selfreferent sentences, various logicians and mathematicians turned to the construct of 'selfreferent predicates'. We may raise the question whether such predicates as 'is short', 'is English', 'has five syllables' or 'is long', 'is German', 'contains four words' do share the property described by them, i.e. whether they are 'self-descriptive' or not (the first three are, the others not). The question whether the predicate 'is non-self-descriptive' is self-descriptive or not, is then said to lead to 'Grellings paradox' since, if it were self-descriptive, then it were non- self-descriptive, and vice versa. Clearly we are caught here in logic trap. To come to grips with the problem, we better omit the negation and ask whether the word sequence "does have the property which it describes" does have the property which it describes. It is immediately clear that the property here talked about between the quotation marks remains totally undefined. But to ask whether something has an undefined property is an utterly meaningless undertaking. The trick with Grellings Paradox evidently lies in that inconspicuous yet indefinite little 'it', which becomes meaningful only when preceded by something it can refer to. Yet, the 'it' in the above construct within the quotation marks is not preceded by anything the like. The additional introduction of the negation in the case of 'non-self-descriptive' does in no way improve on the meaninglessness of these formulations. Any variation in the wording, such as Hofstadter's '"yields falsehood when preceded by its quotation" "yields falsehood when preceded by its quotation"' does not bring any more meaning into the self generated verbal confusion. The only way out of these nonsense-loops is to stick to our common-sense rule to take reference only to subjects that have been exhibited or defined before, or that, at least, can be defined separately. Still, one could claim that all difficulties are avoided and a perfect, self sufficiently meaningful and true sentence were obtained when, instead of using demonstrative pronouns or sentence names in selfreferent intent, an identifying attribute is introduced to form the following 'last sentence of Chapter IV': 'The last sentence of Chapter IV does not refer to anything external to itself'. Footnote No 1 : Please do not consider this footnote to be part of Chapter IV. This would seriously impact the meaning and truth of 'the last sentence of Chapter IV', since then it would no longer refer to itself! But: is that really a good, self sufficiently meaningful sentence that depends in its truth so sensitively on changes in its surroundings? And does it, or does it not, refer to something external to itself? Is it not just another rather absurd example of a nonsensical word sequence, engaged in useless self-satisfaction, that has been invented for no better purpose than to irritate a confused and helpless audience? Footnote No 2: The nonsense of the self-referentially misused demonstrative pronoun is further enhanced when used in 'stand-alone' mode, to arrive at such S.R. sentences as: 'This is a sentence', 'This is a word', 'This is a letter', 'This is this', 'This is nonsense' etc. etc. The inclined reader may meditate on the philosophical profoundness of these 'sentences', or just forget them. It was the intent of this rather lengthy discussion to demonstrate that we certainly are able to produce nonsensical word sequences, but that natural language will not lose any of its capabilities and its value for a meaningful exchange of information when these selfreferent constructs are banned from it once and for all. In the following chapters, it will be shown that in mathematics selfreference serves no better purpose whatsoever.
V The Impredicative Definition and its application in Analysis:
the Unit element, the Dedekind cut, the Set that contains itself
Impredicative definitions are defined as such in which 'the definiens comprises totalities, of which the definiendum is a part'. Under this definition of impredicativity quite harmless definitions may get mixed up with pathological ones. The unit element A certainly harmless case is the definition of the unit element in a group as 'the element x for which, with any element y from the group, 'x ∙ y = y' is a true statement'. This is regarded as an impredicative definition since the unit element of the group is one of all the elements y in this group. At a closer look, however, this definition turns out not to be self-referential at all, since, for the definition of the unit element x, it is sufficient that for any element y (with: y # x) is valid: x ∙ y = y. An additional claim that also x ∙ x = x is not suited to define the unit element since it is fulfilled by x = 0 as well. This is about the same situation as when I write 'in this paper', where, without any self-reference, other sentences are addressed than the one I just formulate. The least upper bound An exemplary specimen of really self-referential impredicative definition that is thought to be needed in the foundation of analysis is the definition of 'the least upper bound B of a given bounded set S of real numbers', as was discussed by Weyl. In this context, the real numbers are treated as Dedekind cuts in the realm of the rational numbers and B is defined as the union of all the Dedekind cuts that belong to S. This union B is also a Dedekind cut and therefore a real number and it evidently has been defined on the basis of the set of all real numbers, of which it is an element itself. No doubt, this is again an Impredicative definition. And yet, it is quite decisively different from the definition of the unit element. Whereas there any single element y whatever was sufficient for the definition of x, any element z whatever out of S is quite useless for the definition of B. Either S contains a determinable largest element, then B is defined through this element (and this element alone!), or S does not contain a largest element, but then we can determine to each element z´ in S another element z´´ > z´ , that, taken alone, is a better approximation to B than the entire union of all the infinitely many elements z in S which are smaller than z´. So, they all together are useless for the definition of B. In general, however, in the process of the above definition we will even not be able to decide whether a given real number belongs to S or not, as long as B is not determined. So, the above definition tries in total self-reference to define B through B, and thereby it turns out to be of no use whatsoever. Here we are left with the question whether there is a need at all for such an existence proof for the least upper bound of a given bounded set of real numbers, or whether the entire formulation of the problem is based on a fundamental misunderstanding. To clarify this, we first have to reach an understanding on what a 'given bounded set S of real numbers' really is. By just formulating the sentence 'a set S be given' such a set certainly is still far from 'being given'. It cannot make any sense whatever to consider a set S as 'given' as long as it has not properly been defined! ‘Define a bounded set of real numbers’ can be done in two essentially different ways: 1.) through direct definition of it’s upper bound, e.g.: S = all z < e or T = all z <_ 1 etc. evidently S has no least upper bound, the least upper bound of T is 1. 2.) through some functional relation like:
S = all Z(r) with Z(r) = 1 – 1/e(exp)r with r = 1, 2, 3, ….. or
T = all Z(r) with Z(r) = π - 1√r with r = 1, 2, 3, ….
in none of these cases arises any doubt whether these sets S have some least upper bound B or not. In each case, the definition of S also contains the definition of B, and B may be an irrational, a rational or even a natural number, just as it has been defined, and in no case do we encounter a need to introduce a self-referential existence proof for B, or, to cite Weyl, 'real numbers of second level'. But it is not only in the discussion of this upper bound that we find such superfluous and useless self-referential definitions: Already the much more fundamental definition of the real number as a 'Dedekind cut' is by no means better.
The Dedekind Cut In Weyl's much cited book (p. 22) we read: 'under a real number a we understand the set of all rational numbers r which are smaller than a '!
No doubt, this is a totally self-referential formulation, and certainly, nobody has ever succeeded in defining a real number in this way. Wherever a real number is defined, this is done in the form of some functional relation on the basis of the natural or the rational numbers, just as the rationals are defined by the functional relation r = p/q. To just name a few of the most well-known: a = √2 or a x a = 2 or
e = 1+1/1!+1/2!+1/3!+ …. or π/4 = 1-1/3+1/5-1/7…..
Based on such definitions, each of these real numbers may be determined to any desired precision and exhibited as a broken- up decimal number. Thus, and only thus, can real numbers be defined, and as their definitions can lexicographically be ordered, they are countably infinite, just as the rationals. On top of all that: the definition of the reals as Dedekind Cuts on the rationals assures the smallest possible difference between two adjacent reals a’ and a’’ to be just one rational that belongs to a’ but not to a’’, so there cannot be more reals than there are rationals. Finally: in case the 'real number a' in Weyl’s definition should by chance be itself a rational number (the rationals are a subset of the reals!) this definition turns to the absurdity that the rational number a is no more itself, but instead identical to 'all rationals that are smaller than itself' ! On the basis of all this, no good argument can be found anywhere to convince us that impredicative definitions or any other Selfreference should or could be needed in the foundation of analysis. The Set that contains itself as Element The next example of impredicative definition to be discussed here, is taken from set theory. Set theorists like to start from the assumption that, to any property whatsoever that can somehow be described in some language or by a mathematical formula, the 'existence in reality' is established for the set of all 'things' that do have this property. In this context we need not discuss the problem what this 'existence in reality' could really mean, we may here content ourselves with the assumption that we can form, in our imagination, a mental conception of such a set. This then is intuitively quite a sound assumption as long as we assure that the definitions of the respective properties are perfectly unambiguous, and as long as we agree to understand by 'all things' all those 'things' of which we are able to have some mental conception before we start to check whether a given thing has one of these properties, or not. So we can easily conceive of the 'set of all those things that are fingers of our left hand' or 'the set of all those sentences in this treatise that contain more than ten words' or 'the set of all those natural numbers that are multiples of 17 and smaller than 10000' etc. etc. The affair becomes more dubious with the 'set of all primes between 10exp10exp10 and 10exp10exp11 , since nobody in our universe with it’s much less than 10¹ºº elementary particles will ever be able to determine such primes in the sense that he could write one of them down in, say, our decimal notation. Yet, most mathematicians even claim that they can conceive of the 'set of all primes' or of 'all natural numbers'. Honestly, I have no idea of how mathematicians manage to do that, and not one of them has ever given a reasonable explanation on what he does when he believes to imagine in his finite small brain such an infinite sequence in its totality. The usual argument 'but we can imagine to count up to any given natural number N, however large that N may be' certainly cannot serve the purpose, since the length of the sequence of the natural numbers up to any large N always remains Zero relative to the length of the sequence of all natural numbers. We all were taught that N/∞ = 0, no matter how large that number N may be. In spite of such difficulties to imagine infinite sets as 'given', a great variety of mathematical arguments has been based on the assumption that some specific infinite set be given (through the definition of the property common to all its elements). Then, by taking reference to 'all' the elements of this set, a further element is defined in such a way as to share the defining property with those elements. Whenever then it is claimed that this element be one of all of the elements on the basis of which it has been defined, this evidently is a case of impredicative definition, and invariably this procedure leads into confusion. The most prominent example of such reasoning is when set-theorists define 'the set of all sets', which, being itself a set, is then claimed, in neglect of the above-stated requirement for 'prior existence' to contain itself as element. The unavoidable consequence of this assumption is that this element of the set of all sets also has to contain itself as an element, which contains itself as element, which... etc., etc. We easily see that this unpronounceable infinite nesting results from the attempt to identify two contradictory concepts with each other, two concepts that, by definition, cannot be identical, i.e. a 'totality' and one of its 'elements'. It is in this category that we find one of the most famous 'mathematicians paradoxa', the one invented by Russell in 1902, who started by defining 'the set of all those sets that do not contain themselves as element' and of which he then claims that it would have to contain itself as element if it did not contain itself as element, and vice versa. A few more such 'definitions' may be listed here: 'The set of all mental concepts' 'The set of all inconceivable and unimaginable things' or, the one I like most of all: 'The set of all useless selfreferent mathematico-philosophical concepts'. I am rather inclined to say that the only paradox in context with such linguistic constructs is that we still find in modern textbooks on the foundations of mathematics such statements as: These paradoxes result from methods of reasoning and ways of thinking that do not appear to be intuitively unjustifiable. To come to the conclusion of this chapter: It has been shown that the concept of 'impredicative definition' leads to a confusing mix-up of selfreferent and non-selfreferent definitions. The selfreferent ones may be as useless as they are harmless when they are tautological, or when they correlate two non-contradictory concepts to each other, as are real numbers and Dedekind cuts. They lead into confusion and contradiction, however, as soon as, in violation of all good common sense, two contradictory entities are identified with each other, as it is done in the definition of the 'set of all sets' and any other set that is to 'contain itself as element!’
VI Cantor's Diagonal Method Since its introduction by Cantor in 1874 the Diagonal Method has found wide application for a variety of proofs all of which contain a certain amount of circularity in the sequence of arguments, and most of which were found to lead to some kind of paradox or antinomy. Therefore, this method and its various applications have to be discussed in all detail. The gist of the discussion will be to demonstrate that the underlying assumptions of this method lead to contradiction and should therefore be dismissed from mathematics. ……………………………….The Enumerable Infinity The definition of 'enumerable infinity' reads: The totality of all natural numbers is said to be an 'enumerably' or 'countably' infinite set since, by counting, we can reach any given natural number n, i.e. any element of this infinite set. The counting procedure determines the sequence 1, 2, 3, 4, ..., such that every element in this set, every natural number, has its predetermined place in that sequence. Any other infinite set, for the members of which a 1-1 mapping to the natural numbers exists, is equally said to be enumerably infinite and, by consequence, to be of the same infinite size as the set of the natural numbers. The most simple of such sets are 'all even numbers', 'all multiples of a given natural number n', 'all square numbers m = nexp2', 'all m = 2n, or 'all m = nexpn, etc, etc. By this definition of „enumerability“, it can also be shown that the set of all rationals x = p/q (with p < q) in the interval 0 < x < 1 is enumerably infinite, the arrangement in the sequence being such that p/q comes before r/s if (p+q)<(r+s), and in the case of (p+q)=(r+s), if p < r. When this sequence is 'extended to infinity', it will clearly comprise 'all' the rationals in the interval 0 < x < 1, and each one has its clearly defined place in the sequence, so the 1-1 mapping to the sequence of the natural numbers is assured. - …………….The Non-enumerable Infinity The first important application of Cantor's diagonal method was the surprising claim that the set of all real numbers r (i.e. “infinite decimal sequences”) in the interval 0 < r < 1 be not enumerable, meaning that there should be more, in fact infinitely more, irrationals than the infinitely many rationals in that interval. The proof runs as follows, and to avoid any mistake, I just copy the wording as given in S.C. Kleene, “Introduction to Metamathematics”: Suppose Xo' X1' X2' X3' ... to be an infinite list or enumeration of some but not necessarily all of the real numbers belonging to the interval. Write down one below the other their respective non-terminating decimal fractions. .Xoo Xo1 Xo2 Xo3 …. Select the diagonal fraction .X1o X11 X12 X13 ….. Xoo X11 X22 X33 …..and .X2o X21 X22 X23 …. change each of the successive digits .X3o X31 X32 X33 …. Xnn to a different digit X`nn, but …. .… …. …. avoid producing a terminating fraction. Say, let X`nn = 5 if Xnn is not = 5, and X`nn = 6 if Xnn = 5 The resulting fraction .X`oo X`11 X`22 X`33 ... represents a real number x which belongs to the interval but not to the enumeration. For the fraction differs from the first of the given fractions in the first (tenths) place, from the second in the second (hundredths) place, from the third in the third (thousandths) place, and so on. Hence the given enumeration is not an enumeration of all the real numbers in the interval. An enumeration of all the real numbers in the interval is non-existent. It is clear that an essential difference has been revealed between the set of the rational numbers on the one hand and the set of the real numbers on the other. The reals are not enumerable. So far S.C.Kleene. Let us shortly summarize the train of thought in this proof: First, an infinite list of infinite decimal fractions is assumed to be given, then, by taking reference to each one of the infinitely many decimal fractions, a new element is defined that, no doubt, is again an infinite decimal fraction, but different from all those in the list. This is assumed to prove that there exist more infinite decimal fractions, i.e. more real numbers in the interval 0 < x < 1 than can be enumerated in any infinite list. Therefrom results as the most outstanding claim that there be substantially more real numbers than rational numbers in that interval. This is rather hard to imagine since, as we all have learned, the rationals already lie so densely that between any two of them, they may be as close to each other as they ever want, there are infinitely many more others in between. Still another argument should make us skeptical against Cantor's claim: With Dedekind's definition of a real number r as 'the set of all rationals that are smaller than r', the smallest possible difference between two real numbers r1 and r2 consists of at least one rational number that belongs to r2 but not to r1. So, we certainly cannot differentiate between more reals than there are rationals in the 0 to 1 interval. We will come back to that after several other modes of Diagonal Argument have been presented. …………………The not effectively calculable functions A rather contrary use is made of the diagonal method to prove that there exist well defined, yet 'not effectively calculable' functions. We follow the argumentation as given by M. Davis (Computability and Insolvability p. XVII): We consider functions of a single variable f(x), defined on the positive integers (that is, for x = 1, 2, 3, etc.) and whose values are positive integers. Examples of such functions are xexp2, 2expx, `the xth digit in the decimal expansion of π' etc. We shall say that such a function f(x) is effectively calculable if there exists a definite algorithm that enables us to compute the functional value corresponding to any given value of x. Let us assure that such an algorithm can be expressed as a set of instructions in the English language. Furthermore, let us imagine all such sets of instructions ordered according to the number of letters they contain: first, those (if any) that consist of a single letter: then those that employ two letters: etc. Where there is more than one set of instructions consisting of the same number of letters, they are to be ordered among themselves, alphabetically, like the entries in a dictionary. Thus, there will be a first set of instructions, a second set of instructions, a third, etc. With each positive integer i, there is associated the ith set of instructions in this list, Ei, which tells us how to compute the values of some function. The function associated in this way with Ei we will call fi(x). Now let
g(x)=fx(x)+1. (2)
Then, g(x) is a perfectly good function. Its value for a given integer x is obtained by finding the xth set of instructions Ex, then applying it to the number x as argument, and finally increasing this result by 1. We have: I.) For no value of i is it the case that g(x) = fi(x). PROOF. Suppose that g(x) = fio(x) = for some integer io Then, by (2), fio(x) = f x(x) + 1 for all values of x. In particular, this equation would have to hold for x = io yielding fio(io) = fio(io) + 1. But this is a contradiction. Now, from the manner of choice of the Ei, the functions fi(x) were to include all effectively calculable functions. This yields: II.) g(x) is 'not effectively calculable'. So much from M. Davis. We will come back to that further down.
………………………… Richard's Paradox
Richard, in his 1905 paper, chose yet another mode of Diagonal argument to end up with a contradiction, a 'paradox'. The Ei are now assumed to constitute the list of all English word sequences that define a number, again in their lexicographical order. On the basis of the decimal expansions of these numbers we can then define an anti-diagonal sequence. This sequence represents a real number, and its definition is an English word sequence of finite length. So this definition must be one of the Ei, with a predetermined place in that list, due to the lexicographical ordering. Yet, due to its definition, this anti-diagonal number is different from all numbers in our list. So we have a contradiction.
………………..The three modes of Diagonal Argument
We summarize shortly the three different modes of 'diagonal', or better 'anti-diagonal argumentation' that we encountered:
For the proof of the non-enumerability of the real numbers the anti-diagonal was argued to be an additional sequence of the same species as the horizontal sequences in the infinite matrix.
For the not-effectively calculable function g(x), the anti-diagonal was concluded to be a new function of an essentially different type than the functions fi(x),
and, to arrive at the 'paradox', the anti-diagonal sequence was identified with one of the horizontal
sequences of the xij-matrix, thus producing the contradictory self-reference.
The origin of these variations is rather obvious. In the first case, the anti-diagonal non-terminating sequence of integers is as indisputably the representation of a real number as are all the horizontal sequences in the xij-matrix. On the other hand, the definition of that matrix was kept rather vague, it was just 'assumed to be infinite', and no word was lost on the question of what happened to an infinite xij-matrix when we try to add another line to it. Any such discussion was suppressed by the claim: 'evidently there are more than enumerably many real numbers'.
In the second case it was ascertained unambiguously that our list contained all the functions fi(x), whereas their property to be 'effectively calculable' was left vague enough so that we could content ourselves with the answer that the 'anti-diagonal function' g(x) be, although well defined, not effectively calculable, whatever that might mean.
In the third case, finally, it was again ascertained that our list contained all numbers that can be defined by finitely many English words, and the anti-diagonal equally turned out to be a number that also was defined by finitely many English words. So we had no other escape but to admit the 'contradiction'.
……………………Counter-Arguments Critical analysis will show that in none of the afore-mentioned three modes of Diagonal Argument do we have inevitably to follow the chosen way of reasoning. With the real numbers we have the choice between two counter- arguments. The most simple is to follow Cantor’s reasoning up to the conclusion: 'An enumeration of all the real numbers in the interval is nonexistent'. Instead of claiming that there be more real numbers than can be accommodated in any completed infinite list, however, we conclude: Certainly, there can be no complete infinite list of all real numbers, since no infinite list can ever be completed! This conception is a self-contradiction from the beginning! This leads to the second counter-argument where we question: What is it to mean when Cantor-Davis start by saying: 'Suppose that xo, x1, x2, ... is an infinite list of real numbers' and 'write down their respective non-terminating decimal fractions'? Nobody has ever succeeded in writing down a single non-terminating decimal fraction. All that can be written down are finite initial pieces of non- terminating decimal fractions. Real numbers, and here we mean essentially the irrationals, cannot be 'given' or defined by anything else but by algorithms or descriptions that yield resp. describe non-terminating decimal fractions. These algorithms and descriptions have to be formulated in some language, say in English, enriched by a series of mathematical symbols. This yields the chance, at least to start, to generate the lexicographically ordered infinite enumeration of 'all' finite definitions of real numbers, just as Richard assumed that the list of 'all' finite number definitions in general could be generated. The word 'all' is put in quotation marks here to indicate that it is not implied that this process could ever be terminated. To assure no to miss a single such definition, we follow J. Richard (1905) and start off with a lexicographically ordered enumeration of 'all' possible permutations (with repetitions) of our enlarged English alphabet, to eliminate, after careful examination, one after the other, all those permutations that do not define a real number. In the course of this examination we will rather early, say after the acceptance of k definitions of real numbers, run into the wording: 'Take the diagonal sequence from the xij-matrix that is defined by the lexicographically ordered sequence of all definitions of real numbers', and a little further down we will encounter something like: 'Take an anti-diagonal sequence to the xij-matrix that ...'. It is evident that the first of these wordings defines at best k decimals, and not one more! The (k+1)th decimal remains undefined with its selfreferent definition: the (k+1)th decimal is equal to the (k+1)th decimal of the (k+1)th sequence. This is just as unfit to define anything as the 'red is red' that was discussed earlier. And certainly all further decimals of this 'diagonal' are equally undefined since the xij-matrix from which they should be taken is not in existence yet. The anti-diagonal definition, showing up in our list after the acceptance of r correct real number definitions, certainly not better than the diagonal one, but not much worse either, is equally unfit to define a real number. The add-on of a self-contradiction in the definition of the (r+1)th decimal does not make much of a change. No doubt, we have to eliminate the diagonal, as well as the anti- diagonal definition once and for all from the infinite enumeration of the real number definitions. Based on this argumentation, Richard himself concluded back in 1905: 'therefore, there is no contradiction'. There is not much to add after 78 years. Cantor's Diagonal Argument and his non-enumerable infinity of the set of the real numbers cannot be recovered without the schizophrenic claim that we should and could first complete the infinite enumeration of all real number definitions and then reanimate the anti-diagonal definition that we had rejected before. Yet we have to keep it well apart from our infinite list, although it has its predetermined place there in the lexicographical order! So, through this resurrection we have maneuvered ourselves into the absurd situation that we try to define a real number by a sentence that does not define a real number as long as we consider it to be a definition of a real number. This absurdity, however, is most simply eliminated when we admit that the outstanding property of any infinite enumeration is that it can never be completed, not even imagined to be completed. So, the anti-diagonal definition will never become a valid definition of a real number. Confronted with these arguments, some mathematicians will tell you: 'Well, accepted that there cannot be more than enumerably many definitions of real numbers. The great majority of the real numbers, the non-enumerable ones, then are the “indefinable” real numbers'. It certainly cannot be questioned that we cannot enumerate what we cannot define. We cannot even discern two indefinable numbers from each other, just as we cannot attribute any meaning to the concept of the 'existence' of one sole indefinable number! But Cantor's whole paradise of transfinite numbers is based on the belief in the non-enumerable quantity of these numbers! The situation with the not-effectively calculable functions is quite similar. Since we will never manage to complete the list of all functions fi(x), the definition of g(x) will never become a well defined function for all values of x, but it certainly will be effectively calculable for every value of i respectively x, as far as the fi(x) have been defined before! Another, equally valid, argument against the not-effectively calculable function g(x) runs as follows: The infinite list of functions of one variable fi(x) yields a two-dimensional matrix of function values. Each such two-dimensional matrix represents basically a function of two variables g(x,y). The diagonal of this matrix, just as any anti-diagonal, is then correctly defined not as a function of one variable but as function of two variables g(x,y), with x = y = 1, 2, 3 and there will never surface the question whether this g(x,y) could be one of the f(x) or not, and there will be no basis for the claim that g(x,y) could be 'not-effectively calculable'.
Apart from this general criticism of the diagonal method, Davis's argumentation for the not effectively calculable function g(x) can be refuted on a much simpler basis: From the choice of the Ei, the set of functions fi(x) is assumed to comprise all effectively calculable functions the computing procedure for which is expressible in the English language. Then these functions are denominated by 'names'. To avoid nonsense and contradictions, these names must be symbols or words that do not belong to the English vocabulary as used in the formulation of the computing procedures Ei. Davis chose the symbols fi(x) for that purpose, which certainly are not part of the English vocabulary. When he then defines g(x) = fx(x) + 1 and calls g(x) a perfectly good function, he may be quite right. However, this g(x) certainly is not formulated in the English language! Neither the symbols fi, nor fx with its variable index belong to it. Therefore, it is unjustified to expect g(x) to be equal to one of the fi’s, or, otherwise, to conclude that it be 'not effectively calculable', since it is not equal to any one fi. g(x), not being definable with the English vocabulary that was used for the Ei is very well and effectively calculable as soon and as far as the symbols fi(x) are explained in English! So, there is no contradiction anywhere and nothing undecidable either. The only way to formulate the computing procedure for g(x) in the same language as used for the computing procedures Ei is the infinite sentence: If x equals 1 then follow the procedure ….. (these dots stand for the full length English formulation of E1) and if x equals 2 then follow the procedure….. (these dots stand for the full length formulation of E2) and if etc. etc. Yet this sentence can never be completed, so g(x) does not have a finite definition in the English language. It has to be emphasized here that the first two of our three versions of the Diagonal Argument are based on the fundamental assumption that an infinite list be first completed before the anti-diagonal is derived from it. Most surprisingly, most mathematicians accept this to be an 'intuitively justifiable' assumption although, as of today, nobody has ever succeeded in advancing another definition of an 'infinite sequence' that were not synonymous with 'a sequence that can NOT be finished'. This is precisely the same situation as with the conception of 'the set of all natural numbers', mathematicians claiming, without offering any proof or demonstration thereof, to dispose of an imaginative capability that appears intuitively absurd to most non-mathematicians. Certainly, there were also a few mathematicians who repudiated Cantor's mode of operating in and beyond the infinite (Kronecker, Brower), yet the overwhelming majority decided with Hilbert that 'no one shall be able to drive us from the paradise that Cantor created for us'. It must have been this enthusiasm for Cantor's paradise of ever higher infinites that forbade mathematicians to realize how easily a contradiction can be derived from Cantor's assumption that an infinite matrix could be completed. This will be shown in the next section.
………………… A list of all real numbers between 0 and 1
The most simplistic reasoning yields a 'proof' that the set of all real numbers x in the interval 0 < x < 1 is of exactly the same infinite size as the set of the natural numbers, as long as this set is assumed, as Cantor does, that it could be 'complete' and 'given' : For this proof we generate, starting with 0, the infinite list of the natural numbers, one below the other, for simplicity reasons in binary notation, by the following 'program':
Step 1: generate 0
1
Step n: put a copy of stage n-1 below stage n-1, put a vertical row of 0's to the left of stage n-1 and a row of 1's to the left of its copy. The n-th stage of this expanding matrix is a list of all natural numbers from zero to 2n-1 in binary notation, respectively a list of all possible 0-1-sequences of length n. The first three stages in this expansion are shown here: 0 00 000 Evidently, the application of Cantor’s Diagonal Method to any stage of this list 1 01 001 can never yield an 0 – 1 sequence that were not contained already in that list.
10 010
11 011
100
101
110
111
Now, if we want our list to comprise all natural numbers (in binary notation), we certainly are not allowed to interrupt its expansion at any finite step N, i.e. at any finite length of the horizontal 0-1-sequences. The complete infinite list of all natural numbers, the existence of which Cantor has succeeded to convince so many of, thus becomes inevitably an infinite xij-matrix which, in contrast to Cantor's xij-matrix, grows much faster in the vertical than in the horizontal direction. And yet, it grows in both directions to the same enumerable infinity. We all were taught the 1-1 mapping argument to make us believe that the set of all numbers m with m = 2expn is of equal infinite size (of cardinality No in the language of Cantor) as the set of all natural numbers n. But, when counted from right to left, the n-th row in our list of the natural numbers is precisely meant to correlate to the value 2expn. So, the set of all those rows is certainly of equal cardinality as the set of all numbers m = 2expn with n = 1, 2, 3, …. On the other hand, after the n-th program step our matrix consists of n rows and 2expn lines. So, it is equally justified to say that in our infinite xij-matrix, the set of all rows is of cardinality No, whereas the set of all lines is of cardinality 2expNo. Inevitably, cardinality 2expNo must be equal to cardinality No ! Cantor and all set-theorists, however, claim that 2expNo » No ! The assumedly 'complete', infinite xij-matrix which we obtained in the effort to generate a complete list of all natural numbers quite obviously is a list of all possible infinite 0-1-sequences. We are free to interpret any infinite 0-1-sequence as a real number in the interval {0,1} . So, unavoidably, our xij-matrix can be understood to be a list of all real numbers in that interval. Yet, this identity of the list of all natural numbers with the list of all real numbers in the {0,1}-interval is in contrast to Cantor's claim of the nonenumerability of the set of all real numbers in {o,1}. The origin of this contradiction clearly resides in the use of the concept 'complete infinite list'. In general, mathematicians do not tolerate concepts or assumptions which lead to contradiction. So let us stick to this principle, which has proved so successful everywhere else! We better admit that the list of 0-1-sequences can never become anything else but a finite list of 0-1-sequences of finite length N, no matter how large that N may be, respectively a list of just the first 2expN natural numbers, which is nothing compared to a list of 'all natural numbers'. And we have equally to admit that we are totally unable to develop in our mind something like a mental concept of a complete infinite list of real numbers in the form of complete infinite 0-1-sequences, from which we could gain another real number by Cantor's Diagonal Method. This honest confession is evidently the only possible way to avoid the above contradiction..
Cantor's original version of Diagonal Argument This discussion of Cantor's Diagonal Argument should not be terminated without mentioning his original version in his 1873 letter to Dedekind. I try to translate from Meschkowski: Assume that all points P in the interval 0 - 1 could somehow be enumerated. We then can select an interval [A1, B1] of length 1/3 that lies within the 0 - 1 interval and that does not contain point P1. The second point P2 in the enumeration may then be either outside of or within [A1, B1]. In either case, however, we can choose an interval [A2, B2] that has 1/3 the length of [A1, B1], that lies totally within [A1, B1], and that does not contain the point P2, and so on. We thus obtain a sequence of intervals [An , Bn ] with the following properties: 1.) [An+1, Bn+1] is contained within [An, Bn] 2.) the length of [A , B ] is 1/3expn 3.) the points P1, P2, P3, ……Pn are not contained in [An , Bn ] It follows from 1.) and 2.) that our sequence of intervals has the character of an 'Intervallschachtelung'. Therefore, there exists one point P which is contained in all intervals of the sequence. This point cannot be equal to any one of the points Pn, since P = Pm would lead to the contradiction: a) P lies within all intervals of the sequence, so it is also within [Am , Bm ] b) from 3.) follows that P = Pm is not within [Am, Bm ] From this contradiction Cantor concludes that the assumption must have been wrong that the points of the 0 - 1 -interval could be enumerated. This argument sounds quite reasonable, yet it ignores another important fact that we are taught in set theory: The mapping x → y = A1 + ⅓ x establishes a one-one mapping between the set of all real numbers in the 0 - 1 -interval to the set of the real numbers in [A1, B1]. A similar one-one mapping exists between all the points of any two successive intervals [An , Bn ] and [An+1,Bn+1] . How then can we believe that by repeating this mapping process over and over again we could ever manage to define one singular point? Let us assume our initial enumeration of points Pn to be the enumeration of the rational points between 0 and 1. The repeated mapping process then teaches us that each of the intervals [An , Bn ] contains just as many, and that is enumerably infinitely many, rational numbers as the 0 - 1 -interval, and each of the rational numbers in [An , Bn ] is also contained in the initial enumeration of the Pn . So, how can we, by this process, ever arrive at the definition of one singular number P that is not contained among the Pn ? We have seen that Cantor's Diagonal Argument is based on the result of the (assumed) execution of infinitely many steps of some mathematical procedure as a valid mathematical concept. Let us conclude this sad story with the most simple proof that this concept leads to contradiction: Assume the set N of all natural numbers, as well as an empty bag B as given. We transfer in step 1 of our infinite procedure first the numbers 1 and 2 to the bag B and then we return the number 1 to set N. The n-th step of this procedure is: transfer numbers 2n-1 and 2n to hag B and return number n to set N. The question is: How many numbers are in bag B after the (assumed) execution of 'infinitely many' steps. We answer with Cantor: There can be no number in the bag since any number ni that we might name has been removed from the bag in the ni-th step. And yet we know that the content of the bag has been augmented by one number with each of the infinitely many steps of our procedure. This simple contradiction should suffice to every sincere mathematician never again to fall back on the concept 'after infinitely many steps’.
VII The Berry Paradox
In the endeavour in Chapter VI to eliminate all those letter permutations from Richard's list that do not define a number we will encounter, apart from the diagonal and anti-diagonal definitions, many more letter sequences which superficially share the appearance of number-definitions, which, however, will have to be discarded for various quite evident reasons. A prominent group of unfit definitions are all those that take reference to some as yet unknown number definitions, i.e. to all those definitions that come later in the lexicographical order. A subgroup of these unfit definitions are all those that take reference to themselves. This selfreference may be accomplished in any one of the three modes that were discussed in Chapter IV, and it is quite immaterial whether these constructs are of the self-ascertaining or the self-contradicting type. A typical selection of such unfit 'number-definitions' is: No.m The number defined by this definition No.n Twice the number defined by definition No.n No.p The number defined by the third definition on page 25 of the treatise 'Selfreference, Sense or Nonsense' No.q One more than the number defined by the next definition No.r The sum of all numbers defined by definitions No.1 to No.r No.s Twice the largest number definable by 61 letters respectively numerals No.t The least integer not nameable in fewer than nineteen syllables It is quite obvious that none of these 'definitions' is fit to define a number. They all have to be eliminated from the list (or set) of number-definitions due to one and the same easily discernible deficiency: to take reference to themselves. Even the reference to 'the next definition' is unacceptable since this 'next definition' is as yet undefined, and might read: one more than the preceding definition. In the latter two, No.s and No.t, the selfreference is somewhat better camouflaged than in the former ones. No.s consists of 61 letters and numerals respectively, so it refers, among other definitions, also to itself. So does No.t, which consists of 18 syllables. This last formulation, which here appears as just one nonsense formula among many similarly constructed ones, has been introduced into the mathematical literature by Bertrand Russell in his version of 'Berry's Paradox', which runs like this: The expression: 'the least integer not nameable in fewer than nineteen syllables' must denote a definite integer; in fact, it denotes 111,777. But 'the least integer not nameable in fewer than nineteen syllables' is itself a name consisting of eighteen syllables; hence the least integer not nameable in fewer than nineteen syllables can be named in eighteen syllables, which is a contradiction! The fact that No.t is just one out of an infinite multitude of selfreferent constructs that have to be eliminated from the list of number-definitions, is thoroughly ignored in this discussion. So, instead of admitting that all these 'definitions' are man-made nonsense, modern mathematicians, like R. Rucker, derive from them such conclusions as 'paradoxes are compact energy sources' or 'The very existence of a paradox like this can be used to derive interesting facts about the relationship between the mind and the universe', or 'the paradoxes indicate that the rational world is incomplete'. Evidently, it provides more self-comfort to assume the world to be incomplete than to suspect one's own training in rational thinking of such a deficiency.
………………………VIII The Barber's Paradox
In the so-called 'Barber's paradox', a village barber is brought into trouble by the order to shave all those male villagers and only those who do not shave themselves. Evidently, with this order, the poor barber cannot decide whether he should shave himself or not. In both cases he violates the order. As realists with some common sense, we easily locate the problem in this story: A shaving barber is a physical phenomenon in space and time. It is a logician's arbitrariness to describe this phenomenon in a purely logical phrase, under elimination of space and time. With a physicist's order, our barber is better off: He is to shave in his shop between 9 a.m. and 11 a.m. all those and only those who do not shave themselves earlier in the morning at home.
This suppression of the parameter time in the description of physical phenomena is at the core of many erroneous claims that selfreference be a widespread phenomenon in our world. One prominent such claim is that every control system with its feedback loops be subject to Goedel’s undecidability problem, due to its built-in selfreference. Every engineer, however, knows about the importance of the time lag which is inherent to any feedback loop: reference is always made not 'to itself' but to an earlier state of the system. And we all are familiar with the most widespread technical 'if on then off and if off then on'- system: the electric door-bell. A second example of the same type of misunderstanding appears in many discussions on what happens when we reflect on our own mind. Again, there is no danger to get caught in a selfreferent loop: when we reflect on our mind, we invariably reflect on earlier states of our mind. A minimum time lag of about one second seems to be a reasonable estimate.
IX ……………… The Formal System P and Recursive Definitions
In defending the application of selfreference in general, it is often claimed by mathematicians that the entire theory of Recursive Functions be based on selfreference. It will be shown here that this is not the case. For this discussion, the concept of 'Formal System' has first to be introduced. We choose here the System P of Principia Mathematica, as it was used by Goedel for the formulation of the proof of his Incompleteness Theorem, to ∙be discussed in the next chapter. Whereas we all did our arithmetic at school with the help of the ten numerals 0, 1, 2,...9 and a variety of function symbols (addition +, subtraction -, multiplication ∙ , division : , faculty! etc.), plus a sequence of variable-symbols (x,y,z...), the Formalists tried around the beginning of this century to reduce arithmetic, in a sense, to its 'atoms'. The intent was to find a minimum number of interpreted symbols, so that, together with a set of rules for the formation of well-formed formulae, all arithmetical propositions could be expressed as such formulae, and vice versa, that all well-formed formulae would yield, when read from left to right, with the given interpretations of the individual symbols, arithmetical propositions. It was further hoped that, with the proper choice of a few well-formed formulae as 'axioms', and the definition of some transformation or derivation rules, all formulae that are 'derivable form the axioms' would yield, when 'interpreted', true arithmetic propositions. It is the totality of all these symbols, axioms, rules of formation and derivation, plus all possible well-formed formulae that are summarized under the concept 'Formal System'. Such a Formal System is called 'consistent' when for no formula A, this formula as well as its negation can be derived from the axioms. The System is called 'complete' when the set of all derivable formulae, 1when read from left to right with proper interpretation of the symbols, yields the set of all true arithmetic propositions.
For our discussion, the following set of basic symbols will serve the purpose: ~ not, v or, A and, > implies, 3 it exists a, = is equal to, 0 = zero, f follower of, (x) for all x is, x, y, z, v... an unlimited number of variable-symbols. A simple example of a formula then is: (x) ~ (fx = 0) with the interpretation: 'for all x it is not (true) that the follower of x equals zero'. This vocabulary might at first sight appear rather scanty, most of all since it contains but one arithmetic function symbol, the follower f. This allows us just to form the sequence of the natural numbers in the form 1= f0, 2 = ff0, 3 = fff0 etc. It is only through the introduction of the recursive definitions of the higher arithmetic functions that our system obtains the necessary strength. In its essence, this is nothing different than the mode in which we learned as children first the addition as 'counting-on', i.e. as a repeated taking of the follower, multiplication as a repeated addition and “faculty” as repeated multiplication. With the more familiar symbols a, b, 0, 1, +, ∙ , !, these processes can be generalized and expressed through the following formulae: a + 0 = a and a + (b+1) = (a+b) + 1 for b = 0, 1, 2, 3,... a ∙ 0 = 0 and a ∙ (b+1) = a ∙ b + a for b = 0, 1, 2, 3,... 0! = 1 and (b+1)! = (b+1) ∙ b! for b = 0, 1, 2, 3,... Successive substitution of the rising sequence of the numbers 0, 1, 2, 3, ... for b gives us our 'childrens arithmetic': a+0 = a, a+1 = a+1, a+2 = a+1+1 a+3 = a+1+1+1 a∙0 = 0, a∙1 = 0+a, a∙2 = 0+a+a, a∙3 = 0+a+a+a etc. 0! = 1, 1! = 1x1 2! = 2 ∙ 1! 3! = 3 ∙ 2! ∙ 1 4! = 4 ∙ 3! = 4 ∙ 3 ∙ 2! ∙ 1 etc. It is only after execution of these successive steps and then forgetting about them, that we can claim that e.g. 4! = 24, i.e. the result of adding 24 numbers “1” one to another , with no need for the function symbols for Faculty, Product and Sum . All this leaves us however with the question of “what IS “y!”” in the same sense as 4! IS (claimed to be) 24, here, where we cannot execute any such successive substitutions? Evidently, it cannot be defined other then by “ y!” plus the above definitions for the symbols “!”, “∙“, and “+”.
In all this, no selfreference can be found anywhere: the first element of the respective sequences is clearly defined, and so is the operation of how to derive the second from the first, the third from the second etc. etc. It is but a plain misunderstanding if a selfreference is interpreted into these definitions by the claim that, e.g. in (b+1)! = (b+1) ∙ b!, the exclamation mark on the one side be defined through the exclamation mark on the other side of that equation. In fact it is one number with the name '(b+1)!' that is explained on the basis of two other numbers, the names of which are '(b+1)' and 'b!'. And that's it! In System P, everything looks much more confusing; the basic logical structure, however, remains the same. Instead of our familiar function symbols (+ , ∙ , !), we have now to use variable symbols as 'function variables'. As recursive definitions for addition, multiplication and faculty we then get the formulae: ………. v1 = x1(y,u) Λ x1(y,0)= y Λ (z)(x1(y,fz) = fx1(y,z)) ……… v2 = x2(y,u) Λ x2(y,0)=0 Λ (z)(x2(y,fz) = x1(x2(y,z),y)) ………. v3 = x3(u) Λ x3(0)=f0 Λ (z)(x3(fz) = x2(x3(z),fz)) After substitution of specific numbers for the free variables y and u, say 3=fff0 for y, and ffff0 for u, these formulae are then considered to be valid representations in System P of the numbers v1= 7 (=3+4), v2 = 12 (= 3x4) and v3 = 24 (= 4!), in the form of recursive definitions. Again, to obtain the result “v3 = 24” we have to take recourse to above definitions for v3, v2, v1 and run through the same long sequence of substitutions as with “4!”. And what we mean by “y!”, here “u!” could not be anything but the combination of these three definitions!
The essential conclusion for us is that in all these constructs no use of selfreference is made anywhere.
X Goedel's Incompleteness Theorem
During the first three decades of this century, all the experience with System P never led to contradictory results, so, the consistency of the system seemed to be fairly well warranted. On the other hand, a series of arithmetical problems was known, which to solve all efforts had as yet
been in vain, problems which could however be formulated in System P (e.g. whether there is a largest prime-pair, like 17-19). So, the completeness of System P appeared less certain, i.e. whether all formulae the interpretation of which is a true arithmetical proposition, could be derived from the axioms. Consequently, it was a basic concern for theoretical mathematicians whether consistency and completeness of System P could not somehow be proved.
In this situation, in 1931, Kurt Goedel published his now famous paper in which he proved the incompleteness of System P by exhibiting a formula (G) that cannot be derived from the axioms of System P and yet has a 'true' interpretation, i.e. “that it cannot be derived from the axioms”!.
The decisive importance attributed to this result until today may here be reflected by the citation of some comments, articles and books that all have Goedel's proof as subject:
- 'Goedel's paper was destined to blow Hilbert's hopes and program sky high' G. Whitrow, 1978
- 'Goedel's work demonstrated that the resources of the human intellect can never be fully formalized, its structure and power being far more complex and subtle than those of any computer...'
G. Whitrow, 1978
- 'The foundations of mathematics appear to be fundamentally problematical...' J. Little, 1980
- 'Mathematics has been shorn of its truth' M. Kline, 1980
- 'The Incompleteness Theorem of Goedel governs control systems as well' A. P. Sage, 1981
- 'Goedel's Theorem points to God: the name of final closure' St. Beer, 1980
- Mind, Machines and Goedel: J.R. Lucas 1958
- God, the Devil, and Goedel: P. Benacerraf, 1967
- Goedel, Escher, Bach: D.G. Hofstadter 1979
In the face of such tremendous attention being paid to Goedel's proof, perhaps even more by philosophers than by mathematicians, and considering the fact that the 'true' interpretation of Goedel's formula (G) is a selfreferent and self-fulfilling construct that says of itself: 'This formula cannot be derived from the axioms', it appears worthwhile to take a very close look at the construction of this formula. With all our prior experience with selfreferent constructs it would not be too surprising to find some defect therein, that would, at least, cast some doubt on the validity or stringency of this 'Proof of Incompleteness'.
For this discussion, we refer here to the booklet 'Goedel's Proof' by E. Nagel and J.R. Newman which gives a fairly comprehensible presentation of this subject even for the mathematically untrained reader. Those familiar with Goedel's Proof may jump from here to page 31.
To enable formulae of System P to refer to 'axioms' and to 'formulae' and finally to 'itself' (these are all strings of the elementary symbols of System P) Goedel introduced specific numbers as names of such strings of symbols, since numbers are the only subjects that can be referred to in arithmetic formulae. To this end, the numbers 1, 2, 3,... are attributed as names, as 'Goedel-numbers', to the individual symbols:
~ v > 3 = 0 f ... x y z...,
1 2 3 4 5 6 7…. 11 19 17..., all further primes being
reserved for the unlimited supply of variable-symbols. On this basis the Goedel-number of a formula is defined to be the product of the rising sequence of primes, beginning with 2, with the i-th prime raised to the power indicated by the Goedel- number of the i-th symbol in that formula. Thus, the Goedel-number of the formula “0 = 0” becomes 2exp6 x 3exp5 x 5exp6 = 243 000 000.
Goedel has shown that, due to this formation procedure, the Goedel-numbers of well-formed formulae share a common arithmetical property that can recursively be described in the symbols of P. On the other hand, we can establish a long list of arithmetical properties that cannot be shared by Goedel-numbers of well-formed formulae, properties that result from meaningless symbol- sequences like '...(f)...' or '. ..=' etc. etc. The demonstration that the Goedel-number of a certain formula shares one such property will then be proof that this formula cannot be derived from the axioms, since our derivation rules warrant that only well-formed formulae can be derived from the axioms. As the next step, the Goedel-number of a proof, which is a sequence of, say, n formulae, is defined to be the product of the first n primes, the i-th prime having the Goedel-number of the i-th formula as exponent. From this construction it is evident that there exists some arithmetical relation between the Goedel-number x of a proof and the Goedel-number z of the last formula of that proof.
An essential part of Goedel's paper is to demonstrate how this relation can be expressed in System P in the shape of a recursive definition, i.e. as a long string of nothing but the elementary symbols of P. With the abbreviation Dem(x,z) for this relation, the formula (x)~Dem(x,z) then has the interpretation: 'For all numbers x it is not that x has the proof-relation to the number z' or 'there is no proof for the formula with Goedel-number z'.
One might suppose that all we have to do to obtain the self- referent formula (G) that says of itself that it cannot be proved, were to substitute in (x)~Dem(x,z) the Goedel-number of this formula for the variable z. Yet, here we encounter a twofold problem: For one, it is evident from the above definitions that the standard representation fff...0 of the Goedel-number of a formula must be much longer than that formula, so it can never be contained in it. Secondly, we run into the chicken-and-egg problem:
A definition of the Goedel-number of this formula cannot be formulated before that formula is completely formulated, and vice versa. After all the problems we encountered with self-referent constructs in natural language, it is not too surprising to see such difficulties in arithmetic as well.
To overcome this obstacle, Goedel invented his ingenious, recursively defined, 'substitution function' sub(m,19,Z(n)), the interpretation of which is: the number which results from number “m” through substitution (a very complicated arithmetical operation) of the “19” by the Gödel number of the number “n”, or , assuming “m” to be the Gödel number of some symbol sequence SS (symbols of the Formal System) “the SS that results from the SS with GN “m” through substitution (normal substitution) of the variable “y” by the numeral “n”.
By combining the proof relation Dem with this substitution function Goedel introduces the formula
(1) (x)~Dem(x,sub(y,19,Z(y)))
the GN of which be n. By substitution of (the representation ff..o of) this n for the variable y in (1) he finally arrives at the formula
(G) (x)~Dem(x,sub(n,19,Z(n)))
with the interpretation 'no x is GN of a proof for the formula with the GN sub(n,19,Z(n)) '. Yet sub(n,19,Z(n)) is (claimed to be) GN of formula (G), since (G) was obtained from (1) through substitution of n for y. So, formula G (is claimed to say) says of itself that it cannot be proved.
To prove the incompleteness of System P, Goedel then concludes - outside of System P - that (G) is a correct arithmetical statement since what it says must be true (if P is consistent), since other-wise it would prove a falsity. So far, so good! The success of the substitution function in generating a selfreferent and true formula appears to be perfect.
However, at a closer look, it is easily seen that, just as we had to violate well-established rules to obtain selfreference in natural language, so had Gödel to violate well-established mathematical rules to obtain his selfreferent formula.
reveals
A first questionable aspect of Gödel’s reasoning shows up in the word-for-word definition of what the abbreviation sub(y,19,Z(y)) is standing for: let us spell out its definition in detail: It reads (in parallel to the interpretation of ‘sub (n, 19, Z(n)’) : 'sub(y,19,Z(y)) is the GN of that formula that is obtained from the formula with GN y by substitution of the free variable y, (the GN of which is 19) by some symbol sequence y, the GN of which being defined by Z(y)’. Unmistakably, the symbol 'y' is here used in one context for two quite different entities: once for the free variable in some formula F(y), and secondly as name for the GN of just that formula (or, more generally, for a variable that ranges over the set of Goedel-numbers of well-formed formulae F(y)!).
It is not the first time in this treatise on selfreferent constructs that we encounter this operation: a more or less well camouflaged identification of two, by definition different, entities with each other! And here it is a quite obvious violation of a well-established rule in mathematics for the handling of variables, at least so long as consistent results are expected. On page 1 of Chapter I of Principia Mathematica, which is as much as the Bible for the theory of Formal Systems, Whitehead and Russell formulate the requirement that a chosen variable 'preserves a recognizable identity throughout the same context'.
The presumably 'true' interpretation of formula (G) is based on the context with formula (1), and the interpretation of formula (1) is based on the assumed existence of some formula F(y), which is addressed in (1) by its GN y. So, we have one context from F(y) through (1) to (G), and unquestionably the identity of the variable y is broken in this context.
So, the correct interpretation of formula (G) reads rather like: 'The formula with GN sub(n,19, Z(n)) has been constructed via an inconsistent application of the symbol 'y', and, therefore, that formula cannot be derived from a consistent set of axioms'.
A second concern arises with the question of what is the above term Z(y) in the symbols of the System? In the long sequence of the some 40 definitions which Gödel introduced for the construction of his Improvable Formula, we find under numbers 16. - 17. the recursive definition of Z(n) : 16. 0 N x = x, and (n + 1) N x = R(3)*n N x n N x corresponds to the operation of “putting the sign “f” n times in front of x” 17. Z(n) = n N [ R (1)] , Z(n) is the Numeral (the Gödel number for the numeral) denoting the number n . We encounter here exactly the same situation as was discussed above with the recursive definition for n! respectively v3. Only a long sequence of similar substitutions leads from e.g. Z(4) = 4 N [ R (1)] to the result “Gödel number of ffff0” (this claim being due to the above attribution of “1” and ”3” as Gödel numbers for the symbols “0” and “f”) However: what is Z(y)? Whereas Gödel takes the pain to tell us expressis verbis that Z(n) IS the Gödel number of the numeral for n, he does not make any remark on what he wants Z(y) to BE! It certainly is NOT the Gödel number for “y”, the number “19”, as would be required for the self referent interpretation of formula (G). And equally it can certainly not be the “Gödel-number of the (not existing) symbol-sequence that results from “putting the sign “f” y times in front of 0”. Unquestionably, Z(y) cannot be anything else but that entire recursive definition 16 + 17 (rewritten in the symbols of the system) with all occurrences of “n” being replaced by “y”. But then, the formula (G), with Z(n) BEING the Gödel number for “n”, certainly cannot be claimed to be derived from formula (1) through “substitution of “n” for “y””! So, the selfreferent interpretation of formula (G) is lost! No better result is obtained from assuming Z(n) not to BE the Gödel number for “n”, but, in parallel to the definition of Z(y), to be the definition 16 + 17 with argument “n” (n = Gödel number of formula (1)). Now formula (G) evidently results from (1) through “substitution of n for y”, but (G) no more says of itself to be obtained from (1) through “substitution of n for y”! Again, no selfreferent interpretation is obtained! That is, what I would like to call:
GÖDEL’S INCONSISTENCY
In the last decades, a variety of other notations for Goedel's proof have been proposed. In the zeal for abstract abbreviations, in all generality the substitution function has either silently been suppressed altogether or at least reduced to something like 's(v1,v1) '. So, the variable that is to be substituted is denied any visible appearance in these formulations. A scrupulous analysis, however, easily reveals that they all suffer from the same malady, the disregard of the first page of Principia Mathematica. The easiest way to get an idea of what must be wrong with Gödel’s invention is anyway just to enlarge the Formal System by the capability to accept symbol sequences in general as arguments, not just those representing numbers. So the need for Gödelization disappears and Gödel’s term ‘sub(y,19,Z(y))’ reduces to the simple Sub(y,y,y) = ‘the symbol sequence resulting from the symbol sequence y via substitution of the free variable y by the symbol sequence y’. No doubt, the symbol y appears here in two different identities! Concluding this chapter, it appears that we have to admit that the vast amount of mathematico-philosophical works and speculations that have by now been generated around Goedel's Theorem during five decades are all founded on a simple violation of Russell Whiteheads rule and on the dubious interpretation of the term Z(y). A last nasty remark may be permitted as to the existence of formula (G) in the Formal System: the Gödel number n of formula (1), and much more yet the Gödel number of this n would be fffff…..0 - sequences with many more symbols f then is the number of elementary particles in this universe, so there is no danger to ever encounter such a monster, at least not in this universe!
XI The Halting Problem A last section must be devoted to the so-called 'Halting Problem' since this is occasionally claimed to offer a basis for a simplified proof of Goedel's Incompleteness Theorem. No doubt, at the core of this argument, we will again find a selfreferent construct. It is based on the following concepts and assumptions: A 'Turing machine' is a (theoretical) version of a rather simple general purpose computer which operates, writes, reads or erases 0's or 1's on the central portion of a one-dimensional tape of, to both sides, unlimited length. 'Data-input' is the tape content (0 - 1 sequence) on which a program starts to operate. 'Data-output' is the tape content after a program comes to a halt by executing the instruction 'Halt and display the tape content'. There is a 'Doubling Program' which doubles the tape content on which it is set to operate, i.e. with a sequence of seven 1's as input, this program generates a sequence of fourteen 1's as output. Programs can be encoded in the form of (0 – 1)- sequences and written onto the tape. There is a 'Universal Program' which enables the Turing Machine to read, decode and execute any such encoded program. So, given 'code(P)v' as input, this program would simulate what would happen if we run program P on the input v. The Halting Problem then consists in the claim that there can be no algorithm, i.e. no program, that would allow to detemine whether a given program, when operating on a given data input, will ever come to a halt or run forever. This claim seems rather surprising since we are all familiar with a series of characteristics from which we can very well tell whether a program will run forever or not, e.g. whether it gets caught in a repeating loop, etc. As proof for that claim the formulation by Martin Davis be reproduced here: Suppose we possess a computing procedure which solves the halting problem for the universal program U. Then we can imagine more complicated procedures of which this supposed procedure is a part. Specifically, we consider the following procedure which begins with a string v of zeros and ones: 1. Try to decode v as the code for a Post-Turing program, i.e., try to find P with code(P) = v. If there is no such P, go back to the beginning of Step 1; otherwise go on to Step 2. 2. Make a copy of v and place it to the right of v getting a longer string which we can write as vv (or equivalently as code(P)v since code(P) = v). 3. Use our (pretended) halting problem procedure to find out whether or not the universal program U will eventually halt if it begins with this string vv as the nonblank portion of the tape, scanning the leftmost symbol. If U will eventually halt, go back to the beginning of Step 3; otherwise stop. This proposed procedure would eventually stop if, first, v = code(P) for some Turing - Post program P (so we will leave Step 1 and go on to Step 2), and, second, if also U will never halt if it begins to scan the leftmost symbol of vv. Since U beginning with code(P)v simulates the behavior of P beginning with v, we conclude that our supposed procedure applied to the string v will eventually stop if and only if v = code(P) where P is a computing procedure that will never stop beginning with v on its tape. By Turing's analysis, there should be a Turing-Post program Po which carries out this very procedure. That is, P will eventually halt beginning with the input v if and only if U will never halt beginning with the input vv. Now let vo = code(Po ). Does U eventually halt beginning with the input vovo? By what we have just said, P eventually halts beginning with the input v if and only if U will never halt beginning with the input vv . But, as we will show, this contradicts our explanation of how U works as a universal program. Since vo = code(Po), U will act, given the input vovo , to simulate the behavior of P when begun on input vo. So U will eventually halt beginning with the input vovo if and only if Po will eventually halt beginning with the input vo . But this contradicts the previous italicized statement. The only way out of this contradiction is to conclude that what we were pretending is untenable. In other words, the halting problem for U is not solvable. (so far Martin Davis) There is quite a sequence of inconsistencies in this 'proof'. We restrict, however, our critical comment on just two of them. The first runs like this: The presumed program which carries out the procedure which solves the halting problem for the universal program U be designated 'program H'. This program must be capable to 'tell' the human operator whether it has succeeded to determine that U, operating on some 'code(P)v'-input, will or will never come to a halt. The only way to do this is by halting and displaying a predetermined symbol, say a 0 for 'will halt' or a 1 for 'will never halt'. So, the program H must of necessity contain two branches which both end with a STOP instruction. When Davis then constructs his procedure Po around the program H with the instruction: 'if U will eventually halt, go back to Step 3' it is implied that, first, program H, as internal part of Po, comes to a Halt and displays a '0', and that after this Halt, program P continues with 'go back to STEP 3'. So, the simple trick with this 'proof' is to sell us a program that will run into a STOP and GO-mode! To protect us from such cheating, we had better replace the simple 'STOP'-instruction by 'STOP and Blow the Fuse'! This will help everyone to realize when a program has come to a STOP! The second argument against this 'proof' is probably more critical yet: Turing claims to have shown that everything computable can be computed by a Turing-Post program P that operates on an appropriate data input v on the tape of a Turing machine. Of necessity, all these programs P must be totally independent of whether we ever consider to 'encode' some of them by translating each instruction into a specific 0-1-sequence or not. Let us call all these programs 'level-1- programs'. A totally different thing is a universal program U that is expected to simulate a program P when operating on the input 'code(P) '! This program U must depend on the specific code that was chosen to encode P! It just has to contain the appropriate 'decoder'. This type of program be called a level-2-program. Logically, just as in Russell's Theory of Types, any program that we expect to simulate the level-2-program U when operating on the input 'code(U) code(P)v', would have to be a level-3-program with the capability to decode the decoder of the level-2-program U etc. etc.
Now, to solve the halting problem in all generality, it suffices entirely to have a procedure, i.e. a program H that solves the halting problem for level-1-programs P. Since this H is to operate on data input 'code(P)v', it certainly has to contain the appropriate decoder. So it is a level-2-program, just as U . But it would be quite unfair to require this H also to solve the halting problem for the level-2-program U if given 'code(U) code(P)v' as input! Davis in his 'proof', however, operates with such an H as part of his level-3-program Po' and, by totally neglecting the various program levels, he then feeds 'code(U) code (Po)’ as input to program Po . So, if Davis proves anything, it is that there can be no procedure that solves the halting problem for the universal program U with it’s built-in decoder. But this is no proof that there could be no procedure that solves the halting problem or every decoder-free level-1-program P ! It is not even a proof that there can be no procedure H that solves the halting problem for the universal program U, provided the program P in the input 'code(P)v', on which U is assumed to operate, does not contain a decoder. And by inserting into H the instruction 'blow the fuse if you find in your input 'code(U) code(P)v' the code of a program P that contains a decoder, we can easily protect ourselves from running with Davis into the infinite double-decode-execute- double-decode-execute... sequence, where we will never find an ultimate decoder-free program which were to be checked whether it will ever halt, just as in Chapter IV with the infinitely nested 'the sentence, the sentence...', where we never found out which sentence should be claimed to be false.
XII Conclusion The starting point of the here-presented considerations was originally a rather vague uneasiness in face of the observation that, on the one hand, two of the most prominent mathematical conceptions of the last hundred years, i.e. Cantor's 'transfinite paradise' and Goedel's Incompleteness Proof, and, on the other hand, the whole series of rather nonsensical 'logical antinomies and paradoxes' are based on essentially the same two types of construct: either a selfreference or a reference to an assumedly complete infinite multitude. Furthermore, the author admits that he has always felt totally incapable to follow his math teachers in their haughty claim to be able to 'see' such a multitude like the set of all natural numbers as one completed totality. A third motive behind the here-exposed considerations was the observation that, in sharp contrast to so many other branches of mathematics, from Cantor's transfinite paradise nothing ever came back to our finite universe that could be claimed to be of any value to the non-mathematical rest of humanity. As it turned out, the investigation had first to concentrate on self-referent constructs in natural language, to show how the so-called 'logical antinomies' are in fact based from the beginning on intuitively nonsensical or self-contradictory suppositions, and that self-referent sentences are really of no value whatsoever for a meaningful application of language. Then, the claim was shown to be untenable that self-reference be required in the foundations of mathematics. Next, the discussion concentrated on a critique of the 'Diagonal Argument', the key to Cantor's 'transfinite paradise', by demonstrating the non-validity of this argument when applied to a potentially infinite list of potentially infinite decimals. In the light of this, it appears quite unclear how the diagonal argument, which is so evident for any finite square of decimals, could ever have been claimed to be just as valid for Cantor's invention of a 'complete' infinite list. Finally, Gödel’s claim to have generated a formula that says of itself, that it cannot be proven, was shown to be unjustified . It cannot be expected that mathematicians, who chose to devote a good part of their lives to cultivating Cantor's paradise, and to speculate about the consequences of Gödel’s invention, will readily take up the here-presented arguments which, in all their simplicity, if not triviality, are hard to believe that they should never have surfaced before. But, quite clearly, they have been ignored so successfully that in no modern text-book on the subject matter any trace of a critical discussion of these aspects of 'infinite' lists and unprovable formulas can be found. Basically, it was tried to sharpen the reader's attention and scepticism towards all types of self-generated pseudo-problems that originate from a careless (or intended?) misuse of language, the favorite pastime of most philosophers since ‘The Liar’ more than 2000 years ago. Clearly, in these days such publications as D.G. Hofstadter's 'Goedel, Escher, Bach', or R.Rucker's 'Infinity and The Mind' are much more 'en vogue' with their trend to rather mystify than to clarify the doings in this branch of mental activity. But how formulated J. von Neumann: 'in mathematics, you don't understand things, you just get used to them!'
B I B L I 0 G RAP H Y
E.W.Beth, Foundations of Mathematics, North Holland 1965
P.W.Bridgman, A Physicists Second Reaction to Mengenlehre, Scripta Mathematica 1934
G.Cantor, Letter to Dedekind, in van Heijenoortf `From Frege to Gödel`
G.J.Chaitin, Göde1’s Theorem and Information, Int.J.Theoret.Physics Vo1.21, No. 12 , 1982 , p. 941
J.W.Dauben, Georg Cantor and the Origins f Transfinite Set Theory, Scientific American ,1983
M.Davis, Computability and Unsolvability, McGraw-Hill, 1958 The Undecidable, Raven Press, 1965
What is a Computation, in L.A.Steen : Mathematics today
L.Fischer, Die Grundlagen der Philosophie und der Mathematik,
F.Meiner Verlag, 1933, p 68 ff
K.Gödel, Über formal unentscheidbare Sätze der Princ. Math. Monatshefte Math. Phys. 38, 1931 ,
P 173-198
W.S.Hatcher, Foundations of Mathematics, Saunders, 1968 J. van Heijenoort, From Frege to Gödel, Harvard Un.Press, 1967
H.Hermes, Aufzäh1barkeit-Entscheidbarkeit, Springer 1961
Einführung in die mathematische Logik, Teubner, 1963
D.Hilbert, P.Bernays, Grundlagen der Mathematik II , Springer 1939 D.R.Hofstadter, Gödel-Escher-Bach, Basic Books, 1979 S.C.Kleene, Introduction to Metamathematics, North Holland 1971 E.Nagel,J.R.Newman, Gödel’s Proof, New York Univers.Press, 1958
J.Richard, The principles of mathematics and the problem of sets,
Revue General des Sciences Pures et Appliquees,1905
B.Rosser, An Informal Exposition of Proofs of Gödel’s Theorems
and Church’s Theorem, J.Symbolic Logic Vol.4, June 1939
R. Rucker , Infinity and the Mind, Birkhäuser 1982 B. Russell, A.N.Whitehead, Principia Mathematica . Cambridge U.P.1910 W. Sierpinski, Cardinal and Ordinal Numbers, Warszawa 1965 R.M.Smullyan, Theory of Formal Systems, Princeton U.P. 1961 L.A.Steen, Mathematics Today, Springer 1978 H. Weyl, Das Kontinuum, Veit & Comp. 1918
nowiki>Insert non-formatted text here</nowiki>