Attempt at an intuitive explanation (ELI12) for the weirdest logic theorem ever (Gödel-Carnap)

alcontali

Explain me like I am 12.

When people write things like this:

The Diagonal Lemma (of Gödel and Carnap) is one of the fundamental results in Mathematical Logic. However, its proof (as presented in textbooks) is very un_intuitive, and a kind of “pulling a rabbit out of a hat”. As a matter of fact, several theorems that are proved by using this lemma now have diagonal-free proofs.

They express their (utter) dislike for this lemma.

Especially its proof is considered to be incomprehensible. That is a problem because both Gödel's first incompleteness theorem and Tarski's undefinability theorem trivially follow from this lemma. Let's attempt to come up with a more intuitive explanation anyway.

First step. We must be able to encode logic sentences as numbers.

Nowadays, doing that is actually trivial. This page is encoded in utf8. It is a perfectly suitable Gödel numbering. We do not need to use Gödel's original encoding which he designed back in the 1930ies before computers existed.

For example, %A = 65 (decimal). That means: the number for the letter A is 65.
Or %(hello) = 0x68656c6c6f (hexadecimal) = 448378203247 (decimal)

You can convert any language expression online from utf8 to hexadecimal (base=16) using this test page and then from hexadecimal to decimal (base=10) using this test page. So, whatever expression we write, in logic or in natural language, we can always represent it as a natural number.

Second step. We must be able to represent properties of logic sentences.

How do we represent the sentence, "The banana is yellow", in logic? If the predicate function yellow is computable and if it accepts a natural number as input, then this form will do the job:

banana $\leftrightarrow$ yellow(%banana)

It means that the banana has the property yellow. In general, the syntactical form, M $\leftrightarrow$ Z(%M), says that M has property Z.

Third step. Let's now specify a property that could not possibly apply to any sentence

Let's define K(%M) = false. Say that K means "heavy". (It could mean anything, really). There is no number or associated sentence that is "heavy" because K always returns false. We just do not want a heavy sentence in our system. Seriously, we are trying to shoehorn the situation here to prevent anything from being provably heavy.

Fourth step. Let's manipulate this property

Take any true sentence S, such as "my cat is sick", because if it is true, then the equivalence:

S $\leftrightarrow$ not K(%S)

will hold. K(%S) will be false. So, not K(%S) will be true. Hence, that true sentence S is simply not "heavy". The following step is merely syntactic. We negate both sides of the equivalence:

not S $\leftrightarrow$ not not K(%S)

After simplifying "not not" for canceling each other, we obtain:

not S $\leftrightarrow$ K(%S)

Since K is always false, we can see that K(%S) = K(%(not S)) = false. Therefore, we are allowed to replace K(%S) by K(%(not S)):

not S $\leftrightarrow$ K(%(not S))

For the sake of the argument, let's now rename "not S" to "P":

P $\leftrightarrow$ K(%P)

Look at that! We now have a sentence P that has the property of being heavy, even though K, the heaviness predicate, always returns false! How is that possible?

Fifth step. Conclusion

Well, that is exactly what the Gödel-Carnap lemma says: For each predicate that is computable in natural number arithmetic, there will always be a logic sentence that successfully has that predicate (and also one that successfully does not have it). This cannot be avoided.

Example use of this lemma. Gödel's first incompleteness theorem

It is the necessary existence of the following true sentence (P):

P $\leftrightarrow$ not provable(%P)

that brought Gödel to fame.

I hope that this explanation is more intuitive than this one. Any comments?

-- disclaimer --
This explanation is just the sketch of an argument by contradiction for the Gödel-Carnap's diagonal lemma, of which the purpose was to give a more intuitive explanation as to why this controversial lemma is provable from number theory. It cannot be considered a fully-fledged proof because it does not implement the complete bureaucracy of formalisms needed in that respect, and also because a complete, original proof by contradiction would need to be thoroughly peer reviewed.

aletheist

This explanation is just the sketch of an argument by contradiction for the Gödel-Carnap's diagonal lemma — alcontali

Thanks for this. Just curious, is there a constructive argument for the lemma, such that it also holds for intuitionistic logic where proof by contradiction is not allowed?

alcontali

Just curious, is there a constructive argument for the lemma, such that it also holds for intuitionistic logic where proof by contradiction is not allowed? — aletheist

Yes, the standard proof does not exploit any contradictions. Its proof strategy is exclusively based on judicious symbol manipulation.

Unfortunately, the standard proof use the original Gödel encoding, which means that it must use two successive encodings/decodings, which is not needed when using a modern numbering scheme. But then again, I guess that tradition has its weight.

What I did was just showing that even in the most extreme case the lemma still holds. In a complete proof it would be a case of formally covering all possibilities. Still, such complete proof would probably no longer be suitable as a clarifying explanation either.

At the Workshop on Proof Theory, Modal Logic and Reflection Principles (October 18, 2017), Moscow, Steklov Mathematical Institute, the speaker was so fed up with the standard proof ("I can never remember it!") that he proceeded by show casing diagonal-free proofs. During the public Q&A, quite a few members of the audience were not convinced about the idea of dropping the diagonal lemma. I actually share that opinion. I think that it is much better to build a better narrative around its proof.

Pfhorrest

