Парадокс Ричарда

В логике парадокс Ришара представляет собой семантическую антиномию теории множеств и естественного языка, впервые описанную французским математиком Жюлем Ришаром в 1905 году. Парадокс обычно используется для обоснования важности тщательного разграничения математики и метаматематики .

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

Описание

Первоначальная формулировка парадокса, сделанная Ричардом (1905), тесно связана с диагональным аргументом Кантора о несчетности множества действительных чисел .

Парадокс начинается с наблюдения, что некоторые выражения естественного языка однозначно определяют действительные числа, в то время как другие выражения естественного языка этого не делают. Например, «Вещественное число, целая часть которого равна 17 и n -й десятичный разряд которого равен 0, если n четное, и 1, если n нечетное» определяет действительное число 17,1010101... = 1693/99, тогда как фраза «столица Англии» не определяет действительное число, как и фраза «наименьшее положительное целое число, не определяемое менее чем шестьюдесятью буквами» (см . Парадокс Берри ).

Таким образом, существует бесконечный список английских фраз (таких, что каждая фраза имеет конечную длину, но сам список имеет бесконечную длину), которые однозначно определяют действительные числа. Сначала мы упорядочиваем этот список фраз по возрастанию длины, затем упорядочиваем все фразы одинаковой длины лексикографически (в словарном порядке, например, мы можем использовать код ASCII , фразы могут содержать только коды от 32 до 126), чтобы порядок был каноническим . Это дает бесконечный список соответствующих вещественных чисел: r ₁ , r ₂ , ... . Теперь определим новое действительное число r следующим образом. Целая часть r равна 0, n -му десятичному разряду числаr равно 1, если n -й десятичный разряд _rn не равен 1, и n -й десятичный разряд r равен 2, если n -й десятичный разряд _rn равен 1.

