Talk:Gödel's incompleteness theorems/Arguments

From Wikipedia, the free encyclopedia

This page is for arguments over the validity of Gödel's incompleteness theorems. This is not an archive; you may feel free to edit this page. Please use this page for comments not directly relevant to improving the article Gödel's incompleteness theorems.
An archive of past discussion is available here.

Contents


[edit] is the incompleteness theorem complete?

This is not an argument against the validity of the incompleteness theorem, and therefore it does not belong in the arguments section. This is a question about the incompleteness theorem and what it means in its own terms. What the theorem says about itself in its own terms is important to the discussion of the article.

The question is, according to the terms of the incompleteness theorem, does the incompleteness theorem apply to itself, and if so, does that make the theorem itself complete, or incomplete? Secondly, if the incompleteness theorem is itself complete, does that make it consistent, or inconsistent? Lastly, how do we really know? I would appreciate it if somebody could give me a straight answer because it is important to the discussion of the article and what it says about itself in its own terms.

Your question is ill-formed. Completeness and consistency are properties of theories. The incompleteness theorem is not a theory, but a proposition. --Trovatore 05:00, 29 January 2007 (UTC)
You may of course consider the incompleteness theorem (for a given theory T, say PA or PM or ZFC etc) as a theory T' with a single axiom. (Not that that would make much sense...)
That is, T' = { A } , where A is the sentence saying that T is incomplete.
For the example theories T mentioned above, T' is weaker than "T + Consistent(T)", and is therefore also an incomplete theory.
(However, depending on the exact formulation of the sentence A, T' may not include enough arithmetic, and may therefore not be essentially incomplete.)
--62.233.163.82 19:44, 10 February 2007 (UTC)
Dear Trovatore, You must explain the difference between a theory and a proposition. —The preceding unsigned comment was added by 72.16.111.54 (talk • contribs) 18:56, 23 March 2007 (UTC)
Sure thing. A theory is a collection of propositions. --Trovatore 19:05, 23 March 2007 (UTC)

[edit] I don't get it, this seems simple to fix

In these terms, the Gödel sentence is a claim that there does not exist a natural number with a certain property. A number with that property would be a proof of inconsistency of the theory. If there were such a number then the theory would be inconsistent, contrary to hypothesis. So there is no such number, and the Gödel statement is true, but the theory cannot prove it.

Ok, so let's say, "There does not exist a number that is prime, higher than 2 and is divisible by 2."

IF we found such a number, then the statement is false. However, since we can't "prove a negative", thus we can't ever *prove* this to be true. Tell me if I am sorta right so far (this might be a retarded example, I'm not a mathematician, just trying to muddle through the logic)?

SO, why can't we just prove the exact reverse of this? i.e. Given an infinite amount of time, we look at ALL the prime numbers greater than 2 and show that all of them are not divisible by 2.

It seems to my logic that when you've got infinity to play with, showing that *all* possible numbers do not have the characteristic is the same as saying that a possible number *cannot* have that characteristic. —The preceding unsigned comment was added by 66.159.227.60 (talk • contribs) 19:36, 1 April 2007 (UTC)

The first big problem in the above is the canard that you can't "prove a negative". In mathematics we prove negative statements all the time, and proving that there is no number with the property you give is in fact very easy. --Trovatore 23:21, 1 April 2007 (UTC)


Yes, that example seems much too simple. I'm not a mathematician either thus I don't understand the theory completely. However to get around the infinity statement, you could just change it to "There does not exist a prime number, higher than 2, less than 100, and is divisible by 2." But I doubt that this is what the inconsistency theory is talking about.Niubrad 23:59, 1 April 2007 (UTC)

[edit] Paradox in Godels incompleteness theorem that invalidates it

There is a simple paradox in Godel's incompleteness theorem, pointed out by the Australian philosopher Colin Leslie Dean, that invalidates it.

Godel claims that:

undecidability "does not depend upon the special nature of the constructed systems [PM and ZF] but rather holds for a very wide class of formal systems"

and yet in his proof he states undecidability is dependent on formal system P which includes PM"hence in every formal system which satisfies assumptions 1 and 2 [ from system P which includes PM] and is w - consistent there exist undecidable propositions". Thus Godel's incompleteness theorem ends in paradox and is meaningless or invalid.


Godel’s incompleteness theorem. Ends in absurdity or meaninglessness Quote: Godel makes the claim that there are undecidable propositions in a formal system that dont depend upon the special nature of the formal system Quote

It is reasonable therefore to make the conjecture that these axioms and rules of inference are also sufficent to decide all mathematical questions which can be formally expressed in the given systems. In what follows it will be shown .. there exist relatively simple problems of ordinary whole numbers which cannot be decided on the basis of the axioms. [NOTE IT IS CLEAR] This situation does not depend upon the special nature of the constructed systems [PM and ZF] but rather holds for a very wide class of formal systems (K Godel , On formally undecidable propositions of principia mathematica and related systems in The undecidable , M, Davis, Raven Press, 1965, p.6).( K Godel , On formally undecidable propositions of principia mathematica and related systems in The undecidable , M, Davis, Raven Press, 1965, p.6)

Thus Godel says he is going to show that undecidability is not dependent on the axioms of a system or the speacial nature of PM and ZF Also Godels refers to PM and ZF AS FORMAL SYSTEMS

"the most extensive formal systems constructed .. are PM ZF" ibid, p.5 so when he states that "This situation does not depend upon the special nature of the constructed systems but rather holds for a very wide class of formal systems" he must be refering to PM and ZF as belonging to these class of formal systems- further down you will see this is true- as well thus he is saying the undecidability claim is independent of the nature of the formal system but PM is a formal system


Godel says he is going to show undecidabilitys by using the system of PM (ibid) he then sets out to show that there are undecidable propositions in PM (ibid. p.8)

where Godel states "the precise analysis of this remarkable circumstance leads to surprising results concerning consistence proofs of formal systems which will be treated in more detail in section 4 (theorem X1) ibid p. 9 note this theorem comes out of his system P he then sets out to show that there are undecidable propositions in his system P -which uses the axioms of PM and Peano axioms. at the end of this proof he states "we have limited ourselves in this paper essentially to the system P and have only indicated the applications to other systems" (ibid p. 38)

now it is based upon his proof of undecidable propositions in P that he draws out broader conclusions for a very wide class of formal systems After outlining theorem V1 in his P proof - where he uses the axiom of choice- he states "in the proof of theorem 1V no properties of the system P were used other than the following 1) the class of axioms and the riles of inference- note these axioms include reducibility 2) every recursive relation is definable with in the system of P hence in every formal system which satisfies assumptions 1 and 2 [ which uses system PM] and is w - consistent there exist undecidable propositions ”. (ibid, p.28)

CLEARLY GODEL IS MAKING SWEEPING CLAIMS JUST BASED UPON HIS P PROOF

Godel has said that undecidability is not dependent on the axioms of a system or the special nature of PM and ZF

There is a contradiction here He says every formal system which satisfies assumption 1 and 2 ie based upon axioms - but he has said undecidablity is independent of axioms

Also there is a contradiction here Godel has said undecidablity is not dependent on PM yet says it is hence” in every formal system which satisfies assumptions 1 and 2 [ which uses system PM] and is w - consistent there exist undecidable propositions “

Thus the paradox undedciablity is not dependent of the axioms of a system or PM but is dependent on the axioms of the system and PM

In the above Godel must be referring to PM and ZF as they are formal systems

but he has said "This situation does not depend upon the special nature of the constructed systems [PM ZF] but rather holds for a very wide class of formal systems"

now P is constructed with the axioms of PM and Peano axioms "P is essentially the system which one obtains by building the logic of PM around Peanos axioms..." K Godel , On formally undecidable propositions of principia mathematica and related systems in The undecidable , M, Davis, Raven Press, 1965,, p.10) so clearly undecidability is dependent on the quirky nature of PM-which is a formal system


but he has told us undecidable propositions in a formal system are not due to the nature of the formal system but he is making claims about a very wide range of formal systems based upon the nature of formal system P

QUOTE [undecidability]does not depend upon the special nature of the constructed systems [PM and ZF] but rather holds for a very wide class of formal systems

contradict this

hence in every formal system which satisfies assumptions 1 and 2 [depending on the special nature of formal system P WHICH USES PM ] and is w - consistent there exist undecidable propositions

HE HAS SAID UNDECIDABILITY DOES NOT DEPEND UPON THE NATURE OF PM YET SAYS UNDECIABILITY IN FORMAL SYSTEMS- OF WHICH PM- IS ONE IS DEPENDENT ON PM put simply

Undecidability is independent on nature of PM, yet is dependent on the nature of PM.

thus undecidability is not dependent on the nature of the [PM and ZF] but he has said undecidability is dependent upon the nature of formal system P which uses PM

thus “[undecidability] does not depend upon the special nature of the constructed systems [PM and ZF] but rather holds for a very wide class of formal systems “

Contradicts this

“hence in every formal system which satisfies assumptions 1 and 2 [ depends upon the special nature of formal system PM] and is w - consistent there exist undecidable propositions ”.

Thus when Godel states

"hence in every formal system [PM example] which satisfies assumptions 1 and 2 and is w [Dependent on the special nature of P and thus PM ] - consistent there exist undecidable propositions"

he is creating paradox and circularity of argument he says undecidability is independent of formal system PM and ZF yet deriving assumptions dependent on this formal system PM he says those formal systems that have these assumption have undecidability and he states ZF has these assumptions (ibid, p.28) put simply

Undecidability is independent on nature of PM, yet is dependent on the nature of PM.

clearly Godel is in paradox and invalid due to meaninglessness


There is another paradox in Godels incompleteness theorem As we have seen undecidability in a formal system is dependent on the system PM but the system PM has undecidability

Godel tells us that among those very wide range of formal systems that have undecidability are to be included those systems which arise from PM by the addition finitely many axioms


As he states “It is reasonable therefore to make the conjecture that these axioms and rules of inference are also sufficent to decide all mathematical questions which can be formally expressed in the given systems. In what follows it will be shown that this is not the case but rather that in both systems cited [PM and ZF] there exist relatively simple problems of ordinary whole numbers which cannot be decided on the basis of the axioms. [NOTE IT IS CLEAR] This situation does not depend upon the special nature of the constructed systems [PM and ZF] but rather holds for a very wide class of formal systems among which are included in particular all those which arise from the given systems [PM and ZF] by addition of finitely many axioms”

In other words PM is included in those systems which have undecidability Thus we have the paradox that while PM is used to find if a formal system is undecidable it is undecidable itself

i.e. hence in every formal system which satisfies assumptions 1 and 2 [ from P which uses system PM] and is w - consistent there exist undecidable propositions

In other words the very system which is used to find undecidability is included in the set of undecidable systems



Thus we have the situation overall that clearly Godel is in paradox and invalid due to meaninglessness

1) there is circularity/paradox of argument he says his consistency proof is independent of the nature of a formal system yet he bases this claim upon the very nature of a particular formal system P- which includes PM which is itself undecidable 2) he is clearly basing his claims for his consistency theorems upon the systems PM and P