not S ↔ K(%(not S))

For the sake of the argument, let's now rename "not S" to "P":

P ↔ K(%P)

Look at that! We now have a sentence P that has the property of being heavy, even though K, the heaviness predicate, always returns false! How is that possible? — alcontali

But because prior steps hinged on S = true, it must be the case that this P = not S = false, so as you have presented it at least, we only know that there is some false proposition that has the same truth value as a predicate function that always returns false, which... duh. I don’t see how any conclusions can be drawn from that to more general statements about predicate functions that sometimes return true or sentences that are true. So to get from here to

P ↔ not provable(%P) — alcontali

requires either that P be false and “not provable()” always returns false, or else some other step I’m missing. We could trivially invert the truth values and say that any true sentence has any predicate that always returns true, but again, duh, and for that to apply to this situation would require “not provable()” to always return true, which just says that in a system in which nothing is provable, any true sentence is not provable, which is again trivial.

alcontali

we only know that there is some false proposition that has the same truth value as a predicate function that always returns false, which... duh. — Pfhorrest

Well, p $\leftrightarrow$ q also means not p $\leftrightarrow$ not q, which is indeed a bit "duh", but formally still correct.

I don’t see how any conclusions can be drawn from that to more general statements about predicate functions that sometimes return true or sentences that are true. — Pfhorrest

My argument just shows an example of an extreme case, really. It is just a case in which you would intuitively not expect the lemma to work, but it still does.

If you want to cover all possible cases, you can always fall back on the full proof. The problem with that full proof is that it is exclusively syntactic symbol manipulation. In the video of the workshop, they pointed out many complaints from people who simply disliked the theorem and its proof for that reason. So, I wanted to show an example where it (unexpectedly) works.

If you provide another example of a class of computable predicates (that return sometimes true and sometimes false) it should also be possible to locate a sentence that will satisfy the lemma.

We could trivially invert the truth values and say that any true sentence has any predicate that always returns true — Pfhorrest

Well, in that case, you would reasonably expect that every sentence would have the property, which is surprisingly, also not the case. There will still exist a sentence that does not have the property.

which just says that in a system in which nothing is provable, any true sentence is not provable, which is again trivial. — Pfhorrest

Gödel's system will first have loaded all the axioms of logic and all the ones of a (sufficiently strong) theory of arithmetic, and the system understands the full language of first-order logic. Gödel spends dozens of pages doing exactly that in his original paper. The problem is that lots of readers will give up because they consider it to be unreadable (which it actually isn't). Therefore, "nothing is provable" will not occur. You will, for example, be able to prove that "1+1=2".

Pfhorrest

All I'm saying is that what you've laid out here does not show why the Incompleteness Theorem must be true. You've successfully shown that any false proposition has the same truth value as any predicate function that always returns false, and that that predicate is thus false of any such false proposition; and equivalently that any true proposition has the same truth value as any predicate function that always returns true, and thus that that predicate is true of any such true proposition; although it sounds like you are now saying the latter is not correct. I'm sure that Godel's actual proof explains the missing gaps here, but I'm curious to see your easier-to-understand explanation bridge those gaps itself.

god must be atheist

You actually did not describe the lemma.

Then you gave a SKETCH of a proof, which is probably meaningless in its shortened form.

So we don't know what the problem is, and we don't know its solution.

Yet you guys (and perhaps gals) talk about it as if it was as commonplace as the inner tube on a bicycle wheel.

I really, but really would like to know the point you guys (and perhaps gals) are making. Why are we talking abou this? What is the meaningfulness of talking about two somethings none of us understands, and none of us has any comprehension or concept of?

alcontali

You actually did not describe the lemma ... What is the meaningfulness of talking about two somethings none of us understands, and none of us has any comprehension or concept of? — god must be atheist

Let me try again.

It is just a game and you must hit the diagonal.

$\begin{bmatrix}(false,false) & (true,false) \\ (false,true) & (true,true) \end{bmatrix}$

The first example predicate, "isEven", will return true if a number is even and false if it is odd.

In this game, you can use whatever logic sentence you want, but if it is true, its number must be even. If it is false, then its number must be odd. You must stay on the diagonal!

The diagonal lemma does not tell you how to do that. It only says that it should be possible to find at least one sentence that will successfully hit the diagonal.

So, let's start up a simple search strategy. We generate arbitrary true sentences and convert them to numbers (using their standard utf8 encoding):

1. utf8( 1=1 ) = 496149
2. utf8( 1=1 or 99=99 ) = 49614932111114325757615757
3. utf8( 1=1 or 99=99 or 0=0 ) = 496149321111143257576157573211111432486148 $\Leftarrow$ BINGO!

Example 3 is true and even. So, it is a solution, i.e. a witness to the lemma. Just for the sake of the argument, let's now try to find an arbitrary false sentence that is odd:

4. utf8( 0=1 ) = 486149 $\Leftarrow$ BINGO!

Example 4 is false and odd. So, it is also a solution, i.e. a witness to the lemma.

Let's take another example predicate, "isPrime", which will return true if the number is a prime number, and false if it is not.

Well, again, the lemma does not tell you how to conduct your search strategy. It only says that you can always hit the diagonal. It is always possible. Hence, you should always be able to win that game if you try long enough. There is even an obnoxious proof that guarantees it (and that everybody seems to be complaining about).

