Exploring the Philosophical Implications of Godel's Incompleteness Theorems

[Demystifier]

Consider the following sentence:
"Prof. Godel cannot prove this sentence."
Is this sentence true? If it is true, can Prof. Godel prove it? If he can't, does it tell us anything about Prof. Godel? More generally, does it tell as anything about creative human mathematicians (who are supposed to be more than formal machines)?

A further (obvious) twist is the sentence:
"Nobody can prove this sentence."
Is this sentence true? If it is, how do you know?

The questions are, of course, philosophical, but Godel himself was thinking a lot about philosophical consequences of his theorems, so we can too.

 

[mfb]

"Prof. Godel cannot prove this sentence."

This sentence is true, Gödel cannot prove it because he is dead.

"Nobody can prove this sentence."

I'm not sure if we can make that statement mathematically well-defined.

 

[Demystifier]

This sentence is true, Gödel cannot prove it because he is dead.

You are missing the point. Replace "Prof. Godel" with "The best living logician".

 

[Demystifier]

Or even better, suppose that a great logician says:
"I cannot convince myself that this sentence is true."

 

[dkotschessaa]

I'm not sure if we can make that statement mathematically well-defined.

Me neither. I think to really investigate the nature of this paradox (if it is something new or if it reduces to one that we already know about) we'd need a more precise way to formulate it.

 

[Demystifier]

Well, logic is not only formal logic. For instance Prof. Smullyan, who has written a serious formal book on Godel theorems
https://www.amazon.com/dp/0195046722/?tag=pfamazon01-20
has also written several non-formal books such as
https://www.amazon.com/dp/0394549430/?tag=pfamazon01-20
where he studies Godel-like logical paradoxes using only plain english. If Prof. Smullyan can get that "low", then so can we.

 

[dkotschessaa]

oh, I have no problem with that. It's just that I find the question interesting and my curiosity leads me to seek a formal investigation. I think your avatar would agree! :)

 

[Demystifier]

I think your avatar would agree! :)

He certainly would, he is famous for works in both formal logic and plain English philosophy.

 

[Demystifier]

The standard Godel sentence can be expressed in plain english as:
"This sentence cannot be proved within a certain closed system of axioms".
This sentence is true and can be proved, but only if one steps out from this closed system of axioms.

It seems to me that my sentences in the posts above are not like this sentence. Instead, they seem to be more like inconsistent sentences such as:
"This sentence is not true."

If I am right, then this seems to resolve the paradox.

 

[stevendaryl]

The standard Godel sentence can be expressed in plain english as:
"This sentence cannot be proved within a certain closed system of axioms".
This sentence is true and can be proved, but only if one steps out from this closed system of axioms.

It seems to me that my sentences in the posts above are not like this sentence. Instead, they seem to be more like inconsistent sentences such as:
"This sentence is not true."

If I am right, then this seems to resolve the paradox.

I think you should use Penrose instead of Godel, because he's alive, and because he seems to think that Godelian arguments can be used to prove that human mathematical abilities are beyond those of machines.

Let's use "unassailably true", because I think that's the phrase Penrose uses in "The Emperor's New Mind". Something is unassailably true if it is true, and it's possible for a competent mathematician to convince himself that it is true, and that there is no doubt possible. For example: "2+2=4". Then define the Penrose sentence to be:

"Penrose will never accept this sentence to be unassailably true"

I do not agree that this is an antinomy such as the Liar paradox---"This sentence is not true"---because it is possible for it to be true, and it's also possible for it to be false (while the Liar paradox cannot consistently be either). It can be true, and yet Penrose never accepts it (there are true statements that he never accepts as unassailably true). Or it can be false (there might be false statements that he mistakenly believes are unassailable truths).

I guess what you could say about it is that Penrose would never accept it to be unassailably true, since it is an obvious mistake to do so. But suppose we add some "closure" properties to his set of unassailable truths: Suppose we assume the following:

