Хорошо-приказывая доказательство внутри

КПЭ

0

+

(-

TR

)

Теперь этап установлен для распространения доказательства хорошего порядка в [5] на нашу теорию множеств

КПЭ

0

+ (-

TR

), подобно тому, как Rüede [8] принимает его для обработки

1

1

трансфинит

зависимый выбор. Мы покажем, что все ординалы меньше чем

ϕω00 доказуемо внутри

КПЭ

0

+ (-

TR

).

Как и в, например, [6] мы работаем с тернарными функциями Веблена для преодоления
достаточно длинного начального сегмента ординалов. Обычная иерархия Веблена
генерируется двоичной функцией

ϕ, начиная с ϕ0β = ω

β

, и часто обсуждается

в литературе, cf. например, [7] или [10]. Троичная функция Веблена

ϕ легко получается

из двоичного файла

ϕ следующим образом:

1.

ϕ0βγ - этоββγ.

2. Если

α > 0, то ϕα0γ обозначает γ-й порядковый номер, который сильно критичен с

уважение ко всем функциям

λξ.λη.δδ η η для δ

3. Если

α > 0 и β >> 0, то ϕαβγ обозначает общую неподвижную точку γ-го

функции

λη.ϕαδη для δ

Позволь

0

быть наименьшим порядковым номером больше 0, который закрыт при сложении и троичном
ϕ. Далее мы будем работать со стандартной примитивной рекурсивной системой счисления
(

ВЗ

, ≺) для всех ординалов меньше, чем

0

. Все необходимые определения просты

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

0

(ср. [7, 10]) и

может быть опущен.

В этом разделе мы позволим a b, c,... (возможно, с подстрочными знаками) диапазон по набору

ВЗ

;

в дополнение,

используется для кодов предельных ординалов; термины ˆ0

, ˆ1, ˆ2,... действуйте как коды для
конечных ординалов. Для упрощения нотации мы часто пишем порядковые константы и
порядковые функции, такие как,

0

,

1

,

ω,

λξ.λη.(ξ + η),

λξ.ω

ξ

,

λζ.λξ.λη.ϕζ ξ η

вместо соответствующих кодов используются и примитивные рекурсивные функции. Еще одна полезная
двоичная операция над порядковыми обозначениями, введенная в [5], задается с помощью

a ↑ b: = ∃c∃ (b = c + a ·).

Для полноты мы также помним, как это выражается, что наше конкретное примитивное рекурсивное
отношение

≺ является хорошо упорядоченным, что формула прогрессивна по отношению к ≺ и как

130

Г. Егер и Д. Пробст

трансфинитная индукция вдоль

≺ определяется для произвольных формул:

Wo

(ля):=

Wo

({b: b ≺ A}, { c, b: c ≺ b ≺ a}),

Еда

(A): = ∀a ((∀b ≺ a)a (b) → A (a)),

ТИ

(Ля):=

Еда

(A) → (∀b ≺ a) A(b).

Возможно, кроме a ↑ b, все эти понятия стандартны в контексте хорошо упорядоченных
доказательств. Для ведения дел с

КПЭ

0

+ (-

TR

) нам нужны дальнейшие предикаты K

н

u) и

Х

н

(a, u, f), которые определяются одновременно индукцией на натуральное число

n, а также предикаты (b, f, a) и M

н

(b, f, a):

T (f): =

Веселье

(Ф) ∧

Дом

(Ф) =

ВЗ

,

К

1

(ля):=

Реклама

(ля),

К

n+1

(ля):=

Реклама

