О классификации счетных булевых термов

Алгебра и логика, 44, № 2 (2005), 173—197

УДК 510.532

О КЛАССИФИКАЦИИ СЧЁТНЫХ БУЛЕВЫХ ТЕРМОВ В. Л. СЕЛИВАНОВ § 1. Предварительные сведения Пусть {Σ0α }α<ω1 — борелевская иерархия подмножеств канторовского пространства 2ω (здесь ω1 — это первый несчётный ординал). Как обычно, Π0α — двойственный класс для класса Σ0α , а ∆0α = Σ0α ∩ Π0α — соответствующий самодвойственный класс. Класс всех борелевских множеств S Σ0α . обозначим B = α<ω1

Уровни иерархии Бореля, как и многие другие классы, изучаемые

в дескриптивной теории множеств, можно определить посредством подходящих (вообще говоря, бесконечноместных) теоретико множественных операций. Определим естественный класс таких операций, называемых ω1 термами, по индукции: константы 0, 1 и переменные vk (k < ω) являются ω1 -термами; если ti (i < ω) — ω1 -термы, то выражения t¯0 , t0 ∪ t1 , t0 ∩ t1 , T S ti также будут ω1 -термами. ti и i<ω

i<ω

Если t = t(vk ) — ω1 -терм, обозначим через t({Ak }) значение терма t,

полученное при присваивании переменной vk (k < ω) значения Ak ⊆ 2ω . Пусть t(Σ01 ) — множество всех значений t({Ak }), где Ak ∈ Σ01 для любого k < ω. Аналогичное обозначение t(C) используется также для других типов термов t и классов множеств C. Как оказалось, классы вида t(Σ01 ) удобно характеризовать в терминах сводимости Вэджа, т. е. предпорядка ≤W на классе P (2ω ) всех подмножеств множества 2ω , определяемого как A ≤W B ↔ A = f −1 (B) c Сибиpский фонд алгебpы и логики, 2005

174

В. Л. Селиванов

для подходящей непрерывной функции f : 2ω → 2ω . Классом Вэджа называется главный идеал вида {X | X ≤W A} для любого фиксированного множества A ⊆ 2ω . Класс Вэджа называется борелевским, если множе¯ где ство A является борелевским, и несамодвойственным, если A 6≤W A, A = 2ω \ A — это дополнение множества A. ТЕОРЕМА 1.1 [1]. Любое C ⊆ P (2ω ) является несомодвойственным борелевским классом Вэджа тогда и только тогда, когда C = t(Σ01 ) для некоторого ω1 -терма t. Эта теорема следует из результата, установленного в [2, 3]. В данной статье рассматривается проблема характеризации ω1 термов t, удовлетворяющих равенству C = t(Σ01 ), для данного борелевского класса Вэджа C (точная формулировка проблемы приводится в следующем разделе). Заметим, что в [1] аналогичные вопросы изучались для конечных булевых и типизированных булевых термов. В. Вэдж и Д. Мартин показали (см. [3]), что структура (B; ≤W ) фундирована, а для любых A, B ∈ B выполняется A ≤W B или B ≤W ≤W A (структуры, обладающие этими двумя свойствами, называются почти вполне упорядоченными). В. Вэдж также вычислил соответствующий (большой) ординал ν. В [4, 5] установлено, что для любого несамодвойственного борелевского класса Вэджа C в точности один из классов C, co(C) имеет свойство отделимости [6]. Через co(C) = {X | X ∈ C} обозначается двойственный класс для C. Эти результаты позволяют определить иерархию Вэджа (борелевских множеств) как последовательность {Σα }α<ν всех несамодвойственных борелевских классов Вэджа, не имеющих свойства отделимости и удовлетворяющих для всех α < β < ν строгому включению Σα ⊂ ∆β . Как обычно, полагаем Πα = co(Σα ) и ∆α = Σα ∩ Πα . Заметим, что Σα \ Πα , Πα \ Σα , ∆α+1 \ (Σα ∪ Πα ), где α < ν, — это в точности классы эквивалентности, индуцированной предпорядком ≤W на B (они известны как степени Вэджа).

О классификации счётных булевых термов

175

Заметим, что Σα и Σ0α в большинстве случаев не совпадают. На самом деле справедливы, например, равенства Σω1 = Σ02 , Σωω1 = Σ03 и т. д. 1

Далее в этом параграфе приводятся некоторые известные факты о булевых термах. В §§ 2 и 3 определяются и изучаются борелевская и разностная иерархии в пространстве P ω всех подмножеств ω с топологией Скотта (заметим, что пространства P ω и 2ω определены по сути на одном и том же множестве, но топологически различны). Результаты этих параграфов основываются на работах [7, 8]. В § 4 рассматривается сводимость Вэджа в пространстве P ω. В § 5 приводится решение основной проблемы данной статьи для некоторых уровней иерархии Вэджа, в частности, для всех уровней разностной иерархии Хаусдорфа. В § 6 обсуждаются некоторые смежные факты и открытые проблемы. Зафиксируем обозначения. Буквами α, β, γ обозначаются ординалы, буквами ξ, η, ζ — элементы 2ω (точки), через σ, τ — конечные цепочки натуральных чисел, буквами A, B, X, Y, Z — подмножества 2ω (точечные множества), буквами A, B, C — подмножества P (2ω ) (точечные классы), через f, g, h — функции на 2ω (а также на некоторых других множествах). Множество ξ ⊆ ω обычным образом отождествляется с последовательностью нулей и единиц: ξ(n) = 1 для n ∈ ξ и ξ(n) = 0 в противном случае, n < ω. Полагаем [ξ, η] = {ζ ⊆ ω | ξ ⊆ ζ ⊆ η} и (ξ, η] = {ζ ⊆ ω | ξ ⊂ ζ ⊆ η}. Через Fin обозначается класс всех конечных подмножеств множества ω. Пусть ω ∗ — множество всех конечных последовательностей (цепочек) натуральных чисел. Пустую цепочку обозначим через ∅, цепочку из n нулей — через 0n , конкатенацию цепочек σ, τ — через σ aτ или просто στ , длину цепочки σ — через lh(σ). Запись σ ⊑ τ используется, когда цепочка σ является начальным сегментом цепочки τ . Введённые понятия применимы также к цепочкам из нулей и единиц, множество которых обозначим через 2∗ . Для σ ∈ 2∗ и ξ ∈ 2ω запись σ ⊑ ξ используется, когда σ является начальным сегментом функции ξ, рассматриваемой как бесконечная цепочка нулей и единиц. Установим связь ω1 -термов с теоретико множественными операция-

176

В. Л. Селиванов

ми, которые были популярны в классической дескриптивной теории множеств. Напомним, что операции счётного объединения и пересечения, а также их итерации впервые рассмотрели Э. Борель и А. Лебег при исследовании борелевской иерархии. П. С. Александров и М. Я. Суслин ввели и изучили A-операцию, важную для исследования аналитических множеств. А. Н. Колмогоров и Ф. Хаусдорф независимо определили понятие позитивных аналитических (или δs-) операций, обобщающих все упомянутые выше операции. Ф. Хаусдорф определил разностные операции — вероятно, первые примеры систематически изучавшихся непозитивных операций. Л. В. Канторович и Е. М. Ливенсон [9] определили ещё более общее понятие операции (следуя [3], будем называть её ω-местной булевой): Любому X ⊆ 2ω сопоставим бесконечный терм dX от переменных vk (k < ω) по правилу dX = dX (vk ) =

