В. Г. Кановей

В. А. Любецкий

Современная теория множеств:

борелевские и проективные

множества

Москва

Издательство МЦНМО

2010

УДК 510.22

ББК 22.12

К19

Кановей В. Г., Любецкий В. А.

Современная теория множеств: борелевские и проективК19

ные множества. М.: МЦНМО, 2010. 320 с.

ISBN 978-5-94057-683-9

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

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

ББК 22. Владимир Григорьевич Кановей Василий Александрович Любецкий современная теория множеств:

борелевские и проективные множества Научное издание Издательство Московского центра непрерывного математического образования.

119002, Москва, Большой Власьевский пер., д. 11. Тел. (499) 241-74-83.

Подписано в печать 13.09.2010. Формат 6090 1/16. Бумага офсетная.

Печать офсетная. Печ. л. 20. Тираж 1500 экз. Заказ 1623.

Отпечатано с готовых диапозитивов в ППП Типография „Наука“.

121099, Москва, Шубинский пер., 6.

c Кановей В. Г., Любецкий В. А., 2010.

978-5-94057-683- Оглавление Предисловие Некоторые теоретико-множественные обозначения......... 1 Польские пространства 1.1 Польские пространства.................. 1.2 Категория и свойство Бэра............... 1.3 Бэровское пространство и канторов дисконтинуум.. 1.4 Деревья и замкнутые множества............ 1.5 Расщепляющиеся системы................ 1.6 Совершенные подмножества в польских пространствах 1.7 Другие примеры польских пространств........ 1.8 Более сложные примеры................. 2 Борелевские множества 2.1 Борелевские множества................. 2.2 Простые свойства борелевских множеств....... 2.3 Операция предела..................... 2.4 Отображения польских пространств.......... 2.5 Полунепрерывность и теорема Адяна......... 2.6 Борелевская изоморфность польских пространств.. 2.7 Теорема иерархии и универсальные множества.... 3 A-множества 3.1 A-операция и A-множества............... 3.2 Простые свойства A-множеств............. 3.3 A-множества как образы и проекции.......... 3.4 Теорема о совершенном ядре.............. 3.5 Суперсовершенные подмножества........... 3.6 C-множества........................ 3.7 Проективные множества................. 4 ОГЛАВЛЕНИЕ 4 CA-множества и ординалы 4.1 Деревья и ранги...................... 4.2 Вложения деревьев и сравнение рангов........ 4.3 Дополнения A-множеств. Конституанты........ 4.4 Принцип ограничения и его следствия......... 4.5 Борелевские и B-измеримые отображения....... 4.6 Решета........................... 4.7 Фундированные отношения............... 4.8 Полные предупорядочения и нормы.......... 10.7 О множествах, накрываемых -компактными множе 13.4 О несчетных последовательностях борелевских мно 15 Проективная иерархия в детерминированном универсуме 15.1 Первая теорема периодичности............. 15.3 Вторая теорема периодичности. Лестницы...... 15.4 Доказательство свойства лестницы........... 15.5 Третья теорема периодичности............. 15.6 Теорема о выборе выигрывающей стратегии..... Суммируемые идеалы и идеал нулевой плотности...... Предисловие Современную теорию множеств трудно изложить иначе чем в нескольких книгах, каждая из которых посвящена одному из ее наи более актуальных разделов. Желательно, чтобы эти книги можно было читать независимо друг от друга и при этом от читателя не требовалась бы никакая специальная подготовка, по крайней мере в части понимания основного материала этих книг. Следуя этому пла ну, мы опубликовали первую книгу такой серии Начала дескрип тивной динамики [13], посвященную одному из важных разделов современной теории множеств дескриптивной теории множеств.

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

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

В гл. 1 мы начинаем с введения в теорию польских пространств, т. е. сепарабельных полных метрических пространств. В дескриптив ной теории изучаются множества именно в таких пространствах. К польским пространствам относятся вещественная прямая R, бэров ское пространство NN, канторов дисконтинуум 2N. Рассматриваются и более сложные польские пространства.

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

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

В гл. 4 рассматриваются множества, которые являются допол нениями к A-множествам. Они называются CA-множествами. CA множества невозможно изучать без использования таких понятий, как счетные ординалы (трансфинитные числа), фундированные де ревья, ранги. Эти понятия используются также при разложении CA множества на борелевские конституанты, при доказательстве тео ремы Суслина о том, что множество, которое является одновременно A- и CA-множеством, борелевское множество, при изучении фун дированных отношений и норм.

Глава 5 содержит обзор некоторых важных понятий дескриптив ной теории множеств. Здесь мы вводим счетно-аддитивные меры и доказываем теоремы измеримости и наличия свойства Бэра у A-множеств, излагаем метод построения неизмеримых множеств по Бернштейну, даем краткое введение в теорию борелевской сводимо сти отношений эквивалентности и действий групп, и заканчиваем наброском доказательства теоремы Хаусдорфа о щели.