(a) ∧ [∀x∃f (T (f) ∧ ∀ a(

Wo

(ч

н

(a, x, f)))]

один

,

Х

н

(а, у, ф):= т (F) ∧ (∀≺б)(б ф ∈ ф (В) ∧ В u ∈ f (В) ∧ К

н

(f (b))),

(b, f, a): = (∀c ≺ b)(∀x ∈ f (c))

ТИ

(x, a),

М

н

(b, f, a): = ∀c(∀d

b) (ω

1

+

один

↑ д ∧

(d, f, c) →

(d, f, ϕ ˆnac)).

Первая Лемма, касающаяся этого механизма, гласит, что каждое множество

а-это доказуемо элемент

из множества

b, который удовлетворяет свойству K

н

. Он играет ключевую роль в нашем хорошо упорядоченном
доказательстве.

Лемма 8 (Главная Лемма). Для любого натурального числа

n > 0>, существует a

формула

Ф

н

(u, v) из L так, чтобы

КПЭ

0

+ (-

TR

) доказывает

∀х∃!Yf

н

(x, y) ∧ ∀ x ∀ y (F

н

(x, y) → x ∈ y ∧ K

н

(год)).

Доказательство. Мы докажем это утверждение полной индукцией на

n. для n = 1 мы просто

должны установить

Ф

1

(u, v): = (v = u

+

).

Из леммы 4 и обсуждения, следующего за этой леммой, мы знаем, что эта формула
F

1

(u, v) удовлетворяет наши требования. Теперь предположим n > 1 и применим индукцию

гипотеза, чтобы обеспечить a

формула

Ф

Н-1

(u, v) так что

КПЭ

0

+ (-

TR

) докажет

∀х∃!Yf

Н-1

(x, y) ∧ ∀ x ∀ y (F

Н-1

(x, y) → x ∈ y ∧ K

н

(год)).

(1)

Исходя из этого

формула

Ф

Н-1

(u, v) введем вспомогательный

формула

Б

н

(u, v, w),

Б

н

(u, v, w): = F

Н-1

({u, v}, w).

Итерация

Операции в теории допустимых множеств

131

Из (1) сразу же следует, что

КПЭ

0

+ (-

TR

) докажет

∀х∀у∃!zB

н

(x, y, z).

(2)

Следовательно

Б

н

(u, v, w) определяет a

операция, к которой мы хотим применить теорему 6 в a

следующий шаг. Эта теорема подразумевает для любого параметра

u и любой элемент c из

ВЗ

тот,

доказуемо в

КПЭ

0

+ (-

TR

),

Wo

(с) →

∃г[

Веселье

(г) ∧

Дом

g) = {d: d ≺ c} ∧

D) B

н

(u, g d, g(d))].

(3)

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

Е

н

(u, c, g) для того чтобы быть

формула

Веселье

(г) ∧

Дом

g) = {d: d ≺ c} ∧ (∀d ≺ c)B

н

(u, g d, g(d)).

До конца этого раздела мы работаем неофициально внутри

КПЭ

0

+(-

TR

) и перепишите заявление

(3) как

∀с∃г(

Wo

c) → E

н

(u, c, g)).

(4)

отражение, предельная аксиома (Lim) и

сохраняемость в связи с гарантией (4)

существование допустимого множества

буду такой что

∀с(∃г ∈ г)(

Wo

д

c) → E

д

н

(u, c, g)).

(5)

Мы также утверждаем, что для всех элементов

g и g из d

Wo

д

c) ∧ a ≺ b ≺ c ∧ E

д

н

(u, b, g) ∧ E

д

н

(u, c, g) → g (a) = g (a),

(6)

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

Е

н

(u, b, g) и

Е

н

(u, c, g). Следующим шагом в доказательстве нашей леммы является установка

Ф:=

{g ∈ d: ∃c(

Wo

д

c) ∧ E

д

н

(u, c, g)} {{c, ∅:

Wo

д

(с)}.

f является элементом из d

+

; по (6) мы знаем, что это функция, и

Дом

(Ф) =

ВЗ

является

непосредственно от его определения. Утверждение (5) и определение понятия

выход f, в добавлении,

тот

Wo

д

(С) → (∀Д ≺ С)(у ∈ ф (д) ∧ ф д ∈ ф (д) ∧ К

Н-1

(f (d)))

(7)

а это, в свою очередь, подразумевает из-за

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

ф

тот

∀x∃f (T (f) ∧ ∀ c(

Wo

c) → H

Н-1

(c, x, f)).

(8)

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

2

размышление на тему:

Реклама

- к тому же...

формула

Один

н

(u, v, w),

Один

н

(u, v, w): = (u = u) ∧ T (w) ∧ ∀ c(

Wo

c) → H

Н-1

(c, v, w)).

