«СИБИРСКОЕ ОТДЕЛЕНИЕ ВЛАДИКАВКАЗСКИЙ НАУЧНЫЙ ЦЕНТР ИНСТИТУТ МАТЕМАТИКИ ИНСТИТУТ ПРИКЛАДНОЙ ИМ. С. Л. СОБОЛЕВА МАТЕМАТИКИ И ИНФОРМАТИКИ А. Г. КУСРАЕВ C. C. КУТАТЕЛАДЗЕ ВВЕДЕНИЕ В БУЛЕВОЗНАЧНЫЙ АНАЛИЗ МОСКВА НАУКА 2005 УДК ...»

РОССИЙСКАЯ АКАДЕМИЯ НАУК

СИБИРСКОЕ ОТДЕЛЕНИЕ ВЛАДИКАВКАЗСКИЙ НАУЧНЫЙ ЦЕНТР

ИНСТИТУТ МАТЕМАТИКИ ИНСТИТУТ ПРИКЛАДНОЙ

ИМ. С. Л. СОБОЛЕВА МАТЕМАТИКИ И ИНФОРМАТИКИ

А. Г. КУСРАЕВ

C. C. КУТАТЕЛАДЗЕ

ВВЕДЕНИЕ

В БУЛЕВОЗНАЧНЫЙ

АНАЛИЗ

МОСКВА «НАУКА»

2005 УДК 517.98 ББК 22.162 К 94 Ответственный редактор академик Ю. Г. РЕШЕТНЯК Рецензенты: доктор физико-математических наук Г. Г. МАГАРИЛ-ИЛЬЯЕВ, доктор физико-математических наук С. А. МАЛЮГИН Кусраев А. Г., Кутателадзе С. С. Введение в булевозначный анализ.—М.: Наука, 2005.—526 с.

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

банаховых пространств и алгебр. Вскрывается имманентная связь последних с решеточно нормированными векторными пространствами, введенными Л. В. Канторовичем.

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

TTI 2005–1– ISBN 5-02-033710- c Российская академия наук, c Издательство «Наука»

(художественное оформление), c Институт прикладной математики и информатики ВНЦ РАН, c Институт математики СО РАН, c А. Г. Кусраев, c С. С. Кутателадзе, Введение Как следует из названия, настоящая книга посвящена булевозначному анализу. Так называют аппарат исследования произвольных математических объектов, основанный на сравнительном изучении их вида в двух моделях теории множеств, конструкции которых основаны на принципиально различных булевых алгебрах. В качестве этих моделей фигурируют классический канторов рай в форме универсума фон Неймана и специально построенный булевозначный универсум, в котором теоретико-множественные понятия и утверждения получают весьма нетрадиционные толкования. Одновременное использование двух моделей для изучения одного объекта — фамильная черта так называемых нестандартных методов современной математики. В этой связи булевозначный анализ принято относить к разновидностям нестандартного анализа.

Своим возникновением булевозначный анализ обязан выдающемуся достижению П. Дж. Коэна, установившему в начале 1960-х годов непротиворечивость добавления отрицания гипотезы континуума CH к аксиомам теории множеств Цермело — Френкеля ZFC. Вместе с более ранним результатом К. Гделя о сове местимости CH с ZFC, установленный П. Дж. Коэном факт означает независимость CH от обычных аксиом ZFC. Шаг, совершенный П. Дж. Коэном, связан с преодолением им принципиальной трудности, отмеченной Дж. Шепердсоном и отсутствующей в случае, разобранном К. Гделем. Доказательство непротивое речивости (ZFC) + (¬ CH) невозможно с помощью стандартных моделей. Точнее говоря, выбрав какую-либо реализацию универсума фон Неймана, мы не можем указать в ней подкласс, служащий моделью (ZFC) + (¬ CH), если применять уже имеющуюся у нас интерпретацию предиката принадлежности. П. Дж. Коэну удалось предложить новый мощный способ построения невнутренних — нестандартных — моделей ZFC, названный им методом форсинга (см. [204]). Термин «форсинг» часто переводят как «вынуждение». Возможно, точнее говорить в этом контексте о методе принуждения. Использованные П. Дж. Коэном приемы — применение аксиомы существования стандартной транзитивной модели ZFC и насильственное превращение последней в принципиально нестандартную модель методом принуждения — вступают в противоречие с обычной математической интуицией, исходящей, по словам самого П. Дж. Коэна, «из нашей веры в естественную почти физическую модель математического мира» [84].

Трудности в восприятии результатов П. Дж. Коэна задолго до их появления прекрасно выразил Н. Н. Лузин в знаменитом докладе «Современное состояние теории функций действительного переменного», сделанном им на Всероссийском съезде математиков в 1927 г.: «Первое, что приходит на ум, это то, что установление мощности continuum’а есть дело свободной аксиомы, вроде аксиомы о параллелях для геометрии. Но в то же время, как при инвариантности всех прочих аксиом геометрии Евклида и при варьировании аксиомы о параллельных меняется самый смысл произнесенных или написанных слов:,,точка“,,,прямая“, etc. — смысл каких слов должен меняться, если мы делаем мощность continuum’а подвижной на алефической шкале, все время доказывая непротиворечивость этого движения? Мощность continuum’а, если только мыслить его как множество точек, есть единая некая реальность и она должна находиться на алефической шкале там, где она на ней есть; нужды нет, если определение этого места затруднительно или, как прибавил бы J. Hadamard,,,даже невозможно для нас, людей“» [136].

Весьма характерный взгляд сформулировал П. С. Новиков: «...возможно (я сам придерживаюсь этого мнения), что результат Коэна имеет чисто отрицательное значение и обнаруживает конец развития,,наивной“ теории множеств в духе Кантора» [152].

Стремление облегчить указанные трудности в восприятии результатов и методов П. Дж. Коэна привело Д. Скотта и Р. Соловея к построению булевозначных моделей ZFC, обладающих привлекательной наглядностью с точки зрения классических математиков и в то же время приспособленных для получения теорем о независимости. Аналогичные модели были построены в тот же период П. Вопенкой.

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

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

Представим себе, что мы лишены возможности одновременного физического поэлементного сравнения моделей, однако можем обмениваться информацией с обладателем другой модели, например, по телефону. В процессе общения легко установить, что собеседник с помощью своей модели изучает объекты, которые он именует знакомыми нам словами, говоря о множествах, их сравнении и принадлежности. Поскольку нас интересует ZFC, мы спрашиваем у него — истинны ли аксиомы ZFC? Поработав в своей модели, он сообщает «да, истинны». Убедившись также, что он использует те же правила вывода, что приняты нами, мы должны признать, что имеющаяся у него модель — это модель интересующей нас теории. Полезно подчеркнуть, что сделав такой вывод, мы ничего не узнали ни об объектах, составляющих его модель, ни о процедурах, с помощью которых он отличает истинные утверждения от ложных1.

Итак, новая концепция моделирования связана как с отказом от отождествления предметных областей, так и с допуском новых процедур верификации утверждений.

При построении булевозначной модели мы начинаем с выбора некоторой полE, Eir и Em” из знаменитого Personal Pronoun Pronouncement представляются существенно более лучшим набором местоимений для данного абзаца (см. [380]).

ной булевой алгебры, краеугольного камня булевозначного универсума и области прибытия оценки истинности, сопоставляющей формуле ZFC некоторый элемент алгебры B. Точнее говоря, задав B, мы строим универсум (B), призванный служить универсумом рассмотрения теории ZFC. Каждой формуле, переменные которой теперь пробегают (B), сопоставляется элемент [[]], лежащий в исходной булевой алгебре B. Величину [[]] называют оценкой истинности формулы.

Оценки истинности позволяют анализировать формулы ZFC. При этом оказывается, что теоремы ZFC получают наибольшую возможную оценку 1B, и мы объявляем их верными внутри (B).

Детальное изложение упомянутых конструкций занимает главы 1–6, составляющие первую часть этой книги. Мы начинаем с изложения необходимых нам сведений из теории множеств и булевых алгебр. Этому посвящены главы 1 и 2.

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

В главах 4–6 представлен инструментарий булевозначного анализа. Приводимые конструкции и, прежде всего, процедуры спуска и подъема, осуществляющие функторные связи между универсумом фон Неймана и булевозначным универсумом (B), составляют техническую основу применений булевозначных моделей к задачам анализа.

Главы 7–12, составляющие вторую часть книги, посвящены демонстрации замечательных возможностей, которые булевозначный анализ предлагает для исследования разнообразных математических объектов. Здесь широко представлены способы превращений функциональных пространств в числовые множества, операторов — в функционалы, вектор-функций — в обычные отображения и т. п.

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

Мы начинаем с детального изучения булевозначных реализаций общих алгебраических систем, которому посвящена глава 7. Теория алгебраических систем, заложенная в трудах А. И. Мальцева и А. Тарского, относится к числу важнейших общематематических достижений. В этой связи ясно, что сведения о булевозначном изображении таких систем необходимы для приложений к любому содержательному разделу математики. Некоторые из таких приложений к анализу изображений групп, колец и полей в булевозначном универсуме собраны в главе 8.

Глава 9 посвящена анализу кардинальных чисел в булевозначных моделях.

Особое место уделено так называемому эффекту «смещения кардиналов», обнаружение которого и позволило П. Дж. Коэну доказать непротиворечивость (ZFC) + (¬ CH).

Исключительно универсальное значение имеют конструкции, представленные в главе 10. Математика, понимаемая как наука о бесконечном, немыслима без вещественных чисел. Булевозначный анализ вскрыл имманентную связь поля вещественных чисел и расширенных пространств Канторовича. Обнаружилось, что каждое из таких пространств служит равноправной моделью поля вещественных чисел. Напомним, что условно полные векторные решетки, называемые также K-пространствами или пространствами Канторовича, были введены в 1930-е годы Л. В. Канторовичем как полезная абстракция поля вещественных чисел.

Для новых объектов Л. В. Канторович выдвинул эвристический принцип, состоящий в том, что элементы K-пространства аналогичны вещественным числам, а утверждениям о функционалах отвечают теоремы об операторах со значениями в K-пространствах. Время позволило вложить точный смысл в принцип Канторовича. Соответствующий аппарат и, в первую очередь, основополагающая теорема Е. И. Гордона составляют ядро главы 10.

Глава 11 посвящена проблеме булевозначной реализации центрального объекта классического функционального анализа — банахова пространства. Оказывается, что изображениями традиционных нормированных пространств служат так называемые решеточно нормированные векторные пространства, также открытые при зарождении теории K-пространств. Здесь речь идет о нормировании элементов векторного пространства не с помощью чисел, как это традиционно делается, а с привлечением в качестве эталонов положительных векторов из какого-нибудь пространства Канторовича.

