Talk:Gödel's incompleteness theorems/Arguments/Archive 1

Gap in Gödel's proof

User:Biedermann, unless you can give a reputable source for there being a gap in Gödels proof, please don't write that in the article. You might wan't to read this for the official policy on the subject.

Rasmus (talk) 11:42, 14 November 2005 (UTC) Biedermann 15:59, 7 December 2005 (UTC) Let me try it again:

Well Sir, I guess, I put my arguments here on the TALK-page, not in the artikel, to give your readers a chance to TALK about these arguments. I cannot consider my stuff to be original research, it is just to point out the flaws in Gödels work. These arguments are so simple and straightforward that for everybody the most ‘reputable source’ should be his own best judgement. So I try to offer you my arguments once more in a more concentrated version. Biedermann 15:59, 7 December 2005 (UTC)

                    THE GAP IN GÖDELS PROOF
                                             

In the long sequence of the some 40 definitions introduced by Gödel (Über formal unentscheidbare Sätze der Princ. Math. 1931) for the construction of his famous Unprovable Formula, we find under numbers 16. - 17. the definitiion of Z(n) as ‘the Gödel number of the presentation of any whole number n’, which is given in Gödels Formal System through n-fold positioning of the symbol f in front of the symbol 0, so Z(4) is the Gödel number of ‘ffff0’. So far so good. But than, Gödel introduces, ( I follow here Nagel-Newman’s way of writing the formulae to get them on a single line of typing) after having defined the Gödel number of the symbol y to be 19, the formula (1): (x)~Dem(x,sub(y,19,Z(y))) , of which he claims to be able to determine the Gödel number n, by means of which he than proceeds, by substitution of n for y, to his famous formula (G): (x)~Dem(x,sub(n,19,Z(n)))

with its self-fullfilling interpretation of its own non-derivability.

However: what is Z(y)? From the above definition it should be the Gödel-number of the symbol sequence that results from the y-fold positioning of f in front of the symbol 0. But this certainly cannot be done! So Z(y) does not exist as a sequence of symbols of the System, and consequently no Gödel number of Z(y) can be determined, no Gödel number of formula (1) can exist, and formula (G) operates with a non-existing number n. So, formula (G) simply does not exist as a sequence of symbols of System S! That is

                   ==THE  GAP  IN  THE  PROOF==

• Another questionable aspect of Gödels reasoning shows up in the word-for-word definition of what the abreviation sub(y,19,Z(y)) is standing for: it reads (due to the definition of ‘19’ to be the Gödel number for the symbol y !):

‘’The Gödel-number of the term that results from the term with Gödel NUMBER y via substitution of the VARIABLE y by the representation of the NUMBER y ‘’!!!

Here the symbol y clearly appears in two different identities, yet, whoever wants to obtain consistent results in mathematics should not start with such ambivalent definitions! It is a common property of all not correctly constructed formulae as well as their negations not to be derivable from the axioms.

• I hesitate to say it bluntly, yet in the light of this analysis, the so enthusiastic acceptance of Gödels paper by the mathematic society appears now to be the BIGGEST BLUNDER that ever occured in modern science. Biedermann 15:59, 7 December 2005 (UTC) biedermann@clix.pt

In fact, the "gap" you have found is really an instance of how Godel's cleverness was able to circumvent the difficulties in making such a proof. Making a self-referential statement is not so easy!

In the statement (x)~Dem(x,sub(y,19,Z(y))), y is a free variable, which has its own value in the numbering system. Z is a recursive function, and so has a value as well. This is totally different from (x)~Dem(x,sub(n,19,Z(n))), where n is not a free variable, but rather a specific integer. Thus the value of Z(y) does not require knowing y; while the value of Z(n) is a function of the number n. So it's perfectly legit to talk about Z(n) where n = Godel number of Z(y). Hope this helps.--Luke Gustafson 11:25, 31 December 2005 (UTC)

Thanks for your comment Luke Gustafson, however, you haven’t convinced me yet: I perfectly agree: making a selfreferent statement is not so easy! But what you call Gödels cleverness, appears to me to be Gödels error, if not his lousy trick!

• Can you please be more specific about what you think the value of Z(y) to be. As I read Gödels definition it should be the Gödel number of the symbol sequence that results from y-fold positioning the symbol f in front of the symbol 0, what nobody is able do! The recursive function Z(), as defined by Gödel, is ranging over the natural numbers as arguments, and nothing else! certainly not over the various symbols of the System ~, = , < , v , or any of the place-holders y, x etc.!

• You have any comment to my argument about the ambiguous application of the symbol y, which is at the heart of Gödels tricks to produce the selfreference of his formula, and which clearly violates what we read on the first page of Principia Mathematica, that a chosen variable has to 'preserve a recognizable identity throughout the same context'!  ?

Biedermann 21:30, 1 January 2006 (UTC)

Biedermann 14:17, 3 January 2006 (UTC)

Z(.) assigns a number to a sequence of symbols. You can calculate Z(4), which happens to be 4 (or ffff0), Z(y), which is 19 (or fffffffffffffffffff0) or Z(19), which is not 19, but something calculated from 1 (or f0) and 9 (or fffffffff0). Oh, and Biedermann, how about you submit this to a peer-reviewed journal, hm? People there are far more qualified to ridicule Wanna-Be-Einsteins and Wanna-Be-Gödels. 88.73.225.37 00:09, 5 September 2006 (UTC)

Sorry, Nr.88.73.225.37, I just find your comment today, somebody moved the stuff to this well hidden Arguments page. Unfortunately I cannot agree with any of your statements: with Gödel’s definition, Z( ) assigns numbers to nothing else but symbol sequences of the kind ffffffff….0 ! Z(4) certainly is not (NOT!) = 4, it is the Gödelnumber of ffff0  ! Z(y) is NOT equal to 19, nor to Z(19), Z(19) is nothing else but the Gödelnumber of fffffffffffffffffff0 !!! Please read first Gödels definition of Z( ) ! and have a pleasant New Year! Biedermann 23:29, 7 January 2007 (UTC)

By the way, I submitted this stuff to many of those peer reviewed papers.

Instead of trying to ridicule me like you as a Wanna-be-Gödel they just tell me. 'That does not fit into the program of our paper'! They never try to give me any ARGUMENTS ! And when I insist,they just don't give any further answers! Biedermann 10:54, 8 January 2007 (UTC)

Self-contradiction in Gödel’s incompleteness theorems “proofs”

Kurt Gödel’s two incompleteness theorems are simply stated as follows:

In any consistent formal axiomatic system that is capable of encoding elementary arithmetic, there will always exist some “meaningful” statement such that neither it nor its negation can be proved within the system.

Within any consistent formal axiomatic system that is capable of encoding elementary arithmetic, there cannot exist any proof of the fact that the system is consistent.

