Richard's Paradox - Analysis and Relationship With Metamathematics

Analysis and Relationship With Metamathematics

Richard's paradox leaves an untenable contradiction, which must be analyzed to find an 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.

A similar phenomenon occurs in formalized theories that are able to refer to their own syntax, such as Zermelo–Fraenkel set theory (ZFC). Say that a formula φ(x) defines a real number if there is exactly one real number r such that φ(r) holds. Then it is not possible to define, in ZFC, the set of all (Gödel numbers of) formulas that define real numbers. For, if it were possible to define this set, it would be possible to diagonalize over it to produce a new definition of a real number, following the outline of Richard's paradox above. Note that the set of formulas which define real numbers may exist, as a set F; the limitation of ZFC is that there is no formula which defines F without reference to other sets. This is closely related to Tarski's indefinability theorem.

The example of ZFC illustrates the importance of distinguishing the metamathematics of a formal system from the statements of the formal system itself. The property D(φ) that a formula φ of ZFC defines a unique real number is not itself expressible in ZFC, but must be studied in the metatheory used to formalize ZFC. From this viewpoint, Richard's paradox results from treating a construction in the metatheory (the enumeration of all statements in the original system that define real numbers) as if that construction could be conducted in the original system.