Глава 12 посвящена теории операторных алгебр. Булевозначный анализ таких алгебр — направление исследований, инициированное пионерскими работами Г. Такеути, — интенсивно развивается в последние десятилетия. Изложение строится на основе булевозначной реализации решеточно нормированных пространств. На этом пути возникает единый метод исследования таких аналитических объектов, как инволютивные банаховы алгебры, банаховы модули, алгебры Йордана — Банаха, алгебры неограниченных операторов и т. п.

Настоящая книга — плод наших размышлений и исследований в области булевозначного анализа, появившийся в результате длительной эволюции из учебного пособия «Записки по булевозначному анализу», написанного нами для студентов Новосибирского государственного университета в далеком 1984 году. Непосредственным предшественником данного издания послужила книга «Булевозначный анализ», выпущенная двумя изданиями Институтом математики им. С. Л. Соболева Сибирского отделения РAH в 1999 и 2003 годах. Издание 1999 года было одновременно воспроизведено Kluwer Academic Publishers на английском языке.

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

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

Выполняя приятный долг, мы выражаем благодарность за помощь в подготовке книги своим коллегам по Институту математики им. С. Л. Соболева Сибирского отделения РАН и Институту прикладной математики и информатики Владикавказского научного центра РАН и Правительства Республики Северная Осетия-Алания.

Часть I

ОСНОВЫ

В кредо наивной теории множеств входит мечта о «канторовом рае» — об универсуме — мире множеств, содержащем все мыслимые в обособленном виде образования, каждое из которых представляет собой «соединение в некое целое M определенных хорошо различимых предметов m нашего созерцания или нашего мышления» [65, с. 173].

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

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

В настоящее время наиболее разработанной и общеупотребительной является теория множеств Цермело — Френкеля. В ее рамках мы и ведем изложение.

С не меньшей тщательностью мы анализируем статус классов множеств в рамках формальной системы, восходящей к Дж. фон Нейману, К. Гделю и П. Бернайсу и являющейся консервативным расширением теории Цермело — Френкеля.

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

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

1.1.1. Аксиоматический метод — один из наиболее сильных и популярных инструментов современной математики. Он включает два аспекта — синтаксический и семантический. Синтаксический аспект аксиоматического метода состоит в изучении логической структуры формальных символических текстов безотносительно к их смыслу; основное понятие синтаксиса — выводимость в формальной системе, соответствующий раздел математической логики принято называть теорией доказательств. Семантический аспект аксиоматического метода состоит в изучении смысла формальных текстов теоретико-множественными средствами; основным понятием семантики является истинность в модели, а соответствующий раздел математической логики называют теорией моделей.

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

теории, исследующей математику или какие-то ее разделы как некоторый самостоятельный объект. Учитывая, что в этой книге нас интересуют не основания математики, а прикладные теоретико-модельные аспекты формальной теории множеств, мы не предъявляем к метаязыку чрезмерно жесткие требования. В частности, в дальнейшем мы широко используем общепринятые выразительные средства и уровень строгости обычной — содержательной — математики.

1.1.2. В качестве алфавита языка рассматривают фиксированный набор A символов произвольной природы — канторово множество. Конечные последовательности символов (= элементов A) называют выражениями, иногда — текстами и записывают в виде a1 a2... an, где ak A при k := 1,..., n. Один и тот же символ может появляться в тексте несколько раз, и всякий раз говорят о вхождении этого символа в рассматриваемое выражение. Если каким-либо способом (предписаниями, алгоритмами и т. п.) выделено некоторое множество «правильно составленных» выражений (A), то говорят, что задан язык с алфавитом A.

При этом выделенные выражения называют формулами.

Далее, фиксируют некоторую конечную или бесконечную совокупность формул, именуемых аксиомами, а также явно описывают допускаемые правила вывода — отношения в (A) и степенях (A). Таким образом, формальная система полностью определена, если заданы ее язык, аксиомы и правила вывода.

Если R (A)n — правило вывода, а 1,..., n — формулы, то включение (1,..., n ) R символизирует тот факт, что n выводится из 1,..., n1.

Формулы, получаемые из аксиом за конечное число шагов с помощью имеющихся правил вывода, называют теоремами. Для формальной системы F и формулы запись F символизирует выражение « есть теорема системы F ».

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

1.1.3. В качестве простого примера формальной системы рассмотрим исчисление высказываний или пропозициональное исчисление PL. Алфавит языка исчисления высказываний содержит бесконечную последовательность символов 0, называемых пропозициональными переменными, логические связки {¬,,, } и скобки (, ). Множество формул языка PL — наименьшее множество текстов в алфавите PL, содержащее 0 и удовлетворяющее условию: если,, то ¬, Рассмотрим две разные аксиоматические системы CL и IL для PL, называемые соответственно классической логикой и интуиционистской логикой.

Аксиоматика системы CL содержит следующие двенадцать схем (, и — произвольные формулы языка PL):

Система CL имеет единственное правило вывода, называемое правилом отделения или, чаще, modus ponens:

(MP) если и — теоремы теории CL, то также теорема CL.

1.1.4. Система IL получается из CL путем удаления из нее схемы аксиом 1.1.3 (12). Таким образом, в IL приняты схемы аксиом 1.1.2 (1–11) и только они, а также правило отделения (MP). Как видно из определения, все IL-теоремы являются теоремами CL. Обратное, разумеется, неверно: CL-теоремы ¬(¬) и (¬)¬(¬) не являются теоремами IL. В то же время ¬(¬) и ¬¬(¬) являются IL-теоремами. Отметим также, что в IL ни одна из логических связок,,, не может быть выражена через другие.

1.1.5. Далее нас будет интересовать специальный тип формального языка — язык первого порядка исчисления предикатов (с равенством). Сигнатурой называют тройку (F, P, a), где F и P — некоторые непересекающиеся множества, называемые множеством символов операций и множеством символов предикатов соответственно, а a — отображение F P в множество целых неотрицательных чисел, называемое отображением арности или местности. Говорят, что u F P есть n-арный или n-местный символ, если a(u) = n. Отметим, что 0-местный функциональный символ называют также символом константы или просто, константой. Алфавит языка первого порядка сигнатуры состоит из следующих символов:

(1) множество символов сигнатуры, т. е. множество F P ;

(2) множество переменных: строчные или прописные латинские буквы, возможно с индексами;

(3) логические связки: — конъюнкция, — дизъюнкция, — импликация, ¬ — отрицание;

(4) кванторы: — квантор общности и — квантор существования;

(5) символ равенства =;

(6) вспомогательные символы: ( — открывающая скобка, ) — закрывающая скобка,, — запятая.

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

1.1.6. Термы сигнатуры составляют наименьшее множество выражений языка (той же сигнатуры), удовлетворяющее условиям:

(1) всякая переменная есть терм;

(2) всякий нульместный символ операции есть терм;

терм.

Если в сигнатуре нет функциональных символов (как, например, в случае исчисления предикатов), то термами являются только переменные и символы констант.

1.1.7. Атомные или атомарные формулы сигнатуры — это выражения вида где t1, t2, y1,..., yn — термы сигнатуры, буква p обозначает n-местный предикатный символ, а q — нульместный предикатный символ.

Формулы сигнатуры составляют наименьшее множество выражений, удовлетворяющее условиям:

(1) атомарные формулы сигнатуры являются формулами сигнатуры ;

также формулы сигнатуры ;

(3) если — формула сигнатуры, а x — переменная, то ( x), ( x) также формулы сигнатуры.

1.1.8. Множество FV() свободных переменных формулы определяют следующим образом:

(1) если — атомарная формула, то FV() совпадает с множеством всех переменных, содержащихся в ;

Переменные, не являющиеся свободными в формуле, называют связанными в. При желании подчеркнуть, что в формуле свободными являются переменные x1,..., xn (и, возможно, не только они) пишут = (x1,..., xn ) или просто (x1,..., xn ).

Терм t называют свободным для переменной x в формуле, если никакое свободное вхождение x в не принадлежит области действия никакого квантора Q y, где y — переменная, входящая в t. (В выражении (Q x) формулу называют областью действия квантора Q.) Формулу без свободных переменных называют замкнутой формулой или высказыванием. Говоря об истинности или ложности формулы, имеют в виду универсальное замыкание формулы, которое получается навешиванием квантора общности на каждую свободную переменную формулы.

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

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

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

1.1.10. Теория первого порядка или элементарная теория сигнатуры возникает, если в языке первого порядка сигнатуры выделено некоторое множество аксиом и правил вывода. При этом аксиомы делятся на две группы — логические аксиомы и специальные или нелогические аксиомы.

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

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

(1) пропозициональные аксиомы — все формулы сигнатуры, получающиеся из схем 1.1.3 (1–12);

(2) кванторные аксиомы — для любой формулы (x) и терма t аксиомами будут формулы ( x) (t) и (t) ( x);

(3) аксиомы равенства — для произвольного терма t формула t = t является аксиомой; для произвольных термов t1 и t2 и формулы (x) аксиомой будет формула (t1 = t2 ) (t1 ) (t2 ).

Здесь необходимо пояснить, что (t) (иногда пишут (t/x)) означает результат замены всевозможных свободных вхождений переменной x в формуле (x) термом t. При этом предполагается, что t является свободной для x переменной в формуле. В рассматриваемой ситуации это означает, что либо t есть константа, либо t — переменная, которая не становится связанной в после подстановки t вместо каждого свободного вхождения переменной x в формулу.

Правил вывода исчисления предикатов всего три — modus ponens и два закона квантификации:

(MP) правило отделения (modus ponens) (см. 1.1.3);

Отметим здесь же, что используемое в настоящей книге исчисление предикатов принято именовать классическим, узким или исчислением первого порядка.

По аналогии с 1.1.3 классическое исчисление предикатов мы обозначим символом CL. Запись CL как и в 1.1.2 будет означать, что формула доказуема в CL.

Если из CL удалить схему аксиом 1.1.3 (12), то возникнет система, которую называют интуиционистским исчислением предикатов и обозначают IL. Смысл обозначения IL очевиден из 1.1.2.

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

1.2.1. Аксиоматическая теория множеств — это формальная система. Язык теории множеств — язык первого порядка, сигнатура которого содержит лишь один бинарный предикатный символ и не имеет прочих предикатных или функциональных символов. Теория множеств — это простой пример теории первого порядка. Обычно пишут x y вместо (x, y) и говорят, что x — элемент y или x принадлежит y. Таким образом, формулы теории множеств суть формальные тексты, составленные из атомарных формул вида x y и x = y посредством пропозициональных связок и кванторов.