132

Г. Егер и Д. Пробст

Из леммы 7 следует существование a

формула

Один

н

(u, v) так что из (8) мы можем

вывести для любого параметра

а то

∃!йа

н

(год),

(9)

∀y(A

н

(a, y) → a ∈ y ∧

Реклама

(y) ∧ (∀x ∈ y) (∃f ∈ y)A

y

н

(a, x, f)).

(10)

Выбрав

Ф

н

(u, v) быть формулой A

н

(u, v), утверждения (9) и (10) вместе взятые

с определением формулы:

К

н

v) сразу же подразумевают:

∀х∃!Yf

н

(x, y) ∧ ∀ x ∀ y (F

н

(x, y) → x ∈ y ∧ K

н

(год)).

Это завершает шаг индукции, и поэтому также доказательство нашей леммы завершено.

Доказательства следующих трех лемм могут быть легко восстановлены путем (более или
менее нотационных) адаптаций соответствующих доказательств в [5] и [8]. Поэтому мы
опускаем все детали и ограничиваемся предоставлением точных ссылок.

Лемма 9. Следующие три утверждения могут быть доказаны в следующих трех случаях:

BS

0

:

1.

Х

1

(, u, f) ∧ (, f, a) →

(, f, ϕa0).

2.

Х

1

(, u, f) →

Еда

({a: (, f, ϕ10a)}).

3.

Х

1

(b, u, f) →

Еда

({a: M

1

(b, f, a)}.

Доказательство. Все подробности, касающиеся доказательства этих трех утверждений, см. В Лемме 5,
Лемме 6 и Лемме 7 из [5].

Лемма 10. Для любого натурального числа

n > 0>, следующие три утверждения могут быть:

доказано в деле

BS

0

:

1.

К

n+1

(a) ∧ [x∀f ∀b(H

н

(b, x, f) →

Еда

({c: M

н

(b, f, c)}))]

один

→ ∀c[(∀x ∈ a)

ТИ

(x, c) → (∀x ∈ a)

ТИ

(x, ϕ ˆnc0)].

2.

К

n+1

(a) ∧ ∀ c [(∀x ∈ a)

ТИ

(x, c) → (∀x ∈ a)

ТИ

(x, ϕ ˆnc0)]

→

Еда

({c: (∀x ∈ a)

ТИ

(x, ϕ (ˆn+1) 0c)}).

3.

Х

н

(b, u, f) ∧ ∀ a [K

н

(ля) →

Еда

({c: (∀x ∈ a)

ТИ

(x, ϕ ˆn0c)})]

→

Еда

({c: M

н

(b, f, c}).

Доказательство. Все подробности, касающиеся доказательства этих трех утверждений, см. В Лемме 4,
Лемме 5 и Лемме 6 из [8].

Лемма 11. Для любого натурального числа

n > 0>, следующие три утверждения могут быть:

доказано в деле

BS

0

:

Итерация

Операции в теории допустимых множеств

133

1.

Реклама

(a) → [∀x∀f ∀bH

н

(b, x, f) →

Еда

({c: M

н

(b, f, c)})]

один

.

2.

К

n+1

(a) → ∀c[(∀x ∈ a)

ТИ

(x, c) → (∀x ∈ a)

ТИ

(x, ϕ ˆnc0)].

3.

К

n+1

(ля) →

Еда

({c: (∀x ∈ a)

ТИ

(x, ϕ (ˆn+1) 0c)}).

Доказательство. Начните показывать, что первое утверждение подразумевает второе, а второе
-третье. Затем докажите первое утверждение индукцией на

n. Подробнее см. теорему 6 из

[8].

Теорема 12 (нижняя граница). Для любого натурального числа

н, у нас это есть

КПЭ

0

+ (-

TR

)

∀икс

ТИ

(x, ϕ ˆn00).

Доказательство. Зафиксируйте любое натуральное число

n > 0. Споря неофициально в

КПЭ

0

+ (-

TR

), пусть a будет

произвольный набор. С учетом леммы 8 мы знаем, что существует множество

b удовлетворительно

a ∈ b ∧ K

n+1

b).

(1)

Вторая часть леммы 11 дает, кроме того, что

К

n+1

(b) → ∀c[(∀x ∈ b)

ТИ

(x, c) → (∀x ∈ b)

ТИ

(x, ϕ ˆnc0)],

(2)

и, следовательно, если мы зададим c = 0,

К

n+1

(b) → (∀x ∈ b)

ТИ

(x, ϕ ˆn00)].

