АФА в теории конструктивных множеств

В этом разделе я представлю некоторые результаты о теоретико-доказательной силе систем
конструктивной теории множеств с AFA вместо

∈-Индукционный.

Конструктивная Теория Множеств

Конструктивная теория множеств выросла из попыток Майхилла [23] обнаружить простой
формализм, который относится к конструктивной математике Бишопа, как ZFC относится к классической
канторианской математике. Позже Акцель модифицировал теорию множеств Майхилла в систему
, которую он назвал конструктивной теорией множеств Цермело-Френкеля, CZF, и подтвердил ее

196

M. Rathjen

конструктивность путем ее интерпретации в теории типов Мартина-Лефа (MLTT), ср. [1].
Интерпретация была во многом канонической и может рассматриваться как предоставление CZF
стандартной модели в теории типов.

Пусть CZF

−

будьте CZF без

∈- индукция и пусть CZFA будет CZF

−

плюс АФА. I.
Lindström [21] показал, что CZFA также может быть интерпретирована в MLTT. Среди других
источников, работа [21] будет использована для калибровки точной прочности различных
расширений CZFA, в частности с недоступными аксиомами набора. В результате получается, что
AFA не дает никакой дополнительной теоретико-доказательной прочности на основе конструктивной
теории множеств и действительно намного слабее в прочности доказательства, чем

∈-Индукционный. Это контрастирует
с теорией множеств Крипке-Платека, KP. Теория кПа, которая принимает АФА вместо схемы
аксиомы основания, является доказательством-теоретически значительно сильнее, чем КП, как
было показано в [26]. С другой стороны, будучи более слабым в теоретико-доказательной силе,
CZFA, по-видимому, “математически” сильнее, чем кПа, поскольку большинство приложений, которые
нашел AFA, могут быть легко формализованы в CZFA, тогда как существуют серьезные трудности
с этим в кПа. Например, доказательство от AFA, что коллекция потоков
над заданным набором

A существует и формирует множество, по-видимому, требует аксиомы экспоненции,
инструмента, который явно не доступен в KPA.

Теория CZFA

Язык CZF является языком первого порядка теории множеств Цермело-Френкеля, LST,
с нелогическим примитивным символом

∈. Мы предполагаем, что LST также имеет постоянную, ω,
для множества натуральных чисел.

Определение 3.1 (аксиомы ЧФ). CZF основан на интуитивистской логике предикатов с
равенством. Теоретико-множественными аксиомами CZF являются следующие:

1. Экстенсиональность.

∀а ∀в (∀У (У ∈ А ↔ Г ∈ Б) → А = B).

2. Пара.

∀а ∀б ∃х ∀у (у ∈ Х ↔ У = а ∨ у = б).

3. Союз.

∀на ∃Х ∀У (У ∈ Х ↔ ∃Z В∈а Y ∈ Z).в

4.

0

- Схема разделения.

∀на ∃Х ∀У (У ∈ Х ↔ У ∈ а ∧ Φ(г)),

для каждой ограниченной формулы

ϕ (y), где формула ϕ (x) ограничена, или

0

, если

все кванторы, встречающиеся в нем, ограничены, т. е. имеют вид

∀x∈b или ∃x∈b.

5. Схема сбора подмножеств.

∀а ∀б ∃c Для ∀у ∀Х∈а ∃у∈B и ϕ(х, г, х) →
∃Д∈С (∀Х∈а ∃у∈ϕ Д(х, г, У) ∧ ∀У∈Д ∃х∈а Φ(Х, У, Й))

для каждой формулы:

ϕ (x, y, u).

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

197

6. Сильная схема сбора данных.

∀а ∀х∈а ∃Y и ϕ(Х, Y) →
∃б (∀х∈а ∃у∈B и ϕ(Х, Y) ∧ ∀у∈б ∃х∈а Φ(Х, Y))

для каждой формулы:

ϕ (x, y).

7. Бесконечность.

(ω1)

0

∈ω ∧ ∀y (y∈ω → y + 1∈ω)

(ω2) ∀х (0∈Х ∧ ∀У (У∈х → г + 1∈х) → ω ⊆ х),

где

y + 1 - это y ∪ {y}, а 0-пустое множество, определенное очевидным образом.