В целом главы 1 – 5 книги соответствует тому, что обычно назы вается классическими методами дескриптивной теории множеств.

Современный подход, включающий методы теории рекурсии, рас сматривается в гл. 6, где мы вводим принятые сейчас обозначения проективных классов и устанавливаем замкнутость этих классов от носительно некоторых операций. В рамках такого подхода мы раз виваем теорию 1 -множеств (бывших A-множеств) и 1 -множеств (бывших CA-множеств) в гл. 7 и 8, доказывая, в частности, теоремы отделимости, редукции, униформизации и нормированности для первого проективного уровня.

Современная дескриптивная теория множеств не может быть раз вита без обращения к эффективным методам. Чтобы пояснить суть дела, заметим, что класс 1 -множеств (т. е. A-множеств) в бэ ровском пространстве NN совпадает с множеством всех проекций замкнутых множеств пространства NN NN на одну из его осей. За мкнутые множества образуют класс 1. Каждое замкнутое множе ство F NN NN эффективно определяется некоторым множеством u(F ) N натуральных чисел (например, посредством перечисления номеров тех бэровских прямоугольников в NN NN, которые не пере секаются с F ). Если множество u(F ) рекурсивно (или, что то же са мое, разрешимо), то F называется множеством класса 0, а его про екция на первую ось N этого пространства множеством класса 1. Если же для некоторого элемента p NN множество u(F ) рекур сивно относительно p, то F называется множеством класса 0 (p), а его проекция на первую ось N множеством класса 1 (p). Тогда 1 = pNN 1 (p), однако все классы вида 1 (p) счетны, а класс 1, т. е. их объединение, несчетен. Эффективные методы в дескрип тивной теории множеств позволяют рассматривать, при помощи со ответствующих методов, не только обычные проективные классы, например класс 1, но и эффективные классы, например 1 (p) для различных параметров p N и, в частности, класс 1. Последний класс соответствует случаю, когда p любая рекурсивная функция из NN, например, тождественный нуль.

На этом пути возникают методы и задачи, не имеющие аналогов для обычных проективных классов. В частности, в гл. 9 исследу ется природа счетного множества, состоящего только из 1 -точек x NN, которое само является множеством класса 1. Там же рас сматриваются вопросы эффективного кодирования борелевских мно жеств.

Следующая глава 10 знакомит читателя с еще одним важным методом современной эффективной дескриптивной теории мно жеств: топологией Ганди–Харрингтона на NN, которая порождена совокупностью всех непустых 1 -множеств X NN. Эта тополо гия, очевидно, усиливает обычную польскую топологию простран ства NN, но не является польской и вообще не метризуема, однако об ладает свойством Шоке, сближающим ее с польскими топологиями в некоторых важных вопросах. Эта топология имеет многообразные применения в теории 1 -множеств. Например, с ее помощью дока зывается следующая теорема, уточняющая теорему Суслина о совер шенных подмножествах несчетных A-множеств: если 1 -множество X N содержит точку не класса 1, то X содержит совершен ное подмножество. Таким образом, мы имеем критерий несчетности 1 -множества: наличие в нем точки не из класса 1. Подобные ре зультаты получены в гл. 10 также в отношении некоторых других свойств 1 -множеств, связанных с компактностью и -компактно стью (вместо счетности).

Результаты гл. 9 и 10 находят применение в гл. 11, где изучаются борелевские множества и 1 -множества со специальными сечения ми. Речь идет о множествах P, лежащих, например, в пространстве NN NN (или в произведении любых двух польских пространств) и таких, что каждое сечение Px = {y : x, y P }, x NN имеет одно определенное свойство, например является не более чем счет ным или не тощим множеством, и пр. Для ряда подобных свойств удается доказать, что борелевские множества P с таким свойством сечений обязательно имеют борелевские проекции, в то время как проекции произвольных борелевских множеств могут быть и небо релевскими 1 -множествами. И это только один тип результатов о множествах со специальными сечениями, другие касаются свойств униформизации, расщепления и пр.

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

Эти результаты отсутствовали в нашей книге Начала дескриптив ной динамики [13], так как там для их доказательства не хватало развитых здесь методов.

Содержание книги до гл. 12 включительно связано в основном с первым проективным уровнем, т. е. c классами 1, 1, 1 (A-мно жеств, CA-множеств, борелевских множеств, соответственно), и именно для первого проективного уровня работают классические ме тоды дескриптивной теории множеств. Уже на втором проективном уровне теоремы, полученные для первого уровня, большей частью не имеют места, а те немногие результаты, которые остаются верными, выглядят по-другому. Для множеств второго проективного уровня возникают проблемы, которые в принципе не имеют решения. Напри мер, проблемы их измеримости и наличия у них свойства Бэра. Об этих проблемах мы говорим в главе 13. Их решение в очень неожи данной форме было получено много лет спустя после того, как они были сформулированы Н. Н. Лузиным в 1920х годах. А именно, было доказано, что проблема измеримости множеств второго проективно го уровня и другие подобные проблемы вообще неразрешимы, т. е. на поставленные Лузиным вопросы нельзя дать ответ да или нет (в рамках обычной системы аксиом теории множеств 1 ). Доказатель ство неразрешимости потребовало разработки таких важнейших тео ретико-множественных методов, как конструктивность и форсинг, изложение которых не вошло в эту книгу из соображений объема.

