Предикативность, цикличность и Антиосновность

Michael Rathjen

Абстрактный. Аксиома Антифундамента, AFA, оказалась универсальным принципом в наборе

теория для моделирования множества круговых и самореферентных явлений. В этой статье исследуется
, может ли AFA и наиболее важные инструменты, исходящие из него, такие как Лемма о решении и
принцип корекурсии, быть разработаны на предикативных основаниях, т. е. в рамках
предикативной теории множеств.

Если бы можно было показать, что большинство круговых явлений, возникших в компьютерной науке
, не требуют для своего моделирования аксиом существования импредикативных множеств, это продемонстрировало бы
, что их кругообразность имеет иной вид, чем тот, который лежит в основе импредикативных определений.

Введение

Рассел обнаружил свой парадокс в мае 1901 года, работая над своими принципами
математики [28]. В ответ на этот парадокс он развил свое различение логических
типов. Хотя впервые введенная в [28], теория типов нашла свое зрелое выражение пять
лет спустя в его статье 1908 года математическая логика как основанная на теории типов
[29]. В [29] Рассел начинает со списка противоречий, которые должны быть решены.
К ним относятся парадокс лжеца Эпименида, его собственный парадокс и антиномия бурали-Форти
с наибольшим порядковым номером. В первом анализе он замечает: "во всех вышеперечисленных противоречиях (которые
являются просто выборками из неопределенного числа) существует общая характеристика,
которую мы можем описать как саморефлексию или рефлексивность” ([29]: 224). При более близком
рассмотрении он различает форму рефлексивности, которая является общим основополагающим корнем для
проблемы следующим образом:

Все, что мы предполагаем быть совокупностью пропозиций, утверждений о том, что

эта совокупность порождает новые предложения, которые под страхом противоречия
должны лежать вне этой совокупности. Бесполезно расширять эту совокупность, ибо это в
равной степени расширяет и объем высказываний о ней. ([29]: 224)

Здесь Рассел очень ясно заявляет о запрете на так называемые импредикативные определения, впервые
сформулированные Пуанкаре. Импредикативное определение объекта относится к предполагаемой
совокупности, членом которой сам определяемый объект является. Например, чтобы
определить набор натуральных чисел

X как X = {n∈N: ∀Y ⊆ N F (n, Y)} является impredica-

тиве, так как она включает в себя количественную переменную ‘

Y ' ранжирование по произвольным подмножествам

192

M. Rathjen

натуральное число

N, из которых множество X определяется как один член. Определяющий

будь то

∀Y ⊆ N F (n, Y)} имеет видимый круг, так как мы должны будем

знаете в частности ли

F (n, X) имеет место—но это не может быть установлено, пока
не будет определен сам X. Импредикативные определения множеств пронизывают ткань теории множеств Цермело-Френкеля
под видом аксиом разделения и замены, а также аксиомы
пауэрсета.

Избегание импредикативных определений также было названо порочным кругом

- Принцип. Этот принцип был очень серьезно воспринят Германом Вейлем:

Глубочайший корень проблемы лежит в другом месте: поле возможностей
, открытых в бесконечность, было ошибочно принято за замкнутую область вещей, существующих
в себе. Как указал Брауэр, это заблуждение, Грехопадение и
первородный грех теории множеств, даже если из нее не вытекает никаких парадоксов. ([34]: 243)

Когда же выяснилось, что разветвленная теория типов многое сделала из элементарного

математика неосуществима, Рассел, забыв о своем первоначальном понимании, ввел, как
специальный прием и по вполне прагматическим причинам, свою пресловутую аксиому сводимости.
Эта "аксиома" гласит, что каждый набор более высокого уровня является коэкстенсивным с одним из самых низких
уровней. Таким образом, он восстановил отмененные импредикативные определения через
заднюю дверь, как бы подорвав всю логику разветвленной иерархии
типов и уровней до такой степени, что ее можно было бы
вообще выбросить. - Насмешливо провозгласил Вейль.:

Рассел для того, чтобы выпутаться из этого дела, заставляет разум
совершить харакири, постулируя вышеизложенное утверждение, несмотря на то, что оно не
подкрепляется никакими доказательствами ("аксиома сводимости"). В небольшой книге "Das
Kontinuum " я попытался сделать честное следствие и построил
поле вещественных чисел первого уровня, в пределах которого
могут выполняться наиболее важные операции анализа. ([34]: 50)