By the way, you can use the utf8 to decimal test page to convert directly from logic sentence to natural number. Just use the "BigDecimal" box. It works really well.

So, what is the link with Gödel's incompleteness theorem? The "isProvable" predicate works exactly in the same way as the "isEven" or "isPrime" predicates.

So, you can also play this game with the "isProvable" predicate, but the really interesting game is with the "isNotProvable" predicate, because as soon as you win the game by finding a true sentence, you will have a true sentence that also "isNotProvable", and that is considered to be an astonishing result in metalogic and metamathematics.

So we don't know what the problem is, and we don't know its solution. — god must be atheist

Well, I am just using a trick of collaborative learning here. I try to force myself to give an understandable explanation about a difficult subject to people who do not understand it, because that also improves my own understanding. So, I was rather hoping to hear really "hard" questions that would somehow compel me to solve them.

Of course, all of that requires people who are interested in learning and who will not merely be complaining that they do not understand things.

So, no, you cannot just say, "you do not understand it". That is not how you test someone's understanding. If you really believe that, then you simply do not understand the term "understanding" itself. You simply need to ask a (difficult) question (and then another one, and so on) and then discover that I cannot find the answer, while I should, if I really understood the problem. It is only the inability to solve problems that reveals a lack of understanding.

god must be atheist

It is just a game and you must hit the diagonal.

[(false,false)(false,true)(true,false)(true,true)][(false,false)(true,false)(false,true)(true,true)]

The first example predicate, "isEven", will return true if a number is even and false if it is odd.

In this game, you can use whatever logic sentence you want, but if it is true, its number must be even. If it is false, then its number must be odd. You must stay on the diagonal! — alcontali

Hm. A fine explanation you gave me, huh?

1. How do you hit a diagonal? What is the meaning of "hitting a diagonal"? There must be some meaning other than punching my computer screen with my fist.
2.use whatever logic sentence you want, but if it is true, its number must be even. You haven't told us how to determine the number of a sentence. And once you give us the rule to determine the number of a sentence (I imagine it's ordinal numbers, not cardinals), then...
3. What's a "logic sentence"? I imagine "Badly written, explained or described logic puzzles must be sentenced to spend a minimum of two years, maximum of five years, term in prison, and/or fined ten thousand dollars."
4. I searched the opening topic, and there are no examples. I looked at more posts down the page, and they were incomprehensible. Certainly not on the level of a 12-year-old. (I can certify this. I asked my 12-year-old granddaughter to please tell me in English what you said and she revealed her wisdom to me: "Grampa, it's gibberish.")
6. What are you using as predicate? "isEven" is not an expression I understand.
7. If I am too stupid to understand this, please tell me now, outright, so I shall cease and desist, and not bother you with questions.

god must be atheist

So, no, you cannot just say, "you do not understand it". — alcontali

I don't think you can prove that. But I can disprove this claim by you.

"You do not understand it", "you do not understand it", "you do not understand it", "you do not understand it", "you do not understand it".

There. Four instances of empirical observations of real occurences that deny the truth of your statement.

alcontali

7. If I am too stupid to understand this, please tell me now, outright, so I shall cease and desist, and not bother you with questions. — god must be atheist

I am convinced that a 12-year old can understand it. Seriously, I mean this.

You haven't told us how to determine the number of a sentence. And once you give us the rule to determine the number of a sentence (I imagine it's ordinal numbers, not cardinals), then... — god must be atheist

This first step is the hardest part and it amounts to learning how to use one text box in a particular web page.

I know from experience that 12-year olds can use otherwise very complicated pages in mobile games. This page is much, much easier to learn how to use than what they already know how to use. Furthermore, learning how to use this page is the hardest part in the Gödel game.

Every minute that I spend on this issue, I get more convinced that it can be explained to a 12-year old.

First, you must be able to reach this page: https://onlineutf8tools.com/convert-utf8-to-decimal.

Just copy this link to your browser bar, or click on the link, or whatever. You will need to go there.

The reason is that we are operating in number theory. So, everything you will say in the game has to be a natural number. This is non-negotiable. Still, you can trivially convert every sentence (or sequence of sentences) into just one number.

You first must configure the page correctly. Somewhere in the middle of the page, you will find the heading:

Utf8 to decimal converter examples Click to use

Below that heading you will find three boxes:

Aliens, UTF8 Lottery Balls, and Big Decimal Number

Click in the box "Big Decimal Number".

Now you will see that the page has moved you up again. You can see two boxes at the top of the page: one box on the left, titled utf8, and another box on the right, titled decimal.

Now you can type any sentence in the utf8 box and it will automatically convert everything that you have typed into one big decimal number in the decimal box.

Example:

I am hungry and I want to eat fish
becomes:

733297109321041171101031141213297110100327332119971101163211611132101971163210210511510446

Again, you really need this step, because if you do not convert your sentences into numbers, you cannot use number theory to say anything about your sentences.

Try to do it for the following example sentences:

CIA Whistleblower 'Professionally Tied' To 2020 Candidate

Which should yield:

677365328710410511511610810198108111119101114323980114111102101115115105111110971081081213284105101100393284111325048504832679711010010510097116101

