patternMajor
Could Gödel’s incompleteness theorem be circumvented with a quine?
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.
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.
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.