Richard's paradox

related topics
{math, number, function}
{language, word, form}

In logic, Richard's paradox is a semantical antinomy in set theory and natural language first described by the French mathematician Jules Richard in 1905. Today, the paradox is ordinarily used in order to motivate the importance of carefully distinguishing between mathematics and metamathematics. The paradox was also a motivation in the development of predicative mathematics.

Contents

Description

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

The paradox begins with the observation that certain expressions in English unambiguously define real numbers, while other expressions in English do not. For example, "The real number whose integer part is 17 and whose nth decimal place is 0 if n is even and 1 if n is odd" defines the real number 17.1010101..., while the phrase "London is in England" does not define a real number.

Thus there is an infinite list of English phrases (where each phrase is of various finite lengths) that unambiguously define real numbers; arrange this list by length and then dictionary order, so that the ordering is canonical. This yields an infinite list of the corresponding real numbers: r1, r2, ... . 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 rn is not 1, and the nth decimal place of r is 2 if the nth decimal place of rn is 1.

The preceding two paragraphs are an expression in English which unambiguously defines a real number r. Thus r must be one of the numbers rn. However, r was constructed so that it cannot equal any of the rn. This is the paradoxical contradiction.

Analysis and relationship with metamathematics

Richard's paradox leaves an untenable contradiction, which must be analyzed to find the error.

The proposed definition of the new real number r clearly contains a finite string of characters, and hence it appears at first to be a definition of a real number. However, the definition refers to definability-in-English itself. If it were possible to determine which English expressions actually do define a real number, and which do not, then the paradox would go through. Thus the resolution of Richard's paradox is that there is no way to unambiguously determine exactly which English sentences are definitions of real numbers (see Good 1966). That is, there is no way to describe in a finite number of words how to tell whether an arbitrary English expression is a definition of a real number. This is not surprising, as the ability to make this determination would also imply the ability to solve the halting problem and perform any other non-algorithmic calculation that can be described in English.

Full article ▸

related documents
Extended real number line
Splitting lemma
Haar measure
Unicity distance
Axiom of pairing
Ring (mathematics)
Assignment problem
Legendre symbol
Idempotence
Meromorphic function
Functional analysis
Presburger arithmetic
Preorder
Elementary group theory
Queue (data structure)
Chain rule
Mathematical model
Associativity
Examples of groups
B-tree
Oracle machine
Extended Backus–Naur Form
Merkle-Hellman
Lagrange inversion theorem
Boolean ring
XSL Transformations
ML (programming language)
Trie
Statistical independence
Monster group