HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

Could Gödel’s incompleteness theorem be circumvented with a quine?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
quinewithincompletenesscouldgödeltheoremcircumvented

Problem

As you all probably know, Gödel’s incompleteness theorem states, that it will never be possible for mathematics to prove its own correctness.

Mainly because that proof would be part of mathematics too, and hence need proving itself. And that leads to an infinite loop in logic.

But I realized that a quine, as in, a program that can output itself, seems to circumvent that problem: It really CAN output ALL of itself.

So I’m wondering, if the general tricks used in quines might be usable to “solve” that problem in mathematics too. At least to arrive at a different problem that might be solvable in a different way.

And if not, then I’m curious why exactly not, so I can lay this to rest in my head.

Solution

Here is the proof of Gödel's incompleteness theorem, in a nutshell, for a theory $T$. We construct a sentence $\Pi$ which states that "$T$ proves that $\Pi$ is false". The sentence mentions itself, just like a quine.

If $T$ proves $\Pi$ then $T$ also proves that $\Pi$ is false, and so $T$ cannot be sound. If $T$ proves that $\Pi$ is false then $\Pi$ is true, and so again $T$ is not sound.

Context

StackExchange Computer Science Q#149847, answer score: 39

Revisions (0)

No revisions yet.