Talk:Gödel's incompleteness theorems

Unicode and ASCII

I've just removed the following from the article

(Note: Computer programs typically represent sentences in Unicode rather than ASCII, and convert them more efficiently to produce smaller numbers. But we only need to choose some method and then apply it consistently to every sentence, and joining together the decimals is simpler to describe.)

The reason being that it is not correct. To start with unicode is not an encoding, so computer programs do not generally represent anything in unicode. Rather they use a specific encoding, which is usually compliant with some version of the Unicode standard. This might seem like a nitpick, and it is something that I could have just fixed. UTF-8, the most common encoding on the internet, is probably what is meant. However, the real issue with this claim is that UTF-8 is backwards compatible with the US-ASCII standard. So to say that UTF-8 is used "rather than ASCII" would be misleading at the very least. Additionally the second clause

Computer programs typically [...] convert them more efficiently to produce smaller numbers.

does not have a very clear meaning to me. However it seems to imply that UTF-8 is a more dense encoding than US-ASCII which is just not true; a character in US-ASCII encoded in UTF-8 is still the same byte, because UTF-8 is backwards compatible with US-ASCII.

So given that, if someone still wants to put a version of this claim into the article I would strongly recommend getting a reliable source for the claim.

AquitaneHungerForce (talk) 10:14, 1 November 2021 (UTC)

In fact, there is an issue here: Unicode has problems with numerical encoding of strings that ASCII doesn't, since the proposed encoding was essentially base-1000, which is works for ASCII and coding up the byte array representation of any encoding but is not collision-free if you work with Unicode codepoints. But while a gesture at practical encoding is appropriate, discussion of the technicalities facing actual computer systems quickly distracts the reader from grappling with the topic of the article. I'm against explicit treatment of this point at any length, regardless of sourcing. I'm wondering if the discussion can readably be made more concise.— Charles Stewart (talk) 11:34, 1 November 2021 (UTC)

If the issue of ASCII vs Unicode ever comes up in this article, then the text in which it comes up should be reworded to remove the need for it. Considerations like that are far off-topic for this article. I understand the desire to make the ideas accessible to readers whose shortest path may be through their computer knowledge, but if specific character encodings ever come up, then we've lost the thread. --Trovatore (talk) 16:31, 1 November 2021 (UTC)

I think that a short mention in a footnote, along the lines of "Actual computer systems use more complex or specialized methods to encode strings e.g. UTF-8" would be fine. But I agree that this article does not need to get in the details and I think it should not be in a parenthetical but rather a footnote because this is not the point. AquitaneHungerForce (talk) 19:02, 1 November 2021 (UTC)

First-order vs. higher-order version

