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 for the development of predicative mathematics.

Description

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, whereas the phrase "the capital of England" does not define a real number, nor the phrase "the smallest positive integer not definable in under sixty letters" (see Berry's paradox).

There is an infinite list of English phrases (such that each phrase is of finite length, but the list itself is of infinite length) that define real numbers unambiguously. We first arrange this list of phrases by increasing length, then order all phrases of equal length lexicographically, 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.

The preceding paragraph is an expression in English that unambiguously defines a real number r. Thus r must be one of the numbers r_n. However, r was constructed so that it cannot equal any of the r_n (thus, r is an undefinable number). This is the paradoxical contradiction.

Analysis and relationship with metamathematics

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

The proposed definition of the new real number r clearly includes a finite sequence of characters, and hence it seems 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 not any way to unambiguously determine exactly which English sentences are definitions of real numbers (see Good 1966). That is, there is not any 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, by 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 that define real numbers may exist, as a set F; the limitation of ZFC is that there is not any formula that defines F without reference to other sets. This is related to Tarski's undefinability 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 by ZFC, but must be considered as part of the metatheory used to formalize ZFC. From this viewpoint, Richard's paradox results from treating a construction of the metatheory (the enumeration of all statements in the original system that define real numbers) as if that construction could be performed in the original system.

Variation: Richardian numbers

A variation of the paradox uses integers instead of real numbers, while preserving the self-referential character of the original. Consider a language (such as English) in which the arithmetical properties of integers are defined. For example, "the first natural number" defines the property of being the first natural number, one; and "divisible by exactly two natural numbers" defines the property of being a prime number (It is clear that some properties cannot be defined explicitly, since every deductive system must start with some axioms. But for the purposes of this argument, it is assumed that phrases such as "an integer is the sum of two integers" are already understood). While the list of all such possible definitions is itself infinite, it is easily seen that each individual definition is composed of a finite number of words, and therefore also a finite number of characters. Since this is true, we can order the definitions, first by length and then lexicographically.

Now, we may map each definition to the set of natural numbers, such that the definition with the smallest number of characters and alphabetical order will correspond to the number 1, the next definition in the series will correspond to 2, and so on. Since each definition is associated with a unique integer, then it is possible that occasionally the integer assigned to a definition fits that definition. If, for example, the definition "not divisible by any integer other than 1 and itself" happened to be 43rd, then this would be true. Since 43 is itself not divisible by any integer other than 1 and itself, then the number of this definition has the property of the definition itself. However, this may not always be the case. If the definition: "divisible by 3" were assigned to the number 58, then the number of the definition does not have the property of the definition itself, since 58 is itself not divisible by 3. This latter example will be termed as having the property of being Richardian. Thus, if a number is Richardian, then the definition corresponding to that number is a property that the number itself does not have. (More formally, "x is Richardian" is equivalent to "x does not have the property designated by the defining expression with which x is correlated in the serially ordered set of definitions".) Thus in this example, 58 is Richardian, but 43 is not.

Now, since the property of being Richardian is itself a numerical property of integers, it belongs in the list of all definitions of properties. Therefore, the property of being Richardian is assigned some integer, n. For example, the definition "being Richardian" might be assigned to the number 92. Finally, the paradox becomes: Is 92 Richardian? Suppose 92 is Richardian. This is only possible if 92 does not have the property designated by the defining expression which it is correlated with. In other words, this means 92 is not Richardian, contradicting our assumption. However, if we suppose 92 is not Richardian, then it does have the defining property which it corresponds to. This, by definition, means that it is Richardian, again contrary to assumption. Thus, the statement "92 is Richardian" cannot consistently be designated as either true or false.

Relation to predicativism

Another opinion concerning Richard's paradox relates to mathematical predicativism. By this view, the real numbers are defined in stages, with each stage only making reference to previous stages and other things that have already been defined. From a predicative viewpoint it is not valid to quantify over all real numbers in the process of generating a new real number, because this is believed to result in a circularity problem in the definitions. Set theories such as ZFC are not based on this sort of predicative framework, and allow impredicative definitions.

Richard (1905) presented a solution to the paradox from the viewpoint of predicativism. Richard claimed that the flaw of the paradoxical construction was that the expression for the construction of the real number r does not actually define a real number unambiguously, because the statement refers to the construction of an infinite set of real numbers, of which r itself is a part. Thus, Richard says, the real number r will not be included as any r_n, because the definition of r does not meet the criteria for being included in the sequence of definitions used to construct the sequence r_n. Contemporary mathematicians agree that the definition of r is invalid, but for a different reason. They believe the definition of r is invalid because there is no well-defined notion of when an English phrase defines a real number, and so there is no unambiguous way to construct the sequence r_n.

Although Richard's solution to the paradox did not gain favor with mathematicians, predicativism is an important part of the study of the foundations of mathematics. Predicativism was first studied in detail by Hermann Weyl in Das Kontinuum, wherein he showed that much of elementary real analysis can be conducted in a predicative manner starting with only the natural numbers. More recently, predicativism has been studied by Solomon Feferman, who has used proof theory to explore the relationship between predicative and impredicative systems.

See also

• Algorithmic information theory
• Berry paradox, which also uses numbers definable by language.
• Curry's paradox
• List of self–referential paradoxes
• Kleene–Rosser paradox
• List of paradoxes
• Löb's theorem
• Ordinal definable set, a set-theoretic concept of definability that is itself definable in the language of set theory
• Paradoxes of set theory
• Russell's paradox: Does the set of all those sets that do not contain themselves contain itself?

References

• Fraenkel, Abraham; Bar-Hillel, Yehoshua & Levy, Azriel (1973). Foundations of Set Theory. With the collaboration of Dirk van Dalen (Second ed.). Amsterdam: Noord-Hollandsche. ISBN 0-7204-2270-1.
• Good, I. J. (1966). "A Note on Richard's Paradox". Mind. 75 (299): 431. doi:10.1093/mind/LXXV.299.431.
• Richard, Jules (1905). Les Principes des Mathématiques et le Problème des Ensembles. Revue Générale des Sciences Pures et Appliquées. Translated in Heijenoort, J. van, ed. (1964). Source Book in Mathematical Logic 1879-1931. Cambridge, MA: Harvard University Press.

External links

• "Paradoxes and contemporary logic", Stanford Encyclopedia of Philosophy