Richard's paradox
Encyclopedia
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.
on the uncountability of the set of real number
s.
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 finite length, but lengths vary in the list) 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.
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 number
s 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.
of integers are defined. For example, "the first natural number" defines the property of being the first natural number, one; and "not divisible by any natural number other than 1 and itself" 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 axiom
s. 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 of word and then lexicographically
(in dictionary order).
Now, we may map
each definition to the set of natural number
s, 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, i.e. the number of letters in the definition equals the integer. If, for example, the 43 letters long (ignoring the spaces) description "not divisible by any integer other than 1 and itself" were assigned to the number 43, 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: "the first natural number" were assigned to the number 4, then the number of the definition does not have the property of the definition itself. 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".)
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. Finally, the paradox becomes: Is n Richardian? Suppose n is Richardian. This is only possible if n does not have the property designated by the defining expression which n is correlated with. In other words, this means n is not Richardian, contradicting our assumption. However, if we suppose n 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 "n is Richardian" can not consistently be designated as either true or false.
Richard (1905) presented a solution to the paradox from the viewpoint of predicativisim. Richard claimed that the flaw in the paradoxical construction was that the expression for the construction of the real number r does not actually unambiguously define a real number, 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 rn, because the definition of r does not meet the criteria for being included in the sequence of definitions used to construct the sequence rn. 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 rn.
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 Henri Poincaré
and Hermann Weyl
in Das Kontinuum, where they showed that much of elementary real analysis
can be conducted in a predicative manner starting with only the natural number
s. More recently, predicativism has been studied by Solomon Feferman
, who has used proof theory
to explore the relationship between predicative and impredicative systems.
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
, Richard's paradox is a semantical antinomy
Antinomy
Antinomy literally means the mutual incompatibility, real or apparent, of two laws. It is a term used in logic and epistemology....
in set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
and natural language first described by the French
France
The French Republic , The French Republic , The French Republic , (commonly known as France , is a unitary semi-presidential republic in Western Europe with several overseas territories and islands located on other continents and in the Indian, Pacific, and Atlantic oceans. Metropolitan France...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
Jules Richard
Jules Richard
Jules Richard was a French mathematician.- Life and Works:...
in 1905. Today, the paradox is ordinarily used in order to motivate the importance of carefully distinguishing between mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and metamathematics
Metamathematics
Metamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories...
. The paradox was also a motivation in the development of predicative mathematics.
Description
The original statement of the paradox, due to Richard (1905), has a relation to Cantor's diagonal argumentCantor's diagonal argument
Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural...
on the uncountability of the set of real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s.
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 finite length, but lengths vary in the list) that unambiguously define real numbers; arrange this list by length and then dictionary order
Lexicographical order
In mathematics, the lexicographic or lexicographical order, , is a generalization of the way the alphabetical order of words is based on the alphabetical order of letters.-Definition:Given two partially ordered sets A and B, the lexicographical order on...
, so that the ordering is canonical
Canonical order
Canonical order may refer to:* in the context of sorting, a standard order, typically a total order, obeying certain rules, e.g. lexicographic order for strings* a monastic order of regular canon...
. 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 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
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
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
Zermelo–Fraenkel set theory
In mathematics, Zermelo–Fraenkel set theory with the axiom of choice, named after mathematicians Ernst Zermelo and Abraham Fraenkel and commonly abbreviated ZFC, is one of several axiomatic systems that were proposed in the early twentieth century to formulate a theory of sets without the paradoxes...
(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 number
Gödel number
In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was famously used by Kurt Gödel for the proof of his incompleteness theorems...
s 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
Tarski's indefinability theorem
Tarski's undefinability theorem, stated and proved by Alfred Tarski in 1936, is an important limitative result in mathematical logic, the foundations of mathematics, and in formal semantics...
.
The example of ZFC illustrates the importance of distinguishing the metamathematics
Metamathematics
Metamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories...
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
Metatheory
A metatheory or meta-theory is a theory whose subject matter is some other theory. In other words it is a theory about a theory. Statements made in the metatheory about the theory are called metatheorems....
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.
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 propertiesArithmetic
Arithmetic or arithmetics is the oldest and most elementary branch of mathematics, used by almost everyone, for tasks ranging from simple day-to-day counting to advanced science and business calculations. It involves the study of quantity, especially as the result of combining numbers...
of integers are defined. For example, "the first natural number" defines the property of being the first natural number, one; and "not divisible by any natural number other than 1 and itself" defines the property of being a prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
. (It is clear that some properties cannot be defined explicitly, since every deductive system
Deductive system
A deductive system consists of the axioms and rules of inference that can be used to derive the theorems of the system....
must start with some axiom
Axiom
In traditional logic, an axiom or postulate is a proposition that is not proven or demonstrated but considered either to be self-evident or to define and delimit the realm of analysis. In other words, an axiom is a logical statement that is assumed to be true...
s. 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 of word and then lexicographically
Lexicographical order
In mathematics, the lexicographic or lexicographical order, , is a generalization of the way the alphabetical order of words is based on the alphabetical order of letters.-Definition:Given two partially ordered sets A and B, the lexicographical order on...
(in dictionary order).
Now, we may map
Map (mathematics)
In most of mathematics and in some related technical fields, the term mapping, usually shortened to map, is either a synonym for function, or denotes a particular kind of function which is important in that branch, or denotes something conceptually similar to a function.In graph theory, a map is a...
each definition to the set of natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s, 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, i.e. the number of letters in the definition equals the integer. If, for example, the 43 letters long (ignoring the spaces) description "not divisible by any integer other than 1 and itself" were assigned to the number 43, 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: "the first natural number" were assigned to the number 4, then the number of the definition does not have the property of the definition itself. 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".)
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. Finally, the paradox becomes: Is n Richardian? Suppose n is Richardian. This is only possible if n does not have the property designated by the defining expression which n is correlated with. In other words, this means n is not Richardian, contradicting our assumption. However, if we suppose n 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 "n is Richardian" can not consistently be designated as either true or false.
Relation to predicativism
Another viewpoint on Richard's paradox relates to mathematical predicativism. In 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 is it not valid to quantify over all real numbers in the process of generating a new real number, because this is believed to lead to a vicious-circle 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 predicativisim. Richard claimed that the flaw in the paradoxical construction was that the expression for the construction of the real number r does not actually unambiguously define a real number, 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 rn, because the definition of r does not meet the criteria for being included in the sequence of definitions used to construct the sequence rn. 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 rn.
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
Foundations of mathematics
Foundations of mathematics is a term sometimes used for certain fields of mathematics, such as mathematical logic, axiomatic set theory, proof theory, model theory, type theory and recursion theory...
. Predicativism was first studied in detail by Henri Poincaré
Henri Poincaré
Jules Henri Poincaré was a French mathematician, theoretical physicist, engineer, and a philosopher of science...
and Hermann Weyl
Hermann Weyl
Hermann Klaus Hugo Weyl was a German mathematician and theoretical physicist. Although much of his working life was spent in Zürich, Switzerland and then Princeton, he is associated with the University of Göttingen tradition of mathematics, represented by David Hilbert and Hermann Minkowski.His...
in Das Kontinuum, where they showed that much of elementary real analysis
Real analysis
Real analysis, is a branch of mathematical analysis dealing with the set of real numbers and functions of a real variable. In particular, it deals with the analytic properties of real functions and sequences, including convergence and limits of sequences of real numbers, the calculus of the real...
can be conducted in a predicative manner starting with only the natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s. More recently, predicativism has been studied by Solomon Feferman
Solomon Feferman
Solomon Feferman is an American philosopher and mathematician with major works in mathematical logic.He was born in New York City, New York, and received his Ph.D. in 1957 from the University of California, Berkeley under Alfred Tarski...
, who has used proof theory
Proof theory
Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as plain lists, boxed lists, or trees, which are constructed...
to explore the relationship between predicative and impredicative systems.
See also
- Algorithmic information theoryAlgorithmic information theoryAlgorithmic information theory is a subfield of information theory and computer science that concerns itself with the relationship between computation and information...
- Berry paradoxBerry paradoxThe Berry paradox is a self-referential paradox arising from the expression "the smallest possible integer not definable by a given number of words". Bertrand Russell, the first to discuss the paradox in print, attributed it to G. G...
, which also uses numbers definable by language. - Gödel's ontological proofGödel's ontological proofGödel's ontological proof is a formal argument for God's existence by the mathematician Kurt Gödel. It is in a line of development that goes back to Anselm of Canterbury. St. Anselm's ontological argument, in its most succinct form, is as follows: "God, by definition, is that for which no...
- Grelling–Nelson paradox
- List of paradoxes
- Ordinal definable setOrdinal definable setIn mathematical set theory, a set S is said to be ordinal definable if, informally, it can be defined in terms of a finite number of ordinals by a first order formula. Ordinal definable sets were introduced by ....
, a set-theoretic concept of definability that is itself definable in the language of set theory - Russell's paradoxRussell's paradoxIn the foundations of mathematics, Russell's paradox , discovered by Bertrand Russell in 1901, showed that the naive set theory created by Georg Cantor leads to a contradiction...
: Does the set of all those sets that do not contain themselves contain itself?
External links
- "Paradoxes and contemporary logic", Stanford Encyclopedia of Philosophy