Richard's paradox

from Wikipedia, the free encyclopedia

Richard's Paradox, a semantic antinomy of set theory and natural language, first described by the French mathematician Jules Richard in 1905. The paradox is usually used to motivate the importance of carefully distinguishing between math and metamathematics. Kurt Gödel cited Richard's antinomy as a semantic analogue to his incompleteness theorem .

description

The original statement of the paradox, owed to Richard (1905), is based on an argument similar to the Cantor diagonalization . The paradox begins with the observation that certain natural language expressions clearly define real numbers, while other natural language expressions do not. The term "The real number whose integer part is 17 and the n th decimal place is 0, if 'n' is straight and, when 'n' odd 1" uniquely defines the real number 17.1010101 ... = 1693/99. In contrast, the expression "the capital of Bavaria" does not define a real number, nor does the expression "the smallest positive integer that cannot be defined in less than sixty letters" (see Berry's paradox ).

Thus there is an infinite list of linguistic expressions that uniquely define real numbers. We first order this list of expressions in increasing length and then we arrange all expressions of the same length in lexicographical order , e.g. in dictionary order, so that the order is canonical. This results in an infinite list of corresponding real numbers r 1 , r 2 , ..., where r n is the real number that is defined by the expression that is in the nth position of the list. Now we can create a new real number r with integer part 0 and n th decimal place 1 when the n th decimal place from r n is equal to 1 or 2 if the n th decimal place from r n is 1, define.

The previous paragraph is a linguistic expression that uniquely defines a real number, namely r . Therefore r must be one of the numbers r n . However, r was constructed in such a way that it cannot correspond to any of the r n . Therefore r is an indefinable number . That is the paradoxical contradiction.

Analysis and relationship to metamathematics

Richard's paradox leads to a contradiction. The proposed definition of the new real number r clearly contains a finite sequence of characters and therefore initially appears to be the definition of a real number. However, the definition relates to the definability of natural language. If one could determine which linguistic expressions actually define a real number and which do not, then the paradox would run away. The solution to Richard's paradox is, therefore, that there is no way to uniquely determine which expressions are definitions of real numbers. That is, there is no way to describe in a finite number of words how to determine whether an arbitrary German expression is a definition of a real number. This is not surprising as the ability to make this determination would imply solving the holding problem and allow other non-algorithmic computations to be performed that can be described in natural language.

A similar phenomenon occurs with formalized theories that can refer to their own syntax, such as the Zermelo-Fraenkel set theory (ZFC). Suppose 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 use ZFC to define the set of all ( Gödel numbers of) formulas that define real numbers. If it were possible to define this set, it would be possible to diagonalize over it to generate a new definition of a real number that corresponds to the paradox described above. It should be noted that the set of formulas that define real numbers can exist as set F in ZFC . The limitation of ZFC is that there is no formula that defines F without reference to other quantities. This is related to Tarski's indefinability theorem .

The ZFC example illustrates the importance of distinguishing the metamathematics of a formal system from the statements of the formal system itself. The property D (φ), with which a formula φ of ZFC defines a unique real number, cannot be expressed by ZFC itself, but must be regarded as part of the metatheory used to formalize ZFC. From this point of view, Richard's paradox arises from the mistake of treating a definition in a metatheory as if it could be defined in the theory itself.

See also

Individual evidence

  1. ↑ Kurt Gödel: About formally undecidable sentences of the Principia Mathematica and related systems I. In: Monthly books for mathematics and physics . 38, 1931, pp. 173-198, doi: 10.1007 / BF01700692 , Zentralblatt MATH.
  2. ↑ Jules Richard: Les Principes des Mathématiques et le Problème des Ensembles  (= Revue Générale des Sciences Pures et Appliquées) 1905.
  3. ^ IJ Good: A Note on Richard's Paradox . In: Min . tape 75 , no. 299 , 1966, pp. 431 , doi : 10.1093 / mind / LXXV.299.431 .