Некоторые Математические Задачи

Все вышесказанное вполне очевидно; кроме того, приложения имеют ограниченную математику-

ical интерес, потому что STT не поддается гибкому выражению математических
свойств на практике. Вот некоторые утверждения из формы

А ∈ б с примой

facie тип из

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

Обратите внимание, что в следующем мы используем (.,.) для операции сопряжения, которая повторяется

придавать форму

n-кортежи. Мы предполагаем, что поняли математические понятия, связанные с этим, cf. [13]

для примеров 4.2-4.4.

4.1 пусть

P-класс всех частично упорядоченных структур и пусть S-субструктура

отношение. Затем

(P, S) ∈ P.

4.2 пусть Set-категория всех множеств, AbGrp-категория всех Абелевых групп,

Верхняя категория всех топологических пространств и т. д., и пусть кошка будет классом всех
категорий. Затем, как и положено, поставили

CAT CAT, AbGrp CAT CAT, Top ∈ CAT и др.

4.3 Также Кошка

CAT CAT, где Cat = (CAT, FUNCT,◦) - категория всех
категорий, объектами которых являются все категории и морфизмы которых являются функторами
между категориями, и

◦ является частичной операцией композиции функторов.

4.4 если

A CAT CAT и B CAT CAT, а затем B

Один

CAT кошка где

Б

Один

= (FUNCT(A, B), NAT (A, B), ◦),

чьи объекты являются функцией класса

(A, B) всех функторов от A до B и
морфизмы которых являются естественными преобразованиями между функторами и где
◦ - операция композиции таких преобразований.

4.5 пусть BA-класс всех булевых алгебр. Затем

(℘(V),∪,∩,−,, V) ∈ БА

где

V-универсальный класс, а ℘ (V) - класс всех подклассов V.

6

6

Этот пример был предложен мне Godehard Link.

Типичная Двусмысленность

141

5. Типичная неоднозначность в системе теории множеств
с вселенными

Пусть L-язык теории множеств ZF, использующий переменные

x, y, z,... для наборов. Примыкаем к

L константы

U

н

для

n = 0, 1, 2,... для возрастающей последовательности отражательных вселенных;

полученный язык обозначается L

(У

<ω

), где мы используем U

<ω

чтобы указать последовательность

от

U

н

для

n Каждый U

н

предполагается, что это набор, который является отражающим в смысле

та-говоря образцово-теоретически-она образует элементарную субструктуру

(В, ∈)

когда отношение членства ограничено до

U

н

. Как обычно, чтобы выразить это, мы используем

операция

ϕ

один

о формировании релятивизации всех кванторов в Формуле

ϕ из L в
a; мы также пишем Rel (ϕ, a) для результирующей формулы. Вселенные также должны
быть сверхтранзитивными, т. е. транзитивными и замкнутыми при работе силового набора

℘; для
последнего достаточно предположить, что вселенные замкнуты под подмножествами членов.
Система ЗФ, ОТВ. ZFC, причем вселенные, удовлетворяющие этим свойствам, обозначаются
ZF

/У

<ω

, соответственно. ZFC

/У

<ω

. Более официально аксиомы заключаются в следующем.

Аксиомы ЗФ

/У

<ω

I. Все аксиомы ZF в L и для каждой из них

n = 0, 1, 2,...:

II.

U

н

∈ У

n+1

.

III. Транс

(У

н

).

IV.

∀x∀y[y ∈ U

н

∧ x → y → x U U

н

].

V. Для каждой формулы L

ϕ (x

1

,..., икс

к

),

∀икс

1

... ∀икс

к

{икс

1

,..., икс

к

∈ У

н

→ [Rel(ϕ, U

н

)(икс

1

,..., икс

к

) ↔

ϕ (x

1

,..., икс

к

)]}.

Аксиомы ZFC

/У

<ω

получаются путем добавления аксиомы выбора, AC.

Теорема 3. ЗФ

/У

<ω

является консервативным расширением ZF.

Доказательство. Это прямое расширение результата Montague and Vaught [14]
, которое, в свою очередь, изменяет хорошо известный аргумент принципа отражения Леви, см. Также [5]:
Раздел 2. Мы приводим здесь краткий очерк связанных с этим идей. Заметим, что для сохранения
нам нужно только показать, как, учитывая любой конечный набор аксиом ZF

/У

<ω

вовлечение только

символы

U

я

для

i = 0,..., n для некоторых n, чтобы определить множества в ZF, удовлетворяющие заданному

аксиомы для этих вселенных. Работая неофициально в ЗФ, пусть

В

α

будь то