If Penrose considers statements $S_1, S_2, ...$ to all be unassailable, and $C$ follows logically from those statements, then he will eventually come to believe $C$ to be unassailably true, as well. If his unassailable beliefs don't have this property, then they might be logically inconsistent, but still paraconsistent---A paraconsistent theory is one that is still useful even if it's logically inconsistent; the inconsistency doesn't make the whole theory useless. I actually think that humans are paraconsistent, but not consistent.

If we assume that Penrose' unassailable beliefs are logically closed, then he might not realize immediately that other unassailable beliefs of his logically imply the Penrose sentence.

 

[stevendaryl]

Here's another take on what @Demystifier is saying.

Suppose that we strap Roger Penrose into a chair and stick probes into his brain, and suppose that we have a theory of brain functioning that is complete enough that we can monitor his thinking. Then we do the following experiment:

1. We project various statements onto a screen and ask Penrose to read each statement and decide whether he agrees with the statement or not.
2. If he agrees, then our brain monitor will know it, and will turn on a green indicator light.
3. If he disagrees, then our brain monitor will turn on a red indicator light.
4. Initially, both indicator lights are off.

Now, suppose that the statement that is projected onto the screen is:

• The green indicator light will not turn on.

In contrast with the Liar paradox, the statement that Penrose is being asked about has a completely clear semantics; there are no philosophical terms such "truth".

But if the machinery works the way I've described, and Penrose knows that, then will the green indicator light come on, or not?

 

[stevendaryl]

Or even better, suppose that a great logician says:
"I cannot convince myself that this sentence is true."

He might suspect that it is true, even though he can't give an airtight convincing argument.

 

[Zafa Pi]

But if the machinery works the way I've described, and Penrose knows that, then will the green indicator light come on, or not?

Can Penrose fake what he believes (vis a vis the machine)?

 

[stevendaryl]

Can Penrose fake what he believes (vis a vis the machine)?

Well, the assumption is that the machine is accurate. You can certainly avoid paradox by saying that any such machine must be (at times) inaccurate.

 

[Zafa Pi]

But if the machinery works the way I've described, and Penrose knows that, then will the green indicator light come on, or not?

But if the machinery works the way I've described, and Penrose knows that, then will the green indicator light come on, or not?

What I was getting at is e.g.: Penrose knows that, but when the machine is turned on Penrose has managed to believe the green light will come on iff Goldbach's conjecture is true. What controls do we have over Penrose's beliefs?

 

[stevendaryl]

What I was getting at is e.g.: Penrose knows that, but when the machine is turned on Penrose has managed to believe the green light will come on iff Goldbach's conjecture is true. What controls do we have over Penrose's beliefs?

With the usual Godel proof, the conclusion is:

"If the system is sound (never proves false statements) then the Godel sentence is a true statement that the system fails to prove."

The corresponding case for Penrose would be:

"If his beliefs are sound, then this is a true statement that he can never know to be true."

So his beliefs being unsound is a loophole. In the case of formal theories, you can strengthen the theorem to "If the system is consistent (never proves a contradiction) then the Godel sentence is neither provable nor refutable". I don't see off the bat how to get a corresponding Penrose statement.

 

[Zafa Pi]

"If his beliefs are sound, then this is a true statement that he can never know to be true."

I have a problem of what constitutes a sound belief. My guess is that it would be defined as one that doesn't believe in something false.
So if he believes that the green light will come on iff Goldbach's conjecture is true, then is that a sound belief?

 

[stevendaryl]

I have a problem of what constitutes a sound belief. My guess is that it would be defined as one that doesn't believe in something false.
So if he believes that the green light will come on iff Goldbach's conjecture is true, then is that a sound belief?

I would have to know whether Goldbach's conjecture is true to know whether that belief is sound.

 

[Zafa Pi]

I would have to know whether Goldbach's conjecture is true to know whether that belief is sound.

I think I'm losing soundness of mind.
Let's assume B.c. is decidable.
So if you knew B.c. is true you would know that belief is sound.
If you knew B.c. was false would you know that belief is sound?
If so, then, then you would know that belief is sound whether or not B.c. is true.

 

