Парадокс Ричарда и различие между математикой и метаматематикой

Введение

Очевидное противоречие в метаматематике
В логике парадокс Ричарда — семантическая антиномия теории множеств и естественного языка, впервые описанная французским математиком Жюлем Ришаром в 1905 году. Этот парадокс обычно используется для обоснования важности четкого разграничения между математикой и метаматематикой. Курт Гёдель специально упоминает антиномию Ричарда как семантический аналог своего синтаксического результата о неполноте во вводной части работы «О формально неразрешимых предложениях Principia Mathematica и связанных с ними систем I». Парадокс также послужил стимулом для развития предикативной математики.

Описание

Первоначальная формулировка парадокса, предложенная Ричардом (1905), тесно связана с диагональным аргументом Кантора о несчетности множества действительных чисел. Парадокс начинается с наблюдения о том, что некоторые выражения естественного языка однозначно определяют действительные числа, а другие – нет. Например, "действительное число, целая часть которого равна 17, а n-я десятичная цифра равна 0, если n четное, и 1, если n нечетное", определяет действительное число 17.1010101 = 1693/99, в то время как фраза "столица Англии" не определяет действительное число, равно как и фраза "наименьшее положительное целое число, которое нельзя определить менее чем шестьюдесятью буквами" (см. парадокс Берри). Существует бесконечный список английских фраз (при этом каждая фраза имеет конечную длину, но сам список – бесконечную), которые однозначно определяют действительные числа. Сначала упорядочим этот список фраз по возрастанию длины, затем упорядочим все фразы одинаковой длины лексикографически, чтобы получить каноническое упорядочение. Это даст бесконечный список соответствующих действительных чисел: r1, r2, … Теперь определим новое действительное число r следующим образом: целая часть r равна 0, n-я десятичная цифра r равна 1, если n-я десятичная цифра rn не равна 1, и n-я десятичная цифра r равна 2, если n-я десятичная цифра rn равна 1. Предыдущий абзац является выражением на английском языке, которое однозначно определяет действительное число r. Следовательно, r должно быть одним из чисел rn. Однако r было сконструировано таким образом, что оно не может быть равно ни одному из rn (таким образом, r является неопределимым числом). Это и есть парадоксальное противоречие.

Анализ и связь с метаматематикой

Парадокс Ричарда приводит к неприемлемому противоречию, которое необходимо проанализировать, чтобы найти ошибку. Предлагаемое определение нового действительного числа r явно включает в себя конечную последовательность символов и, следовательно, на первый взгляд кажется определением действительного числа. Однако определение ссылается на определимость на самом английском языке. Если бы было возможно определить, какие английские выражения действительно определяют действительное число, а какие нет, то парадокс был бы верен. Таким образом, разрешение парадокса Ричарда заключается в том, что не существует способа однозначно определить, какие именно английские предложения являются определениями действительных чисел (см. Good 1966). То есть, не существует способа описать в конечном числе слов, как определить, является ли произвольное английское выражение определением действительного числа. Это не удивительно, поскольку возможность сделать такое определение также подразумевает возможность решения проблемы останова и выполнения любых других неалгоритмических вычислений, которые могут быть описаны на английском языке. Аналогичный феномен встречается в формализованных теориях, способных ссылаться на свой собственный синтаксис, таких как теория множеств Цермело — Френкеля (ZFC). Будем говорить, что формула φ(x) определяет действительное число, если существует ровно одно действительное число r, такое что φ(r) истинно. Тогда невозможно определить, средствами ZFC, множество всех (чисел Гёделя) формул, определяющих действительные числа. Ибо, если бы можно было определить это множество, можно было бы построить диагональ относительно него, чтобы получить новое определение действительного числа, следуя плану парадокса Ричарда, описанному выше. Обратите внимание, что множество формул, определяющих действительные числа, может существовать как множество F; ограничение ZFC заключается в том, что не существует формулы, определяющей F без ссылки на другие множества. Это связано с теоремой о неопределимости Тарского. Пример ZFC иллюстрирует важность различения метаматематики формальной системы и утверждений самой формальной системы. Свойство D(φ), заключающееся в том, что формула φ из ZFC определяет единственное действительное число, само по себе не выразимо средствами ZFC, но должно рассматриваться как часть метатеории, используемой для формализации ZFC. С этой точки зрения, парадокс Ричарда возникает из-за того, что конструкция метатеории (перечисление всех утверждений в исходной системе, определяющих действительные числа) рассматривается как если бы эта конструкция могла быть выполнена в самой исходной системе.

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.

Вариация: Рихардовы числа

