Парадокс Берри

Парадокс Берри — это самореферентный парадокс, возникающий из такого выражения, как «Наименьшее положительное целое число, не определяемое менее чем шестьюдесятью буквами» (фраза из пятидесяти семи букв).

Бертран Рассел , первым обсудивший парадокс в печати, приписал его Дж. Г. Берри (1867–1928), младший библиотекарь библиотеки Оксфорда Бодлианской ​ . Рассел назвал Берри «единственным человеком в Оксфорде, понимающим математическую логику». назвал « парадоксом Ришара » Этот парадокс Жан-Ив Жирар .

Обзор

Рассмотрим выражение:

«Наименьшее положительное целое число, не определяемое менее чем шестьюдесятью буквами».

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

Математик и ученый-компьютерщик Грегори Чайтин в книге «Непознаваемое» (1999) добавляет следующий комментарий: «Ну, мексиканский историк-математик Алехандро Гарсидиего потрудился найти это письмо [Берри, из которого Рассел записал свои замечания], и это совсем другое Парадокс. В письме Берри на самом деле говорится о первом ординале, который нельзя назвать конечным числом слов. Согласно теории Кантора, такой ординал должен существовать, но мы только что назвали его конечным числом слов, что является парадоксом. противоречие."

Разрешение

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

Это семейство парадоксов можно разрешить, включив в язык наслоения значений. Термины с систематической двусмысленностью могут быть записаны с индексами, обозначающими, что один уровень значения считается более приоритетным, чем другой, в их интерпретации. «Число, которое нельзя назвать ₀ менее чем в одиннадцати словах», в соответствии с этой схемой может быть названо ₁ менее чем в одиннадцати словах.

Однако можно прочитать Альфреда Тарского вклад в парадокс лжеца, чтобы понять, почему это решение на языках не соответствует действительности. Альфред Тарский диагностировал парадокс как возникающий только в «семантически закрытых» языках, под которым он имел в виду язык, в котором одно предложение может утверждать истинность (или ложность) другого предложения на том же языке (или даже самого себя). ). Чтобы избежать внутреннего противоречия, необходимо при обсуждении значений истинности представлять себе уровни языков, каждый из которых может утверждать истинность (или ложность) только языков более низкого уровня. Итак, когда одно предложение относится к истинностному значению другого, оно семантически выше. Упомянутое предложение является частью «объектного языка», в то время как соответствующее предложение считается частью «метаязыка» по отношению к объектному языку. Предложения на «языках» выше в семантической иерархии имеют право ссылаться на предложения ниже в «языковой» иерархии, но не наоборот. Это не позволяет системе стать самореферентной.

Однако эта система несовершенна. Хотелось бы иметь возможность делать такие утверждения, как «Для каждого утверждения на уровне α иерархии существует утверждение на уровне α +1, которое утверждает, что первое утверждение ложно». Это истинное и значимое утверждение об иерархии, которую определяет Тарский, но оно относится к утверждениям на каждом уровне иерархии, поэтому оно должно находиться выше каждого уровня иерархии и, следовательно, невозможно внутри иерархии (хотя ограниченные версии предложение возможно). Саулу Крипке приписывают определение этой неполноты в иерархии Тарского в его широко цитируемой статье «Очерк теории истины». и это признано общей проблемой в иерархических языках.

Формальные аналоги

Используя программы или доказательства ограниченной длины, можно построить аналог выражения Берри на формальном математическом языке, как это сделал Григорий Чайтин . Хотя формальный аналог не приводит к логическому противоречию, он доказывает некоторые результаты невозможности.

Булос (1989) использовал формализованную версию парадокса Берри, чтобы доказать теорему Гёделя о неполноте новым и гораздо более простым способом. Основная идея его доказательства состоит в том, что предложение , которое справедливо для x тогда и только тогда, когда x = n для некоторого натурального числа n, назвать определением n можно , и что множество {( n , k ): n имеет определение, которое длина k символов} можно показать, что он представим (с использованием чисел Гёделя ). Тогда предложение « m — первое число, не определяемое менее чем с помощью k символов» можно формализовать и показать, что оно является определением в только что изложенном смысле.

Связь с колмогоровской сложностью

Основная статья: Колмогоровская сложность

В общем случае невозможно однозначно определить, какое минимальное количество символов необходимо для описания данной строки (при определенном механизме описания). В этом контексте термины «строка» и «число» могут использоваться взаимозаменяемо, поскольку число на самом деле представляет собой строку символов, например, английское слово (например, слово «одиннадцать», использованное в парадоксе), хотя, с другой стороны, возможно для обозначения любого слова с номером, например, по номеру его позиции в данном словаре или по подходящей кодировке. Некоторые длинные строки можно точно описать, используя меньше символов, чем требуется для их полного представления, что часто достигается с помощью сжатия данных . Сложность данной строки затем определяется как минимальная длина, необходимая описанию для того, чтобы (однозначно) ссылаться на полное представление этой строки.