P and PM are the meta-theories/systems he uses to prove his claim that there are undecidable propositions in a very wide range of formal systems

We have a dilemma 1)either Gödel is right that his claims for undecidability of formal systems are independent of the nature of a formal system

and thus he is in paradox when he makes claims about formal systems based upon the special nature of P - AND THUS PM

OR 2) he makes claims about formal systems based upon the special nature of P and PM that would mean that PM and P are the meta-systems/meta-theory through which he is make undecidable claims about formal systems

thus indicating the axioms of PM and P are central to these meta claims there by when I argue s these axioms are invalid then Godels incompleteness theorem is invalid and a complete failure. Thus either way Godels incompleteness theorem are invalid and a complete failure :either due to the paradox in his theorem or the invalidity of his axioms.

[edit] Godel system P is invalid -thus his incompleteness theorem is invalid

In regard to system P The Australian philosopher Colin Leslie Dean points that godels system P is invalid http://gamahucherpress.yellowgum.com/books/philosophy/GODEL5.pdf

Godel constructs an artificial system P made up of Peano axioms and axioms including the axiom of reducibility- which is not in the edition of PM he says he is is using. This system is invalid as it uses the invalid axiom of reducibility. Godels theorem has no value out side of his system P and system P is invalid as it uses the invalid axiom of reducibility


"P is essentially the system which one obtains by building the logic of PM around Peanos axioms..." K Godel , On formally undecidable propositions of principia mathematica and related systems in The undecidable , M, Davis, Raven Press, 1965,, p.10)

system P contain the axiom of reducibility


