Talk:Gödel's incompleteness theorems

This mathematics related article has not received a brainstar for quality. Please consider expanding the article appropriately. See RationalWiki:Article rating for more information.

Archives for this talk page:  , (new)

Multiplication?

I always thought induction (or in ZFC, replacement and specification) was the big "gotcha" in this, since it's impossible to express in first-order logic, so you're left with statements that can't be finitely defined. Sake Fueled (talk) 13:07, 22 October 2011 (UTC)

Godel Unknotted

You might want to check out my refutation of Godel's Incompleteness Theorem at: Godel Unknotted. It's kind of interesting. — Unsigned, by: 208.83.126.102 / talk / contribs 19:51, 7 April 2015‎ (UTC)

Ugh, the formatting on that wiki was just too awful. I know this sounds immature, but the way the text was structured undermined my ability to take it seriously. If you weren't claiming to refute one of the most famous theorems in mathematics, I'd probably have made more effort to try to figure out what you were saying, but as it stands, I just couldn't bring myself to try. Is that unfair? ikanreed You probably didn't deserve that 19:59, 7 April 2015 (UTC)
Given as none of the brand new notation is defined, I'd call that an acceptable request for clarity. Like that is so unreadable I don't even know WHICH of the two you're claiming to refute. PacWalker 20:04, 7 April 2015 (UTC)
This may be of use. PacWalker 20:05, 7 April 2015 (UTC)
I'm hoping (or maybe !hoping) this is just an artifact of your formatting, but does the final "look what I did!" read something like
${\displaystyle (\lnot (A\leftrightarrow B))\leftrightarrow (A\nleftrightarrow B)}$
^this? PacWalker 20:21, 7 April 2015 (UTC)
Gödel would have scratched his head and then demolished the argument. Sorte Slyngel (talk) 18:14, 10 December 2015 (UTC)

Gödel and God

Someone with a better understanding of Gödel's theorems may have come across something like: Gödel says there are unprovable but true theorems, hence any logical discussion of God is futile. (Yes, this has been stated, but I saw it so long ago, that I can't remember where.) So that would mean that God is an improvable theorem in an arithmetical system. Is it worthwhile to mention this in the article? Cheers Sorte Slyngel (talk) 20:36, 9 December 2015 (UTC)

I added a paragraph, though honestly this argument is so out there that my first reaction was "what, seriously?" - LucidFox (talk) 08:13, 10 December 2015 (UTC)
Thanks for taking care of that. I saw this argument so long ago that I've forgotten where, but my reaction was precisely the same as yours - that is WTF. But there is nothing so far out, that somebody doesn't claim it as truth. :-) Sorte Slyngel (talk) 18:08, 10 December 2015 (UTC)

Gödel and the constitution

From a mention in a magazine I was reading, came to [1] - with a link to the pdf. What was the flaw? Anna Livia (talk) 00:41, 17 December 2018 (UTC)

