You said,

Here by 'provable' and 'unprovable' we don't mean absolutely unprovable (i.e. not provable from any set of axioms) since there are no absolutely unprovable formulas. Rather we mean unprovable in whatever theory is in question (let's say it's PA for simplicity of exposition). — TonesInDeepFreeze

That means, correct me if I'm wrong, given an axiomatic "theory" A, and Godel sentence G = the theorem T is true and unprovable in axiomatic theory A".

G is claiming that T is true in A i.e. my objection that that's impossible since it's unprovable is valid. T isn't true in some other "theory" like you seem to suggesting when you say "Rather what we mean unprovable in whatever theory is in question" but in A.

correct me if I'm wrong, given an axiomatic "theory" A, and Godel sentence G = the theorem T is true and unprovable in axiomatic theory A". — TheMadFool

I'm correcting you; you are wrong. And you're not even coherent. You've got an extra symbol 'T' that makes no sense.

You're not even reading what I wrote:

Again, G says "G is not provable in A" and G does NOT say "G is true and unprovable in A".

Not only does G not say "G is true in A" but A can't even form the predicate 'is true in A' or A would be inconsistent (this is Tarski's theorem that is a kind of semantic variant of incompleteness).

G is claiming that T is true in A — TheMadFool

I said it about six different ways in the previous posts that that is not correct. I explained in detail why it is not correct.

T isn't true in some other "theory" like you seem to suggesting when you say "Rather what we mean unprovable in whatever theory is in question" but in A. — TheMadFool

You are not just confused, but you are abysmally confused.

(1) Whatever sentence you mean by T, it's not relevant. The only sentence we are concerned with is G (you called it 'F1' elsewhere).

(2) I did NOT say that anything is true in any theory. About six times I said that sentences are not true or false in a theory but rather sentences are true or false in models for the language of the theory.

Why do you keep getting this wrong?

(3) When I said 'unprovable in whatever theory is in question' I was just pointing out that provability is relative to a theory. A sentence may be provable in some theories but not in others. And I am not evading that we are specifically concerned with a given system whether it be PA or Robinson arithmetic or whatever system A might be.

Again, if the theory in question is A, then G (the Godel sentence for A) says:

G is unprovable in A.

And G does not say

G is true and unprovable in A.

Get it through your head!

G is unprovable in A.

And G does not say

G is true and unprovable in A — TonesInDeepFreeze

Godel's Incompleteness Theorems

I'm quitting the discussion. Thanks for your valuable comments.

Put yet another way, without some of the previous simplifications:

A is a recursively axiomatizable, consistent, sufficiently arithmetically expressive theory.

L_A is the language of A.

PA (Peano Arithmetic) is a theory.

L_PA is the language of PA.

M is the standard model for L_A.

M is a model of PA.

Z is set theory.

G_A is the Godel sentence for A.

G_A "says" 'G is not provable in A'.

G_A is true if and only if G is not provable in A.

In Z we prove that G is true in M.

And, get this in your head:

G does NOT say 'G is true in A'.