ath набор в the

кумулятивная иерархия, т. е. для каждого

α, V

α

является ли союз из

℘(В

β

) для всех β Для любого

набор

x, ранг x, ρ (x), является единственным α таким, что x ∈ V

α+1

− В

α

. Один сподвижник

с каждой экзистенциальной формулой

(x) (x, y

1

,..., год

м

) из L м-арной функции F

ψ

чья

ценность

Ф

ψ

(год

1

,..., год

м

) для каждого y

1

,..., год

м

является ли набор всех

x наименьшего ранга такой, что

ψ (x, y

1

,..., год

м

) зацепки. Таким образом

(x) (x, y

1

,..., год

м

) → (∃x ∈ F

ψ

(год

1

,..., год

м

)) ψ (x, y

1

,..., год

м

).

142

С. Феферман

То

Ф

ψ

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

b мы имеем в виду наименьшее V

α

такие что

b ⊆ V

α

. Для любого конечного множества

Q из for-

муласы

(x) (x, y

1

,..., год

м

), по Сколем-рангу-корпусу множества b относительно Q, в

символы

Х

Q

(b), мы имеем в виду наименьшее V

α

такие что

b ⊆ V

α

и такое, что для каждого

(x) (x, y

1

,..., год

м

) в Q и каждый y

1

,..., год

м

∈ В

α

, Ф

ψ

(год

1

,..., год

м

) ⊆ В

α

.

Х

Q

(b)

получается как союз

bj для j

0

= b и каждый b

j +1

является ли ранг

корпус из

[b

j

объединение всех

Ф

ψ

(год

1

,..., год

м

) для всех формул (∃x)ψ(x, y

1

,..., год

м

) в Q и

ВСЕ

y

1

,..., год

м

∈ б

j

]. Для простоты предположим, что Формулы L генерируются из

атомарные формулы

x ∈ y и x = Y by, ∧ и ∃. Теперь, учитывая конечный набор аксиом

из ЗФ

/У

<ω

чтобы смоделироваться в ZF, пусть

S-это замыкание под подформулами всех

L формулы в данном множестве и пусть

Q состоит из всех экзистенциально квантифицированных формул
(∃x)ψ в S. Тогда индукция формулы доказывается тем, что для каждого множества b и каждого ϕ в S,

∀ икс

1

... ∀ икс

к

{икс

1

... икс

к

∈ Ч

Q

(b) → [Rel(ϕ, H

Q

b) (x

1

... икс

к

) ↔ ϕ(x

1

... икс

к

)]}.

Так как Также каждый

Х

Q

(b) является супертранзитивным по конструкции, мы можем определить U

я

для

i = 0,..., n взяв U

0

= Ч

Q

(0) и для каждого i

i+1

= Ч

Q

(У

я

∪ {У

я

}).

NB. Если бы...

θ-это любое предложение из L, затем добавляющее θ как аксиому, поддерживающую консервативность по
этой теореме.

Заключение. ZFC

/У

<ω

является консервативным расширением ZFC.

Обратите внимание, что каждая отражательная Вселенная

U

н

удовлетворяет всем аксиомам ZF, принимая замкнутое
ϕ в аксиоме V за любую из этих аксиом. Из сверхтранзитивности следует, что каждая
Вселенная содержит пустое множество 0 и множество

ω конечных ординалов, замкнутых под
неупорядоченными парами, объединениями и степенными множествами; кроме того, они являются абсолютными, т. е. имеют те же
значения во Вселенной, что и во Вселенной всех множеств. Более того, каждая Вселенная

U

н

замыкается под аксиомой разделения и заменой схем аксиом. Последнее
можно представить себе следующим образом: если

f-любая функция в теоретико-множественном смысле этого слова

то есть определяется в L (относительно любых заданных параметров в

U

н

) и если a ∈ U

н

и

f: A → U

н

, затем

{f (x): x ∈ a} U U

н

. Если кто-то хочет отбросить здесь предположение, что