8.

∈ - Схема индукции.

(Я НАХОЖУ

∈

)

∀а (∀х∈а Φ(х) → ϕ(А)) → ∀а Φ(а),

для каждой формулы:

ϕ (a).

Определение 3.2. Пусть CZF

−

будьте системой CZF без

∈ - Схема индукции.

Замечание 3.3. CZF

−

является достаточно сильным, чтобы показать существование любого примитивного рекурсивного

функция ВКЛ

ω и поэтому арифметика Хейтинга может быть интерпретирована в CZF

−

в самом
очевидном смысле. В качестве примера, давайте проверим это для сложения: в результате
сбора подмножеств получается, что для произвольных наборов

a, b, класс всех функций

От

от А до в,

один

б, это набор. Использование Сильной Коллекции, {

н

ω: n∈ω} является множеством, и таким образом

Плавник

:=

n ω ω

н

ω-это тоже множество. Используя аксиому (ω2), можно показать, что

∀ n, m ω ω × ω ∃!f ∈ Fin θ(n, m, f),

где

θ (n, m, f) обозначает формулу

дом

(f) = m + 1 ∧ f (0) = n ∧ (∀i∈m) f (i + 1) = f (i) + 1.

Используя сильную коллекцию, существует набор

А такое что

∀ N и m ∈ ω × ω ∃е ∈ θ В(Н, м, F) ∧ ∀Е ∈А ∃ N и m ∈ ω × ω θ(Н, м, ф).

Теперь определимся

h: ω × ω → ω, позволяя h (n, m) = k тогда и только тогда, когда

∃f ∈ A θ (n, m, f) ∧ f (m) = k.

Это легко показать, что

h удовлетворяет уравнениям рекурсии

h(n, 0) = n ∧ h(n, m + 1) = h (n, m) + 1.

Определение 3.4. К сожалению, CZF

−

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

198

M. Rathjen

транзитивное замыкание произвольного множества. Чтобы исправить это, мы рассмотрим аксиому
TRANS, которая гарантирует, что каждое множество содержится в транзитивном множестве:

ТРАНС

∀Х ∃У х ⊆ г ∧ (∀У∈М) (∀В∈У) и V∈г.

Пусть CZFA-это теория CZF

−

+ ТРАНС + АФА.

Лемма 3.5. Пусть ТК

(x) подставка для наименьшего транзитивного набора, содержащего все элементы

от

X.CZF

−

+ TRANS доказывает существование TC (x) для любого множества x.

Доказательство. Мы будем использовать следствие коллекции подмножеств, называемой Экспоненцией, которая
утверждает, что для произвольных множеств

a, b, класс всех функций от a до b,

один

б, это набор.

Позволь

x-произвольное множество. По транс существует транзитивное множество a такое, что x ⊆ A.

Для

n∈ω пусть

Б

н

= {Ф ∈

n+1

A: f (0) ∈ x ∧ (∀i∈n) f (i + 1) ∈ f (i)},

ТС

н

(икс) =

{ran (f): f ∈ B

н

},

куда побежал

f) обозначает диапазон значений функции f. Б

н

является множеством вследствие возведения в степень

и

0

Разделение. ТС

н

(x) - это множество по объединению. Кроме Того, C =

n ω ω

ТС

н

(x) является a

установите сильным собранием и соединением. Затем

x = TC

0

(x) ⊆ C. Пусть y-транзитивное множество

такие что

x ⊆ y. с помощью индукции на n легко проверить, что TC

н

(x) ⊆ y, и, следовательно
, C ⊆ y. кроме того, C является транзитивным. Таким образом, C является наименьшим транзитивным множеством, которое содержит
все элементы из

икс.

Определение 3.6. Математически очень полезной аксиомой для теории множеств является
аксиома зависимого выбора, DC, т. е. для всех формул

ψ, всякий раз, когда

(∀x∈a) (∃y∈a) ψ (x, y)

и

б

0

∈a, то существует функция f: ω → a такая, что f (0) = b

0

и

(∀n ω ω) ψ(f (n), f (n + 1)).

Для функции

f пусть dom (f) обозначает область f. Еще более полезно в конструктивном плане

теория множеств-это Релятивизированная аксиома зависимого выбора, RDC.