Godel uses the axiom of reducibility axiom 1V of his system is the axiom of reducibility “As Godel says “this axiom represents the axiom of reducibility (comprehension axiom of set theory)”

http://www.math.ucla.edu/~asl/bsl/1302/1302-001.ps.

"The system P of footnote 48a is Godel’s streamlined version of Russell’s theory of types built on the natural numbers as individuals, the system used in [1931]. The last sentence ofthe footnote allstomindtheotherreferencetosettheoryinthatpaper; KurtGodel[1931,p. 178] wrote of his comprehension axiom IV, foreshadowing his approach to set theory, “This axiom plays the role of [Russell’s] axiom of reducibility (the comprehension axiom of set theory).”


system P is the system from which he derives his incompleteness theorem quote from the van Heijenoort translation


”Theorem XI. Let κ be any recursive consistent63 class of FORMULAS; then the SENTENTIAL FORMULA stating that κ is consistent is not κ-PROVABLE; in particular, the consistency of P is not provable in P,64 provided P is consistent (in the opposite case, of course, every proposition is provable [in P])". (Brackets in original added by Gödel “to help the reader”, translation and typography in van Heijenoort 1967:614)

ALSO

IT MUST BE NOTED THAT GODEL IS USING 2ND ED PM BUT RUSSELL TOOK THE AXIOM OF REDUCIBILITY OUT OF THAT EDITION – which Godel must have known.

The Cambridge History of Philosophy, 1870-1945- page 154

http://books.google.com/books?id=I09hCIlhPpkC&pg=PA154&vq=Russell+repudiated+Reducibility&dq=taken+out+2nd+ed+principia+russell+axiom+of+reducibility&source=gbs_search_r&cad=1_1&sig=-LmJ1voEsKRoWOzml_RmOLy_JS0 Quote

“In the Introduction to the second edition of Principia, Russell repudiated Reducibility as 'clearly not the sort of axiom with which we can rest content'…Russells own system with out reducibility was rendered incapable of achieving its own purpose”


quote page 14 http://www.helsinki.fi/filosofia/gts/ramsay.pdf.

“Russell gave up the Axiom of Reducibility in the second edition of Principia (1925)”

THUS Godel constructs an artificial system P made up of Peano axioms and axioms including the axiom of reducibility- which is not in the edition of PM he says he is is using. This system is invalid as it uses the invalid axiom of reducibility. Godels theorem has no value out side of his system P and system P is invalid as it uses the invalid axiom of reducibility

THAT AR IS INVALID IS SEEN FROM

the standford encyclopdeia of philosophy says of AR

http://plato.stanford.edu/entries/principia-mathematica/

“many critics concluded that the axiom of reducibility was simply too ad hoc to be justified philosophically”

From Kurt Godels collected works vol 3 p.119

http://books.google.com/books?id=gDzbuUwma5MC&pg=PA119&lpg=PA119&dq=godel+axiom+of+reducibility&source=web&ots=-t22NJE3Mf&sig=idCxcjAEB6yMxY9k3JnKMkmSvhA#PPA119,M1

“the axiom of reducibility is generally regarded as the grossest philosophical expediency “

Godel would have know all these criticism by Russell Wittgenstein and Ramsey but still used the axiom. Russell Witgenstein and Ramsey would have know Godel used this invalid axiom in his artificial system P but said nothing —Preceding unsigned comment added by Xamce (talk • contribs) 12:16, 2 March 2008 (UTC)

[edit] Godel uses ad hoc axiom that is not in PM -and which is invalid

The Australian philosopher colin leslie dean points out that Godel uses ad hoc axiom that was not in PM http://gamahucherpress.yellowgum.com/books/philosophy/GODEL5.pdf


godel uses the axiom of reducibility he tell us he is going to use it

“A. Whitehead and B. Russell, Principia Mathematica, 2nd edition, Cambridge 1925. In particular, we also reckon among the axioms of PM the axiom of infinity (in the form: there exist denumerably many individuals),and the axioms of reducibility and of choice (for all types)”


NOTE GODEL TELLS US HE IS USEING 2ND ED PM

and he uses it in his axiom 1v and formular 40