Try also:

The Surge In "Surprise" Medical Bills Bankrupting Americans Can Be Blamed On Private Equity

Which should yield:

84104101328311711410310132731103234831171141121141051151013432771011001059997108326610510810811532669711010711411711211610511010332651091011141059997110115326797110326610132661089710910110032791103280114105118971161013269113117105116121

Copy/paste a few other arbitrary examples by yourself and convert each sentence into a corresponding big decimal number. Once you can do that, the remainder of the game will be much easier to play.

Let me know if it works for you!

-- Note --

Funny, but true, the entire internet happens to be encoded in a Gödel numbering scheme. Every single page is like that! It is not that they consciously "wanted" to do that. It just turned out to be like that.

Andrew M

Especially its proof is considered to be incomprehensible. That is a problem because both Gödel's first incompleteness theorem and Tarski's undefinability theorem trivially follow from this lemma. Let's attempt to come up with a more intuitive explanation anyway. — alcontali

I like what you're attempting here. The first two steps seem okay to me.

Third step. Let's now specify a property that could not possibly apply to any sentence

Let's define K(%M) = false. Say that K means "heavy". (It could mean anything, really). There is no number or associated sentence that is "heavy" because K always returns false. We just do not want a heavy sentence in our system. Seriously, we are trying to shoehorn the situation here to prevent anything from being provably heavy. — alcontali

On my view, this is a category mistake. Sentences aren't the sort of things that are or are not heavy, so K(%M) wouldn't be truth-apt.

Look at that! We now have a sentence P that has the property of being heavy, even though K, the heaviness predicate, always returns false! How is that possible? — alcontali

It can happen when non-truth-apt sentences are treated as truth-apt. Similar to manipulating the liar sentence or "the King of France is bald" sentence.

From your later post:

3. utf8( 1=1 or 99=99 or 0=0 ) = 496149321111143257576157573211111432486148 ⇐⇐ BINGO!

Example 3 is true and even. So, it is a solution, i.e. a witness to the lemma. Just for the sake of the argument, let's now try to find an arbitrary false sentence that is odd:

4. utf8( 0=1 ) = 486149 ⇐⇐ BINGO!

Example 4 is false and odd. So, it is also a solution, i.e. a witness to the lemma. — alcontali

Nice example. Makes sense to me.

So, you can also play this game with the "isProvable" predicate, but the really interesting game is with the "isNotProvable" predicate, because as soon as you win the game by finding a true sentence, you will have a true sentence that also "isNotProvable", and that is considered to be an astonishing result in metalogic and metamathematics. — alcontali

So would this show that some true sentences are not provable, or just that those "true" sentences are problematic in some way, similar to the liar sentence or the above "heavy" sentences?

god must be atheist

Okay. It's easier to admit that I am a fucking goddamned idiot, who is stupider than a typical and normal 12-year-old, than to make sense of any of the foregoing.

I am satisfied with this conclusion.

god must be atheist

Alcontali, did you reword the opening post? I am not accusing you of that, because it was late last night that I last looked at it, but some parts that I see now I could not remember now seeing them last night.

There are for instance imbedded links to pages... were they there yesterday? Or late last night? (Eastern Daylight Savings Time.)

Even this part and the parts preceding it in the opening quote seem brand new to me:

They express their (utter) dislike for this lemma. — alcontali

Again, maybe my memory is playing tricks on me. So I ask you, instead of accusing you: did you reword the opening post?

alcontali

So would this show that some true sentences are not provable, or just that those "true" sentences are problematic in some way, similar to the liar sentence or the above "heavy" sentences? — Andrew M

Well, the term "heavy" was probably a bad choice. I couldn't think of a some good predicate, because the literature pretty much never mentions one. It needs to be something calculable true or false about a sentence. The literature typically says something like: "The sentence S has property K". Any idea of what could be a good example for K?

So would this show that some true sentences are not provable, or just that those "true" sentences are problematic in some way, similar to the liar sentence or the above "heavy" sentences? — Andrew M

Well, since "heavy" is just an arbitrary choice, I wouldn't worry about that. As long as you can calculate the property from a number, it should be ok. For example: "the face is green" should probably work better, because a face can be represented as a number, and figuring out that is green, is just a calculation on its bits and bytes. So, the diagonal lemma says that it should always be possible to construct a face that is green, but also one that is not green.

Again, maybe my memory is playing tricks on me. So I ask you, instead of accusing you: did you reword the opening post? — god must be atheist

No. I stopped drafting it after probably half an hour or so, and then left it like that.

god must be atheist

No. I stopped drafting it after probably half an hour or so, and then left it like that. — alcontali

Thanks.

Andrew M

Well, the term "heavy" was probably a bad choice. I couldn't think of a some good predicate, because the literature pretty much never mentions one. It needs to be something calculable true or false about a sentence. The literature typically says something like: "The sentence S has property K". Any idea of what could be a good example for K? — alcontali

I think either something about the form of the sentence (e.g., HasAnEvenNumberOfLetters) or about the derived Godel number as a number (e.g., your earlier IsEven and IsPrime predicates). IsProvable doesn't seem to meet that criteria since it depends on the meaning of the sentence.