(3)

Из (1) и (3) Делаем вывод

ТИ

(a, ϕ ˆn00), что именно то, что мы должны были показать.

Порядковое числительное

α называется доказуемым в теории

Т

- сформулировано в

L или аналогичный

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

о натуральных числах

порядка-типа

α так что

Т

Wo

(

Н

,).

Наименьший порядковый номер, который не доказуем в

Т

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

Т

и обозначается через

|

Т

|.

Из теоремы 2, теоремы 12 выше и результатов Егера и Страма [6], которые

скажите нам, что

|

КПМ

0

| ≤ωω00, мы получаем следующую характеристику теории

КПЭ

0

+ (-

TR

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

Следствие 13. Множество теорий

КПЭ

0

+ (-

TR

) и

КПМ

0

имейте такое же доказательство-

теоретическая прочность, а именно:

|

КПЭ

0

+ (-

TR

)| = |

КПМ

0

| = ϕω00.

Конечно, Теорема 2 и теорема 12 также показывают, что любой порядковый номер меньше, чем

ϕω00

доказуемо внутри

КПМ

0

. Прямое доказательство этого результата можно найти в Strahm [11].

Подтверждение. Исследование частично поддержано Швейцарской национальной наукой Foon-

дэйшн.

134

Г. Егер и Д. Пробст

Рекомендации

[1]

Barwise, Jon: 1975. Допустимые множества и структуры. Берлин: Спрингер.

[2]

Егер, Герхард: чтобы появиться. Метапредикативный и явный Mahlo: теоретико-доказательная
перспектива. Логический Коллоквиум 2000 Года.

[3]

Jäger, Gerhard: 1984. Сила допустимости без основания. Журнал
символической логики 49 no. 3: 867-879.

[4]

Jäger, Gerhard: 1986. Теории допустимых множеств: объединяющий подход к
теории доказательств. Napoli: Bibliopolis.

[5]

Егер, Герхард, Райнхард Кале, Антон Сетцер и Томас Страм: 1999.
Корректоретический анализ трансфинитно итерированных теорий неподвижных точек. Журнал символьной
логики 64 no. 1: 53-67.

[6]

Jäger, Gerhard and Thomas Strahm: 2001. Верхние оценки для метапредикативного мало в
явной математике и допустимой теории множеств. Журнал символической логики 66 no. 2:
935-958.

[7]

Pohlers, Wolfram: 1989. Теория Доказательств: Введение. Лекционные заметки по математике,
т. 1407. Берлин: Спрингер.

[8]

Rüede, Christian: 2000. Метапредикативные подсистемы анализа. Кандидатская диссертация. Institut
für Informatik und angewandte Mathematik, Universität Bern.

[9]

Rüede, Christian: 2003. Теоретико-доказательный анализ

1

1

трансфинитный зависимый выбор.

Анналы чистой и прикладной логики 122 no. 1: 195-234.

[10] Schütte, Kurt: 1977. Теория Доказательств. Берлин: Спрингер.

[11] Strahm, Thomas: 2002. Wellordering доказательства для метапредикативного Mahlo. The Journal of

Символическая логика 67 no. 1: 260-278.

Institut für Informatik und angewandte Mathematik
Universität Bern
Neubrückstrasse 10
3012 Bern
Switzerland

E-mail: [email protected]

[email protected]