В своих анализах противоречий и антиномий Рассел часто отождествляет
общего виновника с самоотверженностью (ср. выше) и рассматривает проблемы как возникающие из
рефлексивных заблуждений ([29]: 230). Он запрещает предложения этой формы “

x находится среди x ' s "
([28]: 105) и в своей собственной так называемой “неклассовой” теории классов он объясняет, что
пропозициональные функции, такие как функция “

x -это множество”, не может быть применено к
себе, так как самостоятельное применение привело бы к возникновению порочного круга. В отличие от его убедительного анализа
проблемы импредикативности, обвинения Рассела против самореферентных понятий
не так хорошо объяснены. Возможно, что сфера его критики была просто предназначена для того, чтобы
ограничиться вопросами, относящимися к его собственным типовым теориям, хотя более вероятно
, что он рассматривал самоотносимые понятия как несвязные или скорее ошибочные
концепции, которые все равно должны быть запрещены. В истории философии такое обвинение есть
кругооборот является старым и считается равносильным вынесению опровержения. В своей
"Analytica Posteriora " Аристотель ставит вне закона круговые линии аргументации. Точно так же Фома Аквинский
называет бесконечный ряд причин, каждая из которых в некотором смысле зависит от априорного
, порочным регрессом. С другой стороны, в герменевтике был постулат о том, что
постижение может произойти только через молчаливое предвидение, подчеркивая тем самым, что

Предикативность, цикличность и Антиосновность

193

присущая всему пониманию цикличность (герменевтический круг). В том же духе
цикличность была обнаружена во многих интенциональных действиях, связанных с самосознанием,
общением, общим знанием и конвенциями. Например, по мнению Д. Льюиса
в его книге "условность " [20], для того чтобы нечто было условностью среди группы
людей, общее знание об определенных фактах должно быть получено в этой группе. Если

С

и

E являются модальными операторами такими, что Cϕ и E stand означают " ϕ является общеизвестным"

и еще...

ϕ известна всем', соответственно, тогда центральная аксиома которой имплицитно

определяет

C принимает самореферентную форму Cϕ ↔ E (ϕ ∧ cϕ).

В логике циклические концепции, включающие самосопоставление или самоприменение, оказались
очень важными, о чем свидетельствуют теоремы неполноты Геделя
, теорема рекурсии в теории рекурсии, самоприменяющиеся программы и такие так называемые прикладные
теории, как явная математика Фефермана, которые имеют встроенные устройства, позволяющие
самоприменение.

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

Несмотря на отсутствие простых синтаксических критериев для выявления парадоксальных
кругооборотов, представляет большой интерес разработка рамок, в которых можно моделировать многие не парадоксальные
круговые явления. Одной из таких рамок является теория
явной математики Фефермана, ср. [13]. Он подходит для представления конструктивной
математики в стиле Бишопа, а также обобщенной рекурсии, включая прямое выражение структурных
понятий, допускающих самоприменение. Еще одним очень систематизированным инструментарием для построения
моделей различных круговых явлений является теория множеств с антиосновной аксиомой.
Теории, такие как ZF outlaw устанавливает, как

= { } и бесконечные цепочки вида

i+1

∈

я

для всех

i∈ω из-за аксиомы основания, и иногда можно услышать ошибочное
мнение, что единственная согласованная концепция множеств исключает такие множества. Фундаментальное
различие между хорошо обоснованными и не очень обоснованными наборами было сформулировано
Миримановым в 1917 году. Относительная независимость аксиомы основания от других
аксиом теории множеств Цермело–Френкеля была объявлена Бернейсом в 1941 г., но не
появилась до 1950-х гг. версии аксиом, утверждающие существование не вполне обоснованных
множеств, были предложены Финслером (1926). Идеи доказательства независимости Бернайса были:
эксплуатируется Ригер, Хаджек, Боффа и Фельгнер. После Финслера Скотт в 1960 году, по-видимому
, был первым человеком, который рассматривал Антиосновную аксиому, которая
заключает в себе усиление аксиомы экстенсиональности. Аксиома Антиоснования в ее
сильнейшем варианте была впервые сформулирована Форти и Хонсю [16] в 1983 году. Хотя
несколько логиков исследовали теории множеств, вселенные которых содержали не вполне обоснованные множества

194

M. Rathjen