Well, since "heavy" is just an arbitrary choice, I wouldn't worry about that. As long as you can calculate the property from a number, it should be ok. For example: "the face is green" should probably work better, because a face can be represented as a number, and figuring out that is green, is just a calculation on its bits and bytes. So, the diagonal lemma says that it should always be possible to construct a face that is green, but also one that is not green. — alcontali

I'm not sure I follow. "heavy" is a predicate in your third step. But "the face is green" is not a predicate. It's fine as a sentence however (with a Godel number).

I guess what I'm having trouble with is step 3 where you're looking for a property that could not possibly apply to any sentence, yet is predicable of it. Perhaps something that is necessarily false? Such as HasZeroLetters (where a valid sentence must have 1 or more letters).

alcontali

I think either something about the form of the sentence (e.g., HasAnEvenNumberOfLetters) — Andrew M

HasAnEvenNumberOfLetters is also just a property of the number associated with the sentence. Instead of converting to decimal, convert to hexadecimal (or just convert back). Example:

utf8( hello ) = 0x68 0x65 0x6c 0x6c 0x6f

Each group of 2 hexadecimal digits represents a byte. So, for "hello" we have 5 bytes, and therefore an odd number of letters. This simple procedure works for digits in the base plane of utf8. For Greek, Chinese, Japanese, Russian characters (and other non-Latin character sets), it represents one letter as two, three, or four bytes. But then again, you know from the first byte (special value), how many other bytes are attached. So, you can then count the letters by counting the groups of bytes.

Since the restriction of the Unicode code-space to 21-bit values in 2003, UTF-8 is defined to encode code points in one to four bytes, depending on the number of significant bits in the numerical value of the code point. The following table shows the structure of the encoding. The x characters are replaced by the bits of the code point. If the number of significant bits is no more than seven, the first line applies; if no more than 11 bits, the second line applies, and so on.

byte number one (represented in binary) indicates the size of the group of bytes:
0xxxxxxx --> 1 byte, 110xxxxx --> 2 bytes, 1110xxxx --> 3 bytes, 11110xxx --> 4 bytes.

So, counting letters in utf8 is just another numbers game.

IsProvable doesn't seem to meet that criteria since it depends on the meaning of the sentence. — Andrew M

It is also just another numbers game. Say that "12>3" is a simple theorem in arithmetic. Then, the following sequence of sentences is one possible proof:
1) 12>3
2) 12-3>3-3
3) 9>0
In 3) we hit axiom 15 in the equivalent axiomatization: i.e. zero is the minimum element.

So, now we convert the theorem to a number:

utf8("12>3")=49506251
utf8("12>3 ; 12-3>3-3 ; 9>0")=495062513259324950455162514551325932576248

So, now we can say that theorem 49506251 is provable because it is associated to another number. 495062513259324950455162514551325932576248, which is its proof. Therefore, the predicate isProvable(49506251) results in true.

What we need to do, to effectively implement a complete solution, is to store and/or compute the set of all possible 2-tuples :

{ (49506251, 49506...32576248), (theorem2, proof2), (theorem3, proof3), (theorem4, proof4), ... }

From there on, the "isProvable" predicate should work fine simply by attempting a look up in this set of tuples and return true, if it can find a proof for the theorem. It is obvious that this is a thought exercise. Gödel did not go on to execute this plan as to effectively implement "isProvable". He would have needed a computer for that in 1931, which did not even exist by them. Furthermore, even then, it is practically not attainable. Still, in an idealized world the "isProvable" predicate can really be implemented. From there on, it will still not be able to avoid hitting the diagonal lemma: there exists a true sentence which "isNotProvable".

But "the face is green" is not a predicate. It's fine as a sentence however (with a Godel number). — Andrew M

Yes, again, bad example. There is no easy way to attach a truth value to "the face" (a digital image), even if "green" is a calculable predicate about a digital image. In fact, the sentence really has to be sentence in one way or another ...

Andrew M

So, counting letters in utf8 is just another numbers game. — alcontali

Cool. No problem with that.

It is also just another numbers game. Say that "12>3" is a simple theorem in arithmetic. Then, the following sequence of sentences is one possible proof:
1) 12>3
2) 12-3>3-3
3) 9>0
In 3) we hit axiom 15 in the equivalent axiomatization: i.e. zero is the minimum element.

So, now we convert the theorem to a number:

utf8("12>3")=49506251
utf8("12>3 ; 12-3>3-3 ; 9>0")=495062513259324950455162514551325932576248

So, now we can say that theorem 49506251 is provable because it is associated to another number. 495062513259324950455162514551325932576248, which is its proof. Therefore, the predicate isProvable(49506251) results in true. — alcontali

Thanks! Very clear.

Still, in an idealized world the "isProvable" predicate can really be implemented. — alcontali

Meaning that ideally every true statement has a corresponding proof and every false statement has no corresponding proof (or perhaps a corresponding disproof)?

And is that the diagonal? (i.e., false/not provable, true/provable)

From there on, it will still not be able to avoid hitting the diagonal lemma: there exists a true sentence which "isNotProvable". — alcontali

OK, how does this part work?

alcontali

Still, in an idealized world the "isProvable" predicate can really be implemented — alcontali

Meaning that ideally every true statement has a corresponding proof and every false statement has no corresponding proof (or perhaps a corresponding disproof)? — Andrew M

