Войти
В логике, парадокс Ричарда является семантический антиномия из теории множеств и естественного языка впервые описал французский математик Жюль Ричарда в 1905. Парадокс обычно используется, чтобы мотивировать важность тщательного различения между математикой и метаматематике.
Курт Гёдель конкретно цитирует антиномию Ричарда как семантический аналог его результата о синтаксической неполноте во вводном разделе « О формально неразрешимых предложениях в Principia Mathematica и родственных системах I ». Парадокс был также мотивацией развития предикативной математики.
Первоначальное утверждение парадокса, принадлежащее Ричарду (1905), тесно связано с диагональным аргументом Кантора о несчетности множества действительных чисел.
Парадокс начинается с наблюдения, что некоторые выражения естественного языка однозначно определяют действительные числа, а другие выражения естественного языка - нет. Например, «Действительное число, целая часть которого равна 17, а n- й десятичный разряд которого равен 0, если n четное, и 1, если n нечетное» определяет действительное число 17.1010101... = 1693/99, тогда как фраза «столица Англии» не определяет действительное число, ни фраза «наименьшее положительное целое число, не определяемое менее чем шестьюдесятью буквами» (см . парадокс Берри ).
Таким образом, существует бесконечный список английских фраз (таких, что каждая фраза имеет конечную длину, но сам список имеет бесконечную длину), которые однозначно определяют действительные числа. Сначала мы упорядочиваем этот список фраз, увеличивая длину, затем упорядочиваем все фразы одинаковой длины лексикографически (в словарном порядке, например, мы можем использовать код ASCII, фразы могут содержать только коды с 32 по 126), так что порядок будет каноническим. Это дает бесконечный список соответствующих действительных чисел: r 1, r 2,.... Теперь определите новое действительное число 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. Этот последний пример будет называться рихардианским. Таким образом, если число является ричардским, то определение, соответствующее этому числу, является свойством, которым само число не обладает. (Более формально, « х является Richardian» эквивалентно « х никак не обладает свойством обозначенного определяющим выражением, с которой х коррелируются в последовательно упорядоченном множестве определений».) Таким образом, в этом примере, 58 Richardian, но 43 не является.
Теперь, поскольку свойство быть ричихардским само по себе является числовым свойством целых чисел, оно входит в список всех определений свойств. Следовательно, свойству быть ричардианским присваивается некоторое целое число n. Например, определение «быть ричардианцем» может быть отнесено к числу 92. Наконец, парадокс звучит так: является ли 92 ричарданцем? Предположим, 92 - ричардианское. Это возможно только в том случае, если 92 не имеет свойства, обозначенного определяющим выражением, с которым оно коррелируется. Другими словами, это означает, что 92 не является ричардианским, что противоречит нашему предположению. Однако, если мы предположим, что 92 не является ричардианским, тогда он действительно обладает определяющим свойством, которому он соответствует. Это, по определению, означает, что это ричардский, опять же вопреки предположению. Таким образом, утверждение «92 - ричардианское» не может быть последовательно обозначено ни как истинное, ни как ложное.
Другое мнение относительно парадокса Ричарда относится к математическому предикативизму. Согласно этой точке зрения, реальные числа определяются поэтапно, причем каждый этап ссылается только на предыдущие этапы и другие вещи, которые уже были определены. С точки зрения предикативности недопустимо проводить количественную оценку всех действительных чисел в процессе генерации нового действительного числа, потому что это, как полагают, приводит к проблеме цикличности в определениях. Теории множеств, такие как ZFC, не основаны на такого рода предикативной структуре и допускают непредикативные определения.
Ричард (1905) представил решение парадокса с точки зрения предикативизма. Ричард утверждал, что недостаток парадоксальной конструкции состоял в том, что выражение для построения действительного числа r на самом деле не определяет однозначно действительное число, потому что утверждение относится к построению бесконечного набора действительных чисел, из которых само r является раздельно. Таким образом, говорит Ричард, действительное число r не будет включаться как любое r n, потому что определение r не соответствует критериям включения в последовательность определений, используемых для построения последовательности r n. Современные математики согласны с тем, что определение r неверно, но по другой причине. Они считают, что определение r неверно, потому что нет четко определенного понятия, когда английская фраза определяет действительное число, и поэтому нет однозначного способа построить последовательность r n.
Хотя решение Ричарда парадокса не понравилось математикам, предикативизм - важная часть изучения основ математики. Предикативизм был впервые подробно изучен Германом Вейлем в Das Kontinuum, где он показал, что большая часть элементарного реального анализа может быть проведена предикативным способом, начиная только с натуральных чисел. Совсем недавно предикативизм был изучен Соломоном Феферманом, который использовал теорию доказательств для изучения взаимосвязи между предикативными и импредикативными системами.