(или гиперсети, как они называются в настоящее время) эта область считалась довольно экзотической, пока
эти теории не были использованы для разработки строгих счетов круговых понятий в
компьютерной науке, cf. [3]. Оказалось, что Антиосновная аксиома AFA породила
богатую вселенную множеств и обеспечила элегантный инструмент для моделирования всех видов круговых
явлений. Прикладные области варьируются от модальной логики, представления знаний
и теоретической экономики до семантики естественного языка и
языков программирования. Тема гиперсетей и их приложений тщательно разрабатывается в рамках данной статьи.
книги [3] P. Aczel и [5] J. Barwise и L. Moss.

В то время как я читал [3] и [5], у меня возник вопрос о том
, может ли этот материал быть разработан на основе конструктивной Вселенной гиперсетей
, а не классической и импредикативной. В этой статье исследуется, может ли AFA и
наиболее важные инструменты, исходящие из него, такие как Лемма о решении и
принцип коррекурации, быть разработаны на предикативных основаниях, т. е. в рамках
предикативной теории множеств. Результатом будет то, что большинство круговых явлений
, возникших в информатике, не требуют импредикативных аксиом существования множества
для их моделирования, тем самым показывая, что их кругообразность явно отличается
от того, который лежит в основе импредикативных определений.

Аксиома Против Фундамента

Определение 2.1. Граф будет состоять из набора узлов и набора ребер, каждое
из которых является упорядоченной парой

x, y узлов. Если x, y-ребро, то мы запишем x → y

и скажи, что...

y-это дитя X.

Путь -это конечная или бесконечная последовательность

икс

0

→ икс

1

→ икс

2

→ * * * узлов x

0

, икс

1

, икс

2

,...

связанные ребрами

икс

0

, икс

1

, икс

1

, икс

2

,....

Точечный граф -это граф вместе с выделенным узлом

икс

0

называл свою точку зрения.

Точечный граф доступен, если для каждого узла

x существует путь x

0

→ икс

1

→ икс

2

→

* * * → x из точки x

0

Для

икс.

Украшение графика - это назначение

d множества к каждому узлу графа
таким образом, что элементы множества, назначенные узлу, являются множествами, назначенными
дочерним узлам этого узла, т. е.,

d (a) = {d(x): a → x}.

Изображение набора- это доступный точечный график (ПНГ для краткости), который имеет украшение

в которой множество назначается точке.

Определение 2.2. Аксиома Антиоснования, AFA, заключается в утверждении, что каждый график
имеет уникальное украшение.

Заметим, что АФА имеет следствием то, что каждый ПНГ является изображением уникального набора.
АФА-это фактически соединение двух утверждений:

Предикативность, цикличность и Антиосновность

195

* AFA

1

: Каждый график имеет по крайней мере одно украшение.

* AFA

2

: Каждый график имеет самое одно украшение.

АФА

1

является утверждением существования, тогда как AFA

2

является ли усиление Экстенсиональности

аксиома теории множеств. Например, взяв график

Г

0

чтобы состоять из одного узла

икс

0

и

один край

икс

0

→ икс

0

, AFA

1

гарантирует, что этот график имеет украшение

д

0

(x) = {d

0

(год):

x → y} = {d

0

(x)}, порождая множество b такое, что b = {b}. Однако, если есть

другой набор

c, удовлетворяющий c = {c}, аксиома Экстенсиональности не заставляет b быть равным

Для

c, в то время как AFA

2

доходность

b = c. таким образом, по AFA существует ровно один набор

такие что

= { }.

Еще один пример, который демонстрирует экстенсионализующий эффект AFA

2

это pro-

VID by the graph

Г

∞

который состоит из бесконечного множества узлов

икс

я

а еще по краям

икс

я

→ икс

i+1

для каждого

i∈ω. По данным AFA

1

,

Г

∞

имеет украшение. Как

д

∞

(икс

я

) =

определяет такое украшение, АФА

2

влечет за собой, что это только один, в результате чего различные

диаграммы

Г

0

и

Г

∞

дайте начало тому же не вполне обоснованному набору.

Наиболее важные приложения АФА возникают в связи с решением систем
уравнений множеств. В двух словах это показано на следующем примере. Пусть
p и q-произвольные фиксированные множества. Предположим, что нам нужны множества x, y, z такие, что

x = {x, y}
y = {p, q, y, z}

z = {p, x, y}.

(1)

Здесь

p и q лучше всего рассматривать как атомы, в то время как x, y, z являются неопределенными элементами
системы. AFA гарантирует, что система (1) имеет уникальное решение. Существует мощная
методика, которая может быть использована, чтобы показать, что системы уравнений определенного типа
всегда имеют уникальные решения. В терминологии [5] это называется решением леммы.

Мы докажем это в разделах, посвященных применению АФА.