In his so-called “proofs”, Kurt Gödel engaged a formalization of first-order theory that used the minimal set {negation, dusjunction, universal} as primitive logical connectives and quantifier as well as openly admitted that his bone-of-contention undecidable proposition “This assertion cannot be proved” gives a result that is analogous to Richard’s antinomy which is also closely related to the Liar’s antinomy or any epistemological antinomy (logical self-contradiction) while he implicitly invoked IsProvable("ForAllx.P(x)) --> ForAllx.IsProvable(P(x)), which is actually tantamount to invoking the specialization rule ForAll"x.P(x) --> P(x1) for some element x1 of the domain of discourse.

The self-contradiction folly in Kurt Gödel’s so-called “proof by contradiction” of his first incompleteness theorem is basically the same as that in Georg Cantor’s “proofs by contradiction” of his hierarchy-of-infinite-power-sets theorem and existence-of-uncountable-set diagonal argument (see my discussion text in Wikipedia articles “Cantor’s diagonal argument” and “Cantor’s theorem”) because Gödel’s first incompleteness theorem basically asserts that the set of all unprovable formulas of some formal axiomatic system T that encompasses Peano’s axioms for the natural numbers is “uncountable” --- that is, there is no one-to-one correspondence between the set of all natural numbers and the set of all unprovable formulas of T.

Nonsense. The set of formulas is countable, and so is the set of unprovable formulas, because there are obviously less of them. You probably meant enumerable, which is something entirely different. 88.73.225.37 00:37, 5 September 2006 (UTC)

Gödel’s bone-of-contention set is the non-completely constructible indeterminate infinite proper subset K of the set N of all natural numbers that he defined as --- n is in K if and only if ~(Bew[R(n);n]) --- where Bew[x] means x is a provable formula and [R(n);n] designates the formula derived on replacing (by the sign for the natural number n) the free variable of the nth formula in the enumeration (defined by the ordering R) of all the formulas with just 1 variable. Kurt Gödel claimed that “there is a class-sign S such that the formula [S;n] --- interpreted as to its content --- states that n is in K” (he merely vacuously claim that “there is not the slightest difficulty in actually writing out the formula S”). Being a class-sign, S = R(q) for some q in N and the metamathematical formula [R(q);q] asserts its own unprovability --- “as soon as one has ascertained the formula S, one can naturally also determine the number q, and thereby effectively write out the undecidable proposition itself”.

If P is a provable formula (say, one of the axioms) in a formal axiomatic system T, then T is inconsistent if and only if ~P is provable in T or, equivalently, T is consistent if and only if ~P is not provable in T. Hence, the same self-contradiction folly arises in a “proof by self-contradiction” of Gödel’s 2nd incompleteness theorem that purports to demonstrate a recursive formula which expresses in T the unprovability of ~P.

For a first-order theory formalization T that uses Fregean logic’s definition of material implication [P --> Q = ~P OR Q = ~(P AND ~Q) with no implicit existential import for universal quantification] and encompasses the Peano axioms for arithmetic (that is, includes mathematical induction as one of its axioms) --- if T is inconsistent then T is complete and if T is consistent then T is incomplete. These assertions immediately follows from these general facts ---

Material implication (P --> Q) is defined to be true when P is false or Q is true (that is, ~P OR Q). Hence, if P is false then both P --> Q and P --> ~Q are true at the same time and in any respect (that is, without regard for any material relevance in the relationship of P to Q or ~Q) — therefore, the propositions P --> Q and P --> ~Q are not contradictories because there is a condition when they are both true at the same time.

In particular, the first-order mathematical logic formulas ForAllx(fx --> gx) [that is, “All S is P”] and ForAllx(fx --> ~gx) [that is, “All S is non-P”] do not form a contradiction when ~ThereExistsx.fx holds [that is, if there is no S].

The self-contradiction formula fx AND ~fx (regardless of the actual interpretation for x and f) is always a false proposition and any such specification serves to define the empty set --- that is, ~ThereExistsx.fx is true (there is no x that satisfies f).

The Liar’s antinomy self-contradictory statement “This sentence is false” does in fact exist. What must be stressed is that it is not a proposition (that is, some statement which is exactly either true or false --- not neither, not both) at all being (brought forth by its self-referencing signification) both true and false at the same time and in the same respect. In contrast, in the self-contradictory proposition “A is true AND A is false” (without the self-reference attribute) where A is a variable for an element (if it exists) of the set S of all reasonable sentences, there is no sentence A that satisfies the proposition so the latter’s range of significance is the empty set.

The following equivalences hold between quantified formulas ---

ThereExistsx.fx = ~ForAllx.~fx

ThereExistsx.~fx = ~ForAllx.fx

~ThereExistsx.fx = ForAllx.~fx

~ThereExistsx.~fx = ForAllx.fx

By definition, universal and existential quantification mean ForAllx.fx = fx1 AND fx2 AND ... AND fxn and ThereExistsx.fx = fx1 OR fx2 OR ... OR fxn, respectively, where x1, x2, ..., xn (n is in N) are all the countable elements of the domain of discourse. The instant author firmly believes that he has sufficiently refuted any claim (available in the mathematical literature) for existence of an “uncountable” set --- even so, the generally accepted Löwenheim-Skolem theorem guarantees that if any first-order theory has a model then it has a countable model.

De Morgan’s laws state ---

~(fx1 AND fx2 AND ... AND fxn) = ~fx1 OR ~fx2 OR ... OR ~fxn

~(fx1 OR fx2 OR ... OR fxn) = ~fx1 AND ~fx2 AND ... AND ~fxn

Even if n --> infinity (that is, n could be made arbitrarily large as one pleases but remains finite), the truth of ThereExistsx.fx is amply established by just being satisfied by any one of the elements xi (i in N) in the domain --- the truth of fxj for every j > i (j in N) are no longer significant while the truth of ForAllx.fx is established only when the truth of fxj for every i in N could be ascertained --- in many cases, the entire truth of ForAllx.fx could be established through mathematical induction by demonstrating that fx1 is true and fxi+1 is true whenever fxi is true.

Just by a simple understanding of the preceding facts, one can immediately deduce Gödel’s 1st incompleteness theorem from the negation relations between ThereExists (the individual parts) and ForAll (the whole) or between the compound disjunction of all elements in the domain and the entire compound conjunction formula of all the negatives of every element in the domain relative to the incompleteness of a countably infinite domain.

In other words, if the truth of at least one fxi (i in N) could not be established (say, mathematical induction is incapable to assert the truth of ForAllx.fx), then ThereExistsx.fx = fx1 OR fx2 OR ... OR fxn-->infinity and its negation ~ThereExistsx.fx = ForAllx.~fx = ~fx1 AND ~fx2 AND ... AND ~fxn-->infinity could not both be proved in some formalization of first-order theory that engages the minimal set {negation,disjunction,conjunction,ThereExists,ForAll} for primitive logical operators and quantifiers. The Goldbach’s conjecture (modified by Euler — every even integer greater than 2 is the sum of two prime numbers) and the Twin prime conjecture (there exists infinitely many prime number pairs p and p+2) are only two of the most popular undecidable problems of number theory simply because the potentially infinite set N of all natural numbers cannot be completed.

Gödel’s 2nd incompleteness theorem immediately follows from the fact that the negation of any axiom of a first-order theory T is a self-contradiction which, by the formulation of the system, is not satisfiable or provable in T if T is consistent. In particular, the negation of mathematical induction could not be established in any first-order theory that invokes it as an axiom --- in fact, the instant author includes mathematical induction (which is equivalent to the well-ordering principle of the natural numbers --- hence, the pre-existence of the natural numbers prior to any mathematical object including a set) as one of the first principles of demonstration together with Aristotle’s 3 “laws of thought” (principles of identity, excluded middle & non-contradiction) and contraposition (which checks infinite regress of justified reasoning).

Statement and predicate calculus, as well as first-order theories that encompass them, could be independently formalized from some preferred minimal set of operationally complete logical operators and quantifier(s). The so-called independence of the Axiom of Choice and of the Continuum Hypothesis (which should be actually interpreted as the incompleteability of N) follows from the disparate formalizations of predicate calculus that do not include both ThereExists and ForAll as primitive quantifiers and more than one of negation, conjunction, and material implication as joint primitive logical operator with negation.

The drawback of employing only one quantifier along with negation and one logical connective is in the inexpressibility of a negated quantified and|or compound formula to an equivalent formula with all the negations ultimately brought down to the atomic formulas or prime constituents level.

In his paper, Kurt Gödel used the minimal set {negation, disjunction, ForAll} as primitive logical operators and quantifier for his base formal axiomatic system --- this choice has the downsides that ForAll is not distributive over disjunction and that invoking a rule of specialization from universal quantification would be irreconcilable with its not having an existential import and with his rule of immediate consequence: ~B OR C, B yields C (which is indeed equivalent to the rule of inference modus ponendo ponens: B --> C, B yields C).

In the formalization of predicate calculus and first-order theory, the most far-sighted choice for primitive logical operators and quantifier would be the minimal set {negation, disjunction, ThereExists} for at least the following reasons ---

ThereExists has distributive property over disjunction --- ThereExistsx.fx OR ThereExistsx.gx = ThereExistsx(fx OR gx) --- that is, an equivalent formula results if all the ThereExists of a given formula are moved in front of all its subformulas;

ThereExists is already implicit with the mandatory prescription of a non-empty domain for each model of any first-order theory so all occurrences of ThereExists could actually be dropped from any formula of the theory;

every well-formed formula of the theory is guaranteed to be satisfiable --- there will be no self-contradiction since ThereExistsx.~(fx OR ~fx) is not a well-formed formula; and

there is no “paradox of ~fx OR gx” and “proof by contradiction” could be freely applied.

Please read my discussion text in Wikipedia articles “Reductio ad absurdum” and Entscheidungsproblem”. [BenCawaling@Yahoo.com – 10 February 2006] —The preceding unsigned comment was added by 125.212.72.91 (talk • contribs) .

PCE's doubts

The following text was posted to my discussion page on 3 May 2006 by User:Pce3@ij.net after I reverted an edit by User:209.216.92.232. I post this text here because I think it should be discussed here, and not on my discussion page. --Aleph4 10:40, 4 May 2006 (UTC)

I apologize but to placate a previous reverter who was mistakenly concerned about copyright violation I only provided a link to the proof being refuted although Rudy Rucker has since emailed permission to publish his proof under the GFDL.

However, allow me to address your reasons for your reversion first:

Truth of arithmetical sentences is always subject to the discovery of error in special cases if for no other reason than the fact that exceptions are always subject to exception.

Theorems themselves must be open to consideration of special cases or they loose their validity from the start. Consequently if you deny that Gödel's theorem in Rudy Rucker's example has anything to do with discrete and continuous time you automatically invalidate either your position or Gödel's theorem or both.

Perhaps you did not follow the link and read Rudy Rucker’s proof so I will post it here followed by my refutation:

An Outline of Gödel’s Incompleteness Theorem and its Proof

(From Rucker, Infinity and the Mind .)., .....(Reprinted here with permission of the author under the GFDL.)

1. Someone introduces Gödel to a UTM, a machine that is supposed to be a Universal Truth Machine, capable of correctly answering any question at all.
2. Gödel asks for the program and the circuit design of the UTM. The program may be complicated, but it can only be finitely long. Call the program P(UTM) for Program of the Universal Truth Machine.
3. Smiling a little, Gödel writes out the following sentence: "The machine constructed on the basis of the program P(UTM) will never say that this sentence is true." Call this sentence G for Gödel. Note that G is equivalent to: "UTM will never say G is true."
4. Now Gödel laughs his high laugh and asks UTM whether G is true or not.
5. If UTM says G is true, then "UTM will never say G is true" is false. If "UTM will never say G is true" is false, then G is false (since G = "UTM will never say G is true"). So if UTM says G is true, then G is in fact false, and UTM has made a false statement. So UTM will never say that G is true, since UTM makes only true statements.
6. We have established that UTM will never say G is true. So "UTM will never say G is true" is in fact a true statement. So G is true (since G = "UTM will never say G is true").
7. "I know a truth that UTM can never utter," Gödel says. "I know that G is true. UTM is not truly universal."

With his great mathematical and logical genius, Gödel was able to find a way (for any given P(UTM)) actually to write down a complicated polynomial equation that has a solution if and only if G is true. So G is not at all some vague or non-mathematical sentence. G is a specific mathematical problem that we know the answer to, even though UTM does not! So UTM does not, and cannot, embody a best and final theory of mathematics ...

Although this theorem can be stated and proved in a rigorously mathematical way, what it seems to say is that rational thought can never penetrate to the final ultimate truth ... But, paradoxically, to understand Gödel's proof is to find a sort of liberation. For many logic students, the final breakthrough to full understanding of the Incompleteness Theorem is practically a conversion experience. This is partly a by-product of the potent mystique Gödel's name carries. But, more profoundly, to understand the essentially labyrinthine nature of the castle is, somehow, to be free of it.

The Incompleteness of Gödel‘s Incompleteness Theorem

The problem with the above construct is that finite time is discrete and effect must follow cause. If G may be either true or false then what is to stop G from being true at one point in time and false at another point in time? Consequently if we ask the UTM whether G is true or false and the UTM says that G is false and G becomes as the result true then the error we have made is in applying the outdated answer to the resulting state of G rather than laboring to ask the question again. If we ask the question again then the UTM will answer that G is true and G will once again change states and become false. The above construct simply points out the discretion of time and that effect follows cause. If we are going to expect a universal answer from a universal truth machine then we must provide it with a universal rather than a discrete question. The result of this understanding is in fact the principle behind the bistable multivibrator or flip-flop. (Computer Circuits for Experimenters by Forest M. Mims, III, Radio Shack, a Tandy Corporation, 1974, Page 17.)

What a UTM would most likely say to such a discrete question is that G will be true until UTM answers the question that G is true at which time G will become false and vice versa.

-- PCE 19:45, 3 May 2006 (UTC) —Preceding unsigned comment added by Pce3@ij.net (talk • contribs) 19:45, 3 May 2006

End of PCE's edit to my discussion page --Aleph4 10:40, 4 May 2006 (UTC)

Aleph4 answers: You write The problem with the above construct is that finite time is discrete. But time does not appear at all in Gödel's construction. Just like Gödel's smile, time is not part of Gödel's theorem, it appears only as Rucker's embellishment.

But that is my very point. With the consideration of time Gödel is blown apart. Time must be considered or Gödel is blown apart. If time is not considered Gödel is blown apart. You can simply not say that A follows B without the consideration of time. -- PCE 20:57, 5 May 2006 (UTC)

Yes I can. For example, the statement "If A and B holds, then B holds" is true, and does not depend on time at all. Aleph4 16:54, 6 May 2006 (UTC)

But saying it does not make it a valid statement. How do you know that such a statement was or will be or is valid in the presence of a singularity or are you suggesting that the validity of your statement is dependent upon the exclusion of a singularity, i.e., does not apply during the event or case of a singularity? --- PCE 17:48, 6 May 2006 (UTC)

The sentence G does not "become true"; it IS true, just like the sentence "there is a natural number n such that n+17=1023 is true. It does not start out as false, and "becomes" true when you (or somebody) actually finds such an n.

Aleph4 10:40, 4 May 2006 (UTC)

Consider the case of Einstein’s equation E=mc². You can say there is an equation which equates energy to matter that is apparently independent of the consideration of time. But what about prior to the Big Band? Would Gödel say that since our knowledge of the physics of a singularity is incomplete that Einstein’s equation could be false at a certain point in or prior to time? To consider the validity of incompleteness in this example one must consider time. What example of incompleteness can you show me in which consideration of time is not required in the consideration of incompleteness? Or are you saying that Gödel's Incompleteness Theorem applies only to theoretical mathematics but not to applied mathematics as well? -- PCE 21:36, 5 May 2006 (UTC)

See falsifiability for a crucial difference between the laws of physics and theorems in mathematics. The laws of physics are not "proved" in the same way that mathematical theorems are.

Gödel's theorem applies, in the original version, to "Principia Mathematica", but there are many generalisations that apply to other axiomatic systems (such as ZFC) or other formal constructs (such as Turing machines). I am not sure where the borderline between Theoretical/Pure Mathematics and Applied Mathematics is precisely, but it seems clear that Gödel's theorem is a theorem of pure mathematics.

Aleph4 16:54, 6 May 2006 (UTC)

Would you agree or disagree that the presence of time in physics and the absence of time in pure mathematics is the only difference between the two? -- PCE 18:18, 6 May 2006 (UTC)

Disagree. I don't see how this is related to the article we are discussing here. Aleph4 19:35, 6 May 2006 (UTC)

Fortunately no relation to "Dr. Ray" as suggested below! If you look at the edits I made to this question you will see that I was struggling to phrase my question. What I thought we were searching for was a common denominator for physics and pure mathematics so that whatever it was could be used to better understand or explain the role of time in connection with the Theorem. I am trying to approach the idea in a very benign manner that time is the missing link or the item of incompleteness in the Theorem. Once you include time the incompleteness goes away and the Theorem is dismissed. On the other hand if you do not include time then you are saying that pure mathematics only exists in the context of timelessness or no time or for all time or time standing still or in essence the criteria, in regard to time, of a singularity. Please accept the thought that although I likewise have a sense of humor I am not trying to use it to be absurd. -- PCE 22:22, 6 May 2006 (UTC)

Time cube! -lethe ^{talk +} 20:57, 6 May 2006 (UTC)

As an Inclusionist I can not ignore such concepts since some glimmer of truth might be garnered from their consideration following a simple transposition of words. For instance: what happens to this concept if you replace the word "time" with the word "change"? One must be careful when dispensing the bathwater to the back yard that the baby has first been placed safely in its crib. -- PCE 19:36, 8 May 2006 (UTC)

Change cube! -lethe ^{talk +} 19:53, 8 May 2006 (UTC)

Your revertion... Gödel Incompleteness Theorem

The following was copied by me from my talk page. Paul August ☎ 12:45, 4 May 2006 (UTC)

Start of copied text

The proof which I reproduced and referenced on the page is published in print as well as online at many, many websites so I doubt there would be a copyright violation if the proof were published here. I just have not had time to see if it is already published in the Wikipedia but may have time later. The purpose for including the text of the proof in the body of the article is simply to make it easier for the reader to follow the refutation. Although not as easy to follow I have included a link to an external website where the proof is published and I will not revert your deletion of the proof on the body of the article unless or until a Wikipedia reproduction is found.

The refutation however is not copyrighted and is submitted in accordance with the GFDL -- PCE

Hello. The proof outline you inserted is copied verbatim from Infinity and the Mind by Rudy Rucker, which is copyrighted text, publishing it in Wikipedia could be a copyright violation. Your "refutation" is an apparent violation of WP:NOR. Paul August ☎ 13:11, 3 May 2006 (UTC)

Original Message From: "Rudy Rucker" <rudy@rudyrucker.com> To: "Honesty is the BEST policy." <pce3@ij.net> Sent: Wednesday, May 03, 2006 10:20 AM Subject: Re: Permission to reproduce Godel Incompleteness Theorem proof

I don't mind if you quote this page; I think it's all over the web anyway. Do look at a printed copy of the book and make sure you've quoted it accurately, as typos may have crept in.

I also notice you say you want to "refute" the theorem. I am absolutely certain that your refutation will be fallacious. You have no idea how many people have written me over the years with incorrect refutations! One thing to keep in mind is that my passage is only a suggestive summary of the argument, which is a bit more refined. When you have the entry up, send me a link, so I can add a comment defending myself and Godel, should I have the inclination and the time.

Thanks for your interest in my work,

Rudy R.

At 02:34 AM 5/3/2006, you wrote: >Hi Rudy, > >I would like to ask your permission to reproduce >the following excerpt from your book: Infinity >and the Mind. under the GNU license at the >Wikipedia site: >http://en.wikipedia.org/wiki/Wikipedia:Text_of_the_GNU_Free_Documentation_L icense >so that it will be easier for readers to follow >a discussion of the proof's refutation. If this >is okay please reply and if not then I will >simply rely upon an external link to a site where it can be found. > >Thanks,

-- PCE 02:47, 4 May 2006 (UTC)

see User_talk:Trovatore#Godel and User_talk:Aleph4#Your_reversion_of_G.C3.B6del for other places this discussion is taking place (might be nice if all three discussions were moved to the talk page). -lethe ^{talk +} 02:56, 4 May 2006 (UTC)

Wikipedia is not a place for you to carry out a conversation about your refutations of an author's work. Your refutation is original research, and so is not allowed. If you want to get comments on why your refutation is wrong, we'd be happy to help you at Wikipedia:Reference Desk/Mathematics. -lethe ^{talk +} 02:58, 4 May 2006 (UTC)

• In regard to the WP:NOR it appears that in terms of items 1,2,4,5 you may very well be right so I will exclude my refutation until such time as I can meet items 7 using a "reputable" publication or item 5 using something other than the validity of the refutation itself. -- PCE 03:33, 4 May 2006 (UTC)

Good. Paul August ☎ 12:23, 4 May 2006 (UTC)

End of copied text

To Summarize

The absence of the quality of impermanence in pure mathematics is the reason for incompleteness in Gödel's Incompleteness Theorem. -- PCE 01:58, 8 May 2006 (UTC)

Reals and Complexes are sets with complete Axiomatizations ?

The sentence "For example both the real numbers and complex numbers have complete axiomatizations" appears in the "misconceptions" part.

I don't believe this.

These are supersets of the natural numbers. The proof uses natural numbers as a lower-bound on the complexity. How are these sets less complex than the natural numbers?

--168.230.48.248 03:53, 23 June 2006 (UTC) (Andrew)

There's a complete axiomatization for the first-order theory of the real numbers in a language that has only plus and times. The natural numbers are a subset of the reals, but in that language they're not a definable subset. But I agree that the sentence is misleading as stated, since the limitation on the language is not mentioned. As I've said before, I think we should junk the entire section in which that sentence appears; "misconceptions" sections are likely to do more harm than good, especially on a topic like this one, where informal descriptions can be read in so many ways. --Trovatore 05:42, 23 June 2006 (UTC)

Oh. So, the added flexibility of the Reals allows for an axiomatic construction that is less "complex" the axiom system for the Naturals. I guess, but in these systems, there's no way to say "x is a natural number" ? If you can construct the reals, you get the naturals for free, right? 68.107.109.7 17:56, 23 June 2006 (UTC) (Andrew)

The natural numbers are a subset of the reals, but in that language they're not a definable subset appears to be the answer. This is incomprehensible to me. This is completely incomprehensible to me. How can a formalized axmiomatic system contain natural numbers without defining them? 0 and 1 are real numbers. Can't you "define" any natural number as the subset or Real numbers, whis is constructed by subsequently adding 1 to 0? --Kikl 20:01, 23 July 2006 (UTC)

Adding 1 to itself how many times? The answer is a natural number of times, so that definition doesn't work. There's no way to say "x is an integer" using only the axioms of the real number system. —Keenan Pepper 20:20, 23 July 2006 (UTC)

Keenan's answer is excellent, but misleading on one important point; it confounds axiomatics with semantics. It's the language that's inadequate to express the notion "x is an integer", not the axioms. --Trovatore 20:34, 23 July 2006 (UTC)

Why is the language inadequate to express the notion "x is an integer". The only symbols I use are 0, 1 and +. All of these symbols should be part of the language? --Kikl 20:46, 23 July 2006 (UTC)

OK then, let's make it an exercise. Let's see your first-order formula φ, written with only those non-logical symbols (you're also allowed first-order quantifiers, logical connectives, and the equals sign) such that φ(x) holds in the reals if and only if x is an integer. --Trovatore 20:51, 23 July 2006 (UTC)

I'm sorry, I don't want to perform excercises. I would just like to know why it is impossible to define a natural number, if there is a definition for all the real numbers? My point was simply: 0 is a natural number. If x is a natural number then x+1 is a natural number. I think that should cover all the natural numbers. --Kikl 21:00, 23 July 2006 (UTC)

I don't know exactly what you're asking when you ask "why it's impossible". It can be proved to be impossible (precisely by noting that there's a complete axiomatization for the first-order theory of the reals, but not for that of the naturals), but that doesn't seem to be what you're after–rather, you seem to have a candidate in mind for the definition, but you won't tell us exactly what it is. What you've written above is not a definition in the relevant sense; the relevant kind of definition is the one I asked you to produce. Where do we go from here?

This is going above and beyond on my part, but here's a guess as to what you might have in mind: You might want to make a definition like

$x{\textrm {~is~a~natural~number~}}\iff x=0\lor x=1\lor x=1+1\lor x=1+1+1\lor \ldots$

The reason this try doesn't work is the dot dot dot part. We're not considering infinite formulas here (though there are other contexts in mathematical logic where they are considered. Is that what you had in mind? --Trovatore 21:10, 23 July 2006 (UTC)

The issue is not abstract definability of the natural numbers; it is definability in a certain first order language that is being referred to. This is impossible because of the following fact: for any first-order formula in the language of ordered fields with one free variable, the set of reals that satisfy that formula is a finite union of open (possibly unbounded) intervals and points. This follows from Tarski's quantifier elimination theorem for real closed ordered fields - the definable sets are exactly the sets definable with no quantifiers. The proposed definition in the previous post cannot be expressed as a first order formula in the language of ordered fields. I agree with Trovatore that the misconceptions section is not helpful. Perhaps a section on limitations would be more appropriate. I'll try to edit it later today unless someone beats me to it. CMummert 21:18, 23 July 2006 (UTC)

Thanks a lot Mummert. I will have to take a close look at Tarski' theorem. The main point seems to be that "the definable sets are exactly the sets definable with no quantifiers". Good day. --Kikl

I think that a lot of model theory texts have a proof of quantifier elimination for real closed ordered fields; I don't think that it is an obvious fact. It does establish that the natural numbers are not definable as a subset of the reals using the first order language of ordered fields. Simpson's online lecture notes have a proof: http://www.math.psu.edu/simpson/courses/math558/ . The property about definable sets being finite unions of intervals and points is called O-minimality; the real line with the language of ordered fields is the most famous example of an o-minimal structure. CMummert 22:21, 23 July 2006 (UTC)

To Kikl: You asked whether you could define the Natural numbers as the subset of the Real numbers which is constructed by repeatedly adding 1 to 0. The answer is NO, because you would need to talk about subsets of the Real numbers to do so. However, the language of the Real numbers does not include the element relationship nor any other form of higher order logic which would allow you to talk about such sets. Nor can you talk about sequences of Real numbers of indefinite length in that language. You also said "...I don't want to perform exercises.". If you do not work mathematics problems, you will never become good at mathematics. JRSpriggs 02:45, 24 July 2006 (UTC)

Hi JR, thanks for your benevolent advice and elaborate explanation. So you can't define subsets in any form of higher order logic? Kikl 06:35, 24 July 2006 (UTC)

Of course people are free to use higher order logic if they wish. Gödel's theorems only apply to first order theories, however, and because of the nature of higher order logic I think it is unlikely that any similar theorem will ever be proved in that context. In particular, there is no sound, effective, and complete proof system for higher order logic as there is for first order logic; Gödel's theorems rely on the effectivity of the proof system to represent it within arithmetic. This limits the effects of these theorems to first order theories. As the discussion above shows, there is a first-order theory that has the real numbers as a model and yet does not satisfy the hypotheses of Gödel's theorems. What Kikl's proposed definition of the natural numbers could try to show is that the second order theory of the real line (with full second order semantics) is not complete, because Gödel's theorems can be made to apply to it. Any incompleteness of the real line, as a second order theory, will be of a set theoretic rather than arithmetical nature. CMummert 13:48, 24 July 2006 (UTC)

I am sorry that my reference to higher order logic was unclear. Set theory grew out of higher order logic. If higher order logic were applied to the Reals, one could define the natural numbers and encode the meta-mathematics of such a theory within itself. Consequently, it would have to be either incomplete or inconsistent. Contrary to CMummert, Gödel intended to apply his theorem to the system of "Principia Mathematica" by Russell and Whitehead which uses typed (i.e. higher order) logic. JRSpriggs 06:50, 25 July 2006 (UTC)

The theory of Peano arithmetic in second order logic is categorical (has only one model) and is therefore complete; Gödel's theorem does not apply to it. Thus even though the natural numbers are definable inside the reals using second order logic, this does not automatically mean that Godel's theorem will apply there. In fact, using full second order logic (quantifying over all finitary relations), the theory of any infinite structure includes the second order theory of Peano arithmetic; the reals are not special in this regard.

The problem is that we're using different notions of higher order logic; I mean higher order semantics. Typed systems are typically studied in first order logic using Henkin models. For example second order arithmetic is usually studied as a first order theory. I am not familiar with Principia Mathematica but I was under the impression that it used a first-order theory with infinitely many types. CMummert 11:55, 25 July 2006 (UTC)

I think someone is confused or we are talking at cross-purposes. After reading your earlier post, I had a good read of "On formally undecidable propositions of principia mathematica and related systems I" to see if there was anything in what you said. As far as I can see, Godel does not rely on any specifically first-order properties (such as compactness). His theory will go through for any formal system which has enough arithmetic to model recursive functions (as we all know PA with + and * is enough), and it shows that there is at least one sentence which is undecidable within the theory.

Now in SOL you can write down axioms that are categorical for arithmetic, but there are still Godel sentences in SOL. The fact that there is only one model for arithmetic doesn't mean you have written down a system that can internally decide all its own sentences. The fact that one can prove externally that all sentences are decidable is neither here nor there (in other words I fear you are muddling internal and external logics).

This can be shown simply and directly for SOL: Godel's first theorem shows that the truths of arithmetic are not recursive. That SOL with full semantics can categorically describe arithmetic, shows that its sentences cannot be recursively decidable (else contradiction). Remember Godel's theorem works by contradiction (it is the halting problem in disguise): *if* you could decide all sentences in SOL, then I can model that decision process as a predicate and by diagonalisation produce an undecidable sentence. That you can't decide all sentences in SOL doesn't contradict that logic (obviously not). Francis Davey 14:49, 25 July 2006 (UTC)

I agree that we may be talking at cross purposes. My point is just that the consequence of Gödel's theorem that any sufficiently strong effective first order axiomatization of arithmetic is either incomplete or inconsistent does not generalize to the second order setting. Consider the case of second order PA. There are indeed Gödel sentences for this theory, but these are logically implied by the finite list of second order axioms of PA. There are no logically independent sentences for second order PA, not even the Gödel sentences. The fact that logical implication does not correspond to provability in the second order setting is the crucial issue. This is why Gödel's theorem doesn't apply there, because there is no effective concept of provability for second order logic that captures logical implication. In particular, the step of Gödel's proof where he (correctly) goes from the unprovability of a Gödel sentence to the conclusion that it is independent of a first order theory is not valid in higher order settings. CMummert 16:29, 25 July 2006 (UTC)

I don't know whether I can still follow you. My gutt feeling is closer to Davey. His opinion corresponds to my rudimentary understanding of Gödel's theorem. Mummert's statement is quite puzzling to me: "The fact that logical implication does not correspond to provability in the second order setting is the crucial issue." This seems to imply that a sentence may be proven (provability) within second order logic, whithout showing that the sentence can be inferred from the axioms and logical rules (logical implication) or vice vera. My common sense sais: If the sentence can't be proven within the language then it is not a logical implication within the language. Don't trust common sense! That's just mind-boggling. Kikl 19:25, 25 July 2006 (UTC)

When I say logical implication I mean it in the sense of Symbolic_logic#Logical_implication_and_truth. Thus φ logically implies θ if and only if there is no model in which φ is true and θ is false. A theory is complete if it logically implies φ or the negation of φ for every sentence φ in its language. A consequence of Gödel's completeness theorem is that if φ and θ are first order sentences in the same language then φ logically implies θ under first order semantics if and only if $\phi \vdash \theta$ (equivalently, $\vdash \phi \rightarrow \theta$). In the second order situation these provability conditions are sufficient for φ to logically imply θ but not necessary. Worse yet, there is no recursively enumerable set of sound inference rules that suffice to reduce second order logical implication to provability. Gödel's incompleteness theorem establishes incompleteness by showing instead that there is a formula that is neither provable or disprovable, which is not enough to establish incompleteness in the second order setting. CMummert 20:11, 25 July 2006 (UTC)

Hi Mummert, thanks for taking your time and all the explanations. Hmmm, due to Gödels completeness theorem for first order logic all logically valid formulas (true sentences) are provable (deducable within a finite number of steps). The you write: "In the second order situation these provability conditions are sufficient for φ to logically imply θ but not necessary." I guess this just means that second order logic may prove more than first oder logic, since it is an extension of first order logic. " Gödel's incompleteness theorem establishes incompleteness by showing instead that there is a formula that is neither provable or disprovable, which is not enough to establish incompleteness in the second order setting." This only makes sense to me, if the expression provable or completeness are used in different senses in first and second order logic. In my opinion, a reasonable sentence, which may neither be proven or refuted is proof of the incompleteness of a theory. How can a theory be called complete, if it contains sentence, which are neither provable nor refutable? But, I'm really not the expert in this field, which you seem to be. Therefore, I'll continue reading Mr. Simpson's lecture notes, until I understand Tarski's theorem. Good day. Kikl 23:52, 25 July 2006 (UTC)

It may seem that the definitions are different, although they are not, because completeness is defined in terms of the semantic concept of logical implication, which is equivalent to provability in first order logic and not equivalent to provability in higher order logic. Tarski's theorem, by the way, is for the first order theory of real closed ordered fields, not the second order theory. The second order theory of the real line, in the language of ordered fields, is extremely uncomputable. CMummert 00:15, 26 July 2006 (UTC)

Well, your definition of completeness is: "A theory is complete if it logically implies φ or the negation of φ for every sentence φ in its language." This definition does not use semantic concepts. In the next paragraph you say: "... completeness is defined in terms of the semantic concept of logical implication..." There seems to be a logical problem here. How do you like this definition of completeness: ":$\Gamma \vDash \varphi \Longleftrightarrow \Gamma \vdash \varphi$" ? —Preceding unsigned comment added by Kikl (talk • contribs)

That is an independent, different meaning of the word completeness. Every first order theory T has the property that $T\vDash \phi \Leftrightarrow T\vdash \phi$; there is no incomplete first order theory if that is what you mean by complete. As the article Symbolic_logic#Logical_implication_and_truth explains, logical implication is a semantic notion: T logically implies φ means $T\vDash \phi$. CMummert 13:03, 26 July 2006 (UTC)

Yes, its a bit unfortunate that completeness (of a logic) and completeness (of a theory) are really two different animals. Hence an attempt to say semantic completeness and negation completeness to try to distinguish the two. Francis Davey 21:18, 27 July 2006 (UTC)

Incompleteness of second order logic

CMummert said "The theory of Peano arithmetic in second order logic is categorical (has only one model) and is therefore complete; Gödel's theorem does not apply to it. ... The problem is that we're using different notions of higher order logic; I mean higher order semantics.". Second order logic is incomplete. As it correctly says in "Gödel's completeness theorem", "The completeness theorem is a central property of first-order logic that does not hold for all logics. Second-order logic, for example, does not have a completeness theorem.". CMummert's argument using categoricity is invalid because it assumes incorrectly that second order logic is complete. He tries to weasel out of this by referring to "higher order semantics", but that amounts to assuming that we have a complete axiomatization of higher order logic. Yes, if we take the Platonist view that mathematical objects really exist, then there is a complete consistent second order logic, but it is not recursively enumerable and therefor useless in practice. Any really usable second order logic must be recursively enumerable and thus incomplete or inconsistent. JRSpriggs 07:14, 26 July 2006 (UTC)

I am using the completely standard definition of second order logic: there is a language as in first order logic, but now there are for each signature of finitary relation on the domain:

• variable symbols for that signature (arity and type of variables) of relation
• a pair of quantifiers for that signature of relation
• syntax to ask whether some tuple of elements satisfies a particular relation

The semantics of second order logic force these quantifiers to quantify of all of the appropriate relations (unlike Henkin models, which are the first order analogue of this). This logic has a long history and has been thoroughly investigated; I didn't make it up. The question of whether it is useless is neither here nor there; at least, I can say that a great deal of attention has been paid to it. The fact that it has no effective, complete proof theory is not relevant to Gödel's incompletness theorem because incompleteness is a semantic notion.

To clarify a bit here, CMummert is using full semantics for his second order logic. That is not forced by the axioms, but rather by a choice of range for the relation variables. There is no way to force, using a formal system, categoricity in that way. SOL manages to obtain categoricity by using full semantics -- i.e. by making an a priori selection of models (only full models). That's entirely valid.

Where I part company with CMummert is the question of what the incompleteness in the title of the article is about. Godel's proof (read it and see) is all about the undecidability of certain propositions in a formal system. If you present SOL as a formal system (with any axioms and rules of inference you like, provided they are recursively axiomatisable), I can produce a Godel sentence in that system, which is undecidable. In other words SOL is not negation complete. That sense of completeness (which is not a semantic one) is really close to what Godel was trying to do.

Now we know that there is no effective proof system for SOL with full semantics, and one way to prove it is via Godel's incompleteness theorem for any formalisation of SOL, which shows that there is no recursive formalisation of the system intended.

Of course there is no Godel sentence about the naturals within SOL with full semantics because one can construct a categorical model of PA within SOL, but that is really not the same thing as saying that Godel's incompleteness theorem doesn't apply - it does. I say again, there is nothing in Godel's paper that assumes first orderizability. Francis Davey 16:55, 26 July 2006 (UTC)

I agree that first order logic is only required for the conclusion that any sufficiently strong theory of arithmetic is either inconsistent or incomplete. That is, the following statement taken directly from the article is only true in the setting of first order logic:

For any formal theory T including basic arithmetical truths and also certain truths about formal provability, T includes a statement of its own consistency if and only if T is inconsistent.

This statement is false for the second order theory of Peano arithmetic, which includes its consistency statement (along with every fact about provability that first order PA contains). Like the quote above, Gödel's paper implicitly assumes that the underlying logic is first order logic; perhaps this is why it is difficult to locate a specific reference to first order logic in the paper. CMummert 17:21, 26 July 2006 (UTC)

My point in the higher posts is that although the natural numbers are definable as a subset of the real numbers in second order logic, Gödel's incompletness theorem doesn't apply in that setting because the natural numbers are categorical in second order logic. That was, at some point, relevant to the discussion of why Gödel's incompleteness theorem applies to arithmetic but not to the first order theory of real closed fields, of which the real line is a model. CMummert 12:53, 26 July 2006 (UTC)

I think we should finish the topic "completeness" befor we start talking about consitency. Gödel definitely proved: The theory including 1. order logic and the peano axioms is incomplete. He proves this by constructing a sentence, which may not be inferred from the peano axioms using 1. order logic. He uses Gödel numbering for his proof. Thereby, each sentence of the theory is identified with exactly one number. Therefore, the proof only works for a theory, which is capable of expressing the arithmetics or natural numbers. As long as this trick works, Gödels proof should b applicable to a system of first order logic.

Mummbert explained that Gödels theorem is inapplicable to the theory of 1. order logic including the axioms of a real closed ordered field. The axioms of the real closed ordered field do not contain the peano axioms. In particular, the natural numbers may not be expressed in this theory. This is conceivable to me.

However, I don't think that Gödels theorem is inapplicable to a theorem comprising second order logic and the peano axioms.The reason is: 2. order logic is an extension of first order logic. Adding additional rules of inferrence to the logic does not render Gödels theorem wrong. Each logical conclusion in 1. order logic is valid in 2. order logic. Therefore, Gödels incompleteness theorem is applicable to 2. order logic including the peano axioms.Kikl 19:30, 26 July 2006 (UTC)

And if you still don't believe me, then please referr to this book: http://www.godelbook.net/ page 201 chapter 22.8: "In particular, then, PA2 - our formal version of 2. order Peano Arithmetic - is just as much an incomplete theory as is first order peano arithmetic." Good Day. Kikl 21:10, 26 July 2006 (UTC)

I looked the book and I still don't believe you. Whenever you run into two statements that are both claimed to be true but are mutually contradictory, it is a good idea to check the definitions.

Peter Smith, the author of the book, defined an axiom system to be complete if every sentence is either provable or disprovable from the axioms. That is a fine definition for first order logic, where every logically valid sentence is provable, but it is not as useful for higher order systems where there is no complete proof system. The definition of a complete axiom system that is useful in all settings is: a complete axiom system has only one maximal consistent extension. These definitions are equivalent in the first order setting, but not in the higher order setting. An unfortunate consequence of the definition employed in that book is that a theory can be categorical (have only one model) without being complete, which is a strange state of affairs.

Ah, I hadn't realised you were using "complete" in that sense. In the context of a theory its conventionally used to mean negation complete, even for higher order theories. I accept what you say about how useful a term it is in all contexts (I'm not sure its a simple first/second order dichotomy - I've studied some pretty odd logics in my time). What I was concerned about was that Godel seems to be concerned with decidability, which obviously fails for SOL with full semantics. Francis Davey 19:48, 27 July 2006 (UTC)

To be fair, Smith gives a good discussion of the fact that second order PA is logically complete (he uses the synonym semantic entailment for logical consequence) on pages 201--202 that explains what is going on. And since the book is intended for nonmathematicians, the emphasis on provability rather than logical consequence is natural.

I think that much of your confusion about what I am saying stems from misunderstood definitions, so I don't think I will contribute any more to this dicussion. Here is a summary of the points I wanted to raise. The finite set of axioms for second order Peano arithmetic, under second order semantics, is categorical and thus has only one extension to a maximal consistent theory. Thus no sentence can be produced which is logically independent, under second order semantics, of this finite axiom system. In this sense, the axiomatization of second order PA is complete, Gödel's theorems notwithstanding. CMummert 22:45, 26 July 2006 (UTC)

That's ridiculous. The book explicitely says that second order Peano Arithmetic is incomplete. Then you conclude: "To be fair, Smith gives a good discussion of the fact that second order PA is logically complete..." That is a clear disagreement. Now you're trying to save you're ass by inventing a different definition of completeness for first and second order Peano arithmetic. You never made the distinction in the previous discussion. In fact, I explicitely asked you whether you were using different definitions for the term complete and you said no. Therefore, I feel comfortable to say that your form of conduct is dishonorable. Kikl 00:37, 27 July 2006 (UTC)

In hindsight, I have to admit that Francis Davey figured out fast what was going on in this discussion. Namely, Mummert used a definition for completeness, which does not apply to Gödels theorem. To make this clear:

Proposition: A proposition is any sentence in the language of the theory. A proposition may be a theorem and it may not be a theorem.

Theorem: A proposition, which is syntactically derived using the axioms and logical rules of the theorem.

Decidability: A Proposition is decidable if there is an algorithm for determining in a finite number of steps whether or not the sentence is a theorem. A theory is decidable if all the sentences of the theorem are decidable.

Negation Completeness:

A Theory is negation complete, if for any sentence of the theory the following holds: The sentence is a theorem or the negation of the sentence is a theorem.

What is Gödels incompleteness theorem about? Let’s just read the title:

“On formally undecidable propositions of Principia Mathematica and related systems”

What is the main proposition?

Proposition VI: To every ω-consistent recursive class κ of formulae there correspond recursive class signs r, such that neither v Gen r nor Neg(v Gen r) belongs to Flg(κ) (where v is the free variable of r).

Flg is abbreviation for the German word “Folgerung”, which means inference or consequence. Flg(κ) is the set of consequences of κ. v Gen r is a sentence and Neg(v Gen r) is its negation. In other words: Neither the sentence v Gen r nor its negation may be inferred from the theory. Therefore, the theory is not negation complete.

Gödel is definitely talking about negation completeness. There is no doubt about it. The original proof is confined to w-consistent recursive class of formulae. However, it may also be shown for any recursive enumerable theory of arithmetic.

Both first and second order arithmetic are negation incomplete due to Gödels incompleteness theorem. An undecidable Gödel proposition may be constructed in both first and second order arithmetic!

Mummert’s completeness definition/s really has/ve nothing to do with Gödel’s proof of the incompleteness theorem. Here is why:

Interpretation: Any theory may be interpreted in different ways. This is quite apparent. For instance, the derivative of a function may be interpreted as the slope of a geometrical curve or the speed of an object. So the interpretation of the theory refers to its semantic field. The natural numbers are an interpretation of 1. order peano arithmetic.

Model: An Interpretation, which makes all axioms and theorems of a theory true, is a model. The model “semantically entails” all the theorems from the axioms. Note that this is a meta-language about a theory. Semantically entails means that the interpretation of the axioms infers the truth of the interpretation of the theorems in the language of the model.

Isomorphic: Two Interpretations are isomorphic, if there is a one-to-one correspondence between each proposition of the model and the following holds: If a propositions is true in the first interpretation it is also true in the second interpretation.

Categorical theory: A theory is categorical if all its models are isomorphic. Therefore, a proposition, which is true in one model of the theory, is true in any model of the theory. Any axiom or theorem of the theory is true in every model of the theory.

Semantical entailment: A theory semantically entails a proposition, if the proposition may be inferred from the axioms in any model of the theory.

Semantical completeness: A theory is semantically complete means: If a proposition of the theory is semantically entailed, then the proposition is a theorem.

First Order Arithmetics is semantically complete. This follows from Gödels completeness theorem for 1. order predicate logic. This has nothing to do with his incompleteness theorem!

2. Order Arithmetics is semantically incomplete. This means that a proposition may be semantically entailed, even if the proposition is not a theorem.

Finally:

Mummert completeness: A theory is Mummert-complete, if the theory semantically entails all truths of the theory. Consequently, Mummert complete theories are categorical theories.

First order arithmetic is Mummert incomplete. There are true propositions in first order arithmetic, which are no theorems (Due to Gödels incompleteness theorem). These true propositions are not semantically entailed (Due to the completeness theorem of first order logic). Consequently, first order arithmetic is Mummert incomplete.

Second order arithmetic is Mummert complete. Even though the propositions exist, which are no theorems (due to Gödels incompleteness theorem), these propositions are semantically entailed by any model of second order arithmetic. This is conceivable, since second order arithmetic is semantically incomplete and categorical. Kikl 19:04, 27 July 2006 (UTC)

Matiyasevich's theorem mention?

It's been a long time since I'd visited this article, but I am very pleasantly shocked with the additions. In particular, this bit from the mind and machines section:

"In this lecture, Gödel uses the incompleteness theorem to arrive at the following disjunction: (a) the human mind is not a consistent finite machine, or (b) there exist Diophantine equations for which it cannot decide whether solutions exist."

However, Matiyasevich's theorem shows that there are in fact Diophantine equations such that no general algorithm can decide whether solutions exist. Thus, the disjunction can be modified to: (a) or (c)the human mind is such that it's action is algorithmic (i.e. is deterministic and finite and not a hypercomputer,etc.). Anything wrong here? If not, I think it should be added to the article. —The preceding unsigned comment was added by Foggier (talk • contribs) 02:45, 18 October 2006 (UTC)

Comment by Biedermann

(moved here from main article)

’’’Concern’’’, sorry, Sir, yet I have to insert my concern at this place, else nobody will ever take notice of it. To my understanding your ‘’’Proove Sketch’’’ is very successfully concealing the essential problems in the construction of what you designate by ‘’’SU( )’’’, in Gödel’s paper (following Nagel-Newman to get it on a single line of typing) the formula (statement form) (x)~Dem(x,sub(y,13,Z(y))). In the long sequence of some 40 definitions Gödel defines under Nr. 16 and 17 Z(n) to be the Gödel-number of the presentation of the number n as it results from ‘putting the sign ‘f’ n times in front of 0’, so Z(4) is defined as the Gödel-number of ffff0, and Z(y) would have to be the Gödel-number of the symbol sequence that results from ‘putting the sign f ‘’’y’’’ times in front of 0’. But such a symbol sequence does not exist, nobody can do something ‘’’y-times’’. Evidently, ‘’’SU( )’’’, as pretty as it appears as abbreviation, does not exist as a symbol sequence in the Formal System, nor does your pretty ‘’’SU(G(SU))’’’!!! Biedermann 10:44, 6 January 2007 (UTC)

Given a number y, it is possible to produce the Godel number for the sequence of y copies of f followed by 0. Here Z is a function that does this. CMummert 12:50, 6 January 2007 (UTC)

Well, certainly, 'If given a numbery, then you are wright. But here in the disputed formula y is the symbol y and nothing else!!!Biedermann 20:07, 7 January 2007 (UTC)

It is still true that (x)~Dem(x,sub(y,13,Z(y))) is a formula in which y is a free variable. That is all that is required in the remainder of the proof. CMummert 21:07, 7 January 2007 (UTC)

So please just tell me of what symbol sequence is Z(y) the Gödel number ! Biedermann 23:35, 7 January 2007 (UTC)Biedermann

Actually, I am going to stop participating in this conversation. I would recommend that, instead of looking at Godel's original paper, you read a modern textbook in which the proof will be written more clearly. An excellent book is "Computability and Logic" by Boolos, Burgess, and Jeffries. This recommendation is not because Godel's paper is faulty, but only because it is cryptic, leading to the type of confusion that you describe. CMummert 02:51, 8 January 2007 (UTC)

Well, CMummert, I much regret, that you are stopping in this conversation. Sorry, but once you have read Gödel carefully it is not cryptic at all, it is just more specific than any modern proof sketches! I insist on sticking to Gödels original! First step 'in the remainder of the proof' is to determine the Gödel-number n of above formula, and to that purpose you have to know what Z(y) is according to Gödels definition 16 - 17 in the Symbols of the SYSTEM. Please continue! I have no library and no books at my disposal. Biedermann 10:37, 8 January 2007 (UTC)

Well, somebody diagnosed my total lack of understanding. This certainly couldn’t help me to some better understanding. So, let me try to explain in more detail what I think to be my understanding with respect to what Gödel’s term Z(y) could be in the symbols of Gödel’s System. Without such knowledge the Gödel number n of formula (x)~Dem(x,sub(y,19, Z(y))) cannot be determined. But this is essential for the progress of Gödel’s argumentation; just to name it ‘n’ , does not serve the purpose, n not being a symbol of the System. From Gödel’s definitions 16 an17, together with 8 and 9, we know Z(n) to be (to BE, as Gödel says expressis verbis, not to Designate, as some people seem to believe!) the Gödel-number of the number n in the symbols of the System. With the claim that sub(n, 19, Z(n)) be obtained from sub(y, 19, Z(y)) through substitution of 19 (i.e. fffffffffffffffffff0 ) by Z(n), of necessity Z(y) would have to BE the number 19, and the term sub(y, 19, Z(Y)) would in fact be sub(y, 19, 19)), from which the term sub(n, 19, Z(n)) certainly does not result through simple Substitution of n for y ! To my poor understanding, Gödel’s argumentation depends on the assumption that Z( ) could be a function sign expressed in the symbols of the System, in which you may freely exchange the arguments n for y etc., and which could simultaneously yield the mathematical function ‘Gödel number of n’ on the argument n, and the deliberately chosen non-mathematical relation 19 for the argument y ! To my poor understanding it seems evident that such function cannot exist. Would you please be so kind as to explain me what you think to be your better understanding! With kind regards Biedermann Biedermann 12:22, 22 January 2007 (UTC)

Gödel sentence is an objection to AI. Is it true?

This article explains that there ∃ statement F such that neither T ⊢ F nor T ⊢ ~F in a "sufficiently powerful" T. A Gödel sentence G which claims that G cannot be proven is proven to be an example of such statement. J. R. Lucas, as explained in [1], claims that people can see that G is ture while machines cannot do that concluding that people's mind is superior and AI is not possible. I cannot see why the liar's sentence "this sentence is a lie" is ture. Am I a computer? --Javalenok 15:17, 11 January 2007 (UTC)

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)

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)

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.

I just wonder at these long discussions about Gödels work and nobody takes a closer look at the mathematical aspect of gödels construct, i.e the inherent mathematical inconsistancy in his famous Formula G. Gödel himself named the LIAR paradox as basis for his formula. But this 'paradox' is based on the mathematically non-sensical equating 2 = 4 ; the two words the subject 'this sentence' is identified with the 4 words of the whole sentence 'This sentence is false' ! Consequently, Gödels construct suffers from the same inconsistency. This is evident in the so highly praised DIAGONALIZATION, that is based on setting x = Gödelnumber of F(x), so x is used as free variable within a formula F( ) and at the same time it is equated not only with that entire formula that may consist of some hundreds of symbols, but even with the so more complicated Gödel number of this formula. This is a serious violation of the PM - rule for the proper aplication of a variable: that a variable has to preserve one and the same identity throughout a given context. 83.223.161.184 (talk) 11:16, 28 June 2010 (UTC)

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)

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 “

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)

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)