1

Он утверждает, что для

произвольные формулы

φ и ψ, когда бы то ни было

∀x φ (x) → ∃y φ (y) ∧ ψ(x, y)

и

φ(b

0

), то существует функция f с dom (f) = ω такая, что f (0) = b

0

и

(∀n ω ω) φ (f (n)) ∧ ψ(F (N), F (N + 1)).

Ограниченная форма RDC, где

φ и ψ необходимы для того чтобы быть

0

формулы будут называться

0

-НТЦ.

1

В [2] RDC называется аксиомой зависимых выборов, а DC - аксиомой ограниченной зависимости

выбор. Мы отклоняемся от обозначения в [2], поскольку оно отклоняется от использования в классических текстах теории множеств.

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

199

Дефект CZF

−

относительно отсутствия достаточного количества транзитивных множеств можно также сказать:

исправлено путем добавления

0

- От RDC до CZF

−

. Пожалуй, стоит отметить, что

0

-НТЦ

подразумевает ДЦ на базе ЧФ

−

.

Лемма 3.7. CZF

−

+

0

- RDC

- Округ Колумбия.

Доказательство. См. [27]: Лемма 3.4.

Существование транзитивного замыкания любого множества также может быть получено с помощью слабо

усиление индукции на

ω к

1

- IND

ω

φ(0) ∧ (∀n∈ω)(φ(n) → φ(n + 1)) → (∀n∈ω)φ(n)

для всех

1

формулы

φ. Стоит отметить, что

1

- IND

ω

на самом деле подразумевает

- IND

ω

θ(0) ∧ (∀н∈ω)(θ(н) → θ (н + 1)) → (∀н∈ω)θ (н)

для всех

формулы

θ, где то

формулы - это наименьшая коллекция формул

включающ the

0

формулы, которые закрыты под

∧,∨, ограниченная количественная оценка, и

(неограниченная) экзистенциальная количественная оценка. Это связано с тем, что каждый

формула есть

эквивалентно a

1

формула доказуемо в CZF

−

. Последний принцип иногда называют таковым

то

Принцип отражения и может быть доказан, как в теории множеств Крипке-Платека (один легко

проверяет, что доказательство ([4]: I. 4. 3) также работает в CZF

−

).

- IND

ω

позволяет одно к

ввести функции путем

рекурсия ВКЛ

ω ([4]: I. 6), а также транзитивное замыкание

произвольное множество (на основе CZF

−

). Стоит отметить, что

- IND

ω

это на самом деле а

следствие этого

0

-НТЦ.

Лемма 3.8. CZF

−

+

0

- RDC

- IND

ω

.

Доказательство. Предположим, что

θ(0) ∧ (∀н∈ω)(θ(н) → θ (н + 1)), где θ(н) имеет вид

∃xφ (n, x) с φ

0

. Мы хотим это доказать

(∀n ω ω) θ (n).

Если

z-упорядоченная пара x, y пусть 1

ST

(z) обозначить x и 2

nd

(z) обозначим y. так как θ (0)

существует множество

икс

0

такие что

φ (0, x

0

). Поставить

0

= 0, x

0

.

От

(∀n ω ω) (θ (n) → θ (n + 1)) можно сделать вывод

(∀n ω ω)∀y [φ (n, y) → ∃w φ(n + 1, w) ]

и так далее

∀z → (z) → ∃v (ψ (v) ∧ χ(Z, v)),

где

ψ (z) означает, что z -это упорядоченная пара ∧ 1

ST

(z) ∈ ω ∧ φ(1

ST

z), 2

nd

(z)) и

χ (z, v) обозначает 1

ST

v) = 1

ST

z) + 1. Обратите внимание, что ψ и χ являются

0

. Мы также имеем

ψ (a

0

).

Таким образом, путем

0

- RDC существует функция

f: ω → V такое, что f (0) = a

0

и

(∀n ω ω) ψ(f (n)) ∧ χ(F (N), F (N + 1)).

От

χ (f (n), f (n + 1)), используя индукцию на ω, легко вывести, что 1

ST

(f (n))
= n для всех n∈ω. Отсюда и из (∀Н∈ω) ψ(ф (Н)), мы получаем (∀Н∈ω) ∃х φ(н, х) и
(∀Н∈ω) θ(н).

