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

Analogy between Gödel's incompleteness proof and Richard's argument

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
argumentanalogyincompletenessrichardgödelbetweenandproof

Problem

If we take a look at Gödel's paper “On formally undecidable propositions”,
the first self referential proof given in the paper, with the following formula:

$$n \in K \equiv \overline{\textit{Bew}}[R(n); n]$$

Which look like this in more modern mathematics:

$$K = \{n \in \mathbb N : \lnot\text{provable}(R_n(n))\}$$

Gödel says:


The analogy of this argument with Richard antinomy leaps to the eye

I'm trying to figure out how this is the case:

I know Richard's Paradox basically uses Cantor's diagonal argument.

Which begins its set description like so:

$$X = \{s \in S : s \not\in f(s)\}$$

We can see the similarity between this and and Gödel's argument, especially given that both set/class descriptions end up with a self-referential contradiction.

However, I'm trying to construct a more rigorous comparison between Richard and Gödel's arguments, and how they are considered to be analogical of each other.

In particular, how the contradictions are seen to be analogous by Gödel.

Can anyone help out?

Solution

Both examples are instances of diagonalization, a technique also used to prove Cantor's theorem ($\kappa < 2^\kappa$ for all cardinals $\kappa$) and Turing's theorem that the halting problem is undecidable.

An analogy is by nature informal. It is not supposed to be rigorous.

Context

StackExchange Computer Science Q#87953, answer score: 5

Revisions (0)

No revisions yet.