Tricky Natural Language

Consider the following sentence:

This sentence is not provable because it's absurd.

It sounds reasonable, but it can't be true. The sentence says it's absurd, so how can it be true? Now consider the following sentence:

X is false.

It's an assertion, but we can't say whether it is true or not because we don't know what X is. But we can see that X itself has to be an assertion because if, for instance, X were "2+2", the sentence wouldn't assert anything. If X were "2+2=5", the sentence would be true. If X were "2+2=4", the sentence would be false. But what if X were "This"? The sentence would be

This is false.

What does "This" assert? The sentence looks like an assertion, but is it really? And if it doesn't in fact assert anything, it's not logical to say that it is true or false. All you can say is whether the spelling, punctuation, and grammar are correct, but that's not the same thing. If that sentence isn't an assertion, then this one can't be either:

This is not provable.

What isn't provable? Exactly! We haven't asserted anything. Or if we have, then what? If you replace the word "This" with the whole sentence surrounded by quotes, you still cannot discover an assertion. And if you keep substituting for occurrences of "This", you're still none the wiser.

In English if you say "This is not provable", you really mean "That is not provable", or you mean something you're pointing to, or you mean something you're about to say next. So if the sentence on its own doesn't assert anything even in English, how can it possibly assert anything in a formal language?

In the formal language, the assertion is about numbers. By agreeing that those numbers can be taken (by the reader) to refer to strings of symbols, the 'interpreted content' of the assertion about numbers says that the string of symbols that forms the assertion about numbers in the formal system cannot be obtained by transforming the starting strings of the formal system using the allowed rules of transformation.