f определяется, позволяя ему быть любой функцией, то ρ (U

н

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

Теперь мы рассмотрим, в какой степени применение типичной неоднозначности в системе

ЗФ

/У

<ω

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

для решения математических задач, описанных в предыдущем разделе 4.

7

Посмотрел неофициально,

7

Что-то подобное было предложено следующим Куртом Геделем в письме к полу Бернейсу от 1 января
1963 года: “я нахожу интересным, что вы говорите...о "новых абстрактных дисциплинах математики" как о чем-то
, лежащем вне теории множеств. Я предполагаю, что вы таким образом намекаете на понятие категории и на то, что она есть.

Типичная Двусмысленность

143

что мы должны иметь дело с тем, чтобы начать с примерами 4.1-4.3 являются
отношения членства формы

A ∈ B, где B-класс, А A-(возможно) многоразрядная
реляционная структура, каждый из доменов и отношений которой является классом. Во всех рассмотренных случаях
,

B задается как {x|ϕ (x)} для некоторой L формулы ϕ; классы, которые являются

составные части:

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

А и Б-к вселенным. Под типичной отражательной Вселенной U мы подразумеваем любую U

н

; затем путем

следующая Вселенная

U

+

мы имеем ввиду

U

n+1

. Первый шаг в интерпретации проблемы

утверждения о членстве относительно любой такой вселенной

U состоит в том, чтобы идентифицировать классы с помощью

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

U. вторым шагом является идентификация наборов с членами группы

У. Обратите внимание, что так как классы составляют структуру

A являются подмножествами U, у нас есть

A ∈ U

+

. Теперь, чтобы иметь смысл из

A ∈ B, третий шаг состоит в том, чтобы повторно идентифицировать B с

класс всех наборов в

U

+

это удовлетворяет определению B; назовем это

Б

+

. Точнее, если

B задается формально как {x|ϕ (x)}, его первое отождествление с {x ∈ U |ϕ

U

(x)} который

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

{x ∈ U |ϕ (x)}; тогда повторная интерпретация B

+

от

B просто определяется как

быть

{x ∈ U

+

|ϕ (x)}. Это приводит к Конвенции о снятии двусмысленностей:

A ∈ B означает A ∈ B

+

.

(Dis 3)

Чтобы взять самый простой пример, 4.1,

P определяется как класс структур (x, y)

где

y ⊆ x

2

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

x, и S определяется как отношение субструктуры

(x, y) ⊆ (z, w) на P, которое выполняется только в том случае, если x ⊆ z и y = w ∩ x

2

. С

переменные

x, y, z, w взяты в диапазоне по множествам в любой типичной отражательной Вселенной U,

у нас это есть

P и S-подмножества U. В соответствии с принципом двусмысленности

(Dis 3),

(P, S) ∈ P означает, что (P, S) ∈ P

+

, где

П

+

состоит из всех этих наборов

(X, Y) с X, Y в U

+

такие что

Y ⊆ X

2

и

Y является частичным упорядочением X. Это

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

(P, S) ∈ P

+

так что это имеет смысл

по принципу двусмысленности утверждать, что

(P, S) ∈ P. Другими словами: класс
всех частично упорядоченных структур (в типичной Вселенной) вместе с отношением субструктуры
(в этой Вселенной) образует частично упорядоченную структуру (в следующей Вселенной).

Есть еще что сказать о приведенном выше принципе двусмысленности, снова проиллюстрированном

по ссылке на пункт 4.1. По аксиоме отражения V из ZF

/У

<ω

,

П и Р

+

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

(x, y) которые формируют структуры частичного упорядочения. Кроме того, рассмотрим любое свойство
(x, y), сформулированное в L, которое оказывается истинным для всех таких (x, y). Пусть C будет

определяется как класс всех

(x, y) такие, что

(x, y) держит. Это определение принимается
неоднозначным, т. е. его можно рассматривать как относящееся к классу всех множеств или релятивизированное
к любой вселенной. Наше предположение заключается в том, что

P ⊆ C было доказано в ZF, т. е. E., Когда мы

относитесь к классу всех множеств. Из этого следует, что

П

+

⊆ С

+

когда

P интерпретируется как

самостоятельная применимость категорий. Но мне кажется, что все это содержится в теории множеств с
Конечно повторяемым понятием класса, где рефлексивность автоматически приводит к "типичной двусмысленности"
утверждений.(Источник для немецкого оригинала этого письма находится в архиве Бернайса в ETH в
Цюрихе; полное письмо можно найти, наряду со многим другим между Геделем и Бернайсом, в коллекции
переписки в [9].)

144

С. Феферман

класс всех частично упорядоченных структур в любой типичной отражательной Вселенной

U. Из

из принципа двусмысленности следует, что

(P, S) ∈ C. другими словами, (P, S) разделяет
все свойства, которые проверяются для всех частично упорядоченных структур; это пример
правила передачи в этой структуре. В более общем плане, у нас есть:

Теорема 4 (правило переноса). Если бы...

A ∈ B и B ⊆ C доказуемы в ZF, где B, C являются

затем конспекты классов

A ∈ C доказуемо и там.

Доказательство. Ибо...

B при формально как есть {X|ϕ(х)} и c {х|ψ(х)}, что B ⊆ C-это читается как
∀ Х[ϕ(х) → ψ(х)], и что это означает для B ⊆ C, чтобы быть доказуемо в ZF является то, что
∀ Х[ϕ(х) → ψ(х)] доказуемо в ZF. Тогда по аксиоме отражения V, заданной для любой
вселенной

U, (∀ x U U

+

)[Rel(ϕ, U

+

) (x) → Rel (ψ, U

+

) (x)], т. е.

+

⊆ С

+

. От

доказуемость

A ∈ B, что означает, что A ∈ B

+

из (Дис 3) следует, что

С

+

,

т.е.,

A ∈ C, опять же по Конвенции о запрещении двусмысленностей.

Чтобы взглянуть на вещи более обобщенно, рассмотрим структуру типов над множествами, где множества
считаются на уровне типа 0, классы множеств на уровне типа 1, классы классов
множеств на уровне типа 2 и так далее. Мы считаем, что уровень типа структуры A
совпадает с максимальным уровнем типа доменов, отношений, операций и индивидов
, составляющих эту структуру. При этом в примерах 4.1-4.3 проблемных
заявлений о членстве формы

A ∈ B уровень типа как A, так и B равен 1. Но в данном примере...

4.5, структура

A = (℘(V),∪,∩,−,, V) относится к уровню 2 типа, поскольку класс V

все наборы имеют тип level 1 и

℘ (V), класс всех подклассов V, относится к типу уровня 2.

С другой стороны уровень типа

B-в этом случае класс BA всех множеств, являющихся
булевыми алгебрами, по-прежнему равен 1. Но в отличие от случая теории типов, где для устранения неоднозначности
A ∈ B нам пришлось перейти к A ∈ B

++

когда уровень типа из

A-это единица выше, чем у B,
мы все еще можем рассеять неопределенность (Dis 3). Ибо, когда мы интерпретируем наборы как ранжирование по
любой типичной Вселенной

U, A интерпретируется как структура (℘(U),∪, ∩,−,, U)

и с тех пор...

U и ℘ (U) принадлежат U

+

, структура

А в этом случае также принадлежит U

+

,

и фактически является членом подмножества

БА

+

от

U

+

состоящ из всех структур внутри

U

+

которые удовлетворяют условиям, чтобы быть булевой алгеброй. Таким образом, имеет смысл с помощью (Dis 3)
сказать, что

A ∈ B имеет место в этом случае. Дано преимущество перед обычной теорией типов

для нас теоретико-множественной основой является то, что уровень типа

U

+

над

U измеряется
в терминах кумулятивной иерархии бесконечно. Точное объяснение того, как (Дис 3)
может применяться в более общем плане, потребовало бы введения расширения L

+

из L
переменными классов, которые предполагаются (в отличие от теорий Геделя–Бернайса или морса–Келли
), чтобы удовлетворить всем аксиомамzf. Затем для любого приложения объекты ZF
интерпретируются как диапазон по Юниверсу

U и классы интерпретируются как ранжирование более

следующая Вселенная

U

+

. Для целей здесь достаточно посмотреть, как (Dis 3) работает
в нескольких конкретных случаях, таких как 4.5, только что обсужденный, или 4.4, который будет рассматриваться в следующем
разделе.

Типичная Двусмысленность

145

6. Теория категорий в ZF / U

<ω

Предполагается, что читатель знаком с основными понятиями теории категорий.
Стандартная ссылка - это [13]. Мы можем принять категории за структуры вида

A =
(O, M, C), где O-класс объектов A, M-его класс морфизмов, а C
-состав морфизмов в

A; C-частичная операция на M

2

Для

M рассматривается как

трехпозиционное отношение ВКЛ.

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

(M, C).
В качестве альтернативы, и более интуитивно, мы можем принять категории за структуры

форма

A = (O, M, C, D

0

, Д

1

, I) где C, как и прежде, D

0

и

Д

1

являются отображениями из
M в O, дающими домен и кодомен соответственно, а I-отображение из O в
M. Как обычно мы пишем f: x → y или x →

ф

y в A, когда f ∈ M, D

0

f) = x и