That is an excellent question, . I ran into this story while reading a book about Albert Einstein a while ago. I searched for further information on what Godel thought was a flaw in the U.S. Constitution so serious the U.S. herself could become a dictatorship. I never succeeded. :-( Nerd (talk) 01:28, 17 December 2018 (UTC)
To clarify - the article mentioned G's comment - I looked for a link suitable for RW.
Given that KG was Austrian and into incompleteness (albeit of a different kind), and it was 'the time of the bellicose dictators' - could it have been that the US constitution did not provide a sufficiency of methods for containing or removing a President who was becoming dictatorial but #superficially# remaining within the apparent spirit of the constitution.
Should this exchange be copied over to the US Constitution talk page? Anna Livia (talk) 10:56, 17 December 2018 (UTC)
Good idea! Please do! Nerd (talk) 16:25, 19 December 2018 (UTC)
'Category of occasions where it is best to ask first - if you rearrange/clarify on the UCS page. Anna Livia (talk) 23:47, 19 December 2018 (UTC)

True but unproveable

Okay, I once again refreshed my brain about Gödel (My head is still hurting) I readily admit that I have not dealt with this stuff in decades and maybe I have forgotten some pertinent details. That being said, I do not think our statement is accurate (or, at least, it is misleading by omission):

"it is true in some models and false in others"

I am rather certain that G's are true in all consistent models.[Note 1] Any super-system is inconsistent if it claims the G of some sub-system is False (ie. if the super-system claims the sub-system's G can be proven, purely within the G's sub-system) Such a super-system is saying that, within the subsystem, we can prove G is correct in saying G cannot be proven within the subsystem.

Are we being weaselly by leaving out the word "consistent"?

--Bertrc (talk) 13:02, 20 May 2022 (UTC)

Why must you put notes on the talkpage?
More seriously, if I have the first-order Peano axioms (PA), and the Gödel sentence G that cannot be proven or disproven from PA, I can construct a model in which PA and ~G are true, by the completeness theorem. So the Gödel sentence G is not true in all consistent models; although, as I understand it, the incompleteness theorem is still true, and there will be a corresponding sentence G' for the set of axioms PA + ~G. 17:07, 20 May 2022 (UTC)
That's correct. Whether you add G or ~G as an additional axiom, the extended theory will have a new Gödel sentence that it can neither prove nor disprove, and you can continue this process indefinitely. - Linneris (talk) 17:35, 20 May 2022 (UTC)
I do not see how "[PA + ~G]" can be consistent. Doesn't PA's G essentially state that "This statement (that is, PA's G) cannot be proven within PA"? Doesn't ~G essentially state that "PA's G can be proven within PA"? So, "[PA + ~G]" contains both G (transitively, via including PA) and ~G (by construction/definition) -- ie. "[PA + ~G]" contains both "PA's G cannot be proven within PA" and "PA's G can be proven in PA" -- That looks like an inconsistency to me. I could construct a new axiomatic statement, H, which says "PA's G is True". G could now be proven in "[PA + H]" but that doesn't mean that PA's G is false --Bertrc (talk) 20:50, 20 May 2022 (UTC)
In regards to 'I could construct a new axiomatic statement, H, which says "PA's G is True".': I'm not sure what exactly you mean by that. If you want to add an additional axiom to get an extended axiomatic system in which G is provable, then adding G itself as an axiom will suffice. If you want to add an axiom asserting the truth of G by referring to it by its Gödel number, then by Tarski's undefinability theorem, you explicitly can't do that. (Because if you could, then you could construct a formula informally saying "I am false" using a construction similar to G itself.) - Linneris (talk) 12:47, 25 May 2022 (UTC)
I feel you might be saying to-may-toe to my to-mah-toe, but I could very well be missing some terminology nuance. Your phrasing is probably better than my "PA's G is true" paraphrase. Regardless, doesn't the situation I brought up still stand? "[PA + <G as an axiom>]" is different from PA. Sure, you can prove PA's G in "[PA + <PA's G as an axiom>]" and, yes, "[PA + <PA's G as an axiom>]" would remain consistent; never-the-less, PA's G is still unprovable in PA, alone, while, at the same time, "[PA + <PA's G as an axiom>]" has its own personal G that is not provable within "[PA + <PA's G as an axiom>]". If, however, you were to have "[PA + <PA's ~G as an axiom>]", then wouldn't you have created something that is inconsistent? (at least in standard models of mathematics -- and I still do not see how Gödel's theorem is even applicable using a non-standard model. Isn't adding PA's ~G to a system while in a non-standard model like bringing an apple to Gödel's pile of oranges?) --Bertrc (talk) 21:26, 26 May 2022 (UTC)
I'm not a mathematician, so this is not an authoritative comment; I'm answering based on my reading of Wikipedia, Hofstadter's Gödel, Escher, Bach, and my university course on mathematical logic.
1. Consistency is the property of theories, or axiomatic systems, not models; it makes no sense to talk of a consistent model. A model of an axiomatic system is a structure with an interpretation of its symbols in which the axioms hold; for example, the von Neumann numerals with appropriate interpretations of the successor function symbol S, addition function symbol + and multiplication function symbol × are a model of Peano arithmetic assuming PA is consistent (which most mathematicians believe). However, other models are possible. - Linneris (talk) 16:34, 20 May 2022 (UTC)
Ugh, I do not think I have a handle on the difference between "model" and "system", yet, but . . . Are we being weaselly by saying "model" and not "system"? --Bertrc (talk) 20:50, 20 May 2022 (UTC)
2. Gödel's statement G is demonstrably not true in all models of the theory that it is derived from. Suppose that we have a consistent theory T and, using Gödel's construction, derive its G. Since G cannot be proven in T (by construction), the theory extended with its negation (T + ~G) will still be consistent: if we could prove a contradiction in this extended theory, we could prove G in T by reductio ad absurdum. And since T + ~G is consistent, by the model existence theorem it has a model. - Linneris (talk) 16:34, 20 May 2022 (UTC)
I do not see how "[T + ~G]" could be consistent. T includes G (by definition). Therefore, doesn't "[T + ~G]" also include G? Therefore, doesn't "[T + ~G]" include both G and ~G? Wouldn't including G and ~G mean that "[T + ~G]" is inconsistent? (See my response to Serene's Peano axioms post, above) --Bertrc (talk) 20:50, 20 May 2022 (UTC)
3. Now this model is not the natural numbers we know, since G is true in any standard model of arithmetic. Thus, any model of T + ~G is necessarily a non-standard model of arithmetic and has some surprising properties: for example, there is a "number" that is greater than any standard number (that is, any number reachable from 0 by repeatedly adding 1). And that's our escape hatch: G, by itself, expresses an arithmetic relation, and it so happens that for standard numbers, it maps to a statement about logical provability — specifically, to the claim that G itself is not provable. However, when we extend arithmetic operations to non-standard numbers, it is possible to define them in such a way that there will exist non-standard numbers satisfying ~G, and they won't map to any valid logical proof, since the Gödel number of any actual proof will be a standard number. So even though ~G is technically true, we still wouldn't be able to prove G in such a system, thus preserving its consistency. - Linneris (talk) 16:34, 20 May 2022 (UTC)
I am not familiar with non-standard arithmetic, but wasn't Gödel's work built upon standard arithmetic? Doesn't that make it inapplicable to a non-standard arithmetic model (depending on what makes it non-standard?) --Bertrc (talk) 20:50, 20 May 2022 (UTC)
Most of your questions are answered in Douglas Hofstadter's book Gödel, Escher, Bach, which I heartily recommend as a fun and accessible, yet in-depth explanation of Gödel's theorem and its proof for non-specialists. However, to clear up some confusion in definitions:
• An axiomatic system is a (finite or infinite) set of axioms, which are well-formed sentences in a language of formal logic. For example, ∀x (x + 0 = x) is an axiom of Peano arithmetic.
• A theory is a set of axioms and theorems that are derivable from these axioms using the rules of inference of formal logic.
• A model is a set or class of concrete mathematical objects with a suitable interpretation of symbols of the formal language.
• Gödel's work concerns axiomatic systems of arithmetic. Being standard or non-standard is a property of models, not axiomatic systems. Peano arithmetic is indeed a "standard" axiomatization in a sense that all its axioms hold for natural numbers as we know them, with standard interpretations of addition and multiplication. However, it is the very consequence of Gödel's incompleteness theorem that there necessarily exist non-standard, "unintended" models of PA — that is, models consisting of the standard natural numbers plus an infinity of extra objects — and no extension of PA with additional axioms can fix this.
• G does not literally state "G is unprovable in PA", because G is a sentence of arithmetic and can only directly talk about natural numbers and operations on them. G states, roughly, that there do not exist two natural numbers x and y that are involved in a certain very complicated arithmetical relation involving additions and multiplications — and then when you look into what that relation means, it turns out that for standard numbers, it means "x is the Gödel number of a proof of the formula whose Gödel number is y, while y is the Gödel number of G itself". That is, for standard numbers, G states that there is no number that is the Gödel number of a proof of G. However, in a model of PA where non-standard numbers exist, G can be technically false (in that there exist two numbers x and y with the arithmetic relation specified in G, at least one of which is non-standard), yet you cannot obtain an actual proof from it. - Linneris (talk) 05:24, 21 May 2022 (UTC)
Wait, doesn't his proof use "s" as "successor" to express the x and y in your post, above? As I said, it has been decades since I looked at this stuff, but can you even build "G" in a non-standard model? If one of them is non-standard, then how do you express x and y? --Bertrc (talk) 12:06, 23 May 2022 (UTC)
1. I am using the terms "provable", "consistent" and "inconsistent" as defined within Gödel's . . . system? . . . model? . . . Sure, you could use some system/model that does not define them the same way. I guess I am saying that "Using Gödel's definitions and axioms, any sub-system below Gödel's (ie. a system that Gödel's theory can be applied to) is inconsistent if that sub-system claims some sub-sub-system's G is false

