Парадокс Ричардса - Richards paradox

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

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

Описание

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

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

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

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

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

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

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

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

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

Вариант: числа Ричарда

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

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

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

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

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

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

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

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

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

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

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

[1] Соломон Феферман "Предикативность " (2002)

[1]