[

ξ∈X



cξ , где cξ = 

\

ξ(k)=1





vk  ∩ 

\

ξ(k)=0



vk  .

Заметим, что cξ — бесконечные аналоги элементарных конъюнкций, а dX — дизъюнктивных нормальных форм в логике высказываний. Терм dX обычным образом индуцирует ω-местную булеву операцию dX : P (2ω )ω → P (2ω ) на P (2ω ) (на самом деле на любой полной булевой алгебре). Два бесконечных булевых терма назовём эквивалентными, если они задают одну и ту же бесконечноместную операцию в любой полной булевой алгебре. ТЕОРЕМА 1.2 [1]. Любой ω1 -терм эквивалентен терму dX для некоторого борелевского множества X ⊆ 2ω , и наоборот. Итак, ω-местные булевы операции dX (X ∈ B) дают каноническое представление для ω1 -термов. Согласно одной теореме Вэджа [2, 3], любой несамодвойственный борелевский класс Вэджа представим в виде dX (Σ01 ) для подходящего X (из леммы 1.3(ii) легко следует, что такое X с необходимостью будет борелевским, см. теор. 5.1(i)). Попытаемся описать точечные классы типа {X | dX (Σ01 ) ⊆ Σα } и {X | dX (Σ01 ) = Σα }, α < ν.

О классификации счётных булевых термов

177

Большинство результатов статьи формулируются только для вопросов первого типа (для случая включения). Ответ на вопросы второго типа (для случая равенства) является обычно легким следствием ответа на вопрос первого типа и включений уровней иерархии Вэджа (типичный пример — следствие 5.2). Сформулируем некоторые очевидные и хорошо известные свойства введённых понятий. ЛЕММА 1.3. Имеют место следующие утверждения: S (i) cξ ({Ai }) = 2ω и cξ ({Ai }) ∩ cη ({Ai }) = ∅ для ξ 6= η; ξ

(ii) X = dX ({Ai }), где Ai = {ξ ⊆ ω | i ∈ ξ}; T Ai ; (iii) d[ξ,ω] ({Ai }) = i∈ξ

(iv) для любой последовательности {Ai }i∈ω подмножеств множе-

ства 2ω функция X 7→ dX ({Ai }) является эндоморфизмом полной булевой алгебры P (2ω ). Теорема 1.4 даёт решение проблемы данной статьи в случае, когда вместо класса Σ01 берётся класс ∆01 всех открыто-замкнутых множеств. Насколько известно автору, доказательство ранее не было опубликовано, приведём его здесь для полноты изложения. ТЕОРЕМА 1.4 [10]. Для любого X ⊆ 2ω справедливо dX (∆01 ) = = {Y | Y ≤W X}. ДОКАЗАТЕЛЬСТВО. Сначала проверим, что Y ≤W X влечёт Y ∈ ∈ dX (∆01 ). Пусть g : 2ω → 2ω — непрерывная функция, удовлетворяющая равенству Y = g −1 (X). Тогда Y = g −1 (dX ({Ai })) = dX ({g −1 (Ai )}), где Ai — множества из леммы 1.3(ii). Поскольку Ai ∈ ∆01 , получаем Y ∈ ∈ dX (∆01 ). Для проверки обратного включения возьмём произвольное Y ∈ ∈ dX (∆01 ). Пусть Vi — ∆01 -множества со свойством Y = dX ({Vi }). Поскольку Vi лежат в ∆01 (т. е. являются конечными объединениями множеств вида {ξ | σ ⊑ ξ}, σ ∈ 2∗ ), функция f (ξ) = {i | ξ ∈ Vi } непрерывна. По опре-

178

В. Л. Селиванов

делению dX ({Vi }), включение ξ ∈ Y верно тогда и только тогда, когда f (ξ) ∈ X. Итак, Y ≤W X, что завершает доказательство. Теорему 1.4 можно переформулировать как СЛЕДСТВИЕ 1.5. Отображение X 7→ dX (∆01 ) является изоморфизмом структуры всех степеней Вэджа в 2ω на структуру всех классов Вэджа с отношением включения.

§ 2. Борелевская иерархия в P ω В этом параграфе исследуется борелевская иерархия в пространстве P ω, образованном множеством 2ω (отождествляемом с P (ω)), и топологией Скотта. Ниже всегда предполагается, что пространство P ω снабжено топологией Скотта, а пространство 2ω — канторовой топологией. Напомним, что базисные открытые множества топологии Скотта — это множества вида [ξ, ω], где ξ — конечное подмножество ω. Множество A ⊆ 2ω открыто в P ω тогда и только тогда, когда (A; ⊆) замкнуто вверх, а для любого ξ ∈ A найдётся конечное множество η ∈ A со свойством η ⊆ ξ. Функция f : P ω → P ωнепрерывна тогда и только тогда, когда ξ ⊆ η  S S ξi = f (ξi ) для любой последовательности влечёт f (ξ) ⊆ f (η) и f ξ0 ⊆ ξ1 ⊆ . . . .

i

i

Базисные открытые множества топологии Кантора — это множества вида {ξ | σ ⊑ ξ}, σ ∈ 2∗ . Функция f : 2ω → 2ω непрерывна, если при любых ξ ∈ 2ω и n ∈ ω значение f (ξ)(n) определяется по некоторому конечному сегменту σ ⊑ ξ, σ ∈ 2∗ , последовательности ξ. ОПРЕДЕЛЕНИЕ 2.1. Индукцией по α зададим последовательность {S0α }α<ω1 точечных классов: S00 = {∅}, S01 — класс всех открытых множеств, S02 — класс всех счётных объединений конечных булевых комбинаций S01 -множеств и S0α — класс всех счётных объединений множеств из S {co(S0β ) | β < α} для α > 2.

Последовательность {S0α }α<ω1 называется борелевской иерархией в ˜0 = S0 ∩ co(S0 ) — уровнями борелевской P ω, а классы S0α , co(S0α ) и S α α α

иерархии. Нестандартные обозначения уровней борелевской иерархии в

О классификации счётных булевых термов

179

P ω объясняются необходимостью отличать её от борелевской иерархии {Σ0α } в канторовском пространстве 2ω . Соотношения между введёнными уровнями оказываются вполне традиционными: ˜0 . ПРЕДЛОЖЕНИЕ 2.2. Для всех α < β < ω1 справедливо S0α ⊆ S β Следующее предложение объясняет связь пространства P ω с рассматриваемой проблемой. ПРЕДЛОЖЕНИЕ 2.3. (i) Для любого β < ω1 из X ∈ S0β вытекает dX (Σ01 ) ⊆ Σ0β . (ii) Для любых 0 < β < ω1 и ω1 -терма t из X ∈ t(S0β ) вытекает dX (Σ01 ) ⊆ t(Σ0β ). ДОКАЗАТЕЛЬСТВО. (i) Случай α = 0 тривиален, поскольку S = {∅}. Пусть α = 1, X ∈ S01 . Тогда X = Xk для некоторой

d∅(Σ01 )

k

последовательности {Xk }k<ω базисных открытых множеств. Необходимо

показать, что dX ({Ai }) ∈ Σ01 для любой последовательности {Ai } Σ01 S множеств. По лемме 1.3(iv), dX ({Ai }) = dXk ({Ai }), и достаточно покаk

зать, что dY ({Ai }) ∈ Σ01 для любого базисного открытого множества Y в

топологии Скотта. Выберем ξ ∈ Fin так, чтобы Y = [ξ, ω]. По лемме 1.3(iii), T Ai , значит, dY ({Ai }) является конечным пересечением Σ01 dY ({Ai }) = i∈ξ

множеств, откуда dY ({Ai }) ∈ Σ01 .

Пусть теперь X ∈ S02 , тогда X =

S

Xk для некоторой последователь-

ности {Xk } разностей S01 -множеств, Xk = Yk \ Zk . В силу леммы 1.3(iv) достаточно показать, что dXk ({Ai }) ∈ Σ02 для любого k. По той же причине dXk ({Ai }) = dYk ({Ai }) \ dZk ({Ai }) ∈ ∆02 ⊆ Σ02 . При α > 2 доказательство проводится аналогично, с использованием индукции по α. (ii) Пусть X ∈ t(S0β ), тогда X = t({Xk }) для некоторой последовательности {Xk } S0β -множеств. Необходимо показать, что dX ({Ai }) ∈ ∈ t(Σ0β ) для любой последовательности {Ai } Σ01 -множеств. По лемме 1.3(iv) dX ({Ai }) = t({dXk ({Ai })}). По (i) dXk ({Ai }) ∈ Σ0β для любого k < ω, поэтому dX ({Ai }) ∈ t(Σ0β ). Предложение доказано.

180

В. Л. Селиванов Теперь установим связь между борелевскими иерархиями в P ω и 2ω . ПРЕДЛОЖЕНИЕ 2.4. (i) Для любого α < ω1 справедливо S0α ⊆

⊆ Σ0α ⊆ S01+α ; S 0 S 0 (ii) Sn = Σn ; n<ω

n<ω

(iii) для любого бесконечного ординала α < ω1 справедливо S0α = Σ0α ;

(iv) для любого 0 < n < ω справедливо S0n 6⊆ Π0n и Π0n 6⊆ S0n+1 . ДОКАЗАТЕЛЬСТВО. (i) Случай α = 0 тривиален. Пусть α = 1. Любое базисное открытое множество [η, ω] (η ∈ Fin) в P ω лежит в ∆01 , поэтому S01 ⊆ Σ01 . Пусть теперь A ∈ ∆01 , тогда A = {ξ | σ ⊑ ξ} для некоторого σ ∈ 2∗ . Значит, A является разностью двух S01 -множеств, откуда Σ01 ⊆ S02 . При α > 1 доказательство проводится по индукции. (ii), (iii) Требуемые утверждения вытекают из п. (i). (iv) Сначала построим множества An ∈ S0n \ Π0n . Пусть = {ξ | ∃x1 ∀x2 . . . (ξhx1 , . . . , x2n i = 0)},

A2n

A2n+1 = {ξ | ∃x1 ∀x2 . . . (ξhx1 , . . . , x2n+1 i = 1)}, где hx1 , . . . , xn i — биективное канторовское кодирование n-ок натуральных чисел. Из [11, лемма 2.10] следует, что An является W -полным в Σ0n , поэтому An 6∈ Π0n . Остается показать, что An ∈ S0n . Имеем A1 = {ξ | ξ 6= ∅}; A2 =

\

Yx1 , где Yx1 = {ξ | ∃x2 (hx1 , x2 i ∈ ξ)},

x1

A3 =

[\

Yx1 x2 , где Yx1 x2 = {ξ | ∃x3 (hx1 , x2 , x3 i ∈ ξ)},

x1 x2

и т. д. Поскольку множества A1 , Yx1 , Yx1 x2 , . . . лежат в S01 , справедливо A1 ∈ S01 , A2 ∈ co(S02 ), A3 ∈ S03 , . . . , т. е. An ∈ S0n для всех n. Остаётся найти множества Bn ∈ Π0n \ S0n+1 . Пусть B1

= {ξ | ∀x1 (ξ(x1 ) = 1)},

B 2 = {ξ | ∃x1 ∀x2 (ξhx1 , x2 i = 1)}, B3

= {ξ | ∀x1 ∃x2 ∀x3 (ξhx1 , x2 , x3 i = 1)},

О классификации счётных булевых термов

181

и т. д. Как и выше, Bn ∈ Π0n и остаётся проверить соотношение Bn 6∈ S0n+1 . По предложению 2.3(i) достаточно показать, что dBn (Σ01 ) = Π0n+1 . Имеем B1 = {ω}, B 2 =

[

Zx1 , B3 =

x1

\[

Zx1 x2 , . . . ,

x1 x2

где Zx1 = {ξ | {x1 } × ω ⊆ ξ}, Zx1 x2 = {ξ | {x1 } × {x2 } × ω ⊆ ξ}, . . . и X1 × . . . × Xn = {hx1 , . . . , xn i | x1 ∈ X1 , . . . , xn ∈ Xn }. По лемме 1.3(iii), dB1 ({Ai })

=

T

Ax1 ,

x1

dZx1 ({Ai })

=

T x2

dZx1 x2 ({Ai }) =

T x3

Ahx1 ,x2 i , Ahx1 ,x2 ,x3 i , . . . .

По лемме 1.3(iv), dB1 ({Ai }) =

T

Ax1 ,

x1

dB 2 ({Ai }) = dB3 ({Ai }) =

ST x1 x2

Ahx1 ,x2 i ,

TST x1 x2 x3

Ahx1 ,x2 ,x3 i , . . . .

Из определения классов Π02 , Σ03 , . . . вытекает, что dB1 (Σ01 ) = Π02 , dB 2 (Σ01 ) = Σ03 , dB3 (Σ01 ) = Π04 . . . . Итак, dBn (Σ01 ) = Π0n+1 для всех n. Это завершает доказательство предложения. Напомним (используя альтернативную терминологию из [8]) некото˜0 . рые понятия из [7], имеющие отношение к классу S 2 ОПРЕДЕЛЕНИЕ 2.5. Множество A ⊆ 2ω называется (слабо) аппроксимируемым, если для любого ξ ∈ A найдётся конечное множество η ⊆ ξ с условием [η, ξ] ⊆ A (соответственно, [η, ξ] ∩ Fin ⊆ A). ˜0 (оно затем было обобщено в [8]) даёт Полезное описание класса S 2

182

В. Л. Селиванов ТЕОРЕМА 2.6 [7]. Равносильны следующие условия: ˜0 ; A∈S 2

множества A и A аппроксимируемы; множества A и A слабо аппроксимируемы. Множество A ⊆ 2ω называется замкнутым относительно цепей конечных элементов [7], если для любой возрастающей цепи η0 ⊆ η1 ⊆ . . . S конечных множеств из A объединение ηi принадлежит A. i

ПРЕДЛОЖЕНИЕ 2.7 [7]. Множество A ⊆ 2ω слабо аппрокси-

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

§ 3. Разностная иерархия в P ω В этом параграфе приводятся факты о разностной иерархии в P ω, большинство из которых являются частными случаями результатов из [8]. Сначала напомним определение разностных операций Хаусдорфа. Ординал α называется нечётным, если α = 2β + 1 для некоторого ординала β; ординалы, не являющиеся нечётными, называют чётными. Пусть r(α) = 0, если ординал α чётный, r(α) = 1 в противном случае. ОПРЕДЕЛЕНИЕ 3.1. (i) Для любого ординала α определим операцию Dα , сопоставляющую последовательности множеств вида {Aβ }β<α множество Dα ({Aβ }β<α ) =

  Aγ β < α, r(β) 6= r(α) . Aβ \   γ<β

 [

[

(ii) Для любых ординала α и класса множеств A через Dα (A) обозначается класс всех множеств Dα ({Aβ }β<α ), где Aβ ∈ A при всех β < α. Если класс A замкнут относительно счётных объединений (как, например, классы S0α ), то класс Dα (A) совпадает с классом всех множеств Dα ({Aβ }β<α ), где Aβ ∈ A для всех β < α, Aβ ⊆ Aγ для β < γ < α. Определим разностную иерархию Хаусдорфа в P ω (см. также [7]).

О классификации счётных булевых термов

183

ОПРЕДЕЛЕНИЕ 3.2. (i) Для любого 0 < β < ω1 последовательность {Dα (S0β )}α<ω1 называют разностной иерархией над S0β . (ii) Разностную иерархию над S01 называют просто разностной иерархией и обозначают {S−1 α }α<ω1 . ˜−1 = S−1 ∩ co(S−1 ). Для случая польских Как и в § 2, обозначим S α α α пространств хорошо известно (сразу вытекает из определений) следующее ПРЕДЛОЖЕНИЕ 3.3. (i) Для всех α < γ < ω1 и 0 < β < ω1 ˜−1 выполняется Dα (S0β ) ∪ co(Dα (S0β )) ⊆ Dγ (S0β ). В частности, S−1 α ⊆ Sγ . S ˜0 . (ii) Для любого 0 < β < ω1 выполняется {Dα (S0β ) | α < ω1 } ⊆ S β+1 S −1 0 ˜ В частности, {S | α < ω1 } ⊆ S . α

2

ЗАМЕЧАНИЕ. Приведённые выше результаты о разностной иерар-

хии справедливы в произвольном топологическом пространстве. Результаты, приводимые далее, являются более специальными. Следующее непосредственное следствие предложения 2.3 связывает разностную иерархию в P ω с рассматриваемой проблемой. СЛЕДСТВИЕ 3.4. Для всех α < ω1 и 0 < β < ω1 из X ∈ Dα (S0β ) 0 −1 следует dX (Σ01 ) ⊆ Dα (Σ0β ). В частности, X ∈ S−1 α влечёт dX (Σ1 ) ⊆ Σα .

Из предложения 2.4 сразу вытекает следующее соотношение между разностными иерархиями в 2ω и P ω. Через Σ−1 α (α < ω1 ) обозначаются уровни разностной иерархии Хаусдорфа в канторовском пространстве. В [3] установлено, что иерархия Хаусдорфа является начальным сегментом иерархии Вэджа, т. е. Σ−1 α = Σα для любого α < ω1 . ПРЕДЛОЖЕНИЕ 3.5. (i) Для всех α < ω1 и 0 < β < ω1 справед−1 ливо Dα (S0β ) ⊆ Dα (Σ0β ). В частности, S−1 α ⊆ Σα .

(ii) Для всех α < ω1 и ω 6 β < ω1 справедливо Dα (S0β ) = Dα (Σ0β ). Напомним характеризацию уровней разностной иерархии в терминах деревьев [8]. Пусть ω ∗ — множество всех цепочек натуральных чисел. Под деревом понимается любое непустое множество T ⊆ ω ∗ , замкнутое вниз относительно ⊑. Для дерева T и цепочки τ ∈ T через T (τ ) обозначается дерево {σ | τ aσ ∈ T }. Путём через дерево T называется функция f : ω → ω такая, что цепочка (f (0), . . . , f (n − 1)) принадлежит T для любого

184

В. Л. Селиванов

n < ω. Максимальные элементы в (T ; ⊑) называют листьями дерева T . Множество всех листьев T обозначим leaf(T ). Дерево T называется фундированным, если частичный порядок (T ; ⊒) фундирован, т. е. нет пути через дерево T . Как и для любого фундированного частичного порядка, существует каноническая функция ранга rkT из фундированного дерева T в ординалы, определяемая с помощью равенства rkT (τ ) = sup {rkT (σ) + 1 | σ ∈ T ∧ τ < σ}. Ранг rk(T ) фундированного дерева T есть по определению ординал rkT (∅). Хорошо известно, что ранг любого фундированного дерева счётен, а произвольный счётный ординал является рангом подходящего фундированного дерева. ОПРЕДЕЛЕНИЕ 3.6 [8]. Пусть A ⊆ P ω. Альтернирующим деревом для A называется монотонная функция f : T → Fin из дерева T в класс конечных множеств такая, что f (σ) ∈ A тогда и только тогда, когда f (σ an) 6∈ A для любого σ an ∈ T . Ранг f — это ранг дерева T (при условии, что оно фундировано). Альтернирующее дерево f называется 1альтернирующим (0-альтернирующим), если f (∅) ∈ A (соответственно, f (∅) 6∈ A). В [8] установлен следующий простой факт: если f : T → Fin — альтернирующее дерево для A ранга α, то для любых β < α и k < 2 найдётся k-альтернирующее дерево g : S → Fin для A ранга β с условием f (∅) ≤ g(∅). Отсюда индукцией по α легко выводится следующая ЛЕММА 3.7. Пусть f : T → Fin — k-альтернирующее дерево для A ранга α (k < 2, α < ω1 ), S — дерево ранга α. Тогда существует kальтернирующее дерево для A вида g : S → Fin. Значит, в определении 3.6 на самом деле существен только ранг альтернирующего дерева. Альтернирующие деревья с разностной иерархией связывает ТЕОРЕМА 3.8 [8]. Для всех α < ω1 и A ⊆ P ω включение A ∈ S−1 α 0 ˜ и нет 1-альтернирующего верно тогда и только тогда, когда A ∈ S 2

О классификации счётных булевых термов

185

дерева для A ранга α. Из последней теоремы и леммы 3.7 вытекает СЛЕДСТВИЕ 3.9. Пусть α < ω1 , T — дерево ранга α, A ⊆ 2ω . ˜0 и нет Включение A ∈ S−1 верно тогда и только тогда, когда A ∈ S α

2

1-альтернирующего дерева для A вида f : T → Fin. ЗАМЕЧАНИЕ. Лемма 3.7 и следствие 3.9 справедливы для произвольного ϕ-пространства [8]. Основные свойства разностной иерархии в P ω устанавливает ТЕОРЕМА 3.10 [8]. Для пространства P ω справедливо следующее: S ˜0 (i) {S−1 α | α < ω1 } = S2 ; S −1 ˜−1 (ii) для любого α < ω1 верно {S−1 β ∪ co(Sβ ) | β < α} = Sα ; −1 (iii) для любого α < ω1 верно S−1 α 6= co(Sα ).

−1 −1 Если A ∈ S−1 α \co(Sα ), то A назовём собственным Sα -множеством.

Рассмотрим вопрос, в каких случаях такие множества могут содержать ∅ или ω в качестве элементов. ПРЕДЛОЖЕНИЕ 3.11. (i) Для любого α < ω1 , если A является собственным S−1 α -множеством, то ∅ 6∈ A. (ii) Для любых n < ω и собственного S−1 n -множества A включение ω ∈ A верно тогда и только тогда, когда n нечётно. ДОКАЗАТЕЛЬСТВО. (i) Пусть A — собственное S−1 α -множество, {Aβ }β<α — монотонная последовательность S01 -множеств с условием A = = Dα ({Aβ }). Предположим, что ∅ ∈ A. Тогда ∅ ∈ Aβ для некоторого −1 β < α, поэтому Aβ = 2ω . Легко проверить, что A ∈ co(S−1 β+1 ) ⊆ co(Sα ),

противоречие. (ii) Пусть n = 2k+1 нечётно, тогда A = A0 ∪(A2 \A1 )∪. . .∪(A2k \A2k−1 ) для некоторых S01 -множеств A0 ⊆ . . . ⊆ A2k . Если ω 6∈ A0 , то A0 = ∅ и A ∈ S−1 2k , противоречие. Итак, ω ∈ A0 ⊆ A. Пусть теперь n = 2k + 2 чётно (случай n = 0 тривиален, поскольку S−1 = {∅}). Тогда A = (A1 \ A0 ) ∪ . . . ∪ (A2k+1 \ A2k ) для подходящих 0 S01 -множеств A0 ⊆ . . . ⊆ A2k+1 . Необходимо показать, что ω 6∈ A. Предположим противное, тогда ω ∈ (A2i+1 \ A2i ) для некоторого i 6 k. Отсюда

186

В. Л. Селиванов

A2i = ∅ и A ∈ co(S−1 n ), это противоречие завершает доказательство предложения. Предложение 3.11 оставляет открытым вопрос о том, может ли собственное S−1 α -множество для ординала α > ω содержать ω. Покажем, что в этом случае реализуются обе возможности. Сначала установим два вспомогательных факта. Зафиксируем отображение e : ω ∗ → Fin, являющееся изоморфным вложением из (ω ∗ ; ⊓, ∅) в (Fin; ∩, ∅). Здесь через ⊓ обозначается операция инфимума в (ω ∗ ; ⊑). Ясно, что такое отображение существует и является вложением (ω ∗ ; ⊑) в (Fin; ⊆), причём e(σ) содержит в точности lh(σ) элементов для любого σ ∈ ω ∗ . ЛЕММА 3.12. Если e(σ) ⊂ ξ ⊆ e(τi ) для любого i < 2, то τ0 (l) = = τ1 (l), где l = lh(σ). ДОКАЗАТЕЛЬСТВО. Поскольку e(σ) ⊂ ξ ⊆ e(τ0 ) ∩ e(τ1 ), получаем σ < τ0 ⊓ τ1 . Следовательно, τ0 (l) = τ1 (l). Произвольному дереву T поставим в соответствие множество B(T ) = = {ξ | ¬∃τ ∈ T | ξ ⊆ e(τ )}. ЛЕММА 3.13. Для любого фундированного дерева T множество B(T ) лежит в S01 , а множества e(T ) и B(T ) не пересекаются. ДОКАЗАТЕЛЬСТВО. Второе утверждение очевидно, поэтому рассмотрим только первое. Множество B(T ) замкнуто вверх по включению, и остаётся проверить, что для любого ξ ∈ B(T ) найдётся конечное множество η ⊆ ξ с условием η ∈ B(T ). Сначала проверим утверждение: S (a) для любого ξ ∈ 2ω либо ξ 6⊆ e(T ), либо найдутся ⊑-несравнимые

σ, τ ∈ leaf(T ) такие, что ξ пересекается с обоими множествами e(σ), e(τ ). S Предположим противное: ξ ⊆ e(T ) и e(τ ) ∩ ξ 6= ∅ самое большее

для одного τ ∈ leaf(T ). Можем предполагать, что e(τ ) ∩ ξ 6= ∅ для единственного τ ∈ T , поскольку в противном случае ξ = ∅ и существование η очевидно. Тогда ξ ⊆ e(τ ), откуда ξ 6∈ B(T ), противоречие. Пусть теперь η — конечное подмножество ξ, удовлетворяющее (a) (можно найти даже такое η с не более чем двумя элементами). Тогда η ∈

О классификации счётных булевых термов

187

∈ B(T ), и лемма доказана. Определим для любого бесконечного ординала α < ω1 множества Yα и Zα следующим образом: Yα = e(Tα1 ); Zα = e(Tα1 ) ∪ B(Tα ), где Tα — фиксированное дерево ранга α, Tα1 — множество цепочек из Tα нечётной длины. ПРЕДЛОЖЕНИЕ 3.14. Для любого бесконечного ординала α < < ω1 множества Yα и Zα являются собственными S−1 α -множествами, удовлетворяющими ω 6∈ Yα , ω ∈ Zα . ДОКАЗАТЕЛЬСТВО. Два последних утверждения тривиальны, поэтому проверим только, что множества являются собственными S−1 α множествами. Из фундированности Tα и леммы 3.13 следует, что Yα , Zα ∈ ˜0 . Ограничение e на множество Tα является 0-альтернирующим дере∈S 2

вом как для Yα , так и для Zα . По следствию 3.9, Yα и Zα не принадлежат co(S−1 α ). Остаётся показать, что Yα и Zα принадлежат S−1 α , т. е. найти монотонные последовательности {Aβ }β<α и {Cβ }β<α такие, что Yα = Dα ({Aβ }) и Zα = Dα ({Cβ }). Предположим, что α чётно (случай нечётного ординала рассматривается аналогично). Если β < α нечётно, полагаем  [ {[e(τ ), ω] | τ ∈ Tα1 ∧ rk(τ ) 6 β} , Aβ = B(Tα ) ∪ в противном случае Aβ = B(Tα ) ∪

[

 {(e(τ ), ω] | τ ∈ Tα1 ∧ rk(τ ) 6 β + 1} .

Легко проверить, что {Aβ } монотонна и [ Yα = {Aβ+1 \ Aβ | β < α, β чётно} = Dα ({Aβ }), что и требовалось. Пусть C∅ = ∅, C1 = B(Tα ) и C2+β = Aβ ∪ B(Tα ) для β < α. Тогда последовательность {Cβ } имеет требуемые свойства (напомним, что α бесконечно). Предложение доказано.

188

В. Л. Селиванов § 4. Сводимость Вэджа в P ω В этом параграфе устанавливаются некоторые факты о сводимости

Вэджа ≤S в пространстве P ω, определяемой следующим образом. Для A, B ⊆ P ω выражение A ≤S B означает, что A = f −1 (B) для подходящей непрерывной функции f : P ω → P ω. Справедлива следующая очевидная ЛЕММА 4.1. Для всех α, β < ω1 , β > 0 классы S0α , Dα (S0β ) (и даже класс dX (S0β ) для любого X ⊆ 2ω ) замкнуты вниз относительно ≤S . ЗАМЕЧАНИЕ. Определение сводимости Вэджа и лемма 4.1 применимы к любому топологическому пространству. Сосредоточим внимание на результатах, относящихся собственно к пространству P ω. Следующий факт имеет отношение к слабо аппроксимируемым множествам из § 2. ПРЕДЛОЖЕНИЕ 4.2. Множество {ω} является ≤S -наименьшим элементом в классе всех не слабо аппроксимируемых множеств. ДОКАЗАТЕЛЬСТВО. Ясно, что {ω} не является слабо аппроксимируемым. Остаётся показать, что {ω} ≤S X для любого множества X, не являющегося слабо аппроксимируемым. По предложению 2.7 найдутся множество ξ ∈ X и последовательность ζ0 ⊆ ζ1 ⊆ . . . конечных множеств S из X такие, что ζn = ξ. Определим функцию f : P ω → P ω как n

f (η) =

[ {ζn | ∀x < n(x ∈ η)}.

Тогда f непрерывна, f (η) = ξ ∈ X для η = ω, f (η) = ζn 6∈ X для η 6= ω, где n — наименьший элемент в ω \ η. Поэтому {ω} ≤S X, что завершает доказательство. ˜0 . Теперь получим некоторую информацию об S-степенях в классе S 2 В формулировке используются обозначения и множества Yα , Zα из предложения 3.14. ПРЕДЛОЖЕНИЕ 4.3. (i) Для любого n < ω любое S−1 n -множе˜0 \ co(S−1 ). ство S-сводится к любому множеству из S 2

n

˜0 \ co(S−1 ) из (ii) Для любых бесконечного ординала α < ω1 и X ∈ S α 2 ω 6∈ X следует Yα ≤S X, а из ω ∈ X следует Zα ≤S X.

О классификации счётных булевых термов

189

(iii) Для всех бесконечных ординалов α, β < ω1 множества Yα и Zβ S-несравнимы. −1 ˜0 ДОКАЗАТЕЛЬСТВО. (i) Пусть A ∈ S−1 n , B ∈ S2 \ co(Sn ). Рассмот-

рим только случай, когда n = 2k + 2 чётно (оставшийся случай рассматривается аналогично). Пусть A0 ⊆ . . . ⊆ A2k+1 — S01 -множества, удовлетворяющие равенству A = (A1 \ A0 ) ∪ . . . ∪ (A2k+1 \ A2k ). По теореме 3.8 найдётся 0-альтернирующее дерево для B ранга n. Поэтому найдутся конечные множества η0 ⊇ . . . ⊇ ηn такие, что η2i 6∈ B и η2i+1 ∈ B для всех i 6 k. Определим функцию f : P ω → P ω следующим образом. Если ξ 6∈ 6∈ A2k+1 , то f (ξ) = η2k+2 , в противном случае полагаем f (ξ) = ηi , где i — наименьшее число со свойством ξ ∈ Ai . Тогда f непрерывна и A = f −1 (B), откуда A ≤S B. (ii) Проверим, что ω 6∈ X влечет Yα ≤S X (второе утверждение проверяется аналогично). По следствию 3.9 найдется 0-альтернирующее дерево h : Tα → Fin для X. Определим функцию f : P ω → P ω следующим образом. Если ξ ∈ ∈ B(Tα ), полагаем f (ξ) = ω. Предположим, что ξ 6∈ B(Tα ), т. е. ξ ⊆ e(τ ) для некоторого τ ∈ Tα . Если e(n) 6⊆ ξ для всех n ∈ Tα , n < ω, полагаем f (ξ) = h(∅). Пусть e(n) ⊆ ξ для некоторого n ∈ Tα , σ — элемент Tα1 максимальной длины, удовлетворяющий e(σ) ⊆ ξ. Поскольку ξ 6∈ B(Tα ), цепочка σ определена однозначно. Если ξ = e(σ), полагаем f (ξ) = h(σ). Наконец, пусть e(σ) ⊂ ξ. По лемме 3.13 найдётся единственное n < ω с условием σ an ⊑ τ . Полагаем f (ξ) = h(σ an). Ясно, что f непрерывна и Yα = f −1 (X), поэтому Yα ≤S X. (iii) Проверим, что Yα 6≤S Zβ (соотношение Zβ 6≤S Yα проверяется аналогично). Пусть, напротив, Yα = f −1 (Zβ ) для некоторой непрерывной функции f на P ω. Поскольку ω 6∈ Yα , имеем f (ω) 6∈ Zβ . Из того, что B(Tβ ) ⊆ Zβ , следует f (ω) 6∈ B(Tβ ), т. е. f (ω) ⊆ e(τ ) для некоторого τ ∈ Tβ . Последовательность (e(∅), . . . , e(τ )) является 0-альтернирующей цепью для Zβ длины lh(τ ). Поскольку α > ω, найдётся σ ∈ Tα с условием lh(σ) > lh(τ ). Последовательность (e(∅), . . . , e(σ)) является 0-альтерниру-

190

В. Л. Селиванов

ющей цепью для Yα длины lh(σ). Монотонность f влечёт, что последовательность (f (e(∅)), . . . , f (e(σ))) является 0-альтернирующей цепью для Zβ с условием f (e(σ)) ⊆ f (ω) ⊆ e(τ ). Поскольку e(τ ) имеет точно lh(τ ) элементов, получаем противоречие. Предложение доказано. Отсюда сразу вытекает СЛЕДСТВИЕ 4.4. (i) Для любого n < ω класс собственных S−1 n множеств образует S-степень. (ii) Для любого бесконечного ординала α < ω1 класс собственных S−1 α -множеств

содержит две несравнимые S-степени.

До этого множество Yα определялось только для бесконечных счётных ординалов α. Продолжим эту последовательность на натуральные числа, выбирая в качестве Yn (n < ω) любое фиксированное собственное S−1 n -множество. Из предложений 4.3 и 3.14 вытекает СЛЕДСТВИЕ 4.5. (i) Для любого n < ω верно Yn <S Yn+1 и Yn <S <S Y n+1 . (ii) Для всех n < ω и ω 6 α < ω1 верно Yn <S Yα , Yn <S Y α , Yn <S Zα и Yn <S Z α . (iii) Для всех бесконечных ординалов α < β < ω1 верно Yα <S Yβ , Yα <S Z β , Zα <S Y β и Zα <S Zβ . ЗАМЕЧАНИЯ. В этом параграфе приведены только факты об отношении ≤S , касающиеся основной темы данной статьи. Структура (P (P ω); ≤S ) имеет и другие интересные свойства. Например, из теоремы о неподвижной точке для пространства P ω следует, что A 6≤S A для любого A. Следствие 4.5(iii) показывает, что существуют четыре попарно несравнимых множества (например, множества Yα , Y α , Zα , Z α для бесконечного α < ω1 ). В § 6 будет показано, что любой класс из леммы 4.1 содержит S-полное множество, поэтому классы из следствия 4.4(ii) на самом деле содержат не менее трёх S-степеней. § 5. Основные результаты Применим установленные в предыдущих параграфах факты к изучению основной проблемы данной статьи. Сначала рассмотрим её для неко-

О классификации счётных булевых термов

191

торых точечных классов, связанных с высокими уровнями борелевской иерархии. ТЕОРЕМА 5.1. Пусть α < ω1 , ω 6 β < ω1 и X ⊆ 2ω . Имеют место следующие утверждения: (i) X ∈ B тогда и только тогда, когда dX (Σ01 ) ⊆ B; (ii) X ∈ Σ0β тогда и только тогда, когда dX (Σ01 ) ⊆ Σ0β ; S 0 S 0 Σk ; Σk тогда и только тогда, когда dX (Σ01 ) ⊆ (iii) X ∈ k<ω

k<ω

(iv) для любого ω1 -терма t соотношение X ∈ t(Σ0β ) имеет место

тогда и только тогда, когда справедливо dX (Σ01 ) ⊆ t(Σ0β ); в частности, X ∈ Dα (Σ0β ) тогда и только тогда, когда dX (Σ01 ) ⊆ Dα (Σ0β ). ДОКАЗАТЕЛЬСТВО. (i) Пусть X ∈ B. Тогда X ∈ Σ0γ для некоторого γ > ω. По предложению 2.4, X ∈ S0γ . По предложению 2.3(i), dX (Σ01 ) ⊆ ⊆ Σ0γ ⊆ B. Обратная импликация следует из соотношения X ∈ dX (Σ01 ), вытекающего из леммы 1.3(ii). Остальные утверждения проверяются простыми рассуждениями (следует воспользоваться предлож. 2.3, 2.4, 3.4 и 3.5). Теорема доказана. Из структуры иерархии Вэджа легко получить характеризации некоторых утверждений вида dX (Σ01 ) = C из рассмотренных выше утверждений вида dX (Σ01 ) ⊆ C. Например, справедливо СЛЕДСТВИЕ 5.2. Для всех α < ω1 и ω 6 β < ω1 включение X ∈ Dα (Σ0β ) \ co(Dα (Σ0β )) имеет место тогда и только тогда, когда справедливо равенство dX (Σ01 ) = Dα (Σ0β ). Свяжем предпорядок ≤S из предыдущего параграфа с ω-местными булевыми операциями. ТЕОРЕМА 5.3. Для всех X, Y ⊆ P ω из X ≤S Y вытекает dX (Σ01 ) ⊆ dY (Σ01 ). ДОКАЗАТЕЛЬСТВО. Пусть f — непрерывная функция на P ω с условием X = f −1 (Y ). Требуется показать, что для любой последовательности {Ai } Σ01 -множеств найдётся последовательность {Bi } Σ01 -множеств такая, что dX ({Ai }) = dY ({Bi }). Проверим, что последнее равенство вы-

192

В. Л. Селиванов

текает из включений cξ ({Ai }) ⊆ cf (ξ) ({Bi }), ξ ∈ 2ω .

(1)

Включение dX ({Ai }) ⊆ dY ({Ai }) следует из (1) очевидным образом. Для проверки обратного включения возьмём ζ ∈ dY ({Bi }). Тогда ζ ∈ cη ({Bi }) для некоторого η ∈ Y . По лемме 1.3(i) включение ζ ∈ cξ ({Ai }) выполняется для некоторого ξ ∈ 2ω . По (1), ζ ∈ cf (ξ) ({Bi }), откуда cf (ξ) ({Bi }) ∩ ∩ cη ({Bi }) 6= ∅. По лемме 1.3(i), f (ξ) = η ∈ Y , поэтому ξ ∈ X и ζ ∈ dX ({Ai }). Определим последовательность {Bk } точечных множеств следующим образом: Bk = {ζ | ∃η ∈ Fin(k ∈ f (η) ∧ ∀i ∈ η(ζ ∈ Ai ))}. Легко видеть, что Bk ∈ Σ01 для любого k < ω. Для проверки соотношения (1) возьмём произвольное ζ ∈ cξ ({Ai }), тогда ∀i(ζ ∈ Ai ↔ i ∈ ξ).

(2)

Достаточно показать, что ζ ∈ Bk ↔ k ∈ f (ξ) для любого k ∈ ω. Если ζ ∈ ∈ Bk , то для некоторого конечного множества η имеем k ∈ f (η) и ∀i ∈ η(ζ ∈ ∈ Ai ). Из последнего условия и из (2) следует η ⊆ ξ. Поэтому f (η) ⊆ f (ξ) и k ∈ f (ξ), что и требовалось. Обратно, пусть k ∈ f (ξ). Поскольку f непрерывна, k ∈ f (η) для некоторого конечного множества η ⊆ ξ. Из (2) получаем ∀i ∈ η(ζ ∈ Ai ). Итак, ζ ∈ Bk , теорема доказана. СЛЕДСТВИЕ 5.4. Структура несамодвойственных борелевских степеней Вэджа является гомоморфным образом структуры (B; ≤S ). ДОКАЗАТЕЛЬСТВО. Для любого X ∈ B пусть F (X) — полное по Вэджу множество в dX (Σ01 ). Согласно последней теореме X ≤S Y влечёт F (X) ≤W F (Y ). По теореме Вэджа, упомянутой в § 1, для любого несамодвойственного борелевского множества Z найдётся X с условием Z ≡W F (X). По теореме 5.1(i) верно X ∈ B, следствие доказано.

О классификации счётных булевых термов

193

Теперь дадим решение основной проблемы этой статьи для одного низкого уровня борелевской иерархии. ˜0 имеет ТЕОРЕМА 5.5. Для любого X ⊆ P ω включение X ∈ S 2 место тогда и только тогда, когда dX (Σ01 ) ⊆ ∆02 . ДОКАЗАТЕЛЬСТВО. Н е о б х о д и м о с т ь следует из предложения 2.3(i). ˜0 ; надо показать, что dX (Σ0 ) 6⊆ Д о с т а т о ч н о с т ь. Пусть X 6∈ S 2 1 6⊆ ∆02 . По теореме 2.6 хотя бы одно из множеств X, X не является слабо аппроксимируемым. Достаточно рассмотреть случай, когда X не является слабо аппроксимируемым (второй случай двойствен к этому). По предложению 4.2, {ω} ≤S X, по теореме 5.3 имеем d{ω} (Σ01 ) ⊆ T ⊆ dX (Σ01 ). Поскольку d{ω} = cω = vk , выполняется d{ω} (Σ01 ) = Π02 . Итак, k

Π02 ⊆ dX (Σ01 ), а следовательно, dX (Σ01 ) 6⊆ ∆02 . Теорема доказана.

˜0 вытекает Σ0 ⊆ СЛЕДСТВИЕ 5.6. Для любого X ⊆ P ω из X 6∈ S 2 2 ⊆ dX (Σ01 ) или Π02 ⊆ dX (Σ01 ). Наконец, рассмотрим основную проблему этой статьи для уровней Σ−1 α разностной иерархии Хаусдорфа в канторовском пространстве. ТЕОРЕМА 5.7. Для любого α < ω1 включение X ∈ S−1 α имеет место тогда и только тогда, когда dX (Σ01 ) ⊆ Σ−1 α . ДОКАЗАТЕЛЬСТВО. По следствию 3.4 достаточно показать, что 0 −1 0 ˜0 X ∈ 6 S−1 α влечёт dX (Σ1 ) 6⊆ Σα . Если X 6∈ S2 , то, по следствию 5.6, Σ2 ⊆ ⊆ dX (Σ01 ) или Π02 ⊆ dX (Σ01 ). В любом случае, dX (Σ01 ) 6⊆ Σ−1 α . ˜0 \ S−1 влечёт dX (Σ0 ) 6⊆ Σ−1 (даОстаётся показать, что X ∈ S α α 1 2 лее верхний индекс −1 для простоты опускаем; это возможно, поскольку, как отмечалось выше, Σ−1 α = Σα ). Проверим эквивалентное двойственное ˜0 \ co(S−1 ) влечёт dX (Σ0 ) 6⊆ Πα . По теореутверждение о том, что X ∈ S 2

α

1

ме 5.3 и предложению 4.3 достаточно проверить, что dYα (Σ01 ) 6⊆ Πα для любого α < ω и dYα (Σ01 ) 6⊆ Πα , dZα (Σ01 ) 6⊆ Πα для любого бесконечного α < ω1 . По предложению 3.14 и следствию 4.4 последние утверждения эквивалентны соответственно тому, что dYα (Σ01 ) = Σα для любого α < ω и dYα (Σ01 ) = dZα (Σ01 ) = Σα для любого бесконечного α < ω1 .

194

В. Л. Селиванов Проверим последние равенства по индукции. При α = 0 они очевид-

ны, поскольку d∅(Σ01 ) = {∅} = Σ0 . Пусть α = n+1 < ω и утверждение верно для n. Тогда по теореме 5.3 и по индукционному предположению Σn = dYn (Σ01 ) ⊆ dYα (Σ01 ) и Πn = dY n (Σ01 ) ⊆ dYα (Σ01 ). Поэтому Σn ∪ Πn ⊆ dYα (Σ01 ) и, следовательно, Σα ⊆ dYα (Σ01 ) или Πα ⊆ ⊆ dYα (Σ01 ). По следствию 3.4, dYα (Σ01 ) ⊆ Σα , откуда Σα = dYα (Σ01 ). Пусть α = ω. По индукционному предположению, следствию 4.5 и теореме 5.3 имеем Σn ∪ Πn ⊆ dYα (Σ01 ) для любого n < ω. Тогда Σα ⊆ ⊆ dYα (Σ01 ) или Πα ⊆ dYα (Σ01 ), и применимо рассуждение из предыдущего абзаца. Это же рассуждение используется для множества Zα . Наконец, пусть α > ω. По индукции для любого бесконечного β < α справедливы равенства Σβ = dYβ (Σ01 ) и Σβ = dZβ (Σ01 ). По следствию 4.5 и теореме 5.3 для любого β < α имеем Σβ ∪ Πβ ⊆ dYα (Σ01 ). Опять можно повторить предыдущее рассуждение. Теорема доказана. Напомним, что, согласно результату из [3] верно Σω1 = Σ02 . Из следствия 5.6 и теоремы 5.7 вытекает СЛЕДСТВИЕ 5.8. Для любого X ⊆ P ω, либо dX (Σ01 ) совпадает с одним из классов Σα , Πα (α < ω), либо имеет место хотя бы одно из включений Σ02 ⊆ dX (Σ01 ), Π02 ⊆ dX (Σ01 ). § 6. Заключительные замечания Основная проблема этой статьи остаётся открытой для многих уровней иерархии Вэджа и даже иерархии Бореля. Из теорем 5.1 и 5.7 получаем СЛЕДСТВИЕ 6.1. Пусть α = 1 или ω 6 α < ω1 . Включение dX (Σ01 ) ⊆ Σ0α верно в том и только том случае, когда X ∈ S0α . Для всех остальных уровней Σ0n иерархии Бореля, 2 6 n < ω, проблема остаётся открытой, хотя справедливо СЛЕДСТВИЕ 6.2. Для любого 2 6 n < ω верно S0n ⊆ {X | dX (Σ01 ) ⊆ Σ0n } ⊂ Σ0n .

О классификации счётных булевых термов

195

ДОКАЗАТЕЛЬСТВО. Включение S0n ⊆ {X | dX (Σ01 ) ⊆ Σ0n } вытекает из предложения 2.3(i). Включение {X | dX (Σ01 ) ⊆ Σ0n } ⊆ Σ0n вытека6 Σ0n вытекает из ет из леммы 1.3(ii). Неравенство {X | dX (Σ01 ) ⊆ Σ0n } = предложения 2.4(iv), поскольку для множества Bn из доказательства этого предложения выполняются свойства B n ∈ Σ0n и dB n (Σ01 ) = Σ0n+1 . Это завершает доказательство. Предположительно, следствие 6.1 справедливо также для уровней Σ0n , 2 6 n < ω. Если это действительно имеет место, можно надеяться получить полное решение проблемы для всех уровней иерархии Вэджа. Выше основное внимание уделялось классам dX (Σ01 ), поскольку такие классы интенсивно изучались в классической дескриптивной теории множеств. Классы dX (C) для некоторых других естественных точечных классов C также могут представлять интерес. Примером является теорема 1.4. Дадим описание классов dX (S01 ), в некотором смысле аналогичное этой теореме. ТЕОРЕМА 6.3. Для любого X ⊆ P ω справедливо dX (S01 ) = {Y | Y ≤S X}. ДОКАЗАТЕЛЬСТВО. Пусть Y ∈ dX (S01 ); требуется показать, что Y ≤S X. Для некоторой последовательности {Ai } S01 -множеств имеем Y = = dX ({Ai }). Определим функцию f : P ω → P ω как f (ξ) = {i | ξ ∈ Ai }. Тогда f непрерывна и cf (ξ) ({Ai }) = {ξ} для любого ξ. Из последнего соотношения следует Y = f −1 (X), откуда Y ≤S X. Обратно, пусть Y ≤S X, тогда Y = f −1 (X) для некоторой непрерывной функции f на P ω. По лемме 1.3(ii) имеем X = dX ({Ai }), где Ai = {ξ | i ∈ ξ}. Тогда Y = dX ({f −1 (Ai )}). Множества Ai лежат в S01 , поэтому множества f −1 (Ai ) также лежат в S01 . Отсюда Y ∈ dX (S01 ), что завершает доказательство. СЛЕДСТВИЕ 6.4. Предпорядки ({dX (S01 ) | X ⊆ P ω}; ⊆) и (P (P ω); ≤S ) эквивалентны. Последнее свойство и результаты § 4 (см. замеч. после следствия 4.5) показывают, что структура ({dX (S01 ) | X ∈ 2ω }; ⊆) не является почти

196

В. Л. Селиванов

вполне упорядоченной. С другой стороны, из [1, теор. 6.5] следует, что структура ({dX (S0α ) | X ∈ 2ω }; ⊆) для любого α > 2 почти вполне упорядочена. Теорема 6.3 приводит к решению аналога основной проблемы статьи для уровней иерархий, рассмотренных в §§ 2 и 3. Например, справедливо СЛЕДСТВИЕ 6.5. Для любого α < ω включение X ∈ S0α верно тогда и только тогда, когда dX (S01 ) ⊆ S0α . Естественное свойство иерархий из §§ 2 и 3 устанавливает СЛЕДСТВИЕ 6.6. Для всех α, β < ω, β > 0, любой из классов S0β , Dα (S0β ) имеет S-полное множество. ДОКАЗАТЕЛЬСТВО. Любой из указанных классов можно представить в виде dX (S01 ) для подходящего X ⊆ 2ω . По теореме 6.3 множество X является S-полным в dX (S01 ). Это завершает доказательство. Например, простое вычисление показывает, что множество {ξ | µ(ξ) нечётно} S-полно в S−1 ω . Здесь через µ(ξ) обозначается наименьший элемент в ξ (при условии, что ξ не пусто).

ЛИТЕРАТУРА 1. V. L. Selivanov, Fine hierarchies and Boolean terms, J. Symb. Log., 60, N 1 (1995), 289—317. 2. W. Wadge, Degrees of complexity of subsets of the Baire space, Notices Am. Math. Soc., A-714, 1972. 3. W. Wadge, Reducibility and determinateness in the Baire space, PhD thesis, Univ. California, Berkeley, 1984. 4. R. van Wesep, Wadge degrees and descriptive set theory, in: Cabal Semin., Proc. Caltech-UCLA Logic Semin. 1976–77 (Lec. Notes Math., 689), 1978, 151—170. 5. J. Steel, Determinateness and the separation property, J. Symb. Log., 45, N 1 (1981), 41—44. 6. Y. N. Moschovakis, Descriptive set theory, Amsterdam, North-Holland Publ. Co., 1980. 7. A. Tang, Chain properties in P ω, Theor. Comput. Sci., 9 (1979), 153—172.

О классификации счётных булевых термов

197

8. В. Л. Селиванов, Разностная иерархия в ϕ-пространствах, Алгебра и логика, 43, № 4 (2004), 425—444. 9. L. V. Kantorovich, E. M. Livenson, Memoir on the analytical operations and projective sets. I, Fund. Math., 18 (1932), 214—271. 10. R. van Wesep, Subsystems of second-order arithmetic, and descriptive set theory under the axiom of determinateness, PhD thesis, Univ. California, Berkeley, 1977. 11. L. Staiger, Hierarchies of recursive ω-languages, Elektron. Inf. Kybern., 22, N 5/6 (1986), 219—241.

Поступило 15 октября 2003 г. Адрес автора: СЕЛИВАНОВ Виктор Львович, НГПУ, ул. Вилюйская, 28, г. Новосибирск, 630126, РОССИЯ. e-mail: [email protected]