'is true in a model for A' cannot even be formulated in A, since A is consistent (Tarski's theorem).

G is unprovable in A.

And G does not say

G is true and unprovable in A — TonesInDeepFreeze

Here we go again.

Yes, it is the case that G is unprovable in A. And it is the case that G is true if and only if G is unprovable in A. And G is true in the standard model for the language of A.

But G does not say that G is true in A.

(1) 'True in A' doesn't even make sense. Sentences are not true or false in a theory. Rather, sentences are true or false in models for the language of the theory.

(2) G does not even say that G is true in a model for the language of the theory. The language for A cannot even express 'true in a model for the language of A' since then A would be inconsistent.

Wikipedia in general is not reliable regarding mathematics. Much better is the Stanford Encyclopedia of Philosophy. However, possibly that particular article might be okay. I looked at it only briefly just now. I am wondering what you think is in that article that is not compatible with anything I've said.

From the article:

"The first incompleteness theorem shows that the Gödel sentence G_F of an appropriate formal theory F is unprovable in F. Because, when interpreted as a statement about arithmetic, this unprovability is exactly what the sentence (indirectly) asserts, the Gödel sentence is, in fact, true. For this reason, the sentence G_F is often said to be "true but unprovable." However, since the Gödel sentence cannot itself formally specify its intended interpretation, the truth of the sentence GF may only be arrived at via a meta-analysis from outside the system." - Wikipedia

Those are the very points I said also. Most poignantly, it does not say that the Godel sentence says that the Godel sentence is true, but rather it says that the Godel sentence does not say that it is true and that the truth of the Godel sentence is shown outside the theory.

It has the respect of most in the math community, but most of those think they will never come up against that roadblock. — jgill

In my view Gödel's incompleteness theorems, as the other incompleteness results, aren't roadblocks.

The problem is that many view them as like that: hoping that they wouldn't find them in front of them. I think that they, the results I mean, just show that a crucial logical part in our understanding of the foundations of mathematics isn't understood yet. Obviously from our system of natural numbers doesn't come everything in mathematics, that is plain obvious.

I think the problem is that Gödel's theorem is far too complicated and specific to show just where the real problem lies on. People simply fall into the complexities of Gödel numbering etc. I'd prefer something as simple as the diagonalization in Cantor's diagonal argument: the negative self reference. I think there lies the key problem: with negative self reference we get either paradoxes or true but unprovable mathematical objects.

It has the respect of most in the math community, but most of those think they will never come up against that roadblock. — jgill

In my view Gödel's incompleteness theorems, as the other incompleteness results, aren't roadblocks. — ssu

Set theory and foundation people certainly appreciate your perspective. And there are numerous examples of statements - conjectures - that can't be proven within, say, the Peano system, etc. Examples. Some probably are true.

But the fact remains that math people not in those areas are usually not very concerned, even if they are stumped in proving something. However, I haven't been around mathematicians for a long time and I could be mistaken.

"The first incompleteness theorem shows that the Gödel sentence G_F of an appropriate formal theory F is unprovable in F. Because, when interpreted as a statement about arithmetic, this unprovability is exactly what the sentence (indirectly) asserts, the Gödel sentence is, in fact, true. For this reason, the sentence G_F is often said to be "true but unprovable." However, since the Gödel sentence cannot itself formally specify its intended interpretation, the truth of the sentence GF may only be arrived at via a meta-analysis from outside the system." — TonesInDeepFreeze

Indeed! You're right.

Godel sentence = G = There's a mathematical theorem, call it T, in a given axiomatic system A, such that T is unprovable/undecidable (which word is apt?) in A.

Kurt Godel's tour de force was proving G, the Godel sentence, is true. Am I right?

SEP = Stanford Encyclopedia Of Philosophy

statement GF in F is often called “the Gödel sentence” of F — SEP

Therefore (1), GF cannot be false, and must be true. For this reason, the Gödel sentence is often called “true but unprovable (2)” — SEP

The word "therefore" (1) suggests an argument i.e. there's a proof for the Godel sentence GF. However, the next line asserts that GF is ...often called "true but unprovable (2)".

What puzzles me is that the unprovable status of GF is not what matters. GF should be asserting a mathematical theorem, call it T, and asserting that T is unprovable and not that GF itself can't be proved.

What gives? :chin:

You quoted Wikipedia and put my name on it as if they are my own words. Please don't do that.

This discussion is becoming unwieldy with different letter-symbolizations with your own your letters and also letters from Wikipedia and SEP. For example, you use 'A' when Wikipedia uses 'F'. I'm going to stick with Wikipedia here, since its explanation is coherent and quotable.

Godel sentence = G = There's a mathematical theorem, call it T, in a given axiomatic system A, such that T is unprovable/undecidable (which word is apt?) in A. — TheMadFool

That is all messed up.

You seem to be conflating the statement of the incompleteness theorem itself with the Godel-sentence G_F. The statement of the incompleteness theorem is not the Godel-sentence.

By 'the incompleteness theorem' I am referring to the Godel-Rosser incompleteness theorem. I'll call it 'C'. You attempted to express a part of C, but with terrible errors when you wrote:

"There's a mathematical theorem, call it T, in a given axiomatic system A, such that T is unprovable/undecidable (which word is apt?) in A."

Let's fix that (and recall that by 'true' in this context I mean 'true in the standard model of arithmetic').

I think the part of C you have in mind is:

There is a sentence G_F that is true but not provable in F.

I'll call that statement C* (it is a part of the incompleteness theorem C). Both C and C* are not stated in the language of F, but rather in a meta-language for F. And neither C nor C* are the Godel-sentence. In other words, the statement of the incompleteness theorem is different from the Godel-sentence that is used to prove the incompleteness theorem.

Each (appropriate) theory F has its own Godel-sentence that we call 'G_F'. And G_F "says" that G_F is not provable in F.

Kurt Godel's tour de force was proving G, the Godel sentence, is true. Am I right? — TheMadFool

There's a lot more in the proof of incompleteness that is remarkable other than the fact that G_F is true.

When SEP says "true but unprovable" it understood that 'unprovable' is informally brief for 'unprovable in F'.

Therefore (1), GF cannot be false, and must be true. For this reason, the Gödel sentence is often called “true but unprovable (2)”
— SEP

The word "therefore" (1) suggests an argument i.e. there's a proof for the Godel sentence GF. However, the next line asserts that GF is ...often called "true but unprovable (2)". — TheMadFool

The word 'therefore' is not being used in the proof of G_F in the theory F. Rather, 'therefore' is being used in the argument in the meta-language that G_F is true.

the unprovable status of GF is not what matters — TheMadFool

No, that G_F is unprovable in F is at the crux of the incompleteness proof.

GF should be asserting a mathematical theorem, call it T, and asserting that T is unprovable and not that GF itself can't be proved. — TheMadFool

No, that's where you're mixed up. G_F is a statement in the language of F. G_F is a mathematical statement about natural numbers. But G_F is constructed so that in the meta-theory we show that G_F is true if and only if G_F is not provable, and in the meta-theory we show that G_F is true, i.e. that G_F is not provable.

Two different things:

(1) G_F is a statement in the language of F but not a theorem of F.

(2) 'G_F is true' is a theorem of a metatheory for F.

It's crucial to distinguish between (1) the statement G_F itself in the theory F and (2) the statement 'G_F is true' which is a meta-theoretic statement about G_F.

There are two levels of proof: (1) proofs in F and (2) proofs (such as the incompleteness theorem and the statement 'G_F is true' in the meta-theory.

To grasp how exactly it all works and makes perfect and rigorous sense, you really would need to read a book in mathematical logic

Kurt Godel's tour de force was proving G, the Godel sentence, is true. Am I right? — TheMadFool

No.
Below is from three years ago. And you go over this periodically. Its time you learned about what you're claim you're interested in. Or maybe you're not really interested?



This from Assume a consistent theory T
— TheMadFool
Because otherwise, every theorem is provable in T.
G is a statement in T
— TheMadFool
Ok, but now you have to be careful about exactly what G says.
G = This sentence isn't provable from the axioms of T
— TheMadFool
As you have it, G isn't a meaningful expression in T. The problem is with "This sentence." It has to be well defined. Absent that, it's just a variation of the Liar Paradox in English - English isn't math, and Godel's theorem is interesting because it is itself a variation of the Liar Paradox, but expressed in mathematical-logical terms, which the English sentence is not.

Let's assume your G is the sentence "2+2=4 is not provable in T." (T also has to be specified with some care, but for present purpose let's just call it arithmetic.) Well, 2+2=4 is provable in T, so G is false. And the negation of G is provable. But for the Godelian sentence G, neither it nor its negation is provable in T. Crafting the Godelian G is the trick!

It works, roughly, like this: Godel created/discovered a method by which every proposition and every sequence of propositions in T can be assigned a unique number. His sentence (a number - a pretty big number) then (when translated appropriately), becomes (roughly), "The proposition with the Godel number G is not provable (in T)." And you might ask, so what? Well, the number of this proposition is just G itself! (How did he do that? Read the paper, or research Godel numbering. He did it his way, and subsequently other people found different ways.)

If G is provable (i.e., the negation of G), then G is not provable.
If G is not provable, then G is true, and you have a true proposition not provable in T.
Neither G nor its negation is provable in T. What does Godel's G look like? in his paper it's represented as 17Genr.

The proof is constructive in this sense: if you add G as an axiom to T, giving (say) T', then you can construct G' with the same effect in T', and so on into the transfinite.

And there's a bonus in his paper: the consistency of T cannot be proved in T. To say that T is consistent is equivalent to saying there are unprovable propositions in T (else, as above, if T is inconsistent then every proposition is provable.)

Let's let the expression "T is consistent" be represented by w. G is unprovable; we can write, w => unprovable G. However, G asserts its own unprovability(!) We can therefore write, w=>G. The expression w=>G is provable. But, that means that if w were itself provable, then G would be provable. G is not provable, therefore w is not provable. Some trick, and very slippery!

you really would need to read a book in mathematical logic — TonesInDeepFreeze

Thanks for the tip. I don't follow what you're saying but I can make some sense of what tim wood is trying to get at. Please join the conversation if you feel so inclined.

It works, roughly, like this: Godel created/discovered a method by which every proposition and every sequence of propositions in T can be assigned a unique number. His sentence (a number - a pretty big number) then (when translated appropriately), becomes (roughly), "The proposition with the Godel number G is not provable (in T)." And you might ask, so what? Well, the number of this proposition is just G itself! (How did he do that? Read the paper, or research Godel numbering. He did it his way, and subsequently other people found different ways.) — tim wood

So, the key proposition in Gödel's proof is K = The proposition with Gödel number G is not provable (in T) and the "coincidence" is that K is the proposition with Gödel number G. In other words, K is not provable.

But...

K has to be a mathematical theorem, no? After all, "incompleteness" in Gödel's incompleteness theorems refer to mathematical theorems that aren't provable but K [The proposition with Gödel number G is not provable] is definitely not a mathematical theorem. What gives?

At this pace, we'll witness every letter of the English Alphabet being summoned for denotation (under this thread).

It's invigorating, though. When I commenced this discussion, I'd never envisioned my own ignorance of the subject it pertained to. Nevertheless, this has been a revelation.

To grasp how exactly it all works and makes perfect and rigorous sense, you really would need to read a book in mathematical logic — TonesInDeepFreeze

For anybody who's enthused and willing, here's a thorough exposition of Gödel incompleteness - distilled in formal logic. I'm reading it, too.

https://www.math.wisc.edu/~miller/old/m571-08/smith.pdf

I'll call that statement C* (it is a part of the incompleteness theorem C). Both C and C* are not stated in the language of F, but rather in a meta-language for F. And neither C nor C* are the Godel-sentence. In other words, the statement of the incompleteness theorem is different from the Godel-sentence that is used to prove the incompleteness theorem. — TonesInDeepFreeze

What's a meta-language for F? Does that imply that C, and C* are statements that concern or describe the language of F?

But the fact remains that math people not in those areas are usually not very concerned, even if they are stumped in proving something. However, I haven't been around mathematicians for a long time and I could be mistaken. — jgill

I think that the incompleteness results have an effect on a wide range of things not just in the set theoretic realm and with the foundations of mathematics. We just don't want to make or are ignorant about the link to the incompleteness results.

I think the classic example of something being true but unprovable is a game theoretic situation where it's easy to show that a correct solution exists, yet there seems to be no way to get there. The existence of a correct solution can be shown...based on mathematics. Yet then how to get there seems impossible, actually illogical. Hence for example in economics these problem are dealt with taking the approach of there being a "black box" where "something happens" and the correct result is reached. Great! The economist has his function (with the black box) and can say that the issue has been modelled. But then opening up the black box cannot be done. Which basically is sophistry, but it goes with the remark "this is hopefully resolved later".

Why I say that these problems are similar to the incompleteness results is because in many of these cases there is the negative self-reference that similarly is in use in Gödel theorem and in the Halting Problem of Turing.

Mathematicians are far more rigorous. They cannot just assume something will work. Or, as the joke goes, they can have everything work and get every kind of result they want when 0=1. But that is hardly useful.

[The proposition with Gödel number G is not provable] is definitely not a mathematical theorem. — TheMadFool

Yes, it is. Now. Either you satisfy yourself with the level of understanding that English sentence, "This sentence is false," provides, or you do some reading. .

Yes, it is. Now. Either you satisfy yourself with the level of understanding that English sentence, "This sentence is false," provides, or you do some reading. . — tim wood

I want to see something like this: AxAy(x + y = y + x) in a Godel sentence but I don't and if that's the case, the Godel sentence isn't about mathematical theorems. Just so you know, if there's a side to me that's wise which I doubt, I would take your word for it. Thanks. :up:

[The proposition with Gödel number G is not provable] is definitely not a mathematical theorem. What gives? — TheMadFool

Maybe somebody already told you this, but Gödel also uses something called Gödel numbering.

The Gödel statement is coded in a particular Gödel number, and in that way the Gödel statement is a statement about mathematics, since it is statements about mathematics that can be coded in such a way.

This Numberphile video might help:

https://youtu.be/O4ndIDcDSGc

(Around 5:32 he starts to talk about Gödel numbering)

This Numberphile video might help:

https://youtu.be/O4ndIDcDSGc

(Around 5:32 he starts to talk about Gödel numbering) — Amalac

That's an engaging talk, and certainly an unsophisticated introduction of the idea. It may consist, nonetheless, of certain oversimplifications (which might be worth mentioning).

For instance, at one phase, it asserts that the provability of a theorem hinges on its Gödel number being divisible, by the Gödel numbers of a formalized system's constituent axioms. I'm hardly acquainted with the specifics of Gödel Coding, but that appears to be an overly reductionist idea (acknowledged, of course, by the professor).

Yes, he himself says he is simplifying it, but it does give one a rough idea about it, which I thought was a good start for TheMadFool.

Yes, he himself says he is simplifying it, but I does give one a rough idea about it, which I thought was a good start for TheMadFool. — Amalac

It's an excellent resource, for anyone seeking to immerse in the concept.

If only the particulars were that elementary, though - Gödel might have devised a pathway, to resolving all of mathematical enigma. Reverse-mathematics, unsurprisingly enough, is likely to have been standardized.

For instance, at one phase, it asserts that the provability of a theorem hinges on its Godel number being divisible, by the Godel numbers of a formalized system's constituent axioms. — Aryamoy Mitra

In the same way that words have to be spelled correctly. Except that as a practical matter, words do not really have to be spelled correctly - colse cna wrok. But not in math. To say that thirteen is almost divisible by four is to say that thirteen is not divisible by four, and sometimes the does it or doesn't it is what matters. Btw, I see above you're reading an online paper of about 150+ pages, Godel's theorem itself is about 34 pages, and very readable. Even a non-math person like me, with a little effort and work, can get most of it. Of course there are subtleties, like the depth of water under the ice you're skating on. But if the ice is good and skating is what you're doing, then why break through it?

the key proposition in Gödel's proof is K = The proposition with Gödel number G is not provable (in T) and the "coincidence" is that K is the proposition with Gödel number G. In other words, K is not provable. — TheMadFool

Please, let's stick with one set of letter-symbols, so 'F' rather than 'T'.

The Godel-sentence G_F is a formula in the language of number theory. It can be reduced to the primitive language of PA, with only the symbols '0', 'S', '+', and '*', and a quantifier and connectives (even just one connective would work). It is a pure mathematical formula. The ordinary interpretation of the symbols is that they refer to arithmetic.

Then, we show in the meta-theory that G_F is true if and only if G_F is not provable in F. So we say that G_F "says" that G_F is not provable in F. Note that we put 'says' in scare quotes; what we mean more technically than "says" is that we show that G_F is true if and only if G_F is not provable in F.

has to be a mathematical theorem, no? — TheMadFool

I think you are conflating 'sentence' with 'theorem'.

Theoremhood is always relative to a theory. A sentence is a theorem of a theory if and only if the sentence is provable in the theory. In the case of incompleteness, we sometimes leave tacit the theory, and say 'provable' rather than the actually correct 'provable in F'. Also, every sentence is a theorem of some theory or another. The only sentences that are theorems of all theories are the logical validiites.

G_F is not a theorem of F. And the negation of G_F is not a theorem of F. That's the point of incompleteness.

In the same way that words have to be spelled correctly. Except that as a practical matter, words do not really have to be spelled correctly - colse cna wrok. But not in math. To say that thirteen is almost divisible by four is to say that thirteen is not divisible by four, and sometimes the does it or doesn't it is what matters. — tim wood

That's certainly a thought-provoking analogy.

If the notion of Gödel divisibility was of an exact accuracy, though, one might witness a multitude of surprising repercussions emerge. Wouldn't it then be plausible, to Gödel code every unsolved hypothesis - and reverse-trace an axiomatic proof? I'm certain the idea exists at a concrete threshold; only one far more intricate than arithmetic divisibility.

Btw, I see above you're reading an online paper of about 150+ pages, Godel's theorem itself is about 34 pages, and very readable. Even a non-math person like me, with a little effort and work, can get most of it. Of course there are subtleties, like the depth of water under the ice you're skating on. But if the ice is good and skating is what you're doing, then why break through it? — tim wood

I've searched comprehensively for short translations of Gödel's 1931 paper, to no success. I do, nonetheless, intend to learn the language of formal logic, prior to readily engaging in the paradigm (such that to learn Gödel incompleteness with the context it was synthesized in); the 150-page variant is consistent with the second phase.

I've searched comprehensively for short translations of Gödel's 1931 paper, to no success. — Aryamoy Mitra

No such thing as a short translation. But a translation exists here, Godel's pp. 4-39, but other treasures in the book, e,g., pp. 305-337, by Emil Post, although this one starts easy and gets hard.:

https://www.amazon.com/Undecidable-Propositions-Unsolvable-Computable-Mathematics/dp/0486432289/ref=sr_1_1?dchild=1&keywords=The+Undecidable%2C+davis&qid=1616602363&s=books&sr=1-1

And cheaper here:

https://www.abebooks.com/servlet/SearchResults?cm_sp=SearchF-_-topnav-_-Results&ds=20&kn=the%20undecidable%2C%20davis&sts=t

Imo, bang for book-buck is very high.

If the notion of Gödel divisibility was of an exact accuracy, though, one might witness a multitude of surprising repercussions emerge. Wouldn't it then be plausible, to Gödel code every unsolved hypothesis - and reverse-trace an axiomatic proof? — Aryamoy Mitra

Well, that's a good question the answer to which is above my pay grade. The numbering itself is way of both constructing and concatenating numbers, and then multiplying them such that the resultant (usually large) number decomposed reveals the original argument. If the number does not decompose appropriately, then it's not a Godel number - not all numbers are Godel numbers in his numbering scheme.

Your question then amounts to taking an ordering of numbers, perhaps even the integers themselves, and testing them in turn to see if any correspond to expressions of interest. Let's imagine you go on a camping trip for a few days in the forest and on emerging find you no longer have your car keys - they're in the forest somewhere. In principle you can find them. But maybe, just maybe, that's not as simple as it sounds even in principle.

short translations — Aryamoy Mitra

Godel's second incompleteness theorem explained in words of one syllable

No such thing as a short translation. But a translation exists here, Godel's pp. 4-39, but other treasures in the book, e,g., pp. 305-337, by Emil Post, although this one starts easy and gets hard.:

https://www.amazon.com/Undecidable-Propositions-Unsolvable-Computable-Mathematics/dp/0486432289/ref=sr_1_1?dchild=1&keywords=The+Undecidable%2C+davis&qid=1616602363&s=books&sr=1-1

And cheaper here:

https://www.abebooks.com/servlet/SearchResults?cm_sp=SearchF-_-topnav-_-Results&ds=20&kn=the%20undecidable%2C%20davis&sts=t — tim wood

Thank you; these are invaluable.