5
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.