Д

1

(f) = y; id

икс

для

I (x); и fg = h, когда (f, g, h) ∈ C. Когда это необходимо

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

A by

‘

A ' как A = (O

Один

, М

Один

, С

Один

, Д

0

Один

, Д

1

Один

, Я

Один

). A-это большая категория, Если O

Один

и

М

Один

есть оба класса.

A считается локально малым, если для любых объектов x, y класса A

Х

Один

(x, y) = {f / f ∈ M

Один

∧ f: x → y} - это множество; оно мало, если само A является множеством.

Ниже приведены стандартные примеры локально малых категорий.

Категория всех наборов. Set-это категория, объектами которой являются только наборы и

чьи морфизмы все триплы

f = (u, x, y), где u-функция (в обычном наборе-

теоретический смысл) чья область является

x и диапазон содержится в y. тогда D

0

(u, x, y) =

x и D

1

(у, х, г) = г. Состав ф г определяется для F = (у, х, г) и г =
(В, З, Ж) в случае Y = Z, в этом случае ф г = (у; V, х, ж), где U; V является
реляционной состав

u и v. наконец, I (x) принимается равным (u, x, x) для каждого x,

где

u-это функция идентификации от x до x.

Категория Абелевых групп. AbGrp-это категория, объектами которой являются наборы

