Richard's paradox

In logic, Richard's paradox is a semantical antinomy of set theory and natural language first described by the French mathematician Jules Richard in 1905. The paradox is ordinarily used to motivate the importance of distinguishing carefully between mathematics and metamathematics. Kurt Gödel specifically cites Richard's antinomy as a semantical analogue to his syntactical incompleteness result in the introductory section of "On Formally Undecidable Propositions in Principia Mathematica and Related Systems I". The paradox was also a motivation of the development of predicative mathematics.

The original statement of the paradox, due to Richard (1905), is strongly related to Cantor's diagonal argument on the uncountability of the set of real numbers.

The paradox begins with the observation that certain expressions of natural language define real numbers unambiguously, while other expressions of natural language do not. For example, "The real number the integer part of which is 17 and the nth decimal place of which is 0 if n is even and 1 if n is odd" defines the real number 17.1010101... = 1693/99, while the phrase "the capital of England" does not define a real number.

Thus there is an infinite list of English phrases (such that each phrase is of finite length, but lengths vary in the list) that define real numbers unambiguously; arrange this list by length and then order lexicographically (in dictionary order), so that the ordering is canonical. This yields an infinite list of the corresponding real numbers: r₁, r₂, ... . Now define a new real number r as follows. The integer part of r is 0, the nth decimal place of r is 1 if the nth decimal place of r_n is not 1, and the nth decimal place of r is 2 if the nth decimal place of r_n is 1.

...
Wikipedia