Richard’s paradox

The following formulation of Richard’s paradox is from the book Computability and Logic, Chapter 2, Diagonalization, Problem 2.13:

Q: What (if anything) is wrong with the following argument?

The set of all finite strings of symbols from the alphabet, including the space, capital letters, and punctuation marks, is enumerable; and for definiteness let us use the specific enumeration of finite strings based on prime decomposition.Some strings amount to definitions in English of sets of positive integers and others do not. Strike out the ones that do not, and we are left with an enumeration of all definitions in English of sets of positive integers, or replacing each definition by the set it defines, an enumeration of all sets of positive integers that have definitions in English. Since some sets have more than one definition, there will be redundancies in this enumeration of sets. Strike them out to obtain an irredundant enumeration of all sets of positive integers that have definitions in English.

Now consider the set of positive integers defined by the condition that a positive integer n is to belong to the set if and only if it does not belong to the nth set in the irredundant enumeration just described.

This set does not appear in that enumeration. For it cannot appear at the nth place for any n, since there is a positive integer, namely n itself, that belongs to this set if and only if it does not belong to the nth set in the enumeration. Since this set does not appear in our enumeration, it cannot have a definition in English. And yet it does have a definition in English, and in fact we have just given such a definition in the preceding paragraph.

  • Duck

    The errors is that you can enumerate an infinite list in this way. It is similar to the Godel diagonalization problem: write down all distinct positive integers in a matrix. Then write down another number that adds one to the diagonal of every number in the matrix. The new number is different than all the previous numbers and was not in the list. This process may be repeated an infinite number of times.

    There are an infinite combination of finite strings. You can’t write them all down, because I can always find at least one string you left out.