Talk:Gödel's incompleteness theorems/Arguments

From Wikipedia, the free encyclopedia

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

1 Gap in Gödel's proof
2 Self-contradiction in Gödel’s incompleteness theorems “proofs”
3 PCE's doubts
4 Reals and Complexes are sets with complete Axiomatizations ?
- 4.1 Incompleteness of second order logic
5 Matiyasevich's theorem mention?

[edit] 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)

[edit] 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) .

[edit] 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:

[edit] 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.)

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.
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.
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."
Now Gödel laughs his high laugh and asks UTM whether G is true or not.
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.
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").
"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.

[edit] 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) —The preceding unsigned comment was added by Pce3@ij.net (talk • contribs) 19:45, 3 May 2006 (UTC)

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)

[edit] 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

[edit] 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)

[edit] 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$ " ? —The preceding unsigned comment was 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)

[edit] 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)

[edit] 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)

Retrieved from "http://en.wikipedia.org../../../g/%C3%B6/d/Talk%7EG%C3%B6del%27s_incompleteness_theorems_Arguments_c028.html"