Say we added extra starting strings to the formal system so that the string of symbols that forms the assertion about numbers could now be obtained by applying the allowed rules of transformation. The interpreted content of the assertion about numbers would not now be incorrect because it does not say that the string cannot be obtained from the starting strings whatever they happen to be; it says the string cannot be obtained from precisely the strings that were explicitly identified during the definitions that were required to express that particular assertion about numbers.--Vibritannia (talk) 11:25, 24 July 2009 (UTC)

Of course, it can't. And Gödel's rigorous working demonstrates it. He encoded a sentence and then found that it was impossible to determine whether the sentence was true or false within the axiomatic system. In other words, he demonstrated rigorously that the sentence he had encoded asserted nothing. But he didn't realize what his result meant because he was still assuming that the sentence asserted something.

So what we learn from this is that axiomatic systems always give us a correct answer, but there is no guarantee that we will not mistake the meaning of that answer. And given what, for so long, Gödel's Incompleteness Theorem has been believed to mean, that is beautifully ironic.

--Vibritannia (talk) 08:18, 7 August 2008 (UTC)

What is a Rational Conviction?

Consider the following sentence which is intended to refer to itself:

This sentence is not provable.

If the sentence were provable, then what the sentence says would be false. But a proof is only a proof if it proves something that is true, therefore any proof that we might consider could not by definition actually be a proof. Therefore the sentence is not provable.

