В математике , логике и философии математики непредикативным является самореферентное определение . Грубо говоря, определение непредикативно , если оно ссылается (упоминает или квантифицирует) на определяемое множество или (чаще) на другое множество, содержащее определяемую вещь. Не существует общепринятого точного определения того, что значит быть предикативным или непредикативным. Авторы давали разные, но связанные определения.
Противоположностью непредикативности является предикативность, которая по сути влечет за собой построение стратифицированных (или разветвленных) теорий, где квантификация по типу на одном «уровне» приводит к типам на новом, более высоком уровне. Прототипическим примером является интуиционистская теория типов , которая сохраняет разветвление (без явных уровней), чтобы отбросить непредикативность. «Уровни» здесь соответствуют количеству слоев зависимости в определении термина.
Парадокс Рассела — известный пример непредикативной конструкции, а именно множества всех множеств, которые не содержат себя. Парадокс в том, что такое множество не может существовать: если бы оно существовало, можно было бы задать вопрос, содержит ли оно себя или нет — если да, то по определению не должно, а если нет, то по определению должно.
Наивысшая нижняя граница множества X , glb( X ) , также имеет непредикативное определение: y = glb( X ) тогда и только тогда, когда для всех элементов x из X y меньше или равен x , и любой z , меньший или равный всем элементам X , меньше или равен y . Это определение квантифицирует множество (потенциально бесконечное , в зависимости от рассматриваемого порядка ), элементы которого являются нижними границами X , одним из которых является сам glb. Следовательно, предикативизм отверг бы это определение. [1]
Нормы (содержащие одну переменную), которые не определяют классы, я предлагаю называть непредикативными ; те, которые определяют классы, я буду называть предикативными .
(Рассел 1907, стр. 34) (Рассел использовал слово «норма» для обозначения предложения: грубо говоря, чего-то, что может принимать значения «истина» или «ложь».)
Термины «предикативный» и «непредикативный» были введены Расселом (1907), хотя с тех пор их значение несколько изменилось.
Соломон Феферман дает исторический обзор предикативности, связывая ее с текущими нерешенными исследовательскими проблемами. [2]
Принцип порочного круга был предложен Анри Пуанкаре (1905–6, 1908) [3] и Бертраном Расселом в связи с парадоксами как требование к допустимым спецификациям множеств. Множества, которые не удовлетворяют этому требованию, называются непредикативными .
Первый современный парадокс появился в 1897 году в работе Чезаре Бурали-Форти «Вопрос о трансфинитных числах» [4] и стал известен как парадокс Бурали-Форти . Георг Кантор , по-видимому, обнаружил тот же парадокс в своей (Кантора) «наивной» теории множеств , и это стало известно как парадокс Кантора . Осознание проблемы Расселом возникло в июне 1901 года [5] с прочтением им трактата Фреге о математической логике , его Begriffsschrift 1879 года ; оскорбительное предложение в работе Фреге следующее:
С другой стороны, может быть и так, что аргумент определен, а функция неопределенна. [6]
Другими словами, при заданной f ( a ) функция f является переменной, а a — инвариантной частью. Так почему бы не заменить значение f ( a ) на само f ? Рассел немедленно написал Фреге письмо, в котором указал, что:
Вы утверждаете... что функция также может действовать как неопределенный элемент. Я раньше так считал, но теперь эта точка зрения кажется мне сомнительной из-за следующего противоречия. Пусть w будет предикатом: быть предикатом, который не может быть предикатом о себе. Может ли w быть предикатом о себе? Из каждого ответа следует его противоположность. Поэтому мы должны заключить, что w не является предикатом. Точно так же нет класса (как совокупности) тех классов, которые, взятые каждый как совокупность, не принадлежат себе. Из этого я заключаю, что при определенных обстоятельствах определимая совокупность не образует совокупности. [7]
Фреге немедленно ответил Расселу, признав наличие проблемы:
Ваше открытие противоречия вызвало у меня величайшее удивление и, я бы сказал, испуг, поскольку оно потрясло основу, на которой я намеревался построить арифметику. [8]
Хотя проблема имела неблагоприятные личные последствия для обоих мужчин (у обоих были работы в типографиях, которые нужно было исправить), ван Хейеноорт замечает, что «Парадокс потряс мир логиков, и его толчки ощущаются и сегодня. ... Парадокс Рассела, который использует голые понятия множества и элемента, полностью относится к области логики. Парадокс был впервые опубликован Расселом в « Принципах математики» (1903) и обсуждается там очень подробно ...». [9] Рассел, после шести лет фальстартов, в конечном итоге ответил на этот вопрос своей теорией типов 1908 года, «выдвинув свою аксиому сводимости . Она гласит, что любая функция является соразмерной с тем, что он называет предикативной функцией: функцией, в которой типы мнимых переменных не выше типов аргументов». [10] Но эта «аксиома» встретила сопротивление со всех сторон.
Отказ от непредикативно определяемых математических объектов (при принятии натуральных чисел в их классическом понимании) приводит к позиции в философии математики, известной как предикативизм, отстаиваемой Анри Пуанкаре и Германом Вейлем в его работе Das Kontinuum . Пуанкаре и Вейль утверждали, что непредикативно определяемые определения проблематичны только тогда, когда одно или несколько базовых множеств бесконечны.
Эрнст Цермело в своей работе 1908 года «Новое доказательство возможности вполне упорядоченного множества» [11] представляет целый раздел «b. Возражение относительно непредикативного определения », где он выступает против «Пуанкаре (1906, стр. 307) [который утверждает, что] определение является «предикативным» и логически допустимым только в том случае, если оно исключает все объекты, зависящие от определяемого понятия, то есть которые каким-либо образом могут быть определены им». [12] Он приводит два примера непредикативных определений – (i) понятие цепей Дедекинда и (ii) «в анализе, где максимум или минимум ранее определенного «завершенного» множества чисел Z используется для дальнейших выводов. Это происходит, например, в известном доказательстве Коши...». [13] Он заканчивает свой раздел следующим замечанием: «Определение вполне может опираться на понятия, эквивалентные определяемому; действительно, в каждом определении definiens и definiendum являются эквивалентными понятиями, и строгое соблюдение требования Пуанкаре сделало бы всякое определение, а следовательно, и всю науку, невозможными». [14]
Пример Цермело минимума и максимума ранее определенного "завершенного" множества чисел снова появляется в Kleene 1952:42-42, где Клини использует пример наименьшей верхней границы в своем обсуждении непредикативных определений; Клини не решает эту проблему. В следующих параграфах он обсуждает попытку Вейля в его Das Kontinuum ( The Continuum ) 1918 года устранить непредикативные определения и его неспособность сохранить "теорему о том, что произвольное непустое множество M действительных чисел, имеющее верхнюю границу, имеет наименьшую верхнюю границу (ср. также Weyl 1919)". [15]
Рэмси утверждал, что «непредикативные» определения могут быть безвредными: например, определение «самый высокий человек в комнате» является непредикативным, поскольку оно зависит от множества вещей, элементом которого оно является, а именно множества всех людей в комнате. Что касается математики, примером непредикативного определения является наименьшее число в множестве, которое формально определяется как: y = min( X ) тогда и только тогда, когда для всех элементов x из X y меньше или равен x , и y содержится в X .
Берджесс (2005) довольно подробно обсуждает предикативные и непредикативные теории в контексте логики Фреге , арифметики Пеано , арифметики второго порядка и аксиоматической теории множеств .