(The following discussion was started by a side remark at Talk:Peano_axioms#Downgrade_the_quality_level_of_the_article_to_B. It has been moved to here in order to disrupt the main discussion at Talk:Peano_axioms.)

@Vkuncak: Maybe you are the right person to explain to me why Gödel's incompleteness theorem is considered to refer to first-order logic in Wikipedia, while his original 1931 article (e.g. [1]) refers to Principia Mathematica, and, in particular, higher-order logic (in sect.2, p.176, variable symbols of arbitrary high order are introduced before fn.17; on p.177, axiom I.3 is the classical 2nd-order induction axiom, with x₂ a predicate variable, ".", "Π", and "⊃" meaning "and", "for all", and "implies", respectively). I guess I'm unaware of some modern treatment of Gödel's result which transcribed it to FOL. Maybe you could even devise a clarifying remark for the page Gödel's incompleteness theorems? Many thanks in advance - Jochen Burghardt (talk) 19:06, 31 January 2022 (UTC)

Jochen: I'm not Vkuncak, but if I could mix in, I think that may be more of a Principia Mathematica question than a general math-logic question. The notation and terminology used by Russell turned out to be pretty much of a dead end; hardly anyone learns it anymore for mathematical reasons (though historians may still be interested). And yes, I suppose it's probably good to know about if you want to read Gödel's original paper, but the same remarks apply — Gödel was doing something for the first time, and putting it in the context of the day, but there are much more efficient ways to learn the content now.

I'm not competent to answer the question directly because I've never bothered to put in the effort needed to understand Principia Mathematica, but I could offer a guess. It likely has to do with two different senses of the phrase "second-order logic". In the context of this article, for example, second-order logic with "full semantics", plus the original Peano axioms, is enough to make the theory categorical — there is only one model up to isomorphism. "Full semantics" means that you have first-order variables that range over natural numbers and second-order variables that range over sets of natural numbers, and the latter really range over all sets of natural numbers.

On the other hand, you can take exactly the same theory but interpret it with Henkin semantics, which means that you give it an interpretation by specifying what both the first-order and second-order variables range over. That is, you limit the second-order variables to ranging over a pre-specified class of sets of naturals, rather than all of them. Now the theory is no longer categorical. It's actually a theory of first-order logic, though it has second-order variables.

Does that help? It might be a nice thing to bring up at the refdesk if you want more details. We could use some good questions like that. --Trovatore (talk) 19:42, 31 January 2022 (UTC)

Jochen: Thank you for pointing out to this historical development, of which I was not aware of! I was merely following the expositions in several textbooks, including Mendelson and the handbook by Samuel Buss. These all refer to FOL formulation of the problem. What matters for the incompleteness theorem is to have a system where provability is recursively enumerable. Strong enough FOL theory with decidable axiom schemas is one typical way to get recursively enumerable definition of provability. Second order logic with full semantics is not such an effective definition: there is no way to enumerate all true facts according to such semantics. Vkuncak (talk) 20:25, 31 January 2022 (UTC)

Trovatore: Henking semantics for second order (and higher-order) logic could be applied to the question of models of Peano arithmetic and provability, but do we actually have interesting facts to mention in that direction (other than it is a valid thing to consider)? If yes, this line of thinking could be used to expand and clarify analogously the paragraph on categoricity proof carried out in first-order axiomatization of ZFC. I thought how to clarify that paragraph, but I am not entirely sure about the intention was with it originally, so I left it as it is. Vkuncak (talk) 20:25, 31 January 2022 (UTC)

@Trovatore and Vkuncak: Thanks for your answers. I moved the discussion path to here in order not to distract the quality level discussion at Talk:Peano_axioms#Downgrade_the_quality_level_of_the_article_to_B.

My point with Principia Mathematica is just that it admits arbitrary high order quantifications, independent of the uncommon notation.

As for Henkin semantics (of which I was unware - thanks for the hint!), categoricity would depend on the choice of the domain sets for first- and second-order variables; if they are chosen to be the full sets, Henkin semantics coincides with standard semantics, doesn't it? - Jochen Burghardt (talk) 10:04, 1 February 2022 (UTC)

Yes, the standard interpretation will almost always be a model in the Henkin semantics. I've rewritten the paragraph at second-order logic making this clear. We really should have a full article on Henkin semantics: the details are a little tricky but make the picture much clearer. — Charles Stewart (talk) 10:15, 1 February 2022 (UTC)

Second theorem in terms of the first

The first theorem states that there exists a true statement F cannot prove. A few months ago I added an edit stating that the second theorem in particular provides a concrete example of one of the true statements that F cannot prove, namely Cons(F). It was reverted, with edit summary "how do you know it [Cons(F)] is true?" But since one of the premises of the theorem is that F is consistent, Cons(F) is true, so I believe Cons(F) is a concrete example of a true statement not provable from F. If this reasoning is correct, should the specification be re-added to the article? I think it may be helpful to see the second theorem as providing a specific example of the first theorem, even if the first theorem already involves the Godel sentence. C7XWiki (talk) 08:02, 27 October 2022 (UTC)

I have a source that I think claims the second theorem provides an example of the first:

"He [Godel] followed this with his First and Second Incompleteness Theorems. The first one asserts that every sufficiently extensive, consistent formal system (and almost all formal systems are sufficiently extensive) is incomplete in the sense that there exist sentences expressed within the system that cannot be decided within it. The second one provides additional information that consistency of such a system is a sentence of this kind."

From Harvey Friedman's Research on the Foundations of Mathematics (1985), Studies in Logic and the Foundations of Mathematics vol. 117. p.viii. C7XWiki (talk) 09:45, 8 November 2022 (UTC)

Image

Regarding Jochen's addition of an image, here.

Jochen says in the edit summary "no idea how to illustrate the theorem itself", and I basically agree. Oh, someone could probably come up with something, maybe some sort of block diagram, but I doubt it would actually be helpful.

But to be honest I don't think the proffered image is particularly helpful either.

So my vote would be just not to have an image. I don't think there's any great value in having an image purely pro forma. If there's no image that genuinely helps direct the reader to the point of the article, then why have one at all? --Trovatore (talk) 20:25, 20 February 2023 (UTC)

Confusing part about truth of Goedel sentence?

However, since the Gödel sentence cannot itself formally specify its intended interpretation, the truth of the sentence G_F may only be arrived at via a meta-analysis from outside the system. In general, this meta-analysis can be carried out within the weak formal system known as primitive recursive arithmetic, which proves the implication Con(F)→G_F, where Con(F) is a canonical sentence asserting the consistency of F.

Could this part confuse the reader? I am not sure what it would mean for a sentence to "specify its intended interpretation" (perhaps meaning that no sentence can single out the standard/true natural numbers?) For the second sentence it may help to mention that T proving Con(PA) -> (Goedel sentence for PA) and T proving (Goedel sentence for PA) are different phenomena, and while PRA is an example of such a theory T in the former case, much stronger theories need to be considered in the latter case (theories stronger than PA). C7XWiki (talk) 22:39, 19 April 2024 (UTC)

bew redirects to here

Please see Talk:BEW#BEW, Bew, bew and reply there, if desired. I am proposing that the redirect Bew be pointed to BEW instead of to Gödel's incompleteness theorems#Bew. - dcljr (talk) 02:17, 24 April 2024 (UTC)