Proof Does Show Superiority of Human Intellect

Reference 5 states in regard to the Lucas-Penrose argument, "Works with counterarguments are too numerous to list here." If there is any counterargument for which there is a consensus of agreement on its validity, let's see it. Absent a credible counterargument, strong AI is dead on arrival, and that's why many won't accept the Lucas-Penrose argument, no matter how sound it is. I have written an essay that touches on this: Essay:The Death Knell of Dualism?
More Than Magnetic Ink (talk) 04:16, 17 October 2022 (UTC)

You can find lists of works with counterarguments here and here, with the latter also providing a brief summarized form of the standard counterargument. Your essay is uncompelling on this point, because it does not actually address any of the counterarguments, but instead merely asserts that they are unconvincing. Given that there is widespread consensus that Penrose-Lucas is fallacious, your assertions are pretty cavalier, and suggest that you haven't actually read any of these arguments. 16:21, 17 October 2022 (UTC)
Serene, thanks for the helpful feedback. I recommend that RW edit the article as follows: Delete the existing ref. 5 and immediately following the present superscript link to ref. 5, quote the Stanford Encyclopedia of Philosophy (SEP) article's "brief summarized form of the standard counterargument," perhaps as follows:
Raatikainen summarizes the consensus on the Penrose-Lucas argument<ref>{{wpl|Penrose-Lucas argument}}</ref><ref>{{Cite book |last=Penrose |first=Roger |author-link=Roger Penrose |title=Shadows of the Mind: A Search for the Missing Science of Consciousness |publisher=Oxford University Press |year=1989 |page=[https://archive.org/details/shadowsofmindsea00penr_0/page/457 457] |isbn=978-0-19-853978-0 |url-access=registration |url=https://archive.org/details/shadowsofmindsea00penr_0/page/457 }} </ref> as follows:<ref>Raatikainen, Panu, "[https://plato.stanford.edu/archives/spr2022/entries/goedel-incompleteness/ Gödel’s Incompleteness Theorems]," The Stanford Encyclopedia of Philosophy (Spring 2022 Edition), Edward N. Zalta (ed.)</ref>
"These Gödelian anti-mechanist arguments are, however, problematic, and there is wide consensus that they fail. The standard response to this argument goes along the following lines ...: The argument assumes that for any formalized system, or a finite machine, there exists the Gödel sentence which is unprovable in that system, but which the human mind can see to be true. Yet Gödel’s theorem has in reality a conditional form, and the alleged truth of the Gödel sentence of a system depends on the assumption of the consistency of the system. The anti-mechanist’s argument thus also requires that the human mind can always see whether or not a given formalized theory is consistent. However, this is highly implausible."
The sources deleted with reference 5 are restored as part of the three new references 5, 6, and 7 added by the above text. What's not restored is the statement, "Works with counterarguments are too numerous to list here." The quotation from and reference to the SEP article are much more helpful to those on both sides of the argument.
It appears that Lucas has controverted "the standard counterargument" in Minds, Machines and Gödel: a Retrospect. In the same article, Lucas wrote, "I have been much attacked. Although I argued with what I hope was becoming modesty and a certain degree of tentativeness, many of the replies have been lacking in either courtesy or caution. I must have touched a raw nerve. That, of course, does not prove that I was right. Indeed, I should at once concede that I am very likely not to be entirely right, and that others will be able to articulate the arguments more clearly, and thus more cogently, than I did. But I am increasingly persuaded that I was not entirely wrong, by reason of the very wide disagreement among my critics about where exactly my arguments fail. Each picks on a different point, allowing that the points objected to by other critics, are in fact all right, but hoping that his one point will prove fatal. None has, so far as I can see. I used to try and answer each point fairly and fully, but the flesh has grown weak. Often I was simply pointing out that the critic was not criticizing any argument I had put forward but one which he would have liked me to put forward even though I had been at pains to discount it. In recent years I have been less zealous to defend myself, and often miss articles altogether. There may be some new decisive objection I have altogether overlooked. But the objections I have come across so far seem far from decisive." The Wikipedia article Penrose-Lucas argument concurs on the criticisms' lack of consistency, stating, "The Penrose–Lucas argument about the implications of Gödel's incompleteness theorem for computational theories of human intelligence was criticized by mathematicians,[11][12][13] computer scientists,[14] and philosophers,[15][16][17][18][19] and the consensus among experts[20] in these fields is that the argument fails,[21][22][23] with different authors attacking different aspects of the argument." (Emphasis added.) In ref. 23 of that article, a hostile witness concurs: "There is at least this much to be said for Lucas and Penrose, that logicians are not unanimously agreed as to where precisely the fallacy in their argument lies On the Outside Looking In: A Caution about Conservativeness (Burgess, John). More Than Magnetic Ink (talk) 06:21, 20 October 2022 (UTC)