Теория множеств, точнее говоря, та теория множеств, которую мы излагаем в настоящей книге, строится на основе законов классической логики. Иными словами, в ней действуют обычные логические аксиомы и правила вывода классического исчисления предикатов, которое схематически представлено в предыдущем параграфе. Подробности можно найти почти в любом руководстве по математической логике (см., например, учебники Ю. Л. Ершова, Е. А. Палютина [60], С. Клини [77], Э. Мендельсона [113], Дж. Шенфильда [175]).

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

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

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

где — некоторая формула. Полагают также x = y := ¬(x = y) и x y := ¬(x y). Для простейших теоретико-множественных операций приняты обычные соглашения:

Если — формула, то совокупность P (x) всех подмножеств x, удовлетворяющих условию, описывают выражением Пустое множество не содержит элементов, так что В приведенных выше текстах использован весьма употребительный прием сокращения — пропуск части скобок. Отметим также, что запись x y вербализуют выражениями «x — подмножество y», «x — множество в y», «x — лежит в y»

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

1.2.3. Утверждение о том, что x есть неупорядоченная пара элементов y и z, формализуют следующим образом:

При этом полагают {y, z} := x. Отметим, что фигурные скобки отсутствуют в исходном алфавите и, стало быть, суть метасимволы.

Упорядоченную пару и упорядоченную n-ку вводят приемом Куратовского:

где {x} := {x, x}. Элементы x1,..., xn именуют координатами n-ки (x1,..., xn ).

Стоит обратить внимание на перегруженность круглых скобок. Это обстоятельство неизбежно и его не следует воспринимать как повод для обязательного введения новых символов.

С помощью заключенных соглашений можно придать формальный смысл предложению «X — декартово произведение Y Z». Именно, по определению считают: X := {(y, z) : y Y z Z}.

1.2.4. Рассмотрим утверждения:

Соответствующие формальные тексты имеют вид Таким образом, в (1)–(3) речь идет о том, что элементами X служат упорядоченные пары, причем Y — область определения X, а Z — это область значений X.

При этом X иногда называют абстрактным отношением.

Ограничение X на U есть по определению X (U im(X)). Его обозначают X U. Если существует и притом единственное z, для которого (y, z) X, то полагают X‘y := z. В остальных случаях считают X‘y :=. Наконец, по определению X“y := im(X y). Вместо X“{z} пишут X(x) или даже Xx, если это не приводит к недоразумениям.

Однозначность X, или сокращенно Un(X), выражают формулой Полагают Fnc (X) := Func (X) := Un(x) Rel (X). Если выполнено Fnc (X), то по очевидным причинам X часто именуют функцией или отображением, реже морфизмом. При этом для выражения (u, v) X приняты записи v = X(u), X : u v и т. п. Далее, фраза F — отображение или функция из X в Y означает, что F X Y, при этом выполнено Fnc (F ) и область определения F совпадает с X:

Чтобы подчеркнуть тот факт, что рассматривается функция F c областью определения X, используют и другие широко распространенные выражения: «функция F определена на X» или «F действует на всем X» и т. п. В некоторых разделах математики, в частности, в теории категорий, о которой пойдет речь в главе 3, по умолчанию абстрактная запись F : X Y не подразумевает, вообще говоря, что область определения F есть весь объект X. Эта маленькая тонкость и небольшая коллизия в обозначениях традиционны для современной математики и обычно не вызывают затруднений.

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

1.2.5. Абстрактные отношения достойны особого внимания. Приведем уместные подробности.

Соответствием из множества X в множество Y называют упорядоченную тройку := (F, X, Y ), где F — некоторое подмножество произведения X Y.

Отметим, что для F выполнено Rel (F ). Часто говорят, что F — график, X — область отправления и Y — область прибытия соответствия. При этом пишут Gr() = F. Напомним, что отношением или бинарным отношением на X называют соответствие, у которого область отправления и область прибытия есть X.

Образом множества A X относительно соответствия называют проекцию на Y множества (A Y ) F, обозначаемую символом (A) или даже F (A). Итак, Задание соответствия равносильно указанию отображения где P(Y ) — совокупность всех подмножеств множества Y. На этом основании соответствие иногда отождествляется с отображением. Более того, часто не различают отображение, соответствие и график, используя одну и ту же букву для их обозначения. Пишут также (x) вместо ({x}).

Область определения соответствия — это область определения его графика F. Иначе говоря, Аналогично, область значений или образ соответствия im() := im(F ) — это образ его графика.

1.2.6. Предположим, что X и Y — абстрактные отношения, т. е. Rel (X) и Rel (Y ). Можно организовать суперпозицию (или композицию) X и Y, обозначаемую символом Y X, собирая в единое целое в точности те упорядоченные пары (x, z), для которых (x, y) X и (y, z) Y при подходящем y:

Имея абстрактное отношение X, определяют обратное абстрактное отношение X 1 по правилу:

Символом IX обозначают тождественное отношение на X, т. е.

Детализируем сказанное для соответствий.

Итак, пусть := (F, X, Y ) — это соответствие из X в Y. Положим F 1 := {(y, x) Y X : (x, y) F }. Соответствие 1 := (F 1, Y, X) называют обратным для. Рассмотрим еще одно соответствие := (G, Y, Z), и пусть H — образ множества (F Z) (X G) при отображении (x, y, z) (x, z). Ясно, что т. е. H совпадает с суперпозицией G F графиков G и F. Соответствие := (G F, X, Z) называют композицией соответствий и. Справедливы следующие очевидные равенства:

1.2.7. Остановимся еще на одном понятии, связанном с соответствиями. Рассмотрим соответствие := (F, X, Y ). Полярой (A) множества A X относительно соответствия называют совокупность таких y Y, что A {y} F.

Таким образом, Если соответствие фиксировано, то для простоты пишут (A) вместо (A) и 1 (A) вместо 1 (A).

Простейшие свойства поляр таковы:

(2) для любого A X выполнены включения (4) если (A ) — это непустое семейство подмножеств множества X, то 1.2.8. В случае Rel (X) ((X Y 2 ) (X Y 2 ) X) говорят, что X — транзитивное отношение на Y. Если Rel (X) (IY X), то X называют рефлексивным (на Y ). Если X = X 1, то X называют симметричным (на Y ). Наконец, при Rel (X) ((X X 1 ) Y 2 IY ) используют термин «X — антисимметричное отношение на Y ». Здесь, конечно же, использовано стандартное сокращение:

Рефлексивное и транзитивное отношение называют предпорядком (или отношением предпорядка). Антисимметричный предпорядок — это порядок. Симметричный предпорядок — это эквивалентность. Используют и другую стандартную в данной ситуации терминологию. Напомним, в частности, что порядок X на Y называют линейным, а само Y — цепью (относительно X), если Y 2 X X 1. Если всякое непустое подмножество множества Y имеет наименьший (относительно порядка X) элемент, то говорят, что X вполне упорядочивает Y или что Y вполне упорядочено (подразумеваемым порядком X).

1.2.9. Кванторы называют ограниченными или, точнее, ограниченными y, если они входят в текст в виде ( x y) или ( x y). Существует классификация формул теории множеств (и вообще любой теории первого порядка), основанная на характере использования ограниченных и неограниченных (т. е. не являющихся ограниченными) кванторов. В дальнейшем особую роль будут играть два класса формул — ограниченные формулы, называемые иначе 0 -формулами, а также 1 -формулы. Говорят, что формула ограничена, если всякий квантор присутствует в в виде ( x y) или ( x y) (см. сокращения в 1.2.2). Формулу относят к классу 1 или называют 1 -формулой, если строится из атомарных формул и их отрицаний с помощью только логических операций,, ( x y) и ( x). Ясно, что всякая ограниченная формула попадает в класс 1. Однако не всякая 1 -формула ограничена и существуют формулы, не содержащиеся в классе 1. Соответствующие примеры мы рассмотрим ниже в 1.2.10 и 1.2.11.

1.2.10. Запись z = {x, y} эквивалентна ограниченной формуле Отсюда видно, что упорядоченная пара введена ограниченной формулой. То же самое можно сказать и о декартовом произведении, так как Z = X Y можно записать в виде Еще одну ограниченную формулу доставляет понятие «отображение F из X в Y »

(см. 1.2.4). Действительно, из сказанного выше следует, что F X Y — ограниченная формула, а кроме того, выражения dom(F ) = X и Un(F ), эквивалентные соответственно формулам также являются ограниченными формулами.

1.2.11. Утверждение «множества x и y равномощны», означающее, что «существует биекция между x и y» или символически x y, можно записать 1 -формулой так:

Важно помнить, что это обстоятельство не может быть выражено никакой ограниченной формулой. Еще одну 1 -формулу дает понятие абстрактного отношения:

Следующая формула, утверждающая, что множество y не равномощно никакому своему элементу, в класс 1 не входит:

Как уже было отмечено в 1.2.1, аксиомы теории множеств включают в себя логические аксиомы теорий первого порядка, фиксирующие классические правила умозаключений. Ниже будут перечислены специальные аксиомы теории множеств ZF1 –ZF6 и AC. Если принять в качестве специальных аксиом ZF1 –ZF6, то возникнет аксиоматическая система, которую называют теорией множеств Цермело — Френкеля и обозначают ZF. Добавление к ZF аксиомы выбора AC приводит к более широкой теории, которую по-прежнему именуют теорией Цермело — Френкеля, но обозначают символом ZFC. Отметим, что приводимые ниже параллельные словесные формулировки аксиом отражают первичные канторовы представления о множествах.

1.3.1. При изучении ZFC часто используют термины свойство и класс. Уточним их формальный статус. Рассмотрим формулу = (x), построенную в рамках ZFC (символически: (ZFC)). Вместо текста (y) пишут y {x : (x)}.

Таким образом, действует так называемая схема Чрча для классификации Встречая запись y {x : (x)}, на языке ZFC говорят, что y обладает свойством, или y принадлежит классу {x : (x)}. В этом смысле свойство, формула и класс в ZFC — одно и то же. Схемой Чрча мы фактически уже пользовались в 1.2.2 и 1.2.3. При работе с ZFC удобны и другие широко распространенные сокращения:

Перейдем теперь к формулировкам специальных аксиом ZFC.

1.3.2. Аксиома экстенсиональности ZF1 : два множества совпадают в том (и только в том) случае, если они состоят из одних и тех же элементов:

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

1.3.3. Аксиома объединения ZF2 : объединение множества множеств — также множество:

Используя сокращения из 1.2.2 и 1.3.1, аксиому ZF2 переписывают в виде 1.3.4. Аксиома степени ZF3 : все подмножества данного множества составляют некоторое множество, т. е.

или в краткой записи 1.3.5. Аксиома подстановки ZF : образ множества относительно функции — снова множество:

Здесь — формула ZFC, не содержащая свободных вхождений v. В несколько сокращенной записи:

Отметим, что ZF является схемой для бесконечного набора аксиом, так как для каждой подходящей (ZFC) формулируется своя аксиома. Тем не менее для краткости и единообразия говорят просто об аксиоме подстановки, имея в виду отмеченную ее особенность.

Сформулируем полезные следствия ZF. 1.3.6. Пусть = (z) — формула ZFC. Тогда для любого множества x можно составить его подмножество, отбирая элементы x со свойством, т. е.

Это утверждение — аксиома ZF, где в качестве фигурирует формула (x) (x = y). Приведенное положение часто именуют аксиомой выделения или аксиомой свертывания.

1.3.7. Применяя аксиому ZF для формулы и множества u := P(P()), мы убеждаемся в том, что неупорядоченная пара {x, y} двух множеств (ср. 1.2.3) — снова множество. Последнее утверждение часто именуют аксиомой неупорядоченной пары.

1.3.8. Аксиома бесконечности ZF5 : существует по крайней мере одно бесконечное множество:

Значит, существует такое множество x, что x, {} x, {, {}} x, {, {}, {, {}}}} x и т. д. Внимательный читатель заметит некоторую щель между формальной и неформальной формулировками аксиомы бесконечности.

Бдительный читатель может заподозрить злоупотребление термином «бесконечность». На самом деле аксиома бесконечности относится к основополагающим доктринам канторианства. В этой связи некоторое таинство здесь неизбежно и должно приветствоваться.

1.3.9. Аксиома фундирования ZF6 : всякое непустое множество имеет непересекающийся со всем этим множеством элемент Применив аксиому ZF6 к одноэлементному множеству x := {y}, получим y / y. Несколько забегая вперед, отметим, что по аналогичной причине (на этот раз нужно взять x := {x1,..., xn,... }) не существуют бесконечно убывающие -последовательности x1 x2... xn...

1.3.10. Аксиома выбора AC : произведение непустого множества непустых множеств не пусто:

Функцию f в описанной ситуации называют выбирающей для x.

Известно большое количество утверждений, эквивалентных аксиоме выбора в рамках рассматриваемой нами теории, см., например, книгу Т. Йеха [254]. Приведем формулировки двух наиболее популярных из них.

Теорема Цермело (принцип полного упорядочения). Всякое множество может быть вполне упорядочено.

Лемма Куратовского — Цорна (принцип максимальности). Пусть M — (частично) упорядоченное множество, в котором любое линейное упорядоченное множество имеет верхнюю границу. Тогда любой элемент M мажорируется некоторым максимальным элементом.

1.3.11. На основе приведенной аксиоматики возникает точное представление о классе всех множеств как об «универсуме фон Неймана». Исходным объектом построения выступает пустое множество. Элементарный шаг введения новых множеств из уже построенных состоит в формировании объединения множеств подмножеств имеющихся множеств. Трансфинитное повторение таких шагов исчерпывает класс всех множеств. Классы (в «платонистском» стиле) можно мыслить как внешние объекты по отношению к элементам универсума фон Неймана. Класс в этом понимании есть совокупность множеств, удовлетворяющих теоретико-множественному свойству, описываемому формулой теории Цермело — Френкеля. Поэтому класс, состоящий из элементов некоторого множества (по аксиоме подстановки) сам является множеством. Формально корректное определение универсума фон Неймана требует предварительного знакомства с понятиями ординала и кумулятивной иерархии. Подробнее об этом будет сказано в параграфе 1.5.

1.4. Теория фон Неймана — Гделя — Бернайса Схема аксиом подстановки ZF теории множеств Цермело — Френкеля ZFC охватывает бесконечное число аксиом из-за произвола в выборе формулы. Стоит попытаться ввести новые примитивные объекты, определяемые формулами из ZF. Тогда множество утверждений, содержащихся в схеме ZF, предстанет в форме одной аксиомы о таких объектах. При этом потребуются аксиомы, из которых вытекало бы существование объекта, соответствующего формуле. Поскольку все формулы строятся по единой процедуре за конечное число шагов, то не исключено, что можно достичь желаемого с помощью конечного числа аксиом.

Это основное соображение, идущее от Дж. фон Неймана, заложено в аксиоматику теории множеств, развитой К. Гделем и П. Бернайсом и обозначаемой NGB.

Первоначальным неопределяемым объектом (понятием) NGB является класс.

Класс, служащий элементом какого-либо класса, называют множеством. Прочие классы именуют собственными. Объективизация классов составляет коренное отличие NGB от ZFC, в метаязыке которой «класс» и «свойство» принято воспринимать как синонимы.

При аксиоматическом изложении NGB принято использовать, как правило, одну из двух различных модификаций языка ZFC. Первая из них состоит в добавлении к языку ZFC нового одноместного предикатного символа M. Содержательно M (X) означает, что X есть множество. Вторая модификация использует два разных типа переменных для множеств и классов. Стоит подчеркнуть, что указанные приемы не являются обязательными для описания NGB и использованы лишь из соображений удобства.

1.4.1. Система NGB — это теория первого порядка (с равенством). Строго говоря, язык NGB ничем не отличается от языка ZFC. Однако в качестве переменных принято употреблять прописные латинские буквы X, Y, Z,... (с индексами). Строчные латинские буквы мы оставляем для argo, возникающего в результате введения сокращающих символов, отсутствующих в языке NGB.

Пусть M (X) служит сокращением для формулы ( Y )(X Y ) (читается «X есть множество»). Строчные латинские буквы x, y, z,... (с индексами) будут обозначать переменные для множеств. Точнее, формулы ( x)(x) и ( x)(x) являются сокращениями для формул ( X)(M (X) (X)) и ( X)(M (X) (X)) соответственно. Содержательно эти формулы означают: «для любого множества верно » и «существует множество, для которого верно ». При использовании указанных сокращений переменная X не должна входить в формулу, а также в те формулы, частями которых являются эти сокращения. Впрочем, установленных правил употребления строчных и прописных букв мы будем придерживаться лишь в пределах текущего параграфа. Убедившись же в принципиальной формализуемости теории классов, мы постепенно вернемся к общепринятому — более свободному — математическому языку. Например, перенося теоретико-множественную концепцию отображения в новый мир, мы обычно говорим о класс-функциях F, подразумевая, что такое F может уже и не быть множеством, но тем не менее обладает привычными свойствами функции. Такая практика представляет собой неотъемлемую привилегию работающего математика.

Приступим к формулировке специальных аксиом NGB.

1.4.2. Аксиома экстенсиональности NGB1 : два класса совпадают, если (и только если) они состоят из одних и тех же элементов 1.4.3. Аксиомы для множеств:

(1) аксиома (неупорядоченной) пары NGB2 :

(2) аксиома объединения NGB3 :

(3) аксиома степени NGB4 :

(4) аксиома бесконечности NGB5 :

Как видно, эти аксиомы совпадают с одноименными аналогами из ZFC, сформулированными в 1.3.3, 1.3.4, 1.3.7 и 1.3.8. Следует только иметь в виду, что в словесных формулировках слово множество здесь уже означает класс, являющийся элементом класса. В символической же записи аксиом малые латинские буквы свидетельствуют о сокращениях (см. 1.4.1). Так, например, частично развернутая аксиома степени NGB4 имеет вид В записи аксиомы бесконечности NGB5 использовано сокращение Существование пустого множества в NGB заранее не предполагается, как и в ZFC, а вытекает из аксиом. Тем не менее иногда это утверждение включают в список NGB в качестве отдельной аксиомы:

1.4.4. Аксиома подстановки NGB6 : если класс X однозначен, то для любого множества y класс вторых координат тех пар из X, первые координаты которых входят в y, является множеством:

где Un(X) := ( u)( v)( w)((u, v) X (u, w) X v = w).

Как и предполагалось, схема ZF превратилась в одну аксиому. Здесь же отметим, что схеме аксиом выделения из ZF (см. 1.3.6) также соответствует одна аксиома — аксиома выделения. Она утверждает, что для любых множества x и класса Y существует множество, состоящее из элементов, общих для x и Y, т. е.

Эта аксиома слабее аксиомы подстановки (она выводится из NGB6 и нижеследующей теоремы 1.4.14), но в некоторых случаях более удобна в обращении.

Следующая группа из аксиом NGB7 –NGB13 предназначена для формирования классов. Эти аксиомы утверждают, что для некоторых свойств, выраженных формулами, существуют классы всех множеств, обладающих соответствующими свойствами. Единственность при этом вытекает, как это обычно бывает, из аксиомы экстенсиональности NGB1.

1.4.5. Аксиома -отношения NGB7 : существует класс, состоящий в точности из тех упорядоченных пар множеств, у которых первая координата служит элементом второй:

1.4.6. Аксиома пересечения NGB8 : для любых двух классов существует их пересечение:

1.4.7. Аксиома дополнения NGB9 : для каждого класса существует дополнительный ему класс:

Отсюда вытекает существование универсального класса пустого класса.

1.4.8. Аксиома области определения NGB10 : для каждого класса X упорядоченных пар существует класс Y := dom(X), элементами которого являются в точности первые координаты элементов класса X:

1.4.9. Аксиома декартова произведения NGB11 : для всякого класса X существует класс Y := X состоящий из всевозможных упорядоченных пар, первые координаты которых являются элементами класса X:

1.4.10. Аксиомы перестановки NGB12 и NGB13. Пусть := (1, 2, 3 ) — перестановка множества {1, 2, 3}. Класс Y называют -транспонированием класса X, если (x1, x2, x3 ) Y тогда и только тогда, когда (x1, x2, x3 ) X.

Для любого класса X существуют его (2, 3, 1)- и (1, 3, 2)-транспонирования:

1.4.11. Аксиома фундирования NGB14 : в произвольном непустом классе есть элемент, не имеющий с ним общих элементов:

1.4.12. Аксиома выбора NGB15 : для каждого класса X существует выбирающая функция, т. е. однозначный класс, сопоставляющий всякому непустому множеству из X некоторый его элемент:

Это очень сильная форма аксиомы выбора. Она равносильна существованию одновременного выбора по одному элементу из каждого непустого множества.