200

M. Rathjen

Рассмотрим также полную схему индукции на

ω,

IND

ω

ψ(0) ∧ (∀н∈ω)(ψ(н) → ψ(н + 1)) → (∀н∈ω)ψ(н)

для всех формул

ψ.

Лемма 3.9. CZF

−

+ НТЦ

IND

ω

.

Доказательство. Предположим, что

θ(0)∧(∀n∈ω)(θ(n) → θ(n + 1)). Мы хотим доказать (∀n ω ω) θ(n).

Позволь

φ(x) и ψ (x, y) - формулы x∈ω ∧ θ (X) и y = x + 1 соответственно. Тогда
∀x [φ(x) → ∃y (φ(y) ∧ ψ(X, Y))] и φ (0). Следовательно, по RDC существует функция
f с областью ω такая, что f (0) = 0 и ∀n ω ω [φ(f (n)) ∧ ψ(F (N), F (N + 1))]. Пусть
a = {n∈ω: f (n) = n}. Используя принцип индукции (ω2) можно легко проверить ω ⊆ a,
и следовательно

f (n) = n для всех n∈ω. Следовательно, φ (n)для всех n∈ω, и таким образом (∀n ω ω) θ(n).

Предикативизм

Вейль отверг платоновскую философию математики, проявившуюся в импредикативном учении

принципы существования теории множеств Цермело-Френкеля. В своей книге "Das Kontinuum "
он выдвинул предикативный подход к реальным числам и дал жизнеспособный отчет
о существенном куске анализа. Каковы идеи и принципы, на которых
, как предполагается, основывается его “предикативный взгляд”? Центральный принцип заключается в том, что существует
фундаментальное различие между нашим пониманием концепции натуральных чисел
и нашим пониманием концепции множества. Подобно французским предикативистам, Вейль принимает
завершенную бесконечную систему натуральных чисел как исходную точку. И он тоже
принимает классическую логику, но просто работает с множествами, которые имеют уровень один в разветвленной
иерархии Рассела, другими словами, только с принципом арифметических определений.

Логики, такие как Ван, Лоренцен, Шютте и Феферман, затем предложили
основы математики, используя слоистые формализмы, основанные на идее предикативности, которая
отважилась на более высокие уровни разветвленной иерархии. Идея автономного
развития теорий

РА

0

, РА

1

,..., РА

α

,... впервые был представлен в работе Крайзеля [18], а
затем поднят Феферманом и Шютте для определения пределов предикативности.
Понятие автономии в нем основано на самоанализе и, возможно, должно рассматриваться
как условие "пристегивания ремня безопасности". Человек берет структуру натуральных чисел в качестве отправной точки
и затем исследует через процесс активного размышления, что подразумевается
в принятии этой структуры, тем самым развивая растущее тело все более высоких слоев
разветвленной иерархии. Феферман и Шютте [30, 31, 11, 12] показали, что
порядковый номер

0

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

0

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

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

201

каждый порядковый номер меньше чем

0

является предикативно доказуемым порядковым номером. В последствии, каждое

теория с теоретико-доказательным порядковым номером меньше, чем

0

имеет предикативное доказательство согласованности

и к тому же консервативен над теорией

РА

α

для арифметических утверждений для некоторых

α <

0

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

В качестве шкалы для измерения теоретико-доказательной силы теорий
традиционно используются некоторые подсистемы арифметики второго порядка, см. [14, 33]. К
настоящему контексту относятся системы, основанные на следующих принципах:

1

1

аксиома выбора и то

1

1

аксиома о том, что

зависимый выбор. Теория

1

1

- AC является подсистемой арифметики второго порядка с

то

1

1

аксиома выбора и индукции над натуральными числами для всех формул в то время как

1

1

-ПОСТОЯННЫЙ ТОК

0

является подсистемой арифметики второго порядка с помощью

1

1

аксиома зависимого
выбора и индукции над натуральными числами, ограниченная формулами без
кванторов второго порядка (для точных определений см. [14, 33]). Теоретико-доказательный порядковый номер

1

1

- AC есть

ϕε

0

0 пока

1

1