Therefore what the sentence states is correct.

So we have just deduced by the above argument that the sentence is true. In other words, we have proved it. But if we have proved it, then what the sentence says is false. And we cannot have proved true something that is false. So our proof cannot be a proof after all.

But Gödel's sentence doesn't say that it is not provable. Rather it says that a particular string of symbols cannot be obtained by transforming certain starting strings according to certain rules of transformation. When Gödel proves the Gödel sentence, he doesn't do it by transforming starting strings, so he doesn't contradict what his sentence says.

The Gödel sentence is a string of symbols in the formal system. The formal content of that string is an assertion about numbers. The interpreted content of that string is what we understand that assertion about numbers to mean when we accept that the numbers can be taken to refer to strings of symbols. Gödel's argument was that if the interpreted content and the formal content were consistent, the negation of the Gödel sentence could not be true because the interpreted content of that assertion about numbers implied that the unnegated sentence should be true as well. Therefore the negated Gödel sentence must be false, and therefore the Gödel sentence must be true (which was the proof).

The Gödel sentence did not say it was not provable; it said that string could not be obtained by string manipulation. Gödel did not decide the Gödel sentence by string manipulation. He decided it by an argument that relied on the informal interpreted content of the string and certain assumptions about the consistency of the formal system in question.--Vibritannia (talk) 12:05, 24 July 2009 (UTC)