Not every true statement but every theorem will have a corresponding proof. A theorem is defined as a sentence that has a corresponding proof. A true statement is a statement that just happens to be logically true. So, false statements will have no corresponding proof, but the lemma guarantees that there will also be true statements that have no corresponding proof. Such lemma-witness statement will be true, but there is no way that you can prove it.

And is that the diagonal? (i.e., false/not provable, true/provable) — Andrew M

OK, how does this part work? — Andrew M

In general the diagonal is:

== GENERAL CASE ==

$\begin{bmatrix} sentence/hasPropertyX & false & true \\ false & \color{blue}{\boldsymbol{(false,false)}} & (false,true) \\ true & (true,false) & \color{blue}{\boldsymbol{(true,true)}} \end{bmatrix}$

The diagonal lemma's "diagonal" is depicted in blue in the table.

The diagonal lemma says that it is always possible for any arbitrary property about numbers to hit the diagonal. This means that you can always find a true sentence that has the property but also a false sentence that does not have the property.

In logic language, if S is a sentence and P is a property about numbers and %S is the numerical encoding of S then the canonical logic form for that is: S $\leftrightarrow$ P(%S).

This lemma is provable for all number predicates; not just provability (which is itself also just a number predicate). Gödel's incompleteness theorem is just an application of this diagonal lemma. It just just one particular example of the diagonal lemma:

== SPECIAL EXAMPLE CASE ==

$\begin{bmatrix} sentence/\boldsymbol{\color{green}{isNotProvable}} & false & true \\ false & \boldsymbol{(false,false)} & (false,true) \\ true & (true,false) & \color{blue}{\boldsymbol{(true,true)}} \end{bmatrix}$

The general diagonal lemma itself is not considered to be "amazing". It is this one special application of the lemma in the table above, simply by picking propertyX=isNotProvable, that has shaken heaven and earth in 1931.

In my experience, you can develop a good intuition for these theorems by playing the diagonal game a few times more often.

Pick whatever property. Then, generate arbitrary false sentences until you find one that does not have the property. Next, generate true sentences until you find one that does have the property. You win the game as soon as you hit the two boxes of the diagonal.

Andrew M

↪alcontali

OK, to briefly recap:

The sentence "12>3 ; 12-3>3-3 ; 9>0" is a proof of the theorem "12>3". So the sentence "12>3" is both true and provable. It thus hits the diagonal for that sentence and property (in this case, isProvable).

Also, any sentence can be encoded to (and decoded from) a unique natural number (the Godel number).

The diagonal lemma says that it is always possible for any arbitrary property about numbers to hit the diagonal. This means that you can always find a true sentence that has the property but also a false sentence that does not have the property. — alcontali

This is the part I don't understand. How is this proved?

alcontali

This is the part I don't understand. How is this proved? — Andrew M

That is exactly the diagonal lemma.

Take any property, e.g. isLargeNumber. Say that isLargeNumber is true for numbers above 10^20, and false for numbers that are smaller.

Now, the diagonal lemma says that you can always find a true sentence for which isLargeNumber is true. You can also always find a false sentence for which isLargeNumber is false.

Forget about Gödel's incompleteness theorem as long as you do not completely grok the diagonal lemma. Make exercises on the lemma, until you thoroughly understand it.

Andrew M

Take any property, e.g. isLargeNumber. Say that isLargeNumber is true for numbers above 10^20, and false for numbers that are smaller.

Now, the diagonal lemma says that you can always find a true sentence for which isLargeNumber is true. You can also always find a false sentence for which isLargeNumber is false. — alcontali

So a very long sentence could have a Godel number above 10^20 (say, "0=0 and 1=1 and ... 10^20=10^20"). And that sentence could be true or false.

But how about the property isNegativeNumber? That property will never be true.

alcontali

But how about the property isNegativeNumber? That property will never be true. — Andrew M

Actually, you caught me on a semantic problem. I should not have called the property "isLargeNumber". I should simply have called it "isLarge" because it becomes a property of the sentence.

Mutatis mutandis, we should deal with the property "isNegative" and not "isNegativeNumber", even though we will calculate it by checking if the number is negative (which is always false for a utf8 decimal).

Let say that S is a false sentence. isNegative(%S) is false, simply because isNegative of any %X is false. So, since they are both false, the expression:

S $\leftrightarrow$ isNegative(%S)

is on the diagonal, i.e. in the box (false,false). This means that the sentence S has the isNegative property, even though %S is a positive number.

Andrew M

↪alcontali

OK, so to go back to the third step in your initial post, K could be isNegative. And so isNegative(%M) is false. Then, per the fourth step, any false sentence will have the property isNegative.

Given the above, it seems that there doesn't have to be a true statement that is not provable. There could instead be a false statement that is provable. So it would be a choice between incompleteness and unsoundness?

I'm also curious about what happens with isFalse. It seems that it will never hit the diagonal. Is that a problem for the diagonal lemma?

alcontali

OK, so to go back to the third step in your initial post, K could be isNegative. And so isNegative(%M) is false. Then, per the fourth step, any false sentence will have the property isNegative. — Andrew M