которые являются Абелевыми группами и чьи морфизмы являются групповыми гомоморфизмами с
заданной областью и кодомой. Это затем прописано, как в 6.1.

Категория всех топологических пространств. Top-это категория, объектами которой являются

члены Совета

U, которые являются топологическими пространствами, рассматриваются аналогично.

Категория всех категорий. Cat-это категория, объектами которой являются наборы

(o, m, c, d

0

, д

1

, i) которые удовлетворяют условиям, чтобы быть категорией, и чьи морфизмы

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

Кошка сама имеет такую форму

(КОШКА

, Функц...) где CAT = O

Кошка

и функц.

= М

Кошка

.

Теперь с помощью (Dis 3) мы можем понять утверждения в 4.2 и 4.3, которые устанавливают

∈ КОШКА,

AbGrp

CAT CAT, Top ∈ Cat и даже Cat ∈ CAT, т. е. (CAT, FUNCT...) ∈ КОШКА.
Эти утверждения означают, что относительно любого типичного отражательного универсума
U, каждый из множества, AbGrp, Top и Cat является элементом CAT

+

, класс всех множеств

A = (O, M,...) в следующей Вселенной U

+

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

146

С. Феферман

члены Cat, т. е. класс всех малых категорий, также относятся к набору больших категорий
, AbGrp, Top, Cat и т. д.

Категория всех функторов между двумя заданными категориями. Когда мы обратимся к созданию

смысл высказывания 4.4 что

Б

Один

Кот ∈ где А и Б большие категории мы

встретьте проблему что уровень типа prima-facie

Б

Один

это выше, чем у обоих

Один

и

B. В терминологии Mac Lane, B

Один

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

℘ (В). Но есть математические аспекты примера 4.4, которые являются

стоит посмотреть поближе. Рассмотрим обычное теоретико-множественное определение

Б

Один

: его объекты являются

Функц.

(A, B), т. е. E., класс всех функторов F: A → B, и его морфизмы естественны

преобразования

η: F → G между такими функторами. Мы можем взять функторы, чтобы быть классами

которые являются функциями в обычном теоретико-множественном смысле, так что для каждого

x ∈ O

Один

, F (x) ∈ O

Б

;

как обычно, чтобы быть функтором,

F требуется для сохранения состава и идентичности морфизмов,

т. е., для

f, g ∈ M

Один

и

x ∈ O

Один

, F (fg) = F (f)F (g) в B и F (i

икс

) = я

F (x)

. Автор:

естественная трансформация

η: F → G между двумя такими функторами F: A → B и

G: A → B означает отображение из O

Один

Для

М

Б

так что следующая диаграмма является

коммутативный для любого

x, y ∈ O

Один

, в любое время

икс →

u

y в A:

F (x)

F (u)

- - - - → F (y)

η(x)









η(y)

G(x)

G (u)

- - - - → G (y)

Состав природных превращений определяется очевидным образом. Хотя, как
было отмечено выше,

Б

Один

больше не является большой категорией, когда

А и В являются большими, мы все еще
можем использовать конвенцию о неразгадывании (Dis 3), как и в конце предыдущего
раздела, чтобы понять утверждение о том, что он является членом CAT, поскольку, согласно
ему, это просто означает, что относительно любой типичной Вселенной

U, B

Один

∈ КОШКА

+

.

8

Есть

никаких проблем с этим, так как теперь с

О

Один

, М

Один

, О

Б

, и М

Б

рассматривается как подмножество

данной вселенной

U, множества O

С

и

М

С

принадлежат по вышеуказанному определению к

U

+

для

C = B

Один

. Опять же, теорема переноса гарантирует нам, что любое свойство всех малых

категории также применяется к категории superlarge

Б

Один

.