A proof is just a valid argument starting from acceptable premises. If our argument was not a proof, then our argument could not have been a valid argument starting from acceptable premises. Either our argument was not valid, or it did not start from acceptable premises.

So what were our premises? In our first statement, we assumed that the truth of the sentence and the truth of what the sentence says are one and the same thing: we assumed that if the sentence said something false, then the sentence is false. Was that an acceptable premise? To answer that question, let us consider the following sentence:

This is false.

Could we regard this sentence as being true? The sentence says it is false. But the sentence is true, therefore saying that the sentence is false is saying something that is false, which is what the sentence says it says. Therefore the sentence is true. It is true that the sentence is false.

On the other hand, if the sentence is false, then what it says is true. Therefore it is false that what the sentence says is false. So the sentence is false.

We have just considered the case in which the sentence is true and the case in which the sentence is false and found in both cases that the truth of the sentence and that of what the sentence says differ. Therefore if we assume that the sentence is either true or false, it is not the case that the truth of the sentence and the truth of what the sentence says are one and the same thing. And in that case, our premise is not an acceptable one. But on the other hand, if we were to reject our assumption that the sentence must be either true or false, then our premise would become acceptable but inapplicable to the sentence in question.

So by our consideration of a sentence similar to the original one, we have discovered that a premise of our argument presents a significant possibility that it may be either unacceptable given our other premises or inapplicable to the sentence we have applied it. For this reason, it does not make a good choice for a premise from which to start our argument. And for that reason, our argument is not a convincing one.

