30. Борелевские множества

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

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

Простое множество в канторовском пространстве — это синтаксическое выражение вида

где окрестности. Интуитивно говоря, множество в канторовском пространстве простое, если оно налагает условия лишь на конечное число

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

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

1 Если А — простое множество, то борелевское множество.

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

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

Когда ординал равен 0 и узлу сопоставлено или мы получаем два борелевских множества, называемых пустым множеством и всем пространством и обозначаемых соответственно через

Дополнение борелевского множества А получается заменой любого простого множества на его дополнение и взаимной заменой Для объединения двух борелевских множеств мы будем использовать обычную неформальную запись Аналогично для пересечения. Разность двух борелевских множеств определяется соотношением

а симметрическая разность — соотношением

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

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

Аксиома — это секвенция, состоящая целиком из простых множеств, которые вместе покрывают все пространство. Ясно, что если зафиксирована запись простых множеств, то множество, аксиом разрешимо.

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

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

Мы полагаем по определению, что борелевское множество А содержится в борелевском множестве В, и пишем

если секвенция

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

Равенство определяется соотношением

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

(см. скан)

Именно сечение является основным среди этих выводимых правил. Оно играет ту же роль для нашей системы, что основная теорема Генцена [1] для классической логики предикатов первого порядка. Доказательства следуют тому же образцу.

Закон исключенного третьего выражает рефлексивность отношения включения, т. е. тот факт, что для любого борелевского множества А.

Транзитивность отношения включения — это простое следствие правила сечения. Действительно, отношения и означают, что обе секвенций

доказуемы, а тогда доказуема и

т. е. в точности что и требовалось доказать.

Доказательство закона исключенного третьего. Трансфинитной индукцией по бэровскому классу . Базис. Если простое множество, то — аксиома. Шаг индукции. Допустим, что и уже доказано для всех По -введению мы получаем тогда для всех -введение дает

затем что и требовалось. Аналогично, если

Доказательство утончения. Рассмотрим данный вывод секвенции и добавим формулу А к каждой секвенции, входящей в этот вывод. При этом преобразовании каждое применение правила переходит в применение того же правила, так что достаточно доказать возможность утончения аксиом. Это делается трансфинитной индукцией по бэровскому классу А. Если А — пустое множество, утончение очевидным образом допустимо. Допустим, что и что утончение уже доказано для всех Это значит, что для любого мы построили вывод По -введению мы получаем . Аналогично если

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

Если и последнее применение правила в данном выводе имеет вид

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

Если главная формула последнего применения правила в доказательстве , то это применение — либо

В первом случае мы непосредственно получаем для всех а во втором индукционное предположение позволяет нам вывести то же заключение. Это завершает доказательство -удаления.

Доказательство сечения. Доказательство получается индукцией по бэровскому классу формулы А. Базис. Если А—простое множество, мы используем непосредственную трансфинитную индукцию по длинам выводов посылок. В этом месте не возникает трудностей, так как А не может быть главной формулой последнего применения правила в выводе посылки. Кроме того, сечение тривиально имеет место, когда посылки являются аксиомами.

Индукционный переход. Так как сечение симметрично относительно своих посылок, достаточно рассмотреть случай, когда и утверждение доказано для всех Мы снова должны использовать трансфинитную индукцию, на этот раз по длинам выводов посылок. Если А не является главной формулой последнего применения правила в выводе или не является таковой в выводе 0, С А, то рассуждение протекает по следующему образцу. Пусть и последнее применение правила в выводе есть

Предположение индукции позволяет нам выполнить сечение

для всех а затем получается -введением

Если есть главная формула последнего применения правила в выводе секвенции , то это применение имеет вид

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

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

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

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

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