Yes, with false statements already hitting the diagonal (false,false) there is no compelling reason why true statements would hit the diagonal in (true,true). It is simply not possible to make isNegative(%S) return true. So, I don't think that (true,true) could ever occur.

Given the above, it seems that there doesn't have to be a true statement that is not provable. There could instead be a false statement that is provable. So it would be a choice between incompleteness and unsoundness? — Andrew M

Yes, that is exactly what Gödel concluded. Either the system is incomplete, hitting the diagnal in (true,true) or else it is inconsistent (=unsound), hitting the diagonal in (false,false). Let me check the exact phrasing of this conclusion:

The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an effective procedure (i.e., an algorithm) is capable of proving all truths about the arithmetic of natural numbers.

The incompleteness theorems apply to formal systems that are of sufficient complexity to express the basic arithmetic of the natural numbers and which are consistent, and effectively axiomatized, these concepts being detailed below.

There are several properties that a formal system may have, including completeness, consistency, and the existence of an effective axiomatization. The incompleteness theorems show that systems which contain a sufficient amount of arithmetic cannot possess all three of these properties.

Now, then the commentators argue that standard number theory "seems' to be consistent:

The theory of first order Peano arithmetic seems to be consistent. Assuming this is indeed the case, note that it has an infinite but recursively enumerable set of axioms, and can encode enough arithmetic for the hypotheses of the incompleteness theorem. Thus by the first incompleteness theorem, Peano Arithmetic is not complete.

Therefore, the (false,false) box in the diagonal was originally not "considered" possible (false and provable) because arithmetic was "considered" consistent. This statement became quite questioned, until at some point it was actually "mostly" proven:

In 1958, Gödel published a method for proving the consistency of arithmetic using type theory.[21] In 1936, Gerhard Gentzen gave a proof of the consistency of Peano's axioms, using transfinite induction up to an ordinal called ε0.[22] Gentzen explained: "The aim of the present paper is to prove the consistency of elementary number theory or, rather, to reduce the question of consistency to certain fundamental principles". Gentzen's proof is arguably finitistic, since the transfinite ordinal ε0 can be encoded in terms of finite objects (for example, as a Turing machine describing a suitable order on the integers, or more abstractly as consisting of the finite trees, suitably linearly ordered). Whether or not Gentzen's proof meets the requirements Hilbert envisioned is unclear: there is no generally accepted definition of exactly what is meant by a finitistic proof, and Hilbert himself never gave a precise definition.

The vast majority of contemporary mathematicians believe that Peano's axioms are consistent, relying either on intuition or the acceptance of a consistency proof such as Gentzen's proof. A small number of philosophers and mathematicians, some of whom also advocate ultrafinitism, reject Peano's axioms because accepting the axioms amounts to accepting the infinite collection of natural numbers.

So, there is not 100% agreement on the idea that Gentzen's proof of the consistency of number theory is actually finitistic, because the natural numbers themselves are an infinite collection.

So, yes, your interpretation is considered correct: Either a (number-theory-including) theory is inconsistent or it is incomplete. They argued for long after Gödel's initial lecture in 1930 over this conclusion, and the matter was barely settled in 1958.

Standard number theory is considered not to be hitting the diagonal in (false,false) (=inconsistent) but in (true,true) (=incomplete) because its consistency proofs have been accepted.

Andrew M

↪alcontali

Thanks, that was very interesting.

OK, so my understanding is that one sentence that hits (true,true) for isNotProvable is the sentence that asserts that it is itself not provable. How is that expressed as a mathematical sentence?

Also, why is it thought to be true? Is it simply that assuming that it is provable leads to contradiction?

alcontali

OK, so my understanding is that one sentence that hits (true,true) for isNotProvable is the sentence that asserts that it is itself not provable. How is that expressed as a mathematical sentence? — Andrew M

X $\leftrightarrow$ isNotProvable(%X)

The diagonal lemma does not tell you, however, how to find that true sentence. It only guarantees that it exists.

Also, why is it thought to be true? — Andrew M

Because such true sentence exists. With "isNotProvable" being a number predicate, there is an X that satisfies it. We do not need to actually find this sentence X.

Is it simply that assuming that it is provable leads to contradiction? — Andrew M

This true sentence X has the property "isNotProvable". It is not about a contradiction. It is just about the fact that we can define the "isNotProvable" predicate as a number predicate. From there on, there simply exists a true sentence X that satisfies the diagonal lemma.

Searching for such true witness X, requires you to actually construct the "isNotProvable" predicate first. That can, however, only be done as a thought exercise. That is why we do not really search for X. We are already satisfied with the theorem that it must exists.

Andrew M

It is just about the fact that we can define the "isNotProvable" predicate as a number predicate. — alcontali

If no true but unprovable X has been found to satisfy "X ↔ isNotProvable(%X)", then why should we consider it to be a satisifiable definition?

Also, would "X ↔ isNotTrue(%X)" be considered a satisifiable definition? I assume not, but that then raises the question of the criteria for judging that a definition is satisfiable.

simeonz

I would like to rudely interject and ask a neophyte question that has been bugging me for some time. Tell me if you think it deserves a separate thread or has been previously addressed. I am not sure that it is worth its own thread and my understanding of the subject is somewhat limited.