If our argument is unconvincing, and it is our only argument, then we cannot claim to have a conviction about the argument's conclusion. Therefore we cannot claim to have a rational conviction that the sentence is true.

--Vibritannia (talk) 09:36, 17 August 2008 (UTC)

Why the First Incompleteness Theorem is Absurd

A sentence is constructed within an axiomatic system. It is then shown that if that sentence were an immediate consequence of the axioms of the system, then an inconsistency would be implied. Furthermore it is shown that if instead the negation of that sentence were an immediate consequence of the axioms of the system, then that too would imply an inconsistency. It is therefore deduced that neither the sentence nor its negation can be an immediate consequence of the axioms if the system is to be consistent. Since it is believed and desired that the system is consistent, it is accepted that neither the sentence nor its negation is an immediate consequence of the axioms.

Now when it is said that a sentence is an immediate consequence of the axioms, what is meant is that if you start with just the things that you have assumed are true beyond question (the axioms), you can reason with those axioms without introducing any new assumptions and eventually reach a conclusion which is the sentence in question. Gödel said this was what was meant by saying a sentence was provable in a particular system. But note that this notion of proof does not include proof by reductio ad absurdum (because a reductio ad absurdum proof must be begin by assuming the negation of the sentence to be proved, but for an immediate consequence, the only allowable assumptions are the axioms).

