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

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

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

Описание

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

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

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

Предыдущий абзац — это выражение на английском языке, которое однозначно определяет действительное число r . Таким образом, r должно быть одним из чисел r _n . Однако r было построено так, что оно не может равняться ни одному из r _n (таким образом, 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 является рихардовым» эквивалентно « x не x имеет свойства, обозначаемого определяющим выражением, с которым коррелирует в последовательно упорядоченном наборе определений».) Таким образом, в этом примере 58 является рихардовым, а 43 нет.

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

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

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

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

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

См. также

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

Ссылки

• Френкель, Авраам; Бар-Гилель, Джошуа и Леви, Азриэль (1973). Основы теории множеств . При сотрудничестве Дирка ван Далена (второе изд.). Амстердам: Северо-Голландский. ISBN  0-7204-2270-1 .
• Хорошо, Эй Джей (1966). «Заметка о парадоксе Ричарда». Разум . 75 (299): 431. doi : 10.1093/mind/LXXV.299.431 .
• Ричард, Жюль (1905). Основы математики и проблема множеств . Общий обзор чистых и прикладных наук. Переведено на Хейеноорт, Дж. ван, изд. (1964). Справочник по математической логике 1879-1931 гг . Кембридж, Массачусетс: Издательство Гарвардского университета.

Внешние ссылки

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