-ПОСТОЯННЫЙ ТОК

0

имеет меньший теоретико-доказательный порядковый номер

ну как же было

показано Кантини [7]. Здесь

ϕ обозначает функцию Веблена, см. [32].

Теорема 4.1.

(i) теории CZF

−

+

1

- IND

ω

, CZFA

+

1

IND

ω

+

0

- RDC,

CZFA

+

1

- IND

ω

+DC, и

1

1

- DC

0

являются доказательством-теоретически эквивалентны. Их

теоретико-доказательство порядковый номер является

ϕω0.

ii) теории CZF

−

+ IND

ω

, CZFA

+ IND

ω

+ RDC, ID

1

, и

1

1

- AC есть

доказательство-теоретически эквивалентно. Их теоретико-доказательство порядковый номер является

ϕε

0

0.

(iii) CZFA имеет по крайней мере теоретико-доказательную силу арифметики Пеано и поэтому ее доказательство-

теоретический порядковый номер-это как минимум

ε

0

. Верхняя оценка для теоретико-доказательственного порядкового числа

ЧФР является

ϕ20. Следовательно, CZFA является доказательством-теоретически слабее, чем

CZFA

+

0

- RDC.

iv) Все вышеприведенные теории являются предикативно обоснованными.

Доказательство. (ii) следует из [27]: Теорема 3.15.

Что касается (i) важно отметить, что схема дублируется

0

- RDC в [27] не является

то же самое, что

0

- RDC в настоящем документе. В [27],

0

- RDC утверждает для

0

рецептурный

φ и

ψ, что всякий раз, когда (∀х∈а) φ(Х) → (∃У∈в) φ(г) ∧ ψ(Х, Y)

и

б

0

∈a ∧ φ(b

0

),

тогда существует функция

f: ω → a такое, что f (0) = b

0

и

(∀n ω ω) φ(f (n)) ∧

ψ (f (n), f (n + 1)). Последний принцип слабее нашего

0

- RDC как все кванторы

должны быть ограничены заданным набором

a. однако, интерпретация осуществимости

конструктивная теория множеств в ПА

Р

+

- IND, используемый в доказательстве ([27]: Теорема

3.15 (i)) также подтверждает более сильный

0

- RDC настоящего документа (система ПА

Р

стебли из [17]).

Теорема 3.15 (i) из [27] и Лемма 3.8 также подразумевают, что CZF

−

+

0

- RDC это не так

слабее, чем CZF

−

+

1

- IND

ω

. Таким образом, теоретико-доказательная эквивалентность всех систем в

(i)следует.

202

M. Rathjen

iii) является следствием замечания 3.3. В настоящее время точная теоретико-доказательная сила
CZFA неизвестна, однако можно показать, что теоретико-доказательный порядковый номер CZFA
не больше, чем

ϕ20. Последняя граница может быть получена путем проверки интерпретации

из CZFA в PA

Р

+

- IND используется в доказательстве [27]: Теорема 3.15. А осторожный

осмотр показывает, что подтеория

T из PA

Р

+

- IND достаточно. Если быть более точным,

T можно принять за теорию

ПА

Р

+ α α λ λ [α

Использование методов устранения разреза и асимметричной интерпретации,

T может быть частично

интерпретировано на языке РА

<ω

2

. Последняя теория, как известно, имеет теоретико-доказательственный порядковый номер

ϕ20.

iv) вышеуказанные порядковые номера меньше, чем

0

.

Замечание 4.2. Конструктивная теория множеств с АФА имеет интерпретацию в
теории типов Мартина-Лефа, как было показано И. Линдстремом [21]. Теория типов Мартина-Лефа
считается наиболее приемлемой фундаментальной основой идей,которая делает точным
конструктивный подход к математике. Интерпретация CZFA в теории типов Мартина-Лефа
демонстрирует, что существует конструктивное понятие множества, которое придает конструктивный
смысл AFA. Однако теория типов Мартина-Лефа не является предикативной теорией в
смысле Фефермана и Шютте, поскольку она обладает теоретико-доказательным порядком больше, чем

0

. Работа в [27] показывает, что CZFA и его варианты также могут быть сведены к теориям
, которые являются предикативными в более строгом смысле автономных прогрессий.