Колмогоровская сложность определяется с использованием формальных языков или машин Тьюринга , что позволяет избежать двусмысленности относительно того, какая строка является результатом данного описания. Можно доказать, что колмогоровская сложность невычислима. Доказательство от противного показывает, что если бы можно было вычислить колмогоровскую сложность, то можно было бы также систематически генерировать парадоксы, подобные этому, т.е. описания короче, чем предполагает сложность описываемой строки. Иными словами, определение числа Берри парадоксально, потому что на самом деле невозможно вычислить, сколько слов требуется для определения числа, и мы знаем, что такое вычисление невозможно из-за парадокса.

См. также

• Парадокс Бхартрихари , статья 1981 года, посвященная обсуждению Бхартрихари в V веке парадокса самореференции, включая тот факт, что утверждение о том, что что-то не имеет названия, делает это именуемым.
• Занятой бобер - самая долгоработающая машина Тьюринга заданного размера.
• Теорема Чайтина о неполноте - мера алгоритмической сложности. Страницы с краткими описаниями целей перенаправления.
• Определяемое действительное число - действительное число, уникально определенное описанием.
• Парадокс Гильберта-Бернейса - предел классической логики. Страницы, отображающие описания викиданных в качестве запасного варианта.
• Парадокс интересных чисел – О наименьшем неинтересном числе
• Парадоксы теории множеств
• Парадокс Ричарда - Кажущееся противоречие в метаматематике

Ссылки

• Билл, Дж. К.; Гланцберг, Майкл; Рипли, Дэвид (12 декабря 2016 г.). «Парадокс лжеца» . В Залте, Эдвард Н. (ред.). Стэнфордская энциклопедия философии .
• Булос, Джордж (1989). «Новое доказательство теоремы Гёделя о неполноте». Уведомления Американского математического общества . 36 : 388–390, 676. Перепечатано в Булос, Джордж (1998). Логика, логика и логика . Издательство Гарвардского университета . стр. 383–388. ISBN  0-674-53766-1 .
• Чайтин, Г.Дж. (1995). «Парадокс Берри» (PDF) . Сложность . 1 (1): 26–30. дои : 10.1002/cplx.6130010107 . МР   1366300 .
• Жирар, Жан-Ив (2011). Слепое пятно: Лекции по логике . Европейское математическое общество. ISBN  9783037190883 .
• Гланцберг, Майкл (2015). «Сложность и иерархия в предикатах истинности». В Ачуриоти, Теодора; Галинон, Анри; Фернандес, Хосе Мартинес; Фудзимото, Кентаро (ред.). Объединение философии истины . Логика, эпистемология и единство науки. Том. 36. Дордрехт: Спрингер. стр. 211–243. дои : 10.1007/978-94-017-9673-6_10 . ISBN  978-94-017-9672-9 .
• Гриффин, Николас (2003). Кембриджский компаньон Бертрана Рассела . Издательство Кембриджского университета. ISBN  978-0-521-63634-6 .
• Крипке, Саул (ноябрь 1975 г.). «Очерк теории истины». Семьдесят второе ежегодное собрание Американской философской ассоциации, Восточное отделение (6 ноября 1975 г.). Журнал философии . 72 (19): 690–716. дои : 10.2307/2024634 . JSTOR   2024634 .
• Мур, Грегори Х. (2014). Сборник статей Бертрана Рассела, том. 5 . Рутледж. ISBN  9780415820981 .
• Куайн, Уиллард Ван Орман (1976). Пути парадокса и другие очерки (2-е изд.). Издательство Гарвардского университета. ISBN  9780674948358 .
• Рассел, Бертран ; Уайтхед, Альфред Н. (1927). Принципы математики . Издательство Кембриджского университета.

Дальнейшее чтение

• Беннетт, Чарльз Х. (1979). «О случайных и трудноописываемых числах» . Отчет IBM RC7483 . CiteSeerX   10.1.1.27.3492 .
• Френч, Джеймс Д. (1988) « Ложное предположение, лежащее в основе парадокса Берри », Журнал символической логики 53 : 1220–1223.
• Рассел, Бертран (1906) «Парадоксы логики», Revue de метафизики и морали 14 : 627–650

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

• Розен-Рунге, Питер Х. (1997) « Парадокс Берри » .
• Вайсштейн, Эрик В. «Ягодный парадокс» . Математический мир .