Godel uses the axiom of reducibility axiom 1V of his system is the axiom of reducibility “As Godel says “this axiom represents the axiom of reducibility (comprehension axiom of set theory)” (K Godel , On formally undecidable propositions of principia mathematica and related systems in The undecidable , M, Davis, Raven Press, 1965,p.12-13) . Godel uses axiom 1V the axiom of reducibility in his formula 40 where he states “x is a formula arising from the axiom schema 1V.1 ((K Godel , On formally undecidable propositions of principia mathematica and related systems in The undecidable , M, Davis, Raven Press, 1965,p.21 “ [40. R-Ax(x) ≡ (∃u,v,y,n)[u, v, y, n <= x & n Var v & (n+1) Var u & u Fr y & Form(y) & x = u ∃x {v Gen [[R(u)*E(R(v))] Aeq y]}] x is a formula derived from the axiom-schema IV, 1 by substitution “

http://www.math.ucla.edu/~asl/bsl/1302/1302-001.ps.


"The system P of footnote 48a is Godel’s streamlined version of Russell’s theory of types built on the natural numbers as individuals, the system used in [1931]. The last sentence ofthe footnote allstomindtheotherreferencetosettheoryinthatpaper; KurtGodel[1931,p. 178] wrote of his comprehension axiom IV, foreshadowing his approach to set theory, “This axiom plays the role of [Russell’s] axiom of reducibility (the comprehension axiom of set theory).”

(BUT

IT MUST BE NOTED THAT GODEL IS USING 2ND ED PM BUT RUSSELL TOOK THE AXIOM OF REDUCIBILITY OUT OF THAT EDITION – which Godel must have known.

The Cambridge History of Philosophy, 1870-1945- page 154

http://books.google.com/books?id=I09hCIlhPpkC&pg=PA154&vq=Russell+repudiated+Reducibility&dq=taken+out+2nd+ed+principia+russell+axiom+of+reducibility&source=gbs_search_r&cad=1_1&sig=-LmJ1voEsKRoWOzml_RmOLy_JS0 Quote

“In the Introduction to the second edition of Principia, Russell repudiated Reducibility as 'clearly not the sort of axiom with which we can rest content'…Russells own system with out reducibility was rendered incapable of achieving its own purpose”

quote page 14 http://www.helsinki.fi/filosofia/gts/ramsay.pdf.

“Russell gave up the Axiom of Reducibility in the second edition of Principia (1925)”

Phenomenology and Logic: The Boston College Lectures on Mathematical Logic and Existentialism (Collected Works of Bernard Lonergan) page 43

http://books.google.com.au/books?id=Pd5YaLwZugUC&pg=PA43&lpg=PA43&dq=axiom+of+reducibility+second+dropping&source=web&ots=a27lIUxvQU&sig=auv4udKq0S-F6KQ_Xxsh0US6QrI&hl=en

In the second edition Whitehead and Russell took the step of using the simplified theory of types dropping the axiom of reducibility and not worrying to much about the semantical difficulties


Godels paper is called

ON FORMALLY UNDECIDABLE PROPOSITIONS OF PRINCIPIA MATHEMATICA AND RELATED

SYSTEMS

but he uses an axiom that was not in PRINCIPIA MATHEMATICA thus his proof/theorem has nothing to do with PRINCIPIA MATHEMATICA AND RELATED SYSTEMS at all Godels proof is about his artificial system P -which is invalid as it uses the ad hoc invalid axiom of reducibility


Godel constructs an artificial system P made up of Peano axioms and axioms including the axiom of reducibility- which is not in the edition of PM he says he is is using. This system is invalid as it uses the invalid axiom of reducibility. Godels theorem has no value out side of his system P and system P is invalid as it uses the invalid axiom of reducibility


EVERY ONE KNEW THAT AR WAS NOT IN 2ND ED PM EVEN GODEL BUT NO ONE SAID ANYTHING

the standford encyclopdeia of philosophy says of AR

http://plato.stanford.edu/entries/principia-mathematica/

“many critics concluded that the axiom of reducibility was simply too ad hoc to be justified philosophically”

From Kurt Godels collected works vol 3 p.119

http://books.google.com/books?id=gDzbuUwma5MC&pg=PA119&lpg=PA119&dq=godel+axiom+of+reducibility&source=web&ots=-t22NJE3Mf&sig=idCxcjAEB6yMxY9k3JnKMkmSvhA#PPA119,M1

“the axiom of reducibility is generally regarded as the grossest philosophical expediency “

[edit] Godels axioms are invalid thus his incompleteness theorem is invalid

Godel proved his incompleteness theorem with flawed and invalid axioms- axioms that either lead to paradox or ended in paradox –thus showing that Godel’s proof is based upon a misguided system of axioms and that it is invalid as its axioms are invalid. For example Godels uses the axiom of reducibility but this axiom was rejected as being invalid by Russell as well as most philosophers and mathematicians. Thus just on this point Godel is invalid as by using an axiom most people says is invalid he creates an invalid proof due to it being based upon invalid axioms

Godel’s incompleteness theorem. Ends in absurdity or meaninglessness

Godel states that he is going to use the system of PM “ before we go into details lets us first sketch the main ideas of the proof … the formulas of a formal system (we limit ourselves here to the system PM) …” ((K Godel , On formally undecidable propositions of principia mathematica and related systems in The undecidable , M, Davis, Raven Press, 1965,pp.-6)

Godel uses the axiom of reducibility and axiom of choice from the PM

“A. Whitehead and B. Russell, Principia Mathematica, 2nd edition, Cambridge 1925. In particular, we also reckon among the axioms of PM the axiom of infinity (in the form: there exist denumerably many individuals), and the axioms of reducibility and of choice (for all types)” ((K Godel , On formally undecidable propositions of principia mathematica and related systems in The undecidable , M, Davis, Raven Press, 1965, p.5)

But both these axioms have major problems. The axiom of reducibility mathematicians say must be banished from mathematics


AXIOM OF REDUCIBILITY

Godel uses the axiom of reducibility axiom 1V of his system is the axiom of reducibility “As Godel says “this axiom represents the axiom of reducibility (comprehension axiom of set theory)” (K Godel , On formally undecidable propositions of principia mathematica and related systems in The undecidable , M, Davis, Raven Press, 1965,p.12-13. Godel uses axiom 1V the axiom of reducibility in his formula 40 where he states “x is a formula arising from the axiom schema 1V.1 ((K Godel , On formally undecidable propositions of principia mathematica and related systems in The undecidable , M, Davis, Raven Press, 1965,p.21 “As a corollary, the axiom of reducibility was banished as irrelevant to mathematics ... The axiom has been regarded as re-instating the semantic paradoxes” - http://mind.oxfordjournals.org/cgi/reprint/107/428/823.pdf “does this mean the paradoxes are reinstated. The answer seems to be yes and no” - http://fds.oup.com/www.oup.co.uk/pdf/0-19-825075-4.pdf )


IMPREDICATIVE DEFINITIONS

Godel uses impredicative definitions: As he states “ The solution suggested by Whitehead and Russell, that a proposition cannot say something about itself , is to drastic... We saw that we can construct propositions which make statements about themselves,… ((K Godel , On undecidable propositions of formal mathematical systems in The undecidable , M, Davis, Raven Press, 1965, p.63 of this work Dvis notes, “it covers ground quite similar to that covered in Godels orgiinal 1931 paper on undecidability,” p.39.)

Yet Godels has argued that impredicative definitions destroy mathematics and make it false. As he states "consider this rather as a proof that the vicious circle principle is false than that classical mathematics is false”. http://www.friesian.com/goedel/chap-1.htm

Godel used Peanos axioms but these axioms are impredicative and thus according to Russell Poincaré and others must be avoided as they lead to paradox. Poincaré argues that if we fail to establish the consistency of Peano's axioms for natural numbers without falling into circularity, then the principle of complete induction is improvable by general logic. “http://en.wikipedia.org/wiki/Preintuitionism


THEORY OF TYPES

In Godels second incompleteness theorem he uses the theory of types- but with out the very axiom of reducibility that was required to avoid the serious problems with the theory of types and to make the theory of types work.- without the axiom of reducibility virtually all mathematics breaks down. (http://planetmath.org/encyclopedia/AxiomOfReducibility.html) As he states “ We now describe in some detail a formal system which will serve as an example for what follows …We shall depend on the theory of types as our means for avoiding paradox. .Accordingly we exclude the use of variables running over all objects and use different kinds of variables for different domians. Speciically p q r... shall be variables for propositions . Then there shall be variables of successive types as follows x y z for natural numbers f g h for functions

Different formal systems are determined according to how many of these types of variable are used... (K Godel , On undecidable propositions of formal mathematical systems in The undecidable , M, Davis, Raven Press, 1965, p.63 of this work Davis notes, “it covers ground quite similar to that covered in Godels orgiinal 1931 paper on undecidability,” p. 46.). Clearly Godel is using the theory of types as part of his meta-theory to show something in his object theory i.e. his formal system example.

Russell propsed the system of types to eliminate the paradoxes from mathematics. But the theory of types has many problems and complications .One of the devices Russell used to avoid the paradoxes in his theory of types was to produce a hierarchy of levels. A big problems with this device , is that the natural numbers have to be defined for each level and that creates insuperable difficulties for proofs by inductions on the natural numbers where it would more convenient to be able to refer to all natural numbers and not only to all natural numbers of a certain level. This device makes virtually all mathematics break down. (http://planetmath.org/encyclopedia/AxiomOfReducibility.html) For example, when speaking of real numbers system and its completeness, one wishes to quantify over all predicates of real numbers…, not only of those of a given level. In order to overcome this, Russell and Whitehead introduced in PM the so-called axiom of reducibility – but as we have seen this Axiom obliterates the distinction according to levels and compromises the vicious-circle principle in the very specific form stated by Russell. But The philosopher and logician Frank Ramsey (1903-1930) was the first to notice that the axiom of reducibility in effect collapses the hierarchy of levels, so that the hierarchy is entirely superfluous in presence of the axiom. But in the second incompleteness theorem Godel does not use the very axiom of reducibility Russell had to introduce to avoid the serious problems with the theory of types. Thus he uses a theory of types which results in the virtual breakdown of all mathematics (http://www.helsinki.fi/filosofia/gts/ramsay.pdf) (http://planetmath.org/encyclopedia/AxiomOfReducibility.html)


…


[edit] Godel's Resort to Metamathematics

Godel decides on metamathematical grounds that 'Theorem A: A cannot be proved' is a correct theorem. But rather, isn't it just the case that theorem A is not consistent? Because it is not consistent, it is not unambiguously clear what it represents, and therefore it can be neither correct nor incorrect, ie. neither it nor its negation can be deduced from the axioms.

The whole thrust of Godel's conclusions hang on our accepting his metamathematical assertion that theorem A is correct. I don't think it is; I think it is an easy slip to make and an easy slip to miss, but a slip nevertheless. I think theorem A isn't consistent, which means it is impossible for it to be either correct or incorrect.

If the theorem 'Theorem A: A cannot be proved' is not obviously true, in disagreement with what Godel claims metamathematically, then his conclusions don't follow. Instead all you have is 'you can express inconsistent theorems, but you can neither prove nor disprove them' - which is just exactly what you would expect and poses no real problem at all. --Vibritannia (talk) 14:24, 7 March 2008 (UTC)

Any assertion that one may make implicitly includes an assumption that the assertion itself is self-consistent. Clearly there is the potential for situations to arise when that assumption is not valid, assertions containing self-references being the prime candidate. If you explicitly include the assumption of self-consistency in every assertion, then when you consider the negation of the assertion, you are presented with the possibility that the original assertion was not self-consistent.
You can resolve a lot of paradoxes in that way. It's so obvious in hindsight that it's actually a bit embarrassing to argue for. How can anybody assert anything without implicitly asserting that their assertion is self-consistent? (And more generally, for that matter, consistent with that to which it is supposed to pertain?) --Vibritannia (talk) 12:12, 17 April 2008 (UTC)


[edit] Gödel Cake

There is a famous recipe for a cake called a Gödel cake that absolutely no one has succeeded in baking. To every experienced culinary eye, the recipe appears self-evidently to be one that when followed should produce a cake, and yet all attempts to make the cake have been frustrated.

This had led some to question whether the recipe really is a recipe for a cake: if a recipe for a cake has never produced a cake, then there is no evidence that it is a recipe for a cake. The creator of the recipe and his adherents argue however that it is clear from everything we know about the philosophy of cooking that the recipe is a recipe for a cake (in fact he claims to have proved on sound philosophical grounds that, in theory at least, the cake can be baked), and that this means that there can be recipes that can never be cooked until someone invents a presently unimagined new cooking utensil that would enable the successful baking of the cake. Gödel goes on to argue, though, that if such a cooking utensil were in fact to be invented, there is nothing to preclude the possibility that he could create a new cake recipe that included the use of the new utensil in its preparation yet which still no one would be able to succeed in baking.

This is what has come to be known as the fundamental uncookability of all reasonably useful recipe systems, which essentially states that there are recipes that no one can cook using just the currently accepted practices, and that even if new practices were introduced, this would allow new recipes to be described that still nobody can cook.

Vociferous opponents of Gödel argue however that a cake isn’t a cake until you have your cake and eat it, and that Gödel’s culinary thinking is so absurd that it’s not even half-baked.

However, for today at least, it is still generally accepted that the Gödel cake is a true cake.

--Vibritannia (talk) 10:58, 28 April 2008 (UTC)


[edit] What did Gödel Prove?

Gödel encoded a formula equivalent to ‘theorem A: A cannot be proved’ and then showed rigorously that he could not decide whether it was true or not from within the system he had encoded it. He then argued informally (and from outside of the system in which he encoded it) that theorem A was correct, without providing a rigorous proof.

He then concluded that ‘there are true statements that cannot be proved in a consistent system’. But since the true statement referred to was not proved but only informally argued for, we can deduce ‘the conclusion that “there are true statements that cannot be proved in a consistent system” was not proved’. And since a rigorous proof of theorem A is clearly only possible in an inconsistent system, we can deduce ‘the conclusion that “there are true statements that cannot be proved in a consistent system” cannot be proved in a consistent system’.

This is a striking deduction. Gödel’s conclusion appears to be itself an instance of just the sort of true statement of whose existence his conclusion asserts. This is highly suspicious. Clearly the most economical conclusion to draw is that Gödel’s conclusion is false.

--Vibritannia (talk) 10:33, 29 April 2008 (UTC)


[edit] Proof that Gödel’s "True" Statement is not True

Gödel’s true statement was a formula of the form

Theorem A: A is not provable

Gödel argued informally that theorem A was true, so let us consider the following

Theorem A: A is not provable AND A is true

Note this is just an explicit (and possibly redundant) restatement of the original intention of Gödel's construction

Now consider the negation

Theorem ¬A: A can be proved OR A is not true
from ¬(X AND Y) ≡ ¬X OR ¬Y

but

A is not true ≡ A is false ≡ ¬A is not false ≡ ¬A is true

So the negation is equivalent to

Theorem ¬A: A can be proved OR ¬A is true

We note that the negation of A can be true both if A can be proved or if A cannot be proved. Therefore the negation of A is always true, in which case A must be false.

But we notice that we could replace 'A cannot be proved' with anything at all. So now we see that any theorem that asserts its own truth must be false (because we find its negation is always true), therefore truth can only ever be proved, never asserted. In which case, a truth that cannot be proved cannot be a truth.

So Gödel's "true" statement is either false (because it is not provable), or it is an assumption. If it is an assumption, how useful an assumption is it? We are usually only interested in useful assumptions.

--Vibritannia (talk) 12:24, 29 April 2008 (UTC)

Godel's formula for the theory T can be proved to be true assuming that T is consistent. The consistency assumption is very useful since if it is false then the theory T is useless.--Pokipsy76 (talk) 13:00, 29 April 2008 (UTC)


[edit] Proof that Gödel’s “True” Statement is not Self-Consistent

[edit] Outline

In the first incompleteness theorem, Gödel’s “true” statement is of the form A: A cannot be proved. We will prove that A is not a self-consistent statement.

First we will assume the negation of A and by explicitly assuming that the system is consistent, show that this leads to absurdity. Having thereby proved A by reductio ad absurdum, we will have shown that the system is complete in respect of A, without having assumed the system is complete in general. We will then use the completeness in respect of A to show that A also leads to absurdity. In this way, by assuming only consistency, we will have shown that A violates the law of excluded middle.

Second we will instead assume that the system is not consistent. This will allow us to infer that the system is complete, from the principle of explosion. We will then show that A leads to absurdity. Having thereby proved the negation of A by reductio ad absurdum, we will have shown that the system is consistent in respect of A, without having assumed explicitly that the system is consistent in general, by having satisfied the law of non-contradiction. We will then use the consistency in respect of A to show that the negation of A also leads to absurdity. In this way, by assuming that the system is not consistent, we will have shown that A violates the law of excluded middle.

It is thereby shown that regardless of whether the system is consistent or not consistent, A violates the law of excluded middle. Therefore A is not a self-consistent statement.

[edit] Proof

For p = provable, Gödel's true statement is of the form

1. A: \neg p(A)

First we assume the negation of A is true:

2. \neg A: p(A)

If we assume the system is consistent, then

3. p(A) \rightarrow A
in a consistent system, provable A means A is true
4. \neg A \to A
from (2) and (3)

(4) is absurd!

5. A \ \mbox{is proved by reductio ad absurdum}
proved by (2) to (4)

We now consider whether A is true.

Since (5), the system is complete in respect of A, without having assumed the system is complete in general

6. \neg p(A) \to p(\neg A)
from completeness in respect of A, if A isn't provable, then the negation of A must be provable
7. A \to p(\neg A)
from (1) using (6)

Since we have assumed the system is consistent

8. p(\neg A) \to \neg A
in a consistent system, a provable statement is a true statement
9. A \to \neg A
from (7) and (8)

(9) is absurd!

So we have assumed the system is consistent and have showed first that the negation of A is absurd and second that A itself is absurd, i.e. if we assume the system is consistent, then A violates the law of excluded middle. Now we start again, but this time we begin by assuming that the system is not consistent.

1. A: \neg p(A)
2. \neg consistent \to complete
from the principle of explosion

From (2), system is complete, so

3. \neg p(A) \to p(\neg A)
in a complete system, A isn't provable means the negation of A is provable
4. A \to p(\neg A)
from (1) and (3)

We now take the negation of A and substitute it into (4)

5. \neg A: p(A)
by negating (1)
6. A \to p(\ p(A)\ )
by substituting (5) into (4)

Now consider a new statement B that has this form:

7. B:\ p(B)
8. B:\ p(\ p(B)\ )
by substituting (7) into itself
9. p(\ p(B)\ ) \equiv p(B)
from (7) and (8)
10. p(\ p(A)\ ) \equiv p(A)
from (9)
11. A \to p(A)
from (6) and (10)
12 \neg p(A) \to p(A)
by substituting (1) into the left-hand side of (11)

(12) is absurd!

13. \neg A \ \mbox{is proved by reductio ad absurdum}
proved by (1) to (12)

We now consider whether the negation of A is true.

14. \neg A: p(A)
by negating (1)

Since (13), the system is shown consistent in respect of A, without necessarily showing that the system is consistent in general

15. p(A) \to A
from consistency in respect of A, A is provable means A is true
16. \neg A \to A
from (14) and (15)

(16) is absurd!

So by assuming the system is not consistent, we have showed first that A is absurd and then second that the negation of A is also absurd, i.e. if we assume the system is not consistent, then A violates the law of excluded middle.

So we have shown altogether that

1. consistent \to (A \ \mbox{violates the law of excluded middle} )
from the first proof
2. \neg consistent \to (A \ \mbox{violates the law of excluded middle} )
from the second proof
3. (consistent \or \neg consistent) \to (A \ \mbox{violates the law of excluded middle} )
from (1) and (2)
4. (P \or \neg P) \equiv \mbox{TRUE}
where P is any proposition
5. A \ \mbox{violates the law of excluded middle}
from (3) and (4)

Therefore we have proved that A violates the law of excluded middle, without requiring that the system is consistent (as just shown above) or that the system is complete (as can be seen by examining the proofs). Therefore A, though expressible in an otherwise consistent system, must not itself be a consistent statement.

[edit] Conclusion

Gödel concludes from his rigorous formal argument only that A is not decidable. His main conclusion follows from his informal argument that A is obviously true. But we have proved that A is not self-consistent, i.e. that A contains a self-contradiction.

--Vibritannia (talk) 16:55, 4 May 2008 (UTC)


Downloadable PDF version of the above proof_godels_true_statement_not_self_consistent.pdf

[edit] Proof that Maths is Both Consistent and Complete

When we wish to prove a statement S by reductio ad absurdum, we first assume the negation of S is true. If we then succeed in deducing a contradiction, then we say that we have proved S by reductio ad absurdum, and that therefore S is true. Therefore if we were able to assume the negation of S and then deduce S, then we would have proved S by reductio ad absurdum.

So for p = provable,

1. (\neg S \to S) \to p(S)
an instance of reductio ad absurdum
2. (X \to Y) \equiv (\neg X \or Y)
as can be seen by drawing a truth table
3 (S \or S) \to p(S)
from (1) and (2)
4. S \to p(S)
from (3)

Now if we assume maths is consistent

5. p(S) \to S
in a consistent system, a statement is provable means the statement is true
6. (p(S) \to S) \and (S \to p(S))
from (4) and (5)
7. S \equiv p(S)
from (6), (which can be seen by drawing a truth table)

This states that true statements are provable statements, i.e. that maths is complete. Therefore, if we assume reductio ad adsurdum is a valid proof method, then a consistent system is a complete system.

Now we consider Gödel's "true" statement that could not be proved:

1. A: \neg p(A)

But we have already shown

2. p(A) \equiv A
an equivalent restatement of (7) from the previous proof
3. A: \neg A
by substituting (2) for p(A) in the right-hand side of (1)

Suddenly, Gödel's "true" statement is very clearly self-contradictory!


Observation: A system capable of self-reference is capable of self-contradiction.

This means that a statement may be either true, false, or neither – contrary to what the law of excluded middle would have us believe. A way to see why this is the case is by use of a simple visual analogy.

Imagine you are an ant standing on a long strip of paper. If you were standing on the upper side of the paper, then 'you are on the upper surface' would be a true statement. Only by crossing an edge of the paper could you get to the other side and negate your statement. Then it would not be true that 'you are on the upper surface', but it would be true that 'you are on the under-side surface'.

Now imagine that the ends of the strip are joined together (which will provide our analogy of self-reference). Now as before, either it is true that 'you are on the outside surface' or 'you are on the inside surface'. If the former is true, then the latter can only be true if you cross an edge, and vice versa. And you can walk endless circles along the surface of your strip of paper, and this will always be the case.

But now imagine that the paper loop is cut, and one end is twisted through a half turn before the ends are joined again. Now what was the inside surface has been connected to the outside surface. The loop of paper has become a mobius strip. Unaware of the change just imposed, you look around and (as is our custom) confidently proclaim to be true that 'you are on the outside surface', but when you go for a walk along your strip, you find eventually that you are on the inside surface – but you did not cross an edge! Disturbed, you retrace your steps. You decide that there is now something absurd about the outside surface, and so you cross the edge to the inside surface. Relieved, you confidently proclaim that you are on the inside surface and head off for a walk along your strip. But lo and behold, you find yourself on the outside surface again – and again, you did not cross an edge!

What happened? The answer is that by crossing an edge, you did not succeed in passing to a different surface. On a mobius strip, there is only one surface. The outside surface is the same surface as the inside surface. When you cross an edge, you merely take a short-cut to a different place along the same surface (or a different step in your walk).

This is just what happens in the case of a self-contradictory statement. The distinction between true and false is lost. When you negate a self-contradictory statement (cross an edge), you merely take a short-cut to a different step in your deduction (a different place along the same surface).

Self-contradictory statements are simple to construct in mathematics (as simple as mobius strips). One of the most famous is the set defined in Russell's paradox. But we must make sure that we are aware that if we accept such statements, then we are accepting the absurd – in which case, we have lost a useful distinction between what is good sense and what is nonsense.

--Vibritannia (talk) 10:52, 10 May 2008 (UTC)



[edit] Why Accept the Absurd?

Quoted from the article,

If the axiomatic system is consistent, Gödel's proof shows that p (and its negation) cannot be proven in the system. Therefore p is true (p claims to be not provable, and it is not provable) yet it cannot be formally proved in the system.


Just imagine for one moment that we're mistaken and all true statements are really provable statements, and substitute 'true' for 'provable' in the above quote.

If the axiomatic system is consistent, Gödel's proof shows that p (and its negation) cannot be proven in the system. Therefore p is true (p claims to be not true, and it is not true) because it cannot be formally proved in the system.


We could say that it is true that p is not true. But that is not the same thing as saying p is true – except in this strange case it is, because we have effectively constructed p says that p is not true. So if we say that it is true that p is not true, we have in the same breath by implication said that p is true. That is self-contradictory and is therefore absurd.

Are we really to accept that true statements aren't necessarily provable statements just so that we can avoid this substitution and maintain that p is a self-consistent statement? Why are we so ready to believe that p is self-consistent when Gödel himself pointed out in his very own paper that his construction bore a similarity to the Liar's paradox?

The first incompleteness theorem is built upon a paradox, i.e. it is built upon a self-contradiction. It is therefore as nonsensical as that upon which it is founded.

--Vibritannia (talk) 18:31, 20 May 2008 (UTC)


[edit] Proof that Gödel's "True" Statement is Absurd

For p = provable, Gödel's "true" statement is

1. A: \neg p(A)
begin by assuming A to be true
2. consistent
assumed
3. p(B) \to B
from (2), i.e. in a consistent system, a provable statement is a true statement
4. p(\neg B) \to \neg B
from (2), i.e. in a consistent system, if the negation of a statement is provable, then the negation of the statement is true
5. (X \to Y) \equiv (\neg Y \to \neg X)
can be seen by drawing a truth table
6. B \to \neg p(\neg B)
from (4) using (5)
7. A \to \neg p(\neg A)
from (6) since A was assumed in (1)
8. A \to \neg p(A)
from (1)
9. A \to \neg p(A) \and \neg p(\neg A)
from (8) and (7)
10. \neg ( \ \neg p(A) \and \neg p(\neg A) \ ) \to \neg A
from (9) using (5)
11. \neg (\neg X \and \neg Y) \equiv (X \or Y)
can be seen by drawing a truth table
12. ( \ p(A) \or p(\neg A) \ ) \to \neg A
from (10) using (11)
13. (A \or \neg A) \to \neg A
from (12) using (3) and (4)
14. (X \or \neg X) \equiv TRUE
can be seen by drawing a truth table
15. \neg A
from (13) and (14)

We have deduced the negation of A which is a contradiction of what we began by assuming in (1), which was A. Therefore we have demonstrated that A is absurd.

--Vibritannia (talk) 12:32, 21 May 2008 (UTC)


We have also proved reductio ad absurdum (apparently) that the negation of A is true:

16. \neg A: p(A)
the negation of (1)
17. \neg A: p( \ \neg p(A) \ )
by substituting (1) into the right-hand side of (16)

In words, the negation of A says we can prove that we cannot prove A.

Well that is true because a way to prove that you cannot prove a statement is simply to prove its negation. And we've just done that. Therefore the negation of A is both true and provable.

Hmm... is that a surprise?

--Vibritannia (talk) 13:05, 21 May 2008 (UTC)

(13) is incorrect. You cant deduce (A \or \neg A) \to \neg A from (p(A) \or p(\neg A)) \to (A \or \neg A) and ( \ p(A) \or p(\neg A) \ ) \to \neg A. The correct deduction is P→R from P→Q and Q→R, but you have incorrectly deduced P→R from Q→P and Q→R.--Pokipsy76 (talk) 09:00, 1 June 2008 (UTC)
Thank you. My mistake. --Vibritannia (talk) 08:38, 5 June 2008 (UTC)

[edit] The Ultimate Defeat of the First Incompleteness Theorem

From two simple assumptions - one that cannot be refuted without abandoning the concept of mathematical proof altogether, and the other that (as it will be seen subsequently) need not be applicable to the statement to which we will apply it - we will swiftly defeat Gödel's argument.

For p = provable,

1. p(X) \to X
an assumption or definition, the quintessential meaning of mathematical proof
2. \neg p(Y) \to p(\neg Y)
an assumption that is true for all formal statements except independent ones
3. A: \neg p(A)
assumed to be true, to begin with (as Gödel claimed this was obviously the case)
4. \neg A: p(A)
the negation of (3), stated here but not assumed (we will use it immediately after we have deduced it)
5. A \to \neg p(A) \to p(\neg A) \to \neg A \to p(A) \to A
from (3) then (2) then (1), to deduce ¬A, then from (4) then (1)
6. A \to \neg A \quad \land \quad \neg A \to A
from (5)
7. (M \to \neg N \quad \land \quad \neg N \to M) \quad \equiv \quad (M \equiv \neg N)
can be seen by drawing a truth table
8. A \equiv \neg A
from (6) using (7)
9. A \equiv p(A)
from (8) and (4)
10. A: \ p(A)
a restatement of A that agrees with (9) but in which A is independent
11. (M \equiv \neg N) \quad \equiv \quad (\neg M \equiv N) \quad \equiv \quad (M \not\equiv N) \quad \equiv \quad \neg (M \equiv N)
can be seen by drawing truth tables
12. A \not\equiv A
from (8) using (11)
13. A \not\equiv \neg p(A)
from (12) and (3)
14. \neg ( \ A \equiv A \ )
from (8) using (11)
15. \neg ( \ A \equiv \neg p(A) \ )
from (14) and (3)
16. \neg ( \ A: \neg p(A) \ )
from (15) a rejection of the implicit equivalence inherent in the statement of A


So either the statement of A expresses an invalid equivalence, or (2) is an assumption that is rendered inapplicable because A must in fact be independent (in which case there is no rational basis for asserting that A is true and its negation is false or vice versa), or both the former and the latter (because the former does not exclude the latter).

However Gödel's argument relies upon A being obviously and uncontentiously true, but our deduction has cast a serious doubt upon that presumption. It would appear that A is only superficially true because for A to be true, the negation must be false, and this is not demonstrable since the negation claims that A is provable, i.e. that it is provable that A is not provable, which is perfectly "possible", by proving the negation for instance.

The result of our deduction therefore explains why even casual arguments for A (or its negation) cannot be sound ones.


The Ultimate Defeat of the First Incompleteness Theorem


--Vibritannia (talk) 17:31, 28 May 2008 (UTC)

Assumption 2 is true only for a complete theory.--Pokipsy76 (talk) 08:49, 1 June 2008 (UTC)
In an incomplete theory, assumption 2 would also be true for just those statements that are not independent.--Vibritannia (talk) 11:11, 3 June 2008 (UTC)

[edit] Inferences, Broken Symmetries, and True Statements

We can express a true statement S as an inference thus:

S \equiv S \land S
S \equiv (S \lor S) \land \neg (\neg S)
S \equiv (S \lor S) \land \neg (\neg S \lor \neg S)
S \equiv (\neg S \to S) \land \neg (S \to \neg S)
S \equiv (\neg S \to S) \land (S \not\to \neg S)

And similarly if the negation of S is true,

\neg S \equiv (S \to \neg S) \land (\neg S \not\to S)

So we have two potential inferences – one from the statement to its negation and the other from the negation to the statement. For any statement, we may have both, either one, or neither, thus:

For any statement S and its negation
S \to \neg S \neg S \to S S \mbox{ or } \neg S \mbox{ ?} Symmetry of inferences
T T absurd symmetrical
T F ¬S asymmetrical
F T S asymmetrical
F F independent symmetrical


Notice that true and false statements are only possible when the inferences are asymmetrical, and symmetry results in absurdity or independence – apparently two brands of meaninglessness.

It is believed that physical laws are the result of broken symmetries, and here we have discovered that true and false statements too are only possible when symmetry is broken.

It appears we have stumbled upon something deep.

(And it came to light because we realized there was something wrong with the First Incompleteness Theorem).

--Vibritannia (talk) 10:51, 3 June 2008 (UTC)


[edit] Interpretation Problem

There seems to be a disparity between the statement Gödel supposedly encoded and the one he actually encoded. We are supposed to be entertaining a statement that is true but unprovably so. Gödel encoded the equivalent of, for p = provable,

A: \neg p(A)

But notice that the definition of A is not strictly a definition because A appears on the right-hand side as well, and we never actually say what A is.

You can see the problem if you try to eliminate A on the right-hand side by substituting in its definition. Each substitution introduces a new A, and so you can never actually succeed. Even if you could perform infinite substitutions, it is not clear that the resulting statement should be interpreted as intended.

A appears to say that statements such as A are not provable, but without providing a concrete example of such a statement.

A looks like a sort of free variable. Instead we could write a new definition where the thing being defined does not appear in its own definition, and the freedom to replace the letter A with any letter is made explicit:

B(A): A \equiv \neg p(A)

Either B is true or its negation is, which says something very different from the negation of A,

\neg B(A): A \not\equiv \neg p(A)
\neg B(A): A \equiv p(A)


Gödel claimed that his proof was constructive, but he does not appear to have constructed precisely what he assumed he had constructed.

Is this just nitpicking, or is it a valid point?

--Vibritannia (talk) 12:36, 5 June 2008 (UTC)