Anyway, to my knowledge, the trick to Gödel's incompleteness is that it is about semantics. Originally the theorem was formulated in a syntactic variant, which was much more philosophically obvious, but was later refined to semantics, which is to me much more surprising. The theorem tells us that any sufficiently expressive axiomatic system is (ironically) insufficiently expressive to convey its own semantics.

Here is my question. Incompleteness is incurable - i.e. you cannot complete and incomplete axiomatic system by adding axioms. However, our very proof is done in formal logic, and thus provides a new axiomatic system, which embeds the previous one and eliminates the prior incompleteness by means of logical trichotomy - a statement of the original axiomatic system becomes either true, or false, or not provable (but semantically true or false). This new axiomatic system should be incomplete as well. But proving this would require embedding it once more, and reasoning in a similar way. Now, if we take the closure of this process - meaning, if we assume that any statement is provable if it is provable in at least one of the embeddings that define the semantics of the previous axiomatic system, then I speculate that we may be able to explore all embeddings in attempt to prove any statement using gradually expanding method, starting with finite inference steps in the basis axiom system and gradually adding inferences from the meta-systems. The point is - if we find no proof for a statement at all, than we cannot prove that it is semantically true, because it would mean that a proof existed in one of the embeddings, which is a contradiction. Therefore we cannot prove a statement that cannot be proven in this axiomatic system is semantically true, and to the extent of our logical method, this new axiomatic system can never be proven incomplete.

Or am I missing something here. Is there some uncountability involved or will the semantics eventually become inamenable to effective definition.

Edit: I think that I understand the problem now that I wrote it. :) I suspect that the semantics are not "continuous" with respect to the closure operation. The semantics of this new axiomatic system are probably not contained in the union of the embeddings. I can add the axiomatic system for the semantics of the closure to the list of axiomatic systems as well, but I suspect that this list cannot remain a sequence anymore, if I do this continuously.. and my proof method will probably fail.

Edit 2: To think about it - I am not sure whether an axiomatic system with proofs for all true statements of arithmetic exists. The semantic embedding, as I called it. Not for all statements true in its own semantics, just of arithmetic. Now I realize how many gaps I have in my knowledge. :)

alcontali

If no true but unprovable X has been found to satisfy "X ↔ isNotProvable(%X)", then why should we consider it to be a satisifiable definition? — Andrew M

How it materializes in practice is rather that we find a statement S, of which we can prove that neither S nor the opposite of S can be proven in theory T (such as the standard theory of arithmetic). So, is this statement true or false? Well, how can you know this, since you cannot prove anything about it? So, in all practical terms, we do not run into true statements that are unprovable, but into undecidable statements. There are lots of witness statements for fundamental undecidability, some of which must indeed be true, but how can we know that?

Also, would "X ↔ isNotTrue(%X)" be considered a satisifiable definition? I assume not, but that then raises the question of the criteria for judging that a definition is satisfiable. — Andrew M

The conclusion of Tarski's undefinability theorem is that the "IsNotTrue" predicate is simply not allowed in arithmetic:

$\begin{bmatrix} sentence/\boldsymbol{\color{green}{IsNotTrue}} & false & true \\ false & \color{blue}{\boldsymbol{(false,false)}} & (false,true) \\ true & (true,false) & \color{blue}{\boldsymbol{(true,true)}} \end{bmatrix}$

Both slots on the diagonal are poisonous.

The first slot (false,false) means that there exists a false statement that is not "isNotTrue" (meaning, which is true). Hence, that would be a false statement that is true. The second slot (true,true) means that there exists a true statement that "isNotTrue". Hence, that would be a true statement that would be false. Since the diagonal lemma says that there exists a sentence that will hit the diagonal at least in one of both slots, the "isNotTrue" predicate will always lead to the existence of a liar sentence, i.e. an inconsistency.

Therefore, "isNotTrue", "isTrue", "isFalse", and "isNotFalse" cannot be defined as predicates. It is simply not allowed to put them in the table in the green spot. That is the gist of Tarski's undefinability theorem (or truth theorem):

Tarski's undefinability theorem, stated and proved by Alfred Tarski in 1936, is an important limitative result in mathematical logic, the foundations of mathematics, and in formal semantics. Informally, the theorem states that arithmetical truth cannot be defined in arithmetic.The theorem applies more generally to any sufficiently strong formal system, showing that truth in the standard model of the system cannot be defined within the system. The undefinability theorem is conventionally attributed to Alfred Tarski. Gödel also discovered the undefinability theorem in 1930, while proving his incompleteness theorems published in 1931, and well before the 1936 publication of Tarski's work (Murawski 1998). While Gödel never published anything bearing on his independent discovery of undefinability, he did describe it in a 1931 letter to John von Neumann.

The formal statement of Tarski's undefinability theorem is, of course, expressed in terms of the diagonal lemma:

That is, there is no L-formula True(n) such that for every L-formula A, True(g(A)) $\leftrightarrow$ A holds.

So, there does not exist such number predicate True(%S) because there would always exist exceptions to the proposition that: S $\leftrightarrow$ True(%S). That would render the entire theory inconsistent.

Attempt at an intuitive explanation (ELI12) for the weirdest logic theorem ever (Gödel-Carnap)

Welcome to The Philosophy Forum!

Categories

More Discussions