[stevendaryl]

I think I'm losing soundness of mind.
Let's assume B.c. is decidable.
So if you knew B.c. is true you would know that belief is sound.
If you knew B.c. was false would you know that belief is sound?
If so, then, then you would know that belief is sound whether or not B.c. is true.

By "B.C." do you mean "Goldbach's conjecture"? If so, that's a strange acronym for it.

By "that belief", which belief do you mean?

Let's label the various claims:

• C1 = Goldbach's conjecture
• C2 = The green light will come on (indicating Penrose believes whatever statement is printed on the screen).
• C3 = C2 $\Leftrightarrow$ C1
• C4 = whatever statement is shown on the screen

So you were asking what if Penrose believes C3. By definition, his beliefs are sound if and only if he never believes anything false. So if his beliefs are sound, then either:

1. C1 is true and C2 is true and Penrose believes C4 (whatever that is)
2. C1 is false and C2 is false and Penrose does not believe C4.

His beliefs are not sound if either:

1. C1 is true and C2 is false and Penrose dos not believe C4
2. C1 is false and C2 is true and Penrose believes C4

Since I personally don't know whether C1 or C2 is true, I can't say whether Penrose' beliefs are sound or not.

 

[MrRobotoToo]

Regarding Penrose's claim that mathematical understanding is non-algorithmic, it seems to me that he has a too-narrow view of what constitutes an algorithm. What he refers to as 'mathematical understanding' is a mix of pattern recognition and visual reasoning. Such cognitive abilities can't be boiled down to a few simple rules in the same way as Peano arithmetic. Instead, one would have to code either a very complex artificial neural network or a full simulation of an entire human brain.

 

[stevendaryl]

Regarding Penrose's claim that mathematical understanding is non-algorithmic, it seems to me that he has a too-narrow view of what constitutes an algorithm. What he refers to as 'mathematical understanding' is a mix of pattern recognition and visual reasoning. Such cognitive abilities can't be boiled down to a few simple rules in the same way as Peano arithmetic. Instead, one would have to code either a very complex artificial neural network or a full simulation of an entire human brain.

The problem is that any program whatsoever that generates mathematical statements, whether it uses heuristic reasoning or pattern recognition or whatever, is equivalent to a formal theory such as Peano arithmetic, provided that it's deductively closed (that is, if $A \rightarrow B$ is generated and $A$ is generated, then eventually $B$ will be generated.

 

[MrRobotoToo]

The problem is that any program whatsoever that generates mathematical statements, whether it uses heuristic reasoning or pattern recognition or whatever, is equivalent to a formal theory such as Peano arithmetic, provided that it's deductively closed (that is, if $A \rightarrow B$ is generated and $A$ is generated, then eventually $B$ will be generated.

Goodstein's theorem, one of Penrose's favorite examples, isn't provable in Peano arithmetic, but it is provable in second-order arithmetic. I guess the question then becomes whether there exists a formal system that can encompass all mathematical statements that would be of interest to humans, and whether such a system can be executed by a Turing machine.

 

[stevendaryl]

Goodstein's theorem, one of Penrose's favorite examples, isn't provable in Peano arithmetic, but it is provable in second-order arithmetic. I guess the question then becomes whether there exists a formal system that can encompass all mathematical statements that would be of interest to humans, and whether such a system can be executed by a Turing machine.

Well, it can be proved in ZFC. Any so-called "recursively enumerable" theory can be generated by a Turing machine.

 

[sysprog]

Not all self-referential statements produce paradoxes, e.g the statement "this statement comprises five words" is true. That statement is not paradoxical in that it refers to a word count which is first-order verifiable. Statements or systems of statements that are self-referential or inter-referential and that predicate regarding their truth-values are paradoxical e.g if they deny or affirm their own truth-values, e.g. "this statement is false" is paradoxical in that if taken as true it renders its falsity inferable, and if taken as false, it renders its verity inferable, and "this statement is true" cannot be taken as meaningfully true, and taking it as false is contradictory.