На этом список специальных аксиом NGB исчерпан. Как видно, аксиоматика NGB, в отличие от ZFC, конечна. Другое удобное качество системы NGB состоит в том, что она фактически оперирует и с множествами, и со свойствами множеств как с формальными объектами, осуществляя объективизацию, недоступную выразительным средствам ZFC.

1.4.13. Из группы аксиом формирования классов мы выведем несколько утверждений, которые потребуются нам при доказательстве общей теоремы о существовании классов.

(1) Для любого класса существует его (2, 1)-транспонирование:

Аксиома декартова произведения гарантирует существование класса X.

Последовательное применение аксиом (2, 3, 1)- и (1, 3, 2)-транспонирования к классу X дает класс Y всех троек (v, u, w) таких, что (v, u) X. Воспользовавшись аксиомой области определения, заключаем, что Z := dom(Y ) — искомый класс.

(2) Для любых двух классов существует их декартово произведение:

Нужно воспользоваться последовательно аксиомой декартова произведения, утверждением (1), аксиомой пересечения и положить Z := ( Y ) (X Для n 2 в силу (2) определен класс n всех упорядоченных n-ок.

(3) Для любого класса X существует класс Z := (n m ) (X (4) Для любого класса X существует класс Z := (m Для доказательства (3) и (4) нужно применить аксиому декартова произведения и аксиому пересечения.

(5) Для любого класса X существует класс Z такой, что Следует применить аксиомы перестановки и аксиому декартова произведения.

1.4.14. Теорема. Пусть — формула, в построении которой участвуют только переменные из числа X1,..., Xn, Y1,..., Ym, причем предикативна, т. е. в связаны лишь переменные для множеств. Тогда в NGB доказуемо утверждение Пусть формула записана с учетом принятых сокращений в таком виде, что связанными в ней являются только переменные для множеств. Достаточно рассмотреть те, которые не содержат подформул вида Y W и X X, ибо последние можно заменить на эквивалентные: ( x)(x = Y x W ) и ( u)(u = X u X). Кроме того, можно исключить из символ равенства, подставив в соответствии с аксиомой экстенсиональности вместо X = Y выражение ( u)(u X u Y ). Доказательство проводится индукцией по длине k формулы, т. е.

по числу k логических связок и кванторов, входящих в.

При k = 0 формула атомарна и имеет вид x xj, или xj x, или x Yl класс W1, для которого Если же := xj x, то вначале, воспользовавшись той же аксиомой, мы находим класс W2 со свойством а затем применяем 1.4.13 (1). В результате мы подберем класс W3, для которого будет Итак, в любом из этих двух случаев существует такой класс W, что справедлива формула На основании 1.4.13 (4) в формуле можно заменить подформулу (x, xj ) W на (x1,..., x1, x ) Z1 для некоторого другого класса Z1 и добавить кванторы ( x1 )... ( x1 ) в начале. Пусть — получаемая при этом формула. В силу 1.4.13 (5) в формуле вместо подформулы (x1,..., x1, x, xj ) Z1 допустимо написать (x1,..., x, x+1,..., xj ) Z2 для некоторого другого класса Z2 и добавить кванторы ( x+1 )... ( xj1 ) в начале формулы. Наконец, применив 1.4.13 (3) к Z2, найдем класс Z, для которого верна формула Для оставшегося случая x Yl требуемое утверждение следует из существования декартовых произведений W := 1 Yl и Z := W n. Тем самым теорема установлена при k = 0.

Допустим, что для всех k < p теорема доказана и формула имеет p логических связок и кванторов. Достаточно рассмотреть случаи, когда получается из каких-то формул с помощью отрицания, импликации и квантора общности.

Пусть := ¬. По индукционному предположению существует класс V такой, что По аксиоме дополнения имеется класс Z := нужным условиям.

Пусть :=. Вновь по индукционному предположению найдутся классы V и W такие, что для V и выполнено отмеченное выше и, кроме того, Искомый класс Z := \ (V ( \ W )) существует ввиду аксиомы пересечения и аксиомы дополнения.

Пусть := ( x), а V и те же, что и выше. Если применить аксиому области определения к классу X := \ V, то получим класс Z1, для которого Класс Z := \ Z1, который существует по аксиоме дополнения, будет искомым, ибо формула ( x) эквивалентна ¬( x)(¬).

1.4.15. Каждая аксиома формирования классов NGB7 –NGB13 является следствием теоремы 1.4.14 при подходящем выборе формулы. С другой стороны, сама эта теорема, как видно из доказательства, выводится из аксиом формирования классов. Замечательно, что вместо бесконечного числа утверждений, содержащихся в 1.4.14, можно обойтись конечным числом аксиом NGB7 –NGB13.

Теорема 1.4.14 позволяет доказывать существование самых разнообразных классов. Так, для всякого класса Y существуют класс всех его подмножеств P(Y ) и объединение всех элементов класса Y, определяемые обычными формулами В этом можно легко убедиться, если взять (X, Y ) := X Y и (X, Y ) := ( V )(X V V Y ). По аналогичным соображениям возможны определения Z 1, im(Z), Z Y, Z“Y, X Y и т. п., где X, Y и Z — некоторые классы.

1.4.16. Теорема. Всякая теорема ZFC является теоремой NGB.

Все аксиомы ZF являются теоремами NGB. Докажем единственную неочевидную часть этого утверждения, касающуюся аксиомы подстановки ZF. Пусть формула не содержит свободных вхождений переменной y и {x, t, z1,..., zm } — полный набор переменных, использованных в построении. Далее предположим, что для всех x, u, v, z1,..., zm выполняется Формула предикативна, если в ней связанными являются лишь переменные для множеств. По теореме 1.4.14 существует класс Z такой, что Из указанного выше свойства видно, что класс Z однозначен, т. е. в NGB доказуема Un(Z). По аксиоме подстановки NGB6 существует множество y, для которого Ясно, что для y выполняется нужное соотношение 1.4.17. Теорема. Каждая теорема NGB, в которой говорится о множествах, является теоремой ZFC.

Доказательство можно найти, например, в книге П. Дж. Коэна [84]. Оно требует привлечения некоторых фактов из теории моделей, выходящих за рамки настоящей книги.

Теоремы 1.4.16 и 1.4.17 часто формулируют в следующем виде.

1.4.18. Теорема. Теория множеств фон Неймана — Гделя — Бернайса NGB служит консервативным расширением теории множеств Цермело — Френкеля ZFC.

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

1.5.1. Рассмотрим классы X и Y. Скажем, что X есть отношение порядка или просто порядок на Y, если X является антисимметричным, рефлексивным и транзитивным отношением на Y. Антисимметричность, рефлексивность и транзитивность отношения можно записать так же, как и на языке ZFC (см. 1.2.8).

Порядок X на Y называют линейным, если Y Y X X 1. Говорят, что отношение X вполне упорядочивает Y или что Y — вполне упорядоченный класс, если X — порядок на Y и всякий непустой подкласс класса Y имеет наименьший элемент (относительно X). Классы X1 и X2, упорядоченные отношениями R1 и R2 соответственно, именуют подобными, если существует биекция h из X1 на X такая, что (x, y) R1 (h(x), h(y)) R2 для всех x, y X1.

1.5.2. Введем отношение E формулой Класс E существует в силу аксиомы -отношения NGB7 и теоремы 1.4.14. Как видно, E — отношение порядка на универсальном классе Класс X называют транзитивным (это понятие не следует путать с понятием транзитивного отношения), если каждый его элемент является также и его подмножеством:

Ординальным классом мы будем именовать всякий транзитивный класс, вполне упорядоченный отношением E. Запись Ord (X) означает, что X — ординальный класс. Ординальный класс, являющийся множеством, называют ординалом (или порядковым числом, или трансфинитным числом). Класс всех ординалов обозначают символом On. Напомним, что ординалы символизируют, как правило, малыми греческими буквами. При этом приняты следующие сокращения:

Если <, то говорят, что предшествует, а следует за. Привлекая аксиому фундирования NGB14, легко установить следующий факт.

1.5.3. Класс является ординальным в том и только в том случае, если он транзитивен и линейно упорядочен отношением E.

Пусть транзитивный класс X линейно упорядочен отношением E. Возьмем непустой подкласс Y X и покажем, что Y имеет наименьший элемент.

Существует по меньшей мере один элемент y Y. Если y =, то y — искомый наименьший элемент в Y. Если же y =, то по аксиоме фундирования можно подыскать элемент x y такой, что x y =. Тогда x — наименьший элемент множества y, так как y линейно упорядочено. Ввиду линейной упорядоченности класса Y отношением E элемент x будет наименьшим и в классе Y. Значит, X — ординальный класс и достаточность указанного условия обоснована. Необходимость его очевидна.

Итак, в NGB или ZFC можно пользоваться более простым определением ординала:

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

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

1.5.4. Ниже нам потребуются несколько вспомогательных фактов.

(1) Пусть X и Y — произвольные классы. Если X ординален, Y транзитивен и X = Y, то равносильны соотношения Y X и Y X.

При Y X класс Y — множество и Y X из-за транзитивности X. Допустим, в свою очередь, что Y X. Так как X = Y, то Z := X Y =. Класс Z имеет наименьший элемент x Z (в смысле отношения порядка E). Это означает, что x Z = или x Y. Кроме того, x X, ибо x X и класс X транзитивен. Возьмем элемент y Y. Так как X линейно упорядочен, то x y или x = y, или, наконец, y x. Первые два соотношения с учетом транзитивности Y дают x Y, что противоречит вхождению x Z. Следовательно, y x.

Значит, Y x. Принимая в расчет уже доказанное включение x Y, получаем x = Y. Окончательно мы заключаем, что x = Y x X Y X.

(2) Пересечение любых двух ординальных классов есть ординальный класс.

(3) Если X и Y — ординальные классы, то Пусть пересечение X Y = Z не совпадает ни с одним из классов X и Y. Тогда согласно (1) и (2) Z X и Z Y, т. е. Z X Y = Z. Однако для множества Z X соотношение Z Z невозможно. Следовательно, либо Z = X и тогда Y X, либо Z = Y и тогда X Y. Осталось сослаться на (1).

1.5.5. Теорема. Справедливы следующие утверждения:

(1) элементами любого ординального класса могут быть только ординалы;

(2) класс On — единственный ординальный класс, не являющийся ординалом;

(3) для каждого ординала множество + 1 служит ординалом, причем наименьшим из всех следующих за ординалов;

(4) объединение X непустого класса ординалов X On — ординальный класс; если X — множество, то X есть верхняя граница множества X в упорядоченном классе On.

(1): Возьмем ординальный класс X и элемент x X. Так как X транзитивен, то x X. Следовательно, множество x линейно упорядочено отношением E. Установим Tr (x). Если z y x, то z X ввиду транзитивности X. Из возможных трех случаев z = x, x z и z x, первые два приводят к замкнутым циклам z y z и z y x z, противоречащим аксиоме фундирования. Стало быть, z x. Итак, z y z x, т. е. y x. Это доказывает Tr (x), а заодно и Ord (x).

(2): Линейная упорядоченность класса On следует из 1.5.4 (3), а его транзитивность — из (1). Таким образом, Ord (On). Если On — множество, то On — ординал и получается противоречие: On On. Следовательно, On — это ординальный класс, но не ординал. Для произвольного ординального класса X из X On вытекает X = On. Действительно, утверждение 1.5.4 (3) допускает кроме этой еще только одну возможность — On X, которая, однако, противоречит тому, что On — собственный класс.

(3): Если — ординал, то множество +1 линейно упорядочено по очевидным соображениям. Для x + 1 либо x, либо x =, причем в обоих случаях x. Но + 1. Стало быть, x + 1, что и доказывает транзитивность + 1. Окончательно выводим, что + 1 — ординал и < + 1. Если < для некоторого ординала, то и, т. е. {}. Согласно 1.5.4 (1) верно либо {}, либо {} =. Значит, + 1.

(4): Предположив, что X On и y Y := X, подыщем такой элемент x X, что y x. Поскольку x — ординал, то y x и, тем более, y Y. Ввиду транзитивности класса On (см. (2)) из x X следует x On, а потому Y On.

Итак, Y — транзитивный подкласс On и, стало быть, Y — ординал. Если X, X, то Y и вновь по 1.5.4 (1) Y. Следовательно, Y = sup(X).

1.5.6. Точную верхнюю границу множества ординалов x принято обозначать lim(x). Ординал называют предельным, если = и lim() =. Эквивалентно, — предельный ординал, если он не представим в виде = + с каким-либо On. Обозначим символом KII класс всех предельных ординалов. Ординалы, не входящие в KII, образуют класс непредельных ординалов KI := On KII = { On : ( On)( = + 1)}. Обозначим буквой наименьший предельный ординал (существование которого обеспечено теоремой 1.5.5 и аксиомой бесконечности). Можно показать, что совпадает с классом непредельных ординалов таких, что каждый предшественник также является непредельным:

Элементы называют конечными ординалами или положительными целыми числами. Наименьший ординал — нулевое множество 0 := — принадлежит.

Отличные от нуля элементы именуют натуральными числами. Следующий ординал 1 := 0 + 1 = 0 {0} = {} содержит единственный элемент 0. Далее, 2 := 1 {1} = {0} {1} = {0, 1} = {0, {0}}, 3 := 2 {2} = {0, {0}, {{0, {0}}} и т. д.

Итак, Подчеркнем, что по давней онтологической традиции термин «натуральное число» принято применять только к элементам \ {0}. Нуль в системе счета возник значительно позднее единицы и исторически «менее» натурален. Впрочем, в наше время термин «множество натуральных чисел» часто относят и ко всему, в чем нет большого греха. Для обозначения множества натуральных чисел используют специальный символ:

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

1.5.7. Теорема. Справедливы следующие утверждения:

(2) для каждого непосредственно следующий за ним ординал + — натуральное число;

(3) 0 = + 1 ни для какого целого положительного числа ;

(4) для положительных целых чисел и из + 1 = + 1 следует = ;

(5) если класс X содержит пустое множество и с каждым ординалом содержит также непосредственно следующий за ним ординал, то X.

1.5.8. Теорема (принцип трансфинитной индукции). Пусть X — некоторый класс, обладающий свойствами: (1) 0 X; (2) если — ординал и X, то + 1 X; (3) если x — множество ординалов, содержащееся в X, то lim(x) X.

Тогда On X.

Предположим, что On X. Тогда непустой подкласс On \ X вполне упорядоченного класса On имеет наименьший элемент On \ X, причем это означает, что (On \ X) = 0 или X и = 0 ввиду (1). Если KI, т. е. = + Если же KII, то из условия (3) выводим = lim() X. В обоих случаях имеем X, что противоречит вхождению On \ X.

1.5.9. Теорема (принцип трансфинитной рекурсии). Пусть G — некоторая класс-функция. Тогда существует единственная функция F, для которой ограничение F на.

Определим класс Y соотношением Если f, g Y, то либо f g, либо g f. Действительно, если := dom(f ) и := dom(g), то или. Считая, например, что <, положим z := { On : < f () = g()}. Если z = 0, то имеется наименьший элемент z.

Тогда для всех < будет f () = g(), т. е. f = g. Но по определению класса Y верно также f () = G(f ) и g() = G(g ). Следовательно, f () = g() и z. Это противоречит выбору. Значит, z = 0, т. е. f () = g() при всех <. Отсюда получаем требуемое включение g f. Положим F := Y.

dom(F ). Если dom(F ), то (, G(F )) f при некотором f Y. Тогда := dom(f ) dom(F ) и ввиду транзитивности будет dom(F ). Итак, класс dom(F ) транзитивен и по 1.5.4 (1) либо dom(F ) = On, либо dom(F ) On.

Однако последнее включение невозможно. В самом деле, из := dom(F ) On следует, что функция f := F {(, G(F ))} входит в Y. Стало быть, f F, откуда вытекает противоречие: f F dom(f ) dom(F ) dom(F ) =.

1.5.10. Бинарное отношение R называют вполне фундированным, если для последовательности (xn ) со свойством xn R(xn+1 ) для всех n. Примером вполне фундированного отношения служит отношение. Принципы трансфинитной индукции и рекурсии удобно применять в следующем виде.

1.5.11. Теорема. Пусть R — вполне фундированное отношение. Тогда справедливы утверждения:

(1) (индукция по R) если класс X таков, что для каждого x соотношение R1 (x) X влечет x X, то X = (2) (рекурсия по R) для любой функции G : существует такая функция F, что dom(F ) = и F (x) = G(F R (x)) для всех x 1.5.12. Два множества называют равномощными, если существует взаимно однозначное отображение одного из них на другое. Ординал, который не равномощен никакому предшествующему ординалу, называют кардиналом. Любое целое положительное число служит кардиналом. Кардинал, не являющийся целым положительным числом, называют бесконечным. Значит, — наименьший бесконечный кардинал. Для любого ординала обозначим символом бесконечный кардинал, для которого упорядоченное множество всех бесконечных кардиналов, меньших, подобно. Если такой кардинал существует, то он единствен.

1.5.13. Теорема (принцип измерения мощностей). Справедливы следующие утверждения:

(1) бесконечные кардиналы образуют некоторый вполне упорядоченный собственный класс;

(2) для любого ординала существует кардинал, причем отображение является подобием класса ординалов и класса бесконечных кардиналов;

(3) существует отображение |·| из универсального класса на класс всех кардиналов такое, что множества x и |x| равномощны для любого x Доказательство см., например, в книге Э. Мендельсона [146].

Кардинал |x| называют мощностью или кардинальным числом множества x. Итак, всякое множество равномощно единственному кардиналу, а именно своему кардинальному числу. Множество x счетно, если |x| = 0 :=, и не более чем счетно, если |x| 0.

1.5.14. Взяв произвольный ординал, мы обозначим символом 2 мощность множества P( ), т. е. 2 := |P( )|. Такое обозначение оправдано тем, что 2x и P(X) равномощны для любого x, где 2x — класс всех отображений из x в 2. Теорема, установленная Г. Кантором, утверждает, что |x| < |2x |, каково бы ни было множество x. В частности, < 2 для любого ординала. Тогда точные мощности между +1 и 2, т. е. выполнено ли равенство +1 = 2, составляет содержание обобщенной проблемы континуума. При = 0 это классическая проблема континуума. Под гипотезой континуума CH (обобщенной гипотезой континуума GCH ) понимают равенство 1 = 2 (соответственно равенство +1 = 2 для всех On). Иногда в литературе на английский манер говорят о континуум-гипотезе и обобщенной континуум-гипотезе.

1.5.15. Введем порядок в классе On On, который мы будем называть каноническим. Рассмотрим 1, 2, 1, 2 On. Будем считать, что (1, 2 ) (1, 2 ), если выполнено любое из следующих условий:

Таким образом, пары (, ) сравнивают по sup{, }, а в множестве упорядоченных пар (, ), имеющих одинаковый sup{, }, вводят лексикографический порядок.

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

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

1.6.1. Рассмотрим некоторое множество x0 и два однозначных класса Q и R.

Исходя из них, построим новый однозначный класс G. Прежде всего, положим G(0) := x0. Далее, если x — функция и dom(x) = + 1 для некоторого On, то G(x) := Q(x()). Если же dom(x) = — предельный ординал, то для получения G(x) сначала «накопим» множество из значений x() при <, а затем к полученному множеству применим R, т. е. G(x) := R( im(x)). Во всех остальных случаях мы будем считать, что G(x) = 0. В силу теоремы 1.5.9 о трансфинитной рекурсии существует однозначный класс F, удовлетворяющий условиям — стоуново представление B. Положив b (x) := (V (x)) (x B), мы получаем конечную положительную вполне аддитивную меру b на B такую, что b (b) = (V ) > 0.

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

2.6.1. Рассмотрим произвольную решетку L. Псевдодополнением элемента x L относительно y L называют наибольший элемент множества {z L :

x z y}. Псевдодополнение x относительно y, если оно существует, обозначают символом x y. Имеет место следующее очевидное свойство, которое можно рассматривать как другое определение относительного псевдодополнения.

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

(2) Если существует x ((x y) (x z)) для некоторых x, y, z L, то имеет место равенство силу (1) будет y привлекая (1), получаем x (y z) u.

В то же время из определения точной нижней границы видно, что x y x (y z) и x z x (y z). Следовательно, u x (y z).

с нулем 0 и единицей 1 называют гейтинговой алгеброй, если Решетку для любых двух элементов x, y существует относительное псевдодополнение x y. Гейтингову алгебру называют также псевдобулевой алгеброй или брауэровой алгеброй.

(3) Любая гейтингова алгебра является дистрибутивной решеткой.

Очевидное следствие из (2).

2.6.2. Итак, в гейтинговой алгебре определена двуместная операция. Некоторые свойства этой операции собраны в следующем утверждении.

Для любых элементов x, y и z гейтинговой алгебры выполнены следующие соотношения:

Утверждения (1) и (2) следуют непосредственно из определений.

(3): Если в 2.6.1 (1) положить z := y, то получим y x y, что равносильно соотношению (x y) y = y.

(4): Как отмечено в (3), y x y. Поэтому x y x (x y). Но в то же время согласно (3) будет x y y. Стало быть, x (x y) x y.

(5): Пусть x1 x2. Используя (4), можно написать неравенства Отсюда в соответствии с 2.6.1 (1) получаем x2 y x1 y.

(6): Пусть y1 y2. Вновь привлекая (4), выводим:

Согласно 2.6.1 (1) последнее означает x y1 x y2.

соответствии с 2.6.1 (1) будет xu y и xu z. Значит, xu yz. Стало быть, в силу 1.6.1 (1) u x (y z). Наоборот, согласно (6) имеем x (y z) x y и x (y z) x z. Следовательно, x (y z) u.

(x y) z y z. Следовательно, (x y) z u. В то же время, привлекая дистрибутивность гейтинговой решетки (см. 2.6.1 (3)) и формулу (4), выводим:

Ссылка на 2.6.1 (1) дает u (x y) z.

(9): Согласно 2.6.1 (1) требуемое равносильно неравенству x ((x y) (y z)) z, которое легко выводится на основе ассоциативности точных нижних границ и (4):

(10): Следует из (8) в силу 2.6.1 (1).

(11): Для произвольного элемента u в силу 2.6.1 (1) имеет место цепочка эквивалентностей:

Требуемое вытекает из эквивалентности первого и последнего неравенств.

(12): Вновь пользуясь (4), выводим:

Применив теперь дважды 2.6.1 (1), получим сначала (x y) (x (y z)) 2.6.3. Псевдодополнением элемента x L решетки с нулем L называют наибольший элемент множества {y L : x y = 0}. Как видно, в гейтинговой алгебре ким образом, свойства псевдодополнения вытекают из соответствующих свойств относительного псевдодополнения.

Для любых элементов x, y, z гейтинговой алгебры имеют место утверждения:

Утверждения (1)–(4) следуют непосредственно из определений.

определению псевдодополнения.

(6): Если в (5) взять x вместо x, то получим x x. Вместе с тем из (1) и (5) видно, что x x.

(7): Вытекает из 2.6.2 (8) в силу определения псевдодополнения.

(8): В силу дистрибутивности 2.6.1 (3), ассоциативности 2.1.2 (2) и формулы (4) Отсюда, учитывая 2.6.1 (1), получаем x y (x y) 0 = (x y).

(9): Последовательное применение (7), (5), (4) и (2) дает (10): Следует из 2.6.1(11) при z = 0.

(11): Привлекая последовательно (5), 2.6.2 (6) и (10), можно написать: x (12): Вытекает из 2.6.2 (7) при z := y с учетом (4).

2.6.4. Элемент x регулярных элементов гейтинговой решетки с индуцированным из порядком мы обозначим символом R().

некоторого y Если элемент x регулярен, то следует положить y := x. Если же x = y для некоторого y (2) Для произвольной гейтинговой алгебры упорядоченное множество R() является булевой алгеброй.

Покажем, что R() — решетка. Возьмем элементы x, y R() и в соответствии с (1) представим их в виде x = u и y = v. Привлекая 2.6.3 (7), выводим x y = u v = (u v) и согласно (1) x y — регулярный элемент. Значит, точные нижние границы регулярных элементов в и в R() совпадают.

Покажем, что z := (x y) — точная верхняя граница элементов x и y в R(). Регулярность z вытекает из (1). Из 2.6.3 (5) видно, что x z и y z. Если v. Следовательно, привлекая 2.6.3 (1, 7), получим z = (x y ) v = u.

Таким образом, точная верхняя граница элементов x, y R() существует и равна (x y), следовательно, отлична от точной верхней границы в Решетка R() является гейтинговой алгеброй. Действительно, 0 и 1 служат нулевым и единичным элементами в R(). Кроме того, для регулярного элемента y = v в силу 2.6.3 (10) будет x y = (x v), т. е. x y — регулярный элемент. Более того, для x, y R() элемент x y будет псевдодополнением x относительно y в R(). В частности, R() — дистрибутивная решетка.

Осталось убедиться, что для x R() псевдодополнение x является дополнением. Последнее выводится последовательным применением формул 2.6.3 (7), x = x, 2.6.3 (4) и 2.6.3 (2): (x x ) = (x x) = 0 = 1.

2.6.5. Рассмотрим коротко некоторые способы формирования гейтинговых алгебр. Подробности можно найти в книге Е. Расвой и Р. Сикорского [155].

(1) Если подрешетка y и x для произвольных x, y H, то будет самостоятельной гейтинговой алгеброй, которую называют подалгеброй алгебры (2) Гомоморфизмом гейтинговых алгебр называют решеточный гомоморфизм h : 1 2, сохраняющий относительное псевдодополнение и псевдодополнение, т. е. h удовлетворяет условиям (см. 2.2.1):

Как обычно, взаимно однозначный гомоморфизм называют изоморфизмом. Если h : 1 2 — гомоморфизм гейтинговых решеток, то h(1 ) будет подалгеброй алгебры 2. Если h — биекция гейтинговой алгебры на произвольное множество C, то структуру гейтинговой решетки можно перенести с на C так, что при этом h становится изоморфизмом гейтинговых алгебр.

(3) Возьмем семейство гейтинговых алгебр ( )A. Так же, как и в случае булевых алгебр (см. 2.2.5) декартово произведение можно снабдить покоординатным отношением порядка:

Тогда — гейтингова алгебра. Операции в совпадают с соответствующими покоординатными операциями в алгебрах. В частности, для x, y и всех A будет (x y)() = x() y() и x () = x(). Гейтингову алгебру называют декартовым произведением семейства гейтинговых алгебр ( )A.

(4) Фильтр в гейтинговой алгебре определяют так же, как и в булевой алгебре (см. 2.4.2 (2)). Если — фильтр в гейтинговой алгебре то можно ввести в отношение предпорядка := и отношение эквивалентности := формулами:

где по определению x y := (x y) (y x). Рассмотрим фактор-множество / := / и фактор-отображение x [x], где [x] — класс эквивалентности y. Нетрудно показать, что / — гейтингова алгебра, а факторy] x отображение x [x] является гомоморфизмом гейтинговых алгебр.

(5) Гейтингову алгебру называют полной, если она является полной решеткой. Для любой гейтинговой алгебры существуют полная гейтингова алгебра и изоморфизм сохраняющий точные границы любых множеств.

: x e} и h(x) := x e. Тогда e — гейтингова алгебра и h — гомоморфизм гейтинговых алгебр, сохраняющий точные границы любых множеств.

2.6.6. Рассмотрим примеры гейтинговых алгебр.

(1) Топологии. Если (Q, ) — топологическое пространство, то совокупность всех открытых множеств P(Q), упорядоченная по включению, представляет собой гейтингову алгебру. Точные границы в решетке те же, что и в алгебре множеств P(Q). Если U и V — открытые множества, то относительное псевдодополнение U V совпадает с внутренностью множества V (X \ U ).

Регулярные элементы — регулярные открытые множества: R( ) = RO (Q).

(2) Ростки. Вновь рассмотрим топологическое пространство (Q, ). Взяв q Q, определим в отношение эквивалентности q, полагая U q V в том и только в том случае, если существует такая окрестность W точки q, что W U = W V. Фактор-множество / — фактор-алгебра, построенная в 2.6.5 (4), где в качестве взят фильтр (q) всех открытых окрестностей точки q. Таким образом, / — гейтингова алгебра.

(3) Алгебры Линденбаума — Тарского. На множестве всех формул интуиционистского исчисления высказываний IL (см. 1.1.4) введем отношение := IL, полагая отношение есть предпорядок, так как транзитивность вытекает из 1.1.3 (3), а рефлексивность является следствием выводимости формулы из аксиом 1.1.3 (1–11). Скажем теперь, что формулы и эквивалентны, и напишем, если и. Отношение является эквивалентностью и мы можем образовать фактор-множество / с фактор-отображением []. Предпорядок индуцирует отношение порядка в / по правилу: [] [] в том и только в том случае, если. Используя аксиомы 1.1.3 (1–11) и правило отделения modus ponens, можно установить, что упорядоченное множество является гейтинговой алгеброй. При этом отношение является конгруэнцией по отношению к операциям, и, т. е. имеют место соотношения:

(Подробности см. в книге Е. Расвой и Р. Сикорского [155].) Как и в булевом слуе чае (см. 2.3.9) A() := / называют алгеброй Линденбаума — Тарского для IL.

(4) Топологической булевой алгеброй называют булеву алгебру с операцией внутренности I :, удовлетворяющей условиям:

Неподвижные точки отображения I называют открытыми элементами. Мнообозначают символом ( ) := (, I), т. е.

жество всех открытых элементов Множество ( ) с индуцированным из порядком является гейтинговой реи для произвольных x, y ( ) спрашеткой. При этом ( ) — подрешетка дополнения и относительного дополнения в булевой алгебре.

См. Е. Расва и Р. Сикорский [155, теорема IV.1.4].

2.6.7. Теорема. Для любой гейтинговой алгебры существует топологическая булева алгебра такая, что изоморфна ( ).

См. Е. Расва и Р. Сикорский [155, теорема IV.3.1].

2.6.8. Пусть — гейтингова алгебра. Отображение v : 0 называют -оценкой. Так же, как и в случае булевых алгебр эту оценку можно продолжить на множество всех формул, используя следующие правила:

Предложение называют -общезначимым, если v() = 1 для каждой -оценки v. Если же последнее выполнено для каждой гейтинговой алгебры, то мы будем говорить о HA-общезначимости предложения и писать HA.

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

2.6.9. Теорема. Предложение является HA-общезначимым в том и только в том случае, если оно выводимо в интуиционистском исчислении высказываний:

Достаточность состоит в непосредственной проверке HA-общезначимости всех аксиом 1.1.3 (1–11), а также сохранения HA-общезначимости при применении правила modus ponens. Первое делается с помощью 2.6.2 и 2.6.3, а второе вытекает из того, что если v() = v( ) = 1, то в силу 2.6.2 (1) v() v() и поэтому v() = 1. Необходимость вытекает из 2.6.6 (3).

2.7.1. (1) Теория булевых алгебр берет свое начало от классического сочинения Дж. Буля «Исследование законов мысли, на которых основаны математические теории логики и вероятностей» [198, 199], изданного в 1854 году. Свои цели и задачи автор сформулировал следующим образом: «В предлагаемом вниманию читателей трактате мы намереваемся исследовать фундаментальные законы тех операций, которые совершает разум в процессе рассуждений, дабы выразить их в символическом языке исчисления и на этой основе построить науку логики и ее метод». Следуя такой установке, Дж. Буль осуществил алгебраизацию логической системы, которая лежит в основе классических математических рассуждений. Тем самым он обессмертил свое имя, став создателем алгебраической структуры, именуемой булевой алгеброй или алгеброй Буля.

(2) Булевы алгебры имеют разнообразные связи с многими важнейшими направлениями математической науки. Общетеоретическое и прикладное значение булевых алгебр определяет та ключевая роль, которую они играют в математической логике, теории вероятностей и кибернетике. Живо и увлекательно о булевых алгебрах рассказано в книге И. М. Яглома [181] (см. также цитированную там литературу). Для первоначального знакомства с теорией множеств, булевыми алгебрами и математической логикой может послужить книга Р. Р. Столла [164]. Основательное изложение теории булевых алгебр имеется в монографиях Д. А. Владимирова [33] и Р. Сикорского [160].

(3) На первый взгляд, определение 2.1.3 может показаться несколько странным. В самом деле, сразу из него не видно, по каким причинам дистрибутивную решетку принято называть алгеброй, ведь слово «алгебра» относится к общепринятым (ср.: алгебра Ли, банахова алгебра, C -алгебра и т. п.). Возникшее недоумение легко развеивается, ибо в действительности булева алгебра служит алгеброй над двухэлементным полем. Принципиальная важность этого обстоятельства отчасти отражена в параграфе 2.4. Вместе с тем вполне естественно, что в разных контекстах на булевы алгебры удобно смотреть с разных точек зрения. Стоит подчеркнуть, что важные для функционального анализа конкретные булевы алгебры часто возникают как дистрибутивные решетки с дополнениями.

(4) Общая теория решеток изложена в книгах Г. Биркгофа [16] и Г. Гретцера [48]. С другой стороны, булевы алгебры и векторные решетки входят в класс упорядоченных алгебраических систем, теории которых посвящена книга Л. Фукса [168]. Относительно теории решеточно упорядоченных групп см. монографии А. Бигарда, К. Кеймела и С. Вольфенштейна [195], В. М. Копытова [82].

2.7.2. (1) Проблема продолжения булева гомоморфизма с сохранением порядковой непрерывности (-непрерывности) освещена в книгах Д. А. Владимирова [33], А. Г. Кусраева [107], Р. Сикорского [160]. В [306, 307] К. Маттес получил результат о продолжении m-гомоморфизма со значениями в слабо m-дистрибутивной (= слабо (m, m)-дистрибутивной) булевой алгебре. Тот факт, что условие слабой m-дистрибутивности является также необходимым для продолжения m-гомоморфизмов (обращение результата Маттеса), установил М. Райт [404].

В случае -гомоморфизмов со значениями в булевой алгебре счетного типа эти результаты независимо получил Д. А. Владимиров [33]. Общую концепцию (n, m)-дистрибутивности ( n и m — бесконечные кардиналы) для булевой алгебры и ее характеризацию в терминах стоунова компакта см. в книге Р. Сикорского [160]. Слабая -дистрибутивность соответствует случаю, в котором n = m =, где — мощность счетного множества.

(2) Рассмотрим отображение из полной булевой алгебры B в некоторое множество ординалов W On. Предположим, что монотонно, т. е. из x y вытекает (x) -однородными, если (x) = (u) для любого 0 = x Bu. Булева алгебра допускает разложение в прямую сумму -однородных компонент (см. у Д. А. Владимирова [33]).

(3) Булево произведение B := A B из 2.2.7 обладает следующим важным свойством: Если C — произвольная булева алгебра и задано семейство булевых гомоморфизмов h : B C ( A), то существует и притом единственный булев гомоморфизм h : B C такой, что h = h ( A).

(4) Булево произведение B := A B семейства булевых алгебр не будет, вообще говоря, полным, даже если полны все B. Пополнение o(B) не является хорошим претендентом на роль булева произведения семейства полных булевых алгебр (B ), так как для полной булевой алгебры C и для семейства полных гомоморфизмов h : B C гомоморфизм h из (3), вообще говоря, не будет полным и не допускает продолжения до полного гомоморфизма на o(B).

(5) Техника разложения на однородные компоненты (см. 2.6.9 и (2)) независимых подалгебр и булева произведения (см. 2.2.7) и пополнения (см. 2.2.8) имеет свои метрические аналоги, которые играют важную роль в вопросах классификации и представления пространств с мерой и ассоциированных нормированных булевых алгебр, см. книги Д. А. Владимирова [33] и А. А. Самородницкого [161].

2.7.3. (1) Примеры булевых алгебр, приведенные в 2.3.1–2.3.4, хорошо известны, см., например, монографию Р. Сикорского [160]. О борелевских множествах и множествах со свойством Бэра см. книги К. Куратовского [88] и З. Семадени [372].

(2) Общую теорию меры и интеграла см. в следующих монографиях: Н. Бурбаки [20, 21], Н. Данфорд и Дж. Шварц [54], К. Партасарати [153], Г. Е. Шилов и Б. Л. Гуревич [177], П. Халмош [170], Р. Эдвардс [179]. О пространствах с мерой, обладающих свойством прямой суммы, можно прочитать в монографиях Н. Динкуляну [210], А. Ионеску Тулча и К. Ионеску Тулча [252], Л. В. Канторовича и Г. П. Акилова [72], В. Л. Левина [134].

(3) Теория алгебр фон Неймана, возникшая в связи с математическими моделями квантовой механики, изложена в монографиях У. Браттели и Д. Робинсона [17], Р. Кэйдисона и Дж. Рингроуза [263], С. Сакаи [364], М. Такесаки [383].

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

Орторешеткой называют решетку L с нулем, единицей и одноместной операцией (ортодополнения) ( · ) : L L, удовлетворяющей условиям:

Дистрибутивная орторешетка является булевой алгеброй. Элементы x и y орy или, что торешетки называют ортогональными и пишут x y, если x равносильно, y x. Орторешетку L именуют ортомодулярной решеткой или (квантовой) логикой, если для любых x, y L, x y, существует такой элемент z L, что x z и x z = y. Последнее равносильно тому, что из x y следует y = x (y x ). Пример квантовой логики доставляет решетка всех замкнутых подпространств гильбертова пространства с операцией ортогонального дополнения.

(4) Теорема о полноте исчисления высказываний (см. 2.3.10) тесно связана с теоремой Стоуна 2.4.5. Эта связь осуществляется через алгебру Линденбаума — Тарского, подробнее см. у Р. Сикорского [160].

Теорема о полноте имеет место и для исчисления предикатов. Напомним, что замкнутую формулу сигнатуры называют тождественно истинной или логически общезначимой, если она выполняется на любой алгебраической системе (т. е. 2-системе) сигнатуры. Это обстоятельство символически записывают в виде CL.

Теорема Гделя о полноте. Для любой замкнутой формулы исчисления предикатов имеет место эквивалентность Разные подходы к доказательству теоремы Гделя о полноте см., например, в книгах Ю. Л. Ершова и Е. А. Палютина [60], Г. Кейслера и Ч. Чена [74], Э. Мендельсона [146], Е. Расвой и Р. Сикорского [155], Дж. Шенфильда [175].

(5) Булевы алгебры имеют важное прикладное значение при проектировании и расчете сложных электрических сетей и электронных устройств. Следующий пример проясняет, как при этом может использоваться аппарат булевых алгебр, см. [79].

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

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

Введем операции над цепями. Под суммой C D двух цепей C и D понимают цепь, полученную в результате параллельного соединения C и D; это означает, что C D пропускает ток в том и только в том случае, если пропускает ток хотя бы одна из цепей C и D. Произведением C D цепей C и D называют цепь, полученную в результате их последовательного соединения; это означает, что C D пропускает ток лишь тогда, когда пропускают ток обе цепи C и D. Наконец для цепи C символ C обозначает такую цепь, которая пропускает ток лишь в том случае, когда C не пропускает ток. (Технически это делается с помощью переключателя.) Абстрактные электрические цепи, снабженные введенными операциями и должным образом отождествленные, можно рассматривать как булеву алгебру (где и служат соответственно максимальным и минимальным элементами).

2.7.4. (1) В связи с 2.4.4 (2) стоит сформулировать один результат о продолжении булевых гомоморфизмов.

Теорема Сикорского о продолжении. Допустим, что B0 — произвольная подалгебра булевой алгебры B. Тогда любой гомоморфизм из алгебры B0 в полную булеву алгебру B допускает продолжение до гомоморфизма из B в B.

Доказательство можно найти в книге Р. Сикорского [160]. Теорема Сикорского является интерпретацией предложения 1.2.2 (5) в подходящей булевозначной модели (см. 9.4.5 и [52]).

(2) Теорема 2.4.5, установленная М. Стоуном в 1936 году, показывает, что булева алгебра полностью определена своим стоуновым пространством. Точнее говоря, каждое свойство булевой алгебры B, переведенное на топологический язык, становится свойством стоунова компакта St(B) булевой алгебры B. Такой способ изучения булевых алгебр называют реализационным или, более полно, методом стоуновой реализации.

(3) Теорема Сикорского 2.4.8 обеспечивает применимость метода стоуновых реализаций к изучению гомоморфизмов. Приведем формулировку одного факта, придерживаясь обозначений 2.4.8. Подробности см. у Р. Сикорского [160, § 22].

Теорема. Гомоморфизм h будет порядково непрерывным в том и только в том случае, если прообраз любого тощего множества при отображении St(h) является тощим.

2.7.5. (1) Понятие компактификации восходит к К. Каратеодори. Общее определение компактификации (компактного расширения) впервые ввел А. Н. Тихонов в 1929 году. Он же установил, что компактификацией обладают только лишь вполне регулярные (тихоновские) пространства. Стоун-чеховская компактификация (X) является наибольшей компактификацией пространства X в том смысле, что если (Y, j) — какая-нибудь компактификация X (т. е. j : X Y — гомоморфизм и j(X) плотно в Y ), то существует непрерывное отображение k : (X) Y такое, что k = j, см. работы Дж. Келли [75] и Р. Энгелькинга [180].

Экстремально несвязные пространства были введены М. Стоуном. Эти пространства обладают многими замечательными свойствами, см. работы А. В. Архангельского и В. И. Пономарева [10], Л. Гильмана и М. Джерисона [234], З. Семадени [372], Р. Энгелькинга [180]. В частности, экстремально несвязный компакт является стоун-чеховской компактификацией любого своего всюду плотного подмножества (см. [372]).

(2) Понятие абсолюта (см. 2.5.6) можно ввести для более широкого класса топологических пространств. Пусть X и Y — топологические пространства.