Предыдущий абзац представляет собой выражение на английском языке, однозначно определяющее действительное число r . Таким образом , r должно быть одним из чисел r _n . Однако r было построено так, что оно не может равняться ни одному из rn (таким образом, r — неопределимое число ₎ . Это парадоксальное противоречие.

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

Парадокс Ричарда приводит к несостоятельному противоречию, которое необходимо проанализировать, чтобы найти ошибку.

Предложенное определение нового действительного числа r явно включает в себя конечную последовательность символов и, следовательно, на первый взгляд кажется определением действительного числа. Однако определение относится к самой определяемости на английском языке. Если бы можно было определить, какие английские выражения действительноопределите действительное число, а какие нет, то парадокс пройдет. Таким образом, разрешение парадокса Ричарда заключается в том, что нет никакого способа однозначно определить, какие именно английские предложения являются определениями действительных чисел (см. Good 1966). То есть нет никакого способа описать конечным числом слов, как определить, является ли произвольное английское выражение определением действительного числа. Это неудивительно, так как возможность сделать это определение также подразумевала бы способность решить проблему остановки и выполнить любые другие неалгоритмические вычисления, которые можно описать на английском языке.

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

Пример ZFC иллюстрирует важность отличия метаматематики формальной системы от утверждений самой формальной системы. Свойство D(φ), заключающееся в том, что формула φ ZFC определяет уникальное действительное число, само по себе не выражается ZFC, но должно рассматриваться как часть метатеории , используемой для формализации ZFC. С этой точки зрения парадокс Ричарда возникает в результате трактовки построения метатеории (перечисления всех утверждений в исходной системе, определяющих вещественные числа), как если бы это построение могло быть выполнено в исходной системе.

Вариация: числа Ричарда

Вариант парадокса использует целые числа вместо действительных чисел, сохраняя при этом самореферентный характер оригинала. Рассмотрим язык (например, английский), в котором определены арифметические свойства целых чисел. Например, «первое натуральное число» определяет свойство быть первым натуральным числом, единицей; а «делиться ровно на два натуральных числа» определяет свойство быть простым числом (ясно, что некоторые свойства не могут быть определены явно, поскольку каждая дедуктивная система должна начинаться с некоторых аксиом. Но для целей этого аргумента предполагается, что такие фразы, как «целое число есть сумма двух целых чисел», уже понятны). Хотя список всех таких возможных определений сам по себе бесконечен, легко заметить, что каждое отдельное определение состоит из конечного числа слов и, следовательно, из конечного числа символов. Поскольку это так, мы можем упорядочить определения сначала по длине, а затем лексикографически .

Теперь мы можем сопоставить каждое определение с набором натуральных чисел , так что определение с наименьшим количеством символов и алфавитным порядком будет соответствовать числу 1, следующее определение в ряду будет соответствовать числу 2 и так далее. Поскольку каждое определение связано с уникальным целым числом, возможно, что иногда целое число, присвоенное определению, подходит .это определение. Если бы, например, определение «не делится ни на какое целое число, кроме 1 и самого себя» оказалось бы 43-м, то это было бы верно. Так как 43 само не делится ни на какое целое число, кроме 1 и самого себя, то число этого определения обладает свойством самого определения. Однако это может быть не всегда так. Если бы число определения: «делится на 3» было присвоено числу 58, то число определения не имеет свойства самого определения. Поскольку 58 само по себе не делится на 3. Этот последний пример будет называться имеющим свойство быть ричардианским . Таким образом, если число является ричардовским, то определение, соответствующее этому числу, является свойством, которым само число не обладает. (Более формально, " xявляется ричардианским » эквивалентно « х не обладает свойством, обозначенным определяющим выражением, с которым х коррелирует в последовательно упорядоченном наборе определений».) Таким образом, в этом примере 58 является ричардовским, а 43 — нет.

Теперь, поскольку свойство быть ричардианским само по себе является числовым свойством целых чисел, оно принадлежит к списку всех определений свойств. Следовательно, свойству быть ричардианским присваивается некоторое целое число n. Например, определение «быть ричардианцем» может быть отнесено к числу 92. Наконец, возникает парадокс: является ли 92 ричардианцем? Предположим, что 92 — это Ричардиан. Это возможно только в том случае, если 92 не имеет свойства, обозначенного определяющим выражением, с которым оно коррелирует. Другими словами, это означает, что число 92 не является ричардианским, что противоречит нашему предположению. Однако, если мы предположим, что число 92 не является ричардианским, тогда оно обладает определяющим свойством, которому оно соответствует. Это, по определению, означает, что это Ричардианство, опять же вопреки предположению. Таким образом, утверждение «92 является ричардианским» не может последовательно обозначаться ни как истинное, ни как ложное.

Отношение к предикативизму

Другое мнение относительно парадокса Ришара относится к математическому предикативизму . С этой точки зрения действительные числа определяются поэтапно, причем каждый этап ссылается только на предыдущие этапы и другие вещи, которые уже были определены. С предикативной точки зрения недопустимо проводить количественную оценку всех действительных чисел в процессе генерации нового действительного числа, потому что считается, что это приводит к проблеме цикличности в определениях. Теории множеств, такие как ZFC, не основаны на такой предикативной структуре и допускают непредикативные определения.

Ричард (1905) представил решение парадокса с точки зрения предикативизма. Ричард утверждал, что недостатком парадоксальной конструкции было то, что выражение для построения действительного числа r на самом деле не определяет действительное число однозначно, потому что утверждение относится к построению бесконечного множества действительных чисел, из которых само r является отдельно. Таким образом, говорит Ричард, действительное число _r не будет включено как любое rn , потому что определение r не соответствует критериям включения в последовательность определений, используемых для построения _{последовательности} rn . Современные математики сходятся во мнении, что определениеr недействителен, но по другой причине. Они считают, что определение r неверно, потому что нет четко определенного понятия, когда английская фраза определяет действительное число, и поэтому нет однозначного способа построить последовательность r _n .

Хотя решение парадокса Ричардом не получило одобрения математиков, предикативизм является важной частью изучения основ математики . Предикативизм был впервые подробно изучен Германом Вейлем в Das Kontinuum , где он показал, что большая часть элементарного реального анализа может быть проведена предикативным образом, начиная только с натуральных чисел . Совсем недавно предикативизм был изучен Соломоном Феферманом , который использовал теорию доказательств для изучения взаимосвязи между предикативными и непредикативными системами. ^[1]

Смотрите также

• Алгоритмическая теория информации
• Парадокс Берри , в котором также используются числа, определяемые языком.
• Парадокс Карри
• Парадокс Греллинга – Нельсона
• Парадокс Клини – Россера
• Список парадоксов
• Теорема Лёба
• Порядковое определимое множество , теоретико-множественное понятие определимости, которое само по себе определимо на языке теории множеств.
• Парадокс Рассела : содержит ли множество всех тех множеств, которые не содержат себя?

использованная литература

• Френкель, Авраам; Бар-Хиллель, Иегошуа и Леви, Азриэль (1973). Основы теории множеств . В сотрудничестве с Дирком ван Даленом (второе изд.). Амстердам: Северная Голландия. ISBN 0-7204-2270-1.
• Хорошо, И. Дж. (1966). «Заметка о парадоксе Ричарда». Разум . 75 (299): 431. doi : 10.1093/mind/LXXV.299.431 .
• Ричард, Жюль (1905). Les Principes де Mathématiques и ле Problème де Ensembles . Revue Générale des Sciences Pures et Appliquées.Переведено в Heijenoort, J. van, изд. (1964). Справочник по математической логике 1879-1931 гг . Кембридж, Массачусетс: Издательство Гарвардского университета.

внешняя ссылка

• « Парадоксы и современная логика », Стэнфордская философская энциклопедия.