The statements are second-order statements which by their forms must for legitimacy make reference to first-order statements, e.g. the statement "statement A is false" must refer to a statement A that is a first-order statement. If statement A is a first-order predication, then in classical logic it is either true or false, and the truth-values of statements about its truth or falsity can be determined based on its truth or falsity. A second-order statement that refers to another second-order statement or to itself as if it were referring to a first-order statement is not well-formed.

If we recognize such statements as making second-order predications, we can resolve the paradoxes by recognizing that the statements to which they refer are not first-order predications, so the statements, qua second-order predications, have non-legitimate referents.

 

[stevendaryl]

If we recognize such statements as making second-order predications, we can resolve the paradoxes by recognizing that the statements to which they refer are not first-order predications, so the statements, qua second-order predications, have non-legitimate referents.

Yes, having a hierarchy of statements (it's not just first and second order, but nth order, for every n) prevents semantic paradoxes, but what Godel's theorem shows is that analogs of the Liar paradox can show up in a purely first-order theory. The statement "This sentence is not provable" can be constructed in a purely first-order way. It has some of the paradoxical flavor of "This sentence is false".

 

[Zafa Pi]

By "B.C." do you mean "Goldbach's conjecture"? If so, that's a strange acronym for it.

My error, meant to type G.c.

By "that belief", which belief do you mean?

I highlighted your words, see post #19.

This business is becoming too confusing for my microbrain. I would never be able to pass the Turing test.

 

[sysprog]

Yes, having a hierarchy of statements (it's not just first and second order, but nth order, for every n) prevents semantic paradoxes, but what Godel's theorem shows is that analogs of the Liar paradox can show up in a purely first-order theory. The statement "This sentence is not provable" can be constructed in a purely first-order way. It has some of the paradoxical flavor of "This sentence is false".

I regard the statement "this sentence is false" as a second-order statement proffering itself as its first-order referent, which is improper due to the referent being a second-order statement -- i.e. a statement about the truth-value of a statement, and not a statement directly referential to a logical or empirical fact. A first-order statement says something directly about the logical or empirical world. A statement about a first order statement is by its form a second-order statement. A statement the referent of which is a second-order statement is a third-order statement. If statement A is "statement B is true" and statement B is "statement C is true" and statement C is "bicycles are vehicles" Then A, B, and C are all true, and C is first-order, B is second-order and A is third-order.

Similarly, the statement "this statement is not provable" is by its form a second-order statement, in that it refers to a statement, and not directly to a logical or empirical fact. The statement is improper, because its referent is a second-order statement. The statement "the statement '2 + 2 = 4' is provable" is a valid and true second-order statement; not a first-order statement -- the first-order statement "2+ 2 = 4" is a legitimate first-order statement within the second-order statement as its first-order referent.

As soon as we have determined that a statement is by its form of second order, it must have a first-order referent, or at least have a first-order predication on its referent, in order to be well-formed. If the referent is itself, and it contains a first order predication thereon, as the statement "this statement comprises five words" does -- that predication is directly of an empirically verifiable fact, then it is valid. But predications on and within "this statement ..." that are such as "is false" or "is provable" are second-order predications on second-order statements, i.e. they depend for their verity or falsity on the verity or falsity or provability of statements rather than on immediate facts.

 

[sysprog]

... By definition, his beliefs are sound if and only if he never believes anything false. ...

For me a reasonable definition of soundness of a belief is that a belief is sound if and only if and it is true, and validly justified, and some set or sets of true facts and valid precepts sufficient to constitute such valid justification is or are solely what is relied upon for the belief.

 

[sysprog]

For me a reasonable definition of soundness of a belief is that a belief is sound if and only if and it is true, and validly justified, and some set or sets of true facts and valid precepts sufficient to constitute such valid justification is or are solely what is relied upon for the belief.

... should be ".. if and only if it ..." -- not "... if and only if and it ..." -- I didn't notice the typo before my edit time elapsed ...

 

[stevendaryl]

Similarly, the statement "this statement is not provable" is by its form a second-order statement, in that it refers to a statement, and not directly to a logical or empirical fact. The statement is improper, because its referent is a second-order statement. The statement "the statement '2 + 2 = 4' is provable" is a valid and true second-order statement; not a first-order statement -- the first-order statement "2+ 2 = 4" is a legitimate first-order statement within the second-order statement as its first-order referent.

Yes, "this sentence is not provable" seems like a second-order statement, but it's not. That's the beauty of Godel's proof.

What Godel did was to come up with a way to map the "second-order" concept of proof to first-order concepts. The idea is roughly this:

1. Come up with a numerical "code" for each statement of arithmetic. For example, you can write down the statement using ASCII characters. Each ASCII character can be represented as a base-8 numeral. Concatenate all the base-8 numerals in a statement to get a base-8 number. Given a code, we can talk about $S_n$, the nth statement of arithmetic. Every statement of arithmetic will be $S_n$ for some value of $n$
   
2. Similarly come up with a code for each proof in the theory of Peano arithmetic.
   
3. Then corresponding to "the set of provable statements of arithmetic" is a set of numbers, "the set of codes of provable statements of arithmetic".
4. Show that this set of numbers can be defined by a formula of arithmetic. So there is some formula $P(x)$ with one free variable, x, such that for every natural number $n$, we have that $P(n)$ is true (and in fact, provable in Peano arithmetic) if and only if $S_n$ is a provable statement of arithmetic. What's important to note is the formula $P(x)$ is just an ordinary arithmetic formula, involving zero, plus, times, equality, etc.
   
5. Come up with a statement $G$ with corresponding code $g$ (that is, $G = S_g$) such that it is provable in Peano Arithmetic that $G \Leftrightarrow \neg P(g)$

So [/itex]G[/itex] is some statement of arithmetic, and $g$ is some number, and $\neg P(g)$ is another statement of arithmetic. It's all perfectly first-order. However, by the way that $P(g)$ is defined, we can see that $P(g)$ is true if and only statement $S_g$ is provable. So the negation, $\neg P(g)$, is true if and only if the statement $S_g$ is not provable. But $S_g = G$. So we have:

• $G$ is true if and only if $G$ is not provable.

G doesn't literally say "I am not provable", but we can see that it is true if and only if it is not provable.

 

[stevendaryl]

For me a reasonable definition of soundness of a belief is that a belief is sound if and only if and it is true, and validly justified, and some set or sets of true facts and valid precepts sufficient to constitute such valid justification is or are solely what is relied upon for the belief.

It's just a matter of definition. There is a distinction between something being true and there being a convincing argument that it is true. Godel's theorem actually shows that there is such a distinction, in the sense that no notion of "convincing argument" can ever completely capture all true statements.

 

[RockyMarciano]

I thought both the OP riddles and the limitations of distinguishing between n-orders to solve them were suficiently clarified at least from the early thirties and Godel's theorems and actually even before in a more heuristic way. There will always be assertions whose "truth" is unprovable if one insists on remaining within the original system of axioms. There simply are no universal axiomatic systems as Hilbert dreamt, this is formally admited but many seem not to have internalized it (the OP seems to be an example).

 

[stevendaryl]

I thought both the OP riddles and the limitations of distinguishing between n-orders to solve them were suficiently clarified at least from the early thirties and Godel's theorems and actually even before in a more heuristic way. There will always be assertions whose "truth" is unprovable if one insists on remaining within the original system of axioms. There simply are no universal axiomatic systems as Hilbert dreamt, this is formally admited but many seem not to have internalized it (the OP seems to be an example).

The OP wasn't talking about a fixed axiom system.

 

[RockyMarciano]

The OP wasn't talking about a fixed axiom system.

Ah, ok, I just noticed #9.