Вариант парадокса использует целые числа вместо действительных, сохраняя самореферентный характер оригинала. Рассмотрим язык (например, английский), в котором определены арифметические свойства целых чисел. Например, "первое натуральное число" определяет свойство быть первым натуральным числом, то есть единицей; а "делится на ровно два натуральных числа" определяет свойство быть простым числом (очевидно, что некоторые свойства нельзя определить явно, поскольку любая дедуктивная система должна начинаться с некоторых аксиом. Но для целей данного рассуждения предполагается, что такие фразы, как "целое число является суммой двух целых чисел", уже понятны). Хотя список всех таких возможных определений сам по себе бесконечен, легко заметить, что каждое отдельное определение состоит из конечного числа слов и, следовательно, также из конечного числа символов. Поскольку это так, мы можем упорядочить определения, сначала по длине, а затем лексикографически. Теперь мы можем сопоставить каждое определение множеству натуральных чисел, так что определение с наименьшим количеством символов и в алфавитном порядке будет соответствовать числу 1, следующее определение в последовательности – числу 2 и так далее. Поскольку каждое определение связано с уникальным целым числом, то возможно, что иногда целое число, присвоенное определению, удовлетворяет этому определению. Если, например, определение "не делится ни на какое целое число, кроме 1 и самого себя" окажется 43-м, то это будет так. Поскольку 43 само по себе не делится ни на какое целое число, кроме 1 и самого себя, то число этого определения обладает свойством, определяемым этим определением. Однако это не всегда так. Если определение "делится на 3" было присвоено числу 58, то число определения не обладает свойством, определяемым этим определением, поскольку 58 само по себе не делится на 3. Этот последний пример будет назван обладающим свойством быть рихардианским. Таким образом, если число является рихардианским, то определение, соответствующее этому числу, является свойством, которым само число не обладает. (Более формально, "x является рихардианским" эквивалентно "x не обладает свойством, обозначенным определяющим выражением, с которым x соотносится в последовательно упорядоченном наборе определений".) Таким образом, в этом примере 58 является рихардианским, а 43 – нет. Теперь, поскольку свойство быть рихардианским само по себе является числовым свойством целых чисел, оно входит в список всех определений свойств. Поэтому свойству быть рихардианским присваивается некоторое целое число, n. Например, определение "быть рихардианским" может быть присвоено числу 92. Наконец, парадокс формулируется так: является ли 92 рихардианским? Предположим, что 92 является рихардианским. Это возможно только в том случае, если 92 не обладает свойством, обозначенным определяющим выражением, с которым оно соотносится. Иными словами, это означает, что 92 не является рихардианским, что противоречит нашему предположению. Однако, если предположить, что 92 не является рихардианским, то оно обладает определяющим свойством, которому оно соответствует. Это, по определению, означает, что оно является рихардианским, что опять же противоречит предположению. Таким образом, утверждение "92 является рихардианским" не может последовательно быть признано ни истинным, ни ложным.

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.

Связь с предикативизмом

Другое мнение относительно парадокса Ричарда связано с математическим предикативизмом. Согласно этой точке зрения, вещественные числа определяются поэтапно, причём каждый этап опирается только на предыдущие этапы и другие уже определённые объекты. С предикативной точки зрения, некорректно квантифицировать по всем вещественным числам в процессе генерации нового вещественного числа, поскольку это, как считается, приводит к проблеме круговой зависимости в определениях. Теории множеств, такие как ZFC, не основываются на подобной предикативной структуре и допускают импредикативные определения. Ричард (1905) предложил решение парадокса с точки зрения предикативизма. Ричард утверждал, что недостаток парадоксальной конструкции заключается в том, что выражение для построения вещественного числа r на самом деле не определяет вещественное число однозначно, поскольку утверждение относится к построению бесконечного множества вещественных чисел, частью которого является само r. Таким образом, по мнению Ричарда, вещественное число r не будет включено ни в одно rn, поскольку определение r не соответствует критериям для включения в последовательность определений, используемых для построения последовательности rn. Современные математики согласны с тем, что определение r недействительно, но по другой причине. Они считают, что определение r недействительно, поскольку отсутствует чёткое понятие о том, когда английская фраза определяет вещественное число, и, следовательно, нет однозначного способа построить последовательность rn. Хотя решение Ричарда парадокса не получило признания у математиков, предикативизм остаётся важной частью изучения основ математики. Предикативизм был впервые подробно изучен Германном Вейлем в работе «Континуум», где он показал, что значительная часть элементарного вещественного анализа может быть проведена предикативным образом, начиная только с натуральных чисел. В последнее время предикативизм изучал Соломон Феферман, который использовал теорию доказательств для исследования взаимосвязи между предикативными и импредикативными системами.

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 predicativisim. 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 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 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.