Парадокс Берри — это самореферентный парадокс, возникающий из выражения типа «Наименьшее положительное целое число, не определяемое менее чем шестьюдесятью буквами» (фраза из пятидесяти семи букв).
Бертран Рассел , первый, кто обсудил этот парадокс в печати, приписал его Г. Г. Берри (1867–1928), [ 1] младшему библиотекарю Бодлианской библиотеки Оксфорда . Рассел называл Берри «единственным человеком в Оксфорде, который понимал математическую логику». [2] Этот парадокс был назван « парадоксом Ричарда » Жаном-Ивом Жираром . [3]
Рассмотрим выражение:
Так как в английском алфавите всего двадцать шесть букв, то существует конечное число фраз из менее чем шестидесяти букв, и, следовательно, конечное число положительных целых чисел, которые определяются фразами из менее чем шестидесяти букв. Так как существует бесконечно много положительных целых чисел, это означает, что существуют положительные целые числа, которые не могут быть определены фразами из менее чем шестидесяти букв. Если существуют положительные целые числа, которые удовлетворяют заданному свойству, то существует наименьшее положительное целое число, которое удовлетворяет этому свойству; следовательно, существует наименьшее положительное целое число, удовлетворяющее свойству «не определимо менее чем за шестьдесят букв». Это целое число, к которому относится приведенное выше выражение. Но приведенное выше выражение имеет длину всего пятьдесят семь букв, поэтому оно определимо менее чем за шестьдесят букв и не является наименьшим положительным целым числом, не определимым менее чем за шестьдесят букв, и не определяется этим выражением. Это парадокс: должно быть целое число, определяемое этим выражением, но так как выражение является противоречивым (любое определяемое им целое число определимо менее чем за шестьдесят букв), не может быть никакого определяемого им целого числа.
Математик и специалист по информатике Грегори Чайтин в своей книге «Непознаваемое» (1999) добавляет следующий комментарий: «Ну, мексиканский историк математики Алехандро Гарсидиего потрудился найти это письмо [Берри, на основе которого Рассел написал свои замечания], и это совсем другой парадокс. В письме Берри на самом деле говорится о первом порядковом числе, которое нельзя назвать конечным числом слов. Согласно теории Кантора, такое порядковое число должно существовать, но мы только что назвали его конечным числом слов, что является противоречием».
Парадокс Берри, сформулированный выше, возникает из-за систематической двусмысленности слова «определимый». В других формулировках парадокса Берри, например, в той, которая вместо этого гласит: «...не именуемый в менее...», термин «имеемый» также имеет эту систематическую двусмысленность. Термины такого рода порождают заблуждения порочного круга . Другие термины с таким типом двусмысленности: выполнимый, истинный, ложный, функция, свойство, класс, отношение, кардинальный и порядковый. [4] Чтобы разрешить один из этих парадоксов, нужно точно указать, где именно наше использование языка пошло не так, и ввести ограничения на использование языка, которые могут их избежать.
Это семейство парадоксов может быть разрешено путем включения стратификации значений в язык. Термины с систематической двусмысленностью могут быть записаны с нижними индексами, обозначающими, что один уровень значения считается более приоритетным, чем другой в их интерпретации. «Число, не называемое 0 менее чем одиннадцатью словами» может быть названо 1 менее чем одиннадцатью словами в этой схеме. [5]
Однако можно прочитать вклад Альфреда Тарского в Парадокс Лжеца, чтобы увидеть, как это разрешение в языках не оправдывает ожиданий. Альфред Тарский диагностировал парадокс как возникающий только в языках, которые являются «семантически закрытыми», под чем он подразумевал язык, в котором одно предложение может предицировать истинность (или ложность) другого предложения на том же языке (или даже самого себя). Чтобы избежать внутреннего противоречия, необходимо при обсуждении значений истинности представлять себе уровни языков, каждый из которых может предицировать истинность (или ложность) только языков более низкого уровня. Таким образом, когда одно предложение ссылается на значение истинности другого, оно семантически выше. Предложение, на которое ссылаются, является частью «языка-объекта», в то время как ссылающееся предложение считается частью «метаязыка» по отношению к языку-объекту. Для предложений в «языках», находящихся выше в семантической иерархии, допустимо ссылаться на предложения, находящиеся ниже в иерархии «языка», но не наоборот. Это не позволяет системе стать самореферентной.
Однако эта система неполна. Хотелось бы иметь возможность делать утверждения, например, «Для каждого утверждения на уровне α иерархии существует утверждение на уровне α +1, которое утверждает, что первое утверждение ложно». Это истинное, осмысленное утверждение об иерархии, которую определяет Тарский, но оно относится к утверждениям на каждом уровне иерархии, поэтому оно должно быть выше каждого уровня иерархии и, следовательно, невозможно внутри иерархии (хотя возможны ограниченные версии предложения). [6] [7] Солу Крипке приписывают выявление этой неполноты в иерархии Тарского в его часто цитируемой статье «Очерк теории истины» [7] , и это признано общей проблемой в иерархических языках. [8] [7]
Используя программы или доказательства ограниченной длины, можно построить аналог выражения Берри на формальном математическом языке, как это сделал Грегори Чайтин . Хотя формальный аналог не приводит к логическому противоречию, он доказывает определенные результаты невозможности. [9]
Булос (1989) построил на формализованной версии парадокса Берри доказательство теоремы Гёделя о неполноте новым и гораздо более простым способом. Основная идея его доказательства заключается в том, что предложение , которое справедливо для x тогда и только тогда, когда x = n для некоторого натурального числа n, может быть названо определением для n , и что множество {( n , k ): n имеет определение длиной k символов} можно показать как представимое (используя числа Гёделя ). Тогда предложение " m - первое число, не определяемое менее чем за k символов" можно формализовать и показать, что оно является определением в только что указанном смысле. [10]
В общем случае невозможно однозначно определить, какое минимальное количество символов требуется для описания данной строки (при наличии конкретного механизма описания). В этом контексте термины строка и число могут использоваться взаимозаменяемо, поскольку число на самом деле является строкой символов, например, английское слово (например, слово «eleven», используемое в парадоксе), в то время как, с другой стороны, можно ссылаться на любое слово с помощью числа, например, по номеру его позиции в данном словаре или с помощью подходящей кодировки. Некоторые длинные строки можно точно описать, используя меньше символов, чем требуется для их полного представления, что часто достигается с помощью сжатия данных . Сложность данной строки затем определяется как минимальная длина, которая требуется описанию для того, чтобы (однозначно) ссылаться на полное представление этой строки.
Сложность Колмогорова определяется с помощью формальных языков , или машин Тьюринга , которые избегают двусмысленности относительно того, какая строка получается из данного описания. Можно доказать, что сложность Колмогорова невычислима. Доказательство от противного показывает, что если бы было возможно вычислить сложность Колмогорова, то также было бы возможно систематически генерировать парадоксы, подобные этому, то есть описания короче, чем то, что подразумевает сложность описываемой строки. То есть, определение числа Берри парадоксально, потому что на самом деле невозможно вычислить, сколько слов требуется для определения числа, и мы знаем, что такое вычисление невозможно из-за парадокса.