Авторы думают, что и с методической точки зрения изучение этих весьма сложных доказательств лучше начинать после изучения ма териала этой книги (и, возможно, книги [13]). Поэтому теоремы о неразрешимости сопровождаются здесь не полными доказательства ми, а только ссылкой на нашу статью [11]. Эти доказательства мог ли бы войти в третью книгу нашей серии, посвященную доказатель ствам неразрешимости вопросов Лузина и современному состоянию метода форсинга (вынуждения).

Естественно, теоремы о неразрешимости приводят к мысли уси лить аксиоматику ZFC какой-нибудь аксиомой, которая позволит решить вопросы Лузина. Было предложено несколько аксиом такого рода, например аксиома конструктивности, аксиома Мартина, акси омы больших кардиналов и т. д. Однако несомненное преимущество в этом списке, как с точки зрения естественности и мотивирован ности самой аксиомы, так и в плане богатой картины математиче ских следствий, имеют две аксиомы: аксиома детерминированности AD и аксиома проективной детерминированности PD. Эти аксио мы рассматриваются в заключительных главах 14 и 15. Всё же по тем или иным причинам ни одна из них не принята в состав обыч ной содержательной математики. И упомянутые проблемы Лузи на остаются неразрешимыми (или, как иногда говорят, абсолютно неразрешимыми).

1 Здесь важно, что рамках такой системы аксиом, например аксиоматики тео рии множеств Цермело–Френкеля ZFC, формулируются и доказываются все содержательные математические результаты (а следовательно, и результаты естественных наук, выразимые на языке математики). Таким образом, нет такой аксиомы, которая могла бы помочь в решении вопросов Лузина и при этом не изменила обычную содержательную математику, а являлась бы ее естествен ной частью. Конечно, тут мы подходим к грани некоторой философской дис куссии: что есть содержательная математика. Практический ответ: это есть математика, которая излагается в рамках аксиоматики ZFC. Правда, в эту ак сиоматику не включены приемы работы с особо большими множествами (типа множества всех абелевых групп и т. п.; чтобы подчеркнуть отличие от обыч ных, маленьких множеств, эти особо большие множества еще называют сово купностями или классами, употребляя последнее слово в ином смысле, чем оно использовалось выше). Но если расширить ZFC средствами, которые обеспечи вают работу с совокупностями, то и тогда вопросы Лузина останутся неразреши мыми. То же самое остается верным, если расширить ZFC возможностью рабо тать с совокупностями совокупностей и т. д. Так что неразрешимость вопросов Лузина не связана с тем, сколь большие множества разрешается использовать.

Она возникает на уровне уже одних только вещественных чисел.

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

В качестве приложения приведено переработанное доказатель ство одной теоремы нашей книги Современная теория множеств:

начала дескриптивной динамики [13], которое в первоначальном изложении [13, §5г] представило некоторые ключевые моменты без достаточных деталей.

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

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

Работа авторов над книгой была частично поддержана грантами:

РФФИ 07-01-00445 и МНТЦ 3807.

Авторы посвящают книгу своим родителям; становясь старше, они всё чаще думают о них.

Некоторые теоретико-множественные обозначения • P(A) = {x : x A} множество всех подмножеств, множе ство-степень множества A;

• N = {0, 1, 2,...} • 2 = {0, 1}, и вообще n = {0, 1,..., n 1}, т. е. каждое натураль ное число множество всех меньших натуральных чисел;

• кортеж конечная последовательность любого вида;

• X Y = {f : f есть функция из Y в X};

• в частности, X n множество всех функций s из множества n = {0, 1,..., n 1} в X, т. е. множество всех кортежей длины n из элементов множества X ;

• при X = 2 = {0, 1} через 2n обозначается множество всех диа дических (т. е. с членами 0, 1) кортежей длины n; не путать с арифметической степенью;

найдется такой номер kn N, что соотношение (ai, aj ) <, т. е. ai n = aj n, выполнено для любых i, j > kn. Это дает нам возможность определить un = ak n для любого n, где k > kn произвольно, так что un кортеж из n натуральных чисел, удовлетворяющий условию un = ak n для всех k > kn. По очевидным соображениям мы имеем un un+1 (т. е. un+1 продолжает un ) для всех n. Следовательно, имеется одна определенная точка a NN, удовлетворяющая условию un = a n для всех n. Для нее согласно сказанному выше выполнено равенство a n = ai n, т. е. (a, ak ) < n для всех n и k > kn.

Это и означает, что в метрике (1) имеет место a = limk ak, что и требовалось.

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