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$

1 Answer 1

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$
2
  • $\begingroup$ I can't understand how Goedel's argument is diagonalization. Would you care to explain? $\endgroup$ Commented Feb 10, 2018 at 18:40
  • $\begingroup$ See this for example: columbia.edu/~hg17/Inc07-chap0.pdf. $\endgroup$ Commented Feb 10, 2018 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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