And for a sentence to be provable, in the sense that it is an immediate consequence of the axioms, it must be a sentence that is either true or false, i.e. if the sentence is an immediate consequence of the axioms, then the negation of that sentence cannot be an immediate consequence of the axioms (or else we say the system is inconsistent, and nothing is proved by any immediate consequence of the axioms if the system is inconsistent). Now if a sentence must be true or false, we say that sentence asserts something, i.e. it is an assertion.

So an assertion had been constructed within the axiomatic system, a sentence that said something that must either be true or false, but for which neither, Gödel said, could ever be proved in the axiomatic system – because proof of either would imply an inconsistency, and systems containing inconsistencies prove nothing.

Wrong! It was not the case that neither could ever be proved in the axiomatic system. Rather the strings of symbols for those assertions could not be obtained from the specific starting strings explicitly identified in the definitions that were required to express those assertions. The strings of those assertions might be obtainable from other starting strings (other axioms), and if such were the case, no inconsistency would be implied by it (because an inconsistency would only result if the sentence were an immediate consequence of the originally identified axioms, not if it were to turn out to be an immediate consequence of any axioms we might subsequently add).--Vibritannia (talk) 12:26, 24 July 2009 (UTC)

But here is the problem. If we have expressed something in our axiomatic system that must be either true or false, if it is not an immediate consequence of the axioms we have already identified, then it or the negation of it must be a new axiom by default, in which case the assertion or its negation is now an immediate consequence of the axioms (since it is itself just an axiom). And in that case, the system is inconsistent.

However that is not the accepted view. But how can we ignore something that is true, when we have validly expressed it within our system, just so as to avoid inferring that our system is inconsistent? If something is true, refusing to acknowledge it formally (by not making it an axiom) won’t absolve us from it. The very idea is absurd.

The answer I suspect is that the sentence in question does not say something that must either be true or false. In other words, the sentence is not an assertion. It looks a bit like an assertion, but when one tries to pin down precisely what is being asserted, one finds oneself unable to do so without getting in a tangle of self-contradiction. And if it is not an assertion, it most certainly cannot be an axiom, in which case our system does not contain the inconsistency that would be implied if it were.

Gödel said that the sentence he constructed was not decidable in the system, but his subsequent conclusion was absurd. Instead he had showed that the syntax of his axiomatic system was flexible enough to allow that he could construct a sentence that did not self-consistently assert anything, and that such a non-assertion could not be an immediate consequence of the axioms.

--Vibritannia (talk) 13:47, 13 October 2008 (UTC)

Supernatural numbers

I have pondered Gödel's Incompleteness Theorem for over ten years, since I first learned about it at age 14 as an advanced mathematics student.

One idea essential to the proof is that the theory ZFC, considered as an object within Zermelo-Fraenkel set theory itself, contains its own theory, ZFC´, which contains its own theory again, ZFC´´, and so forth. The undecidable statement G does not quite say, "I am unprovable," but, "My next reflection, G´, in the next theory, ZFC´, is unprovable." In doing so, it creates an endless chain of semantical reference, and we end up with something like this:

G --states unprovable--> G´ --states unprovable--> G´´ --states unprovable--> ...

or,

The following cannot be proven: The following cannot be proven: The following cannot be proven: ...

The addition of ~G as an axiom results in omega-inconsistency, which means that there is a property P such that while

P(1), P(2), P(3), ...

are all provable, the statement

(Ex)(x is a natural number and ~P(x))

is also provable. A number x that satisfies ~P might be called a supernatural number.

You may ask, "How is this even possible? Why can't mathematical induction 'reach' x? If induction applies to 1, 2, 3, and so forth, every step of the way, shouldn't x inherit the property P? Isn't that just what induction states?"

The answer turns out to be very simple. What we can do is add new numbers that, while unreachable outside the theory, act as if they were reachable inside the theory by functioning logically as unknown variables. The supernatural number x, even though you can't actually count to it, is made to inherit inductive properties by playing the role of 'some number,' in the way that any variable would. In such a case, you could say that the new theory would be made 'blind' to the property of x's actual unreachability.

It is a bit like a drop of colored water falling into a clear pond. The drop begins as an entity distinct from the rest of the pond (the supernatural is 'unreachable'), but after the splash is made, the color dilutes the rest of the pond and loses its distinguishing property.

Of course, a proof x of G´ in ZFC + ~G would translate into the very proof of G´´ whose nonexistence it would purport to prove. The proof x can't both exist and prove itself nonexistent in ZFC´, so ZFC´ (and thus ZFC´ + ~G´) would become inconsistent with the addition of ~G. In other words, mathematics would not be able to refer to itself as a consistent theory. The theory ZFC + ~G, however, would remain consistent.

Scott7261 (talk) 03:30, 6 December 2008 (UTC) Scott H

I'd never heard of supernatural numbers before. Your use of primes (the notation marks) has given me a useful idea. --Vibritannia (talk) 10:04, 15 December 2008 (UTC)