close

Вход

Забыли?

вход по аккаунту

?

Теоретико-множественные сводимости по решетке множеств.

код для вставкиСкачать
2006
ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ
МАТЕМАТИКА
Є 1 (524)
УДК 512.565:510.57
А.Н. ФРОЛОВ
ТЕОРЕТИКО-МНОЖЕСТВЕННЫЕ СВОДИМОСТИ
ПО РЕШЕТКЕ МНОЖЕСТВ
Все рассматриваемые множества будут подмножествами множества натуральных чисел
! = f0; 1; 2; : : : g. Под решеткой множеств понимается класс множеств D P (!) = fA j A !g,
замкнутый относительно операций объединения и пересечения. Решеткой множеств с наименьшим (с наибольшим) элементом назовем решетку множеств D, если ; 2 D (или ! 2 D соответственно).
Под алгеброй множеств понимается решетка множеств с наименьшим и наибольшим элементами, замкнутая относительно операции теоретико-множественной разности. Дополнение
множества A будем обозначать A = ! ; A.
В данной работе изучаются две сводимости, называемые теоретико-множественными сводимостями по решетке множеств. Известны различные сводимости, например, тьюринговая сводимость, 1-сводимость, m-сводимость и др. ([1]{[3]). Изучение этих сводимостей направлено на
изучение алгоритмической сложности различных структур. Изучаемые в данной статье сводимости отображают теоретико-множественную сложность, поэтому эти сводимости называются
теоретико-множественными (по решетке множеств D) и обозначаются как DSET-1 и DSET-2 .
1. Теоремы о нормальной форме
Пусть D | решетка множеств, тогда назовем функцию : Dn ! D теоретико-множественной
по классу множеств D, если она либо совпадает с одной из следующих: 1 (X; Y ) = X [ Y ,
2 (X; Y ) = X \ Y или n;m
3 (X1 ; : : : ; Xn ) = Xm (1 m n), либо может быть получена из них
применением конечного числа раз операции суперпозиции.
Определение 1. Пусть D | решетка множеств, тогда будем говорить, что множество B
SET-1-сводится (SET-2-сводится) к множеству A по классу множеств D и будем писать
A DSET-1 B (A DSET-2 B );
если существуют такие множества R1 ; : : : ; Rn 2 D и такая теоретико-множественная функция
: Dn+1 ! D ( : Dn+2 ! D), что A = (B; R1 ; : : : ; Rn ) (или A = (B; B; R1 ; : : : ; Rn ) соответственно).
Если A DSET-1 B (A DSET-2 B ) не верно, то говорим, что B не SET-1-сводится к A (B не
SET-2-сводится к A), и пишем A 6DSET-1 B (A 6DSET-2 B ).
Для 1 i 2 введем обозначение A <DSET-i B , если A DSET-i B и B 6DSET-i A.
Будем также писать A DSET-i B , если A DSET-i B и B DSET-i A.
Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (грант Є 02-01-00169) и Министерства образования и науки Российской Федерации (грант
Є E02-1.0-177).
57
Легко видеть, что введенные отношения DSET-i рефлексивны и транзитивны, а отношения
являются отношениями эквивалентности. Классы эквивалентности будем обозначать
D
D
SET-i = fB ! j B SET-i Ag, где 1 i 2. Пусть R 2 D , тогда класс [R]SET-i | наименьший
D
D
элемент по SET-i-сводимости, причем [R]SET-1 = D. Легко видеть, что [R]SET-2 | наименьшая
по включению алгебра множеств, содержащая D. Следовательно, если D | алгебра множеств,
то [R]DSET-2 = D.
Если A DSET-1 B , то очевидно A DSET-2 B . Очевидно также, что A DSET-2 A для любого
A !.
D
Лемма 1. Если D | алгебра множеств, то A SET 1 B тогда и только тогда, когда
D
A SET 1 B .
0
Доказательство. ()). Если A = (B; R1 ; : : : ; Rn ), где R1 ; : : : ; Rn 2 D , то A = (B; R1 ; : : : ; Rn ),
где формула 0 получается из формулы заменой операции [ на \, а \ на [. Заметим, что
R1 ; : : : ; Rn 2 D, т. к. D { алгебра множеств.
((). Аналогично.
Определения теоретико-множественных сводимостей неудобны для дальнейших действий с
ними, поэтому необходимы критерии для этих сводимостей, так называемые нормальные формы. Далее в теоремах 1 и 2 установим критерии для теоретико-множественных SET-1- и SET-2сводимостей.
Теорема 1 (о нормальной форме для SET-1-сводимости). Для решетки множеств D и для
любых множеств A и B выполнено A DSET 1 B тогда и только тогда, когда существуют такие
множества R1 ; R2 2 D, что R1 R2 и справедливо одно из следующих представлений :
1) A = B ,
2) A = B \ R1 ,
3) A = B [ R1 ,
4) A = (B [ R1 ) \ R2 = (B \ R2 ) [ R1 .
Приведем сначала лемму 2, справедливость которой проверяется непосредственно.
Лемма 2. Для любых множеств R1 R2 , R3 R4 и B имеем
1) ((B [ R1 ) \ R2 ) [ ((B [ R3 ) \ R4 ) = (B [ (R1 [ R3 )) \ (R2 [ R4 ),
2) ((B [ R1 ) \ R2 ) \ ((B [ R3 ) \ R4 ) = (B [ (R1 \ R3 )) \ (R2 \ R4 ).
Кроме того, R1 [ R3 R2 [ R4 и R1 \ R3 R2 \ R4 .
Замечание 1. Представим теорему 1 в следующей более удобной записи.
Пусть D | решетка множеств. Тогда для любых множеств A и B выполнено A DSET-1 B
тогда и только тогда, когда существуют такие множества R1 2 D [ f;g и R2 2 D [ f!g, что
R1 R2 и A = (B [ R1 ) \ R2.
Отметим также, что если R1 R2 , то (B [ R1 ) \ R2 = (B \ R2 ) [ R1 .
D
Доказательство теоремы 1. ()). Пусть A SET-1 B , тогда существуют такие множества
R1 ; : : : ; Rn 2 D и такая теоретико-множественная функция , что A = (B; R1 ; : : : ; Rn ). Любая теоретико-множественная функция реализуется некоторой конечной записью специальных
символов | базисных формул 1 , 2 , n3 +1;m (1 m n + 1) и специального символа, который связывает базисные формулы операцией суперпозиции. Зафиксируем такую запись для
функции .
Введем понятие длины записи множества B в записи теоретико-множественной функции .
Эту длину будем обозначать через Ln (B ) как число встречающихся в записи функции символов n3 +1;1 . Далее будем вести индукцию по Ln (B ).
I) Пусть Ln (B ) = 0, тогда A = (B; R1 ; : : : ; Rn ) = e (R1 ; : : : ; Rn ), где теоретико-множественная функции e полностью совпадает с , т. к. в данном случае формальный параметр B можно
DSET-i
[A]D
-
-
-
58
опустить. Следовательно, A 2 D, т. к. D является решеткой множеств. Тогда A = (B [ R) \ R и
R R, где R = A 2 D.
II) Если Ln (B ) = 1, то либо A = (B; R1 ; : : : ; Rn ) = 01 (B; R1 ; : : : ; Rn ) [ 001 (B; R1 ; : : : ; Rn ),
либо A = (B; R1 ; : : : ; Rn ) = 01 (B; R1 ; : : : ; Rn ) \ 001 (B; R1 ; : : : ; Rn ), либо A = (B; R1 ; : : : ; Rn ) =
3n+1;i (B; R1 ; : : : ; Rn ), 1 i n + 1 (в последнем случае теорема доказана), где Ln (B ) +
Ln (B ) = 1. В силу коммутативности операций объединения и пересечения, без ограничения
общности можем предположить, что Ln (B ) = 1 и Ln (B ) = 0. Тогда по случаю I) имеем
001 (B; R1 ; : : : ; Rn ) 2 D.
Аналогично, 01 (B; R1 ; : : : ; Rn ) = 02(B; R1 ; : : : ; Rn )002 (B; R1 ; : : : ; Rn ), где означает [ или \,
Ln (B ) = 1 и Ln (B ) = 0. И так далее, пока выполняется 0n = n3 +1;i для некоторого i 2
f1; : : : ; n + 1g (такое число существует, т. к. запись для конечна). Таким образом, получим
представление множества A (при s = 0 теорема доказана)
A = (: : : ((B1 R10 )2 R20 ) : : : s Rs0 ); где i 2 f[; \g и Ri0 2 D; 1 i s:
(1)
Заметим, что B = (B [ ;) \ ! и Ri0 = (B [ Ri0 ) \ Ri0 (1 i s). Неоднократно применяя
лемму 2, из (1) получим A = (B [ P1 ) \ P2 , где P1 2 D [ f;g, P2 2 D [ f!g и P1 P2 .
III) Пусть Ln (B ) = k > 1 и для любой формулы 0 (B; R1 ; : : : ; Rn ) при Ln (B ) < k существуют такие множества R0 2 D [ f;g, R00 2 D [ f!g, что R0 R00 и 0 (B; R1 ; : : : ; Rn ) = (B [ R0 ) \ R00 .
Так же, как и в п. II), получим формулу (случай s = 0 очевиден)
A = (: : : (0(B; R1 ; : : : ; Rn )1 R10 )2 : : : )s Rs0 ;
(2)
0
0
0
0
где i 2 f[; \g, Ri 2 D (1 i s), (B; R1 ; : : : ; Rn ) = 1 (B; R1 ; : : : ; Rn ) [ 2 (B; R1 ; : : : ; Rn ) или
0 (B; R1 ; : : : ; Rn ) = 01 (B; R1 ; : : : ; Rn ) \ 02 (B; R1 ; : : : ; Rn ), где Ln (B ) 6= 0 и Ln (B ) 6= 0 (т. е.
Ln (B ) < k и Ln (B ) < k).
Применим индукцию к 01 и 02 . Тогда существуют такие множества P1 ; P3 2 D[f;g и P2 ; P4 2
D[f!g, что P1 P2 и P3 P4 , 01(B; R1 ; : : : ; Rn ) = (B [ P1 ) \ P2 и 02(B; R1 ; : : : ; Rn ) = (B [ P3) \ P4 .
По лемме 2 имеем 0 (B; R1 ; : : : ; Rn ) = (B [ P 0 ) \ P 00 , где P 0 2 D [f;g, P 00 2 D [f!g и P 0 P 00 .
п. II) по лемме 2 из (2) следует существование таких множеств Re 1 2 D [ f;g и
eR2 2Аналогично
D [ f!g, что Re1 Re2 и A = (B [ Re1) \ Re2.
((). Очевидно по определению SET-1-сводимости.
Из замечания 1 вытекает
Следствие 1. Для решетки множеств D с наименьшим или с наибольшим элементом и для
любых множеств A и B выполнено A DSET-1 B тогда и только тогда, когда существуют такие
множества R1 ; R2 2 D, что R1 R2 и справедливо одно из следующих представлений:
1 ) A = B [ R1 (если D с наименьшим элементом) или A = B \ R1 (если D с наибольшим
элементом соответственно),
2 ) A = (B [ R1 ) \ R2 = (B \ R2 ) [ R1 .
Если ;; ! 2 D, то случай 1 ) можно опустить.
Теорема 2 (о нормальной форме для SET-2-сводимости). Для решетки множеств D и для
любых множеств A и B выполнено A DSET 2 B тогда и только тогда, когда либо A DSET 1 B ,
либо A DSET 1 B , либо существуют такие множества R1 , R2 2 D, что A = (B [ R1) \ (B [ R2).
Следующие две леммы доказываются непосредственной проверкой.
Лемма 3. Для любых множеств R1 R2 и B справедливо равенство
(B [ R1 ) \ R2 = (B [ R1 ) \ (B [ R2 ):
Лемма 4. Для любых множеств R1 , R2 , R3 , R4 и B имеем
1) ((B [ R1 ) \ (B [ R2 )) [ ((B [ R3 ) \ (B [ R4 )) = (B [ (R1 [ R3 )) \ (B [ (R2 [ R4 )),
2) ((B [ R1 ) \ (B [ R2 )) \ ((B [ R3 ) \ (B [ R4 )) = (B [ (R1 \ R3 ) \ (B [ (R2 \ R4 ))).
0
1
00
1
0
00
1
0
1
00
2
2
0
0
1
0
0
2
0
1
2
-
-
-
59
Замечание 2. В силу леммы 3 аналогично замечанию 1 запишем теорему 2 о нормальной
форме для SET-2-сводимости в следующем виде.
Пусть D | решетка множеств. Тогда для любых множеств A и B выполнено A DSET-2 B
тогда и только тогда, когда существуют такие множества R1 ; R2 2 D [ f;; !g, что
A = (B [ R1 ) \ (B [ R2 ):
D
Доказательство теоремы 2. ()). Пусть A SET-2 B , тогда существуют такая теоретикомножественная функция и такие множества R1 ; : : : ; Rn 2 D, что A = (B; B; R1 ; : : : ; Rn ).
Аналогично тому, как это делалось при доказательстве теоремы 1, введем понятие длины
записи множества B в записи теоретико-множественной функции , которую будем обозначать
через Ln (B ) как число встречающихся в записи функции символов n3 +1;2. Далее будем вести
индукцию по Ln (B ).
I) Пусть Ln (B ) = 0, тогда A = (B; B; R1 ; : : : ; Rn ) = e (B; R1 ; : : : ; Rn ), т. е. A DSET-1 B .
II) Если Ln (B ) = 1, то аналогично рассуждениям, проведенным при доказательстве теоремы 1, можно обосновать представление
A = (: : : (B1 Q1 )2 : : : )s Qs ;
(3)
где i 2 f[; \g и LnQ (B ) = 0, 1 i s. Так как LnQ (B ) = 0, то из теоремы 1 имеем
Qi = (B [ P1i ) \ P2i ; где P1i ; P2i 2 D [ f;; !g и P1i P2i (1 i s):
Так как B = (B [ !) \ (B [;) и Qi = (B [ P1i ) \ (B [ P2i) для любого i 2 f1; : : : ; sg (см. лемму 3),
то из леммы 4 и (3) следует, что A = (B [ P 0 ) \ (B [ P 00 ), где P 0 ; P 00 2 D [ f;; !g.
III) Пусть Ln (B ) = k > 1 и для любой формулы 0 (B; B; R1 ; : : : ; Rn ), где Ln (B ) < k,
существуют такие множества R0 ; R00 2 D [ f;; !g, что 0 (B; B; R1 ; : : : ; Rn ) = (B [ R0 ) \ (B [ R00 ).
Так же, как и в п. II), получим формулу
A = (: : : (0 (B; B; R1 ; : : : ; Rn)1 Q1)2 : : : )s Qs;
(4)
где i 2 f[; \g, Qi = (B [ P1i ) \ P2i , P1i ; P2i 2 D [ f;; !g, P1i P2i , 1 i s, причем
0 (B; B; R1 ; : : : ; Rn ) = 01(B; B; R1 ; : : : ; Rn )02 (B; B; R1 ; : : : ; Rn ), где 2 f[; \g, Ln (B ) < k и
Ln (B ) < k.
Применим индукцию к 01 и 02 . Тогда существуют такие множества P1 ; P2 ; P3 ; P4 2 D[f;; !g,
что 01 (B; B; R1 ; : : : ; Rn ) = (B [ P1 ) \ (B [ P2 ) и 02(B; B; R1 ; : : : ; Rn ) = (B [ P3 ) \ (B [ P4 ). Тогда
по лемме 4 существуют такие T1 ; T2 2 D [ f;; !g, что 0 (B; B; R1 ; : : : ; Rn ) = (B [ T1 ) \ (B [ T2 ).
Далее, так же, как и в п. II), согласно леммам 3 и 4 из (4) следует A = (B [ T 0 ) \ (B [ T 00 ),
где T 0 ; T 00 2 D [ f;; !g.
((). Очевидно по определению SET-2-сводимости.
В силу замечания 2 сразу получается
Следствие 2. Для решетки множеств D с наименьшим и наибольшим элементами и для любых множеств A и B выполнено A DSET-2 B тогда и только тогда, когда существуют множества
R1 ; R2 2 D такие, что A = (B [ R1) \ (B [ R2 ).
i
i
0
0
1
0
2
2. Частные случаи и теоремы о почти нормальной форме
В предыдущем разделе были доказаны теоремы 1 и 2, теоремы о нормальных формах для
SET-1- и SET-2-сводимостей. Однако в таких частных случаях, как A \ B = ;, A B и B A,
сводимости A DSET-1 B и A DSET-2 B (D | некоторая решетка множеств) по предложениям 1 и
2 можно записать в еще более простом виде.
60
Предложение 1. Если D | решетка множеств и A \ B 2 D , то
1) A DSET 1 B тогда и только тогда, когда A 2 D;
2) A DSET 2 B тогда и только тогда, когда A DSET 1 B .
D
D
Доказательство. 1) Очевидно, если A 2 D , то A SET-1 B . Пусть теперь A SET-1 B , тогда
по теореме 1 существуют такие множества R1 2 D [ f;g и R2 2 D [ f!g, что R1 R2 и
A = (B [ R1 ) \ R2 :
Имеем A = (A [ R1 ) \ A = (A [ R1 ) \ (B [ R1 ) \ R2 = ((A \ B ) [ R1 ) \ R2 2 D, т. к. A \ B 2 D.
2) Очевидно, если A DSET-1 B , то A DSET-2 B . Пусть теперь A SET-2 B , тогда по теореме 2
существуют такие множества R1 ; R2 2 D[f;; !g, что A = (B [ R1 ) \ (B [ R2 ) = (B \ R2 ) [ (B \ R1) =
R0 [ (B \ R1 ), где R0 = B \ R2 = A \ B 2 D. Следовательно, A DSET-1 B.
Предложение 2. Пусть D | решетка множеств. Если A B , тогда следующие условия
эквиваленты :
1) A DSET 1 B ,
2) A DSET 2 B ,
3) существует такое множество R 2 D, что A = B или A = B \ R,
4) существует такое множество R 2 D [ f!g, что A = B \ R.
Также эквивалентны условия :
10 ) B DSET 1 A,
20 ) B DSET 2 A,
30 ) существует такое множество R 2 D, что A = B или A = B [ R,
40 ) существует такое множество R 2 D [ f;g, что A = B [ R.
Доказательство. 1) ) 2), 3) , 4) и 4) ) 1) очевидны. Докажем 2) ) 4).
Пусть A DSET-2 B , тогда по теореме 2 существуют такие множества R1 ; R2 2 D [ f;; !g, что
A = (B [ R1 ) \ (B [ R2). Так как A B , то A = A \ B = B \ R2 . Заметим, что если R2 = ;, то
R2 = ; = A \ B 2 D.
Вторая часть предложения доказывается аналогично.
Следствие 3. Пусть D | решетка множеств с наибольшим (с наименьшим) элементом.
Если A B , то эквивалентны условия:
1) A DSET-1 B (B DSET-1 A),
2) A DSET-2 B (B DSET-2 A),
3) существует такое множество R 2 D, что A = B \ R (A = B [ R).
Заметим, что из предложения 2 также следует, что теоремы о нормальной форме для SET-1и SET-2-сводимостей улучшить нельзя, т. е. нельзя таким образом множество A выразить через
множество B и через некоторое множество R 2 D с помощью операций объединения и пересечения.
Можно предположить, например, что A DSET-1 B \ R или A DSET-1 B [ R для некоторого
R 2 D. Далее в следствии 4 покажем, что наше предположение верно.
Теорема 3 (о почти нормальной форме для SET-1-сводимости). Пусть D | алгебра множеств, тогда если для любых множеств A и B1 ; : : : ; Bn выполнено A DSET 1 Bi , где 1 i n,
то существуют такие множества R1 ; R2 2 D, что для любого i 2 f1; : : : ; ng A0 = Bi \ R1 ,
A00 = Bi [ R2 и A DSET 1 A0, A DSET 1 A00 .
D
Доказательство. Пусть для любого i 2 f1; : : : ; ng выполнено A SET-1 Bi , тогда по теореме 1 существуют такие множества R1i ; R2i 2 D, где 1 i n, что A = (Bi [ R1i ) \ R2i = (Bi \ R2i ) [ R1i
и R1i R2i .
-
-
-
-
-
-
-
-
61
Таким образом, для любого i 2 f1; : : : ; ng имеем R1i A R2i . Пусть P1 = [ni=1 R1i 2 D
и P2 = \ni=1 R2i 2 D, тогда P1 A P2 и согласно следствию 3 A0 = A \ P1 DSET-1 A и
A00 = A [ P2 DSET-1 A.
Следовательно, для любого i 2 f1; : : : ; ng выполнено A0 = A \ P 1 = (Bi [ R1i ) \ R2i \ R11 \
\ Rn1 = Bi \ R2i \ R11 \ \ Rn1 = T i , где T i = R2i \ R11 \ \ Rn1 2 D, 1 i n. Имеем
A0 = Bi \ T 1 \ \ T n = Bi \ T , где T = \ni=1 T i 2 D.
Аналогично, существует такое множество T 0 2 D, что A00 = A [ T 0 .
Следствие 4. Пусть D | алгебра множеств. Для любых множеств A и B выполнено
A DSET-1 B тогда и только тогда, когда существуют такие множества R1 ; R2 2 D, что A DSET-1
B \ R1 и A DSET-1 B [ R2 .
Доказательство ()) следует из теоремы 3 при n = 1.
((). Очевидно.
Предложение 3. Пусть D является алгеброй множеств и A B , тогда эквивалентны
условия :
1) A DSET 1 B;
2) A DSET 2 B;
3) B ; A 2 D.
D
D
D
Доказательство. 1) ) 3), 2) ) 3). Если A SET-i B , то A SET-i B и B SET-i A, где
i 2 f1; 2g. Так как A B , то по предложению 3 существуют такие множества R1 ; R2 2 D, что
A = B \ R1 и B = A [ R2.
Имеем B ; A = B \ A = B \ (A [ R2 ) \ A = B \ R2 \ A = B \ R2 \ (B [ R1 ) = (R2 \ R1 ) 2 D,
т. к. D | алгебра множеств.
3) ) 1). Пусть B ; A 2 D, тогда B = A [ (B ; A) и A = B \ B ; A, т. к. B ; A 2 D.
Следовательно, B DSET-1 A и A DSET-1 B . Таким образом, A DSET-1 B .
1) ) 2) очевидно.
Предложение 4 (о почти нормальной форме для SET-2-сводимости). Предположим, что
D | алгебра множеств. Если A DSET 2 B , то существуют такие множества R1; R2 2 D,
что R1 \ R2 = ; и A DSET 1 (B [ R1 ) \ (B [ R2 ).
D
Доказательство. Пусть A SET-2 B , тогда по теореме 2 существуют такие множества
P1 ; P2 2 D, что A = (B [ P1) \ (B [ P2) = (B \ P2 ) [ (B \ P1 ).
Пусть P = P1 \ P2 6= ; и A0 = A ; P , тогда P A и A = A0 [ P , т. е. A DSET-1 A0 . Более того,
0
A = A \ P (P 2 D, т. к. D | алгебра множеств), т. е. A0 DSET-1 A. Таким образом, A DSET-1 A0 ,
где A0 = A \ P = ((B \ P2 ) [ (B \ P1 )) \ P = (B \ R2 ) [ (B \ R1 ) = (B [ R1 ) \ (B [ R2 ), R1 = P1 \ P ,
R2 = P2 \ P и R1 \ R2 = ;.
-
-
-
-
3. Верхние и нижние грани
В этом разделе получим точные верхние и нижние грани для SET-1- и SET-2-сводимостей.
В теореме 4 опишем все начальные сегменты по SET-1-сводимости.
D
D
D
D
Лемма 5. Если B SET i A и C SET i A, то (B [ C ) SET i A и (B \ C ) SET i A, где D |
решетка множеств и 1 i 2.
D
D
0
1
1
Доказательство. Пусть B SET-1 A и C SET-1 A, тогда B = (A; R1 ; : : : ; Rs ) и C =
00
2
2
(A; R1 ; : : : ; Rt ). Следовательно,
B [ C = (A; R11 ; : : : ; Rs1 ; R12; : : : ; Rt2 ) = 0 (A; R11 ; : : : ; Rs1 ) [ 00 (A; R12 ; : : : ; Rt2):
Все остальные случаи леммы доказываются аналогично.
-
-
-
62
-
Если B DSET-i B [ C (или B DSET-i B \ C ) и C DSET-i B [ C (или C DSET-i B \ C ),
то существует точная верхняя грань [B ]DSET-i _ [C ]DSET-i для SET-i-сводимости и [B ]DSET-i _ [C ]DSET-i =
[B [ C ]DSET-i (или [B ]DSET-i _ [C ]DSET-i = [B \ C ]DSET-i соответственно), где D | решетка множеств и
1 i 2.
Следствие 5.
Если A DSET-1 B и A DSET-1 C , то A DSET-1 (B [ C ) и A DSET-1 (B \ C ),
где D | решетка множеств.
Предложение 5.
Если A DSET-1 B и A DSET-1 C , то по теореме 1 существуют такие множества R1 ; R3 2 D[f;g и R2 ; R4 2 D[f!g, что R1 R2 , R3 R4 , A = (B [ R1 ) \ R2 = (B \ R2 ) [ R1 и
A = (C [ R3 ) \ R4 = (C \ R4) [ R3. Следовательно, R1 ; R3 ; B \ R2; B \ R4 A R2 ; R4 ; B [ R1 ; C [ R3.
Имеем A = A[A = (B \R2 )[R1 [(C \R4 )[R3 = (B [C [R1 [R3 )\(B [R4)\(R2 [C )\(R2 [R4) =
(B [ C [ R1 [ R3 ) \ ((B \ R2 ) [ R4 ) \ ((C \ R4 ) [ R2 ) = (B [ C [ R1 [ R3 ) \ R4 \ R2 , причем
R1 [ R3 2 D[f;g и R2 \ R4 2 D[f!g. Следовательно, A DSET-1 (B [ C ). Аналогично доказывается,
что A DSET-1 (B \ C ).
D
D
Следствие 6. Пусть D | решетка множеств. Если B [ C SET-1 B (или B \ C SET-1 B )
и B [ C DSET-1 C (или B \ C DSET-1 C ), то существует точная нижняя грань [B ]DSET-1 ^ [C ]DSET-1
для SET-1-сводимости и [B ]DSET-1 ^ [C ]DSET-1 = [B [ C ]DSET-1 (или [B ]DSET-1 ^ [C ]DSET-1 = [B \ C ]DSET-1
соответственно).
Доказательство.
Теорема 4. Пусть D | решетка множеств. Тогда для любого множества A начальный
сегмент [DSET-1 A] = f[B ]DSET-1 j B DSET-1 Ag является дистрибутивной решеткой с наименьшим и наибольшим элементами относительно взятия точных верхних и нижних граней,
причем если D | алгебра множеств, то [DSET-1 A] является булевой алгеброй.
Очевидно, [;]DSET-1 и [A]DSET-1 являются наименьшим и наибольшим элементами соответственно. В п. 1 докажем, что для любых двух элементов из [DSET-1 A] существуют
точные верхняя и нижняя грани. В п. 2 проверим выполнение условия дистрибутивности. В случае, когда D является алгеброй множеств, в п. 3 для любого элемента укажем его дополнение.
1) Если A01 DSET-1 A и A02 DSET-1 A, то по теореме 3 существуют такие множества A1 DSET-1 A01
и A2 DSET-1 A02 , что A1 = A [ R1 и A2 = A [ R2 .
Пусть C1 = A1 [ A2 = A [ R1 [ R2 , тогда C1 = A1 [ R2 и, следовательно, C1 DSET-1 A1 .
Аналогично имеем C1 DSET-1 A2 . Тогда из следствия 6 получим [C1 ]DSET-1 = [A1 ]DSET-1 ^ [A2 ]DSET-1 .
Пусть C2 = A1 \ A2 = A [ (R1 \ R2 ), тогда A1 = C2 [ R1 и, следовательно, A1 DSET-1 C2 .
Аналогично, A2 DSET-1 C2 . Тогда из следствия 5 будем иметь [C2 ]DSET-1 = [A1 ]DSET-1 _ [A2 ]DSET-1 .
2) Если A01 ; A02 ; A03 DSET-1 A, то по теореме 3 существуют такие R1 ; R2 ; R3 2 D, что Ai =
A \ Ri DSET-1 A0i для любого i 2 f1; 2; 3g. Согласно п. 1 этой теоремы получаем
Доказательство.
([A1 ]DSET-1 _ [A2 ]DSET-1 ) ^ [A3 ]DSET-1 = [A1 \ A2 ]DSET-1 ^ [A3 ]DSET-1 =
= [(A1 \ A2 ) [ A3 ]DSET-1 = [(A1 [ A3 ) \ (A2 [ A3 )]DSET-1 = [A1 [ A3 ]DSET-1 _ [A2 [ A3 ]DSET-1 =
= ([A1 ]DSET-1 ^ [A3 ]DSET-1 ) _ ([A2 ]DSET-1 ^ [A3 ]DSET-1 ):
Аналогично имеем ([A1 ]DSET-1 ^ [A2 ]DSET-1 ) _[A3 ]DSET-1 = ([A1 ]DSET-1 _ [A3 ]DSET-1 ) ^([A2 ]DSET-1 _
[A3 ]DSET-1 ).
3) Предположим, что D | алгебра множеств. Если A00 DSET-1 A, то по теореме 3 существует
такой R 2 D, что A [ R = A0 DSET-1 A00 . Пусть A00 = A [ R, тогда A00 DSET-1 A, т. к. R 2 D.
Поскольку A0 [ A00 = ! и A0 \ A00 = A, то ввиду п. 1 этой теоремы имеем [A0 ]DSET-1 ^ [A00 ]DSET-1 =
D
[!]SET-1 = [;]DSET-1 и [A0 ]DSET-1 _ [A00 ]DSET-1 = [A]DSET-1 . Таким образом, элемент [A00 ]DSET-1 является
дополнением элемента [A0 ]DSET-1 = [A00 ]DSET-1 .
63
4. Минимальные элементы
В данном разделе опишем все конечные начальные сегменты по SET-1-сводимости (теорема 7), дадим критерий плотности (теорема 6), а также в теореме 5 приведем критерий минимальности для SET-1- и SET-2-сводимостей.
Определение 2. Пусть D | решетка множеств, тогда множество A 2
= D называется D-минимальным, если не существует такого множества B 2= D, что B <DSET-1 A.
Теорема 5 (критерий минимальности). Для алгебры множеств D и A 2
= D следующие условия эквивалентны :
1) A является D-минимальным;
2) для любого множества B DSET 2 A либо B 2 D, либо B DSET 2 A;
3) для любого множества R 2 D либо A \ R 2 D, либо A \ R 2 D;
4) для любого множества R 2 D либо A \ R 2 D, либо A \ R 2 D.
Доказательство. 1) ) 3). Пусть A является D -минимальным и существует такое множество R 2 D, что A \ R 2= D и A \ R 2= D, тогда для множества B = A \ R 2= D имеем
; <DSET-1 B DSET-1 A (; 2 D, т. к. D | алгебра множеств).
Поскольку A ; B = A \ (A [ R) = A \ R 2= D и B A, то по предложению 3 имеем
; <DSET-1 B <DSET-1 A, что противоречит D-минимальности множества A.
2) ) 3) и 1) ) 4) аналогично.
3) ))1. Предположим, что для любого множества R 2 D выполнено A \ R 2 D или A \ R 2 D.
Пусть для некоторого множества A0 выполнено A0 DSET-1 A, тогда по теореме 3 существует такое
множество R 2 D, что A0 DSET-1 A \ R.
Если A \ R 2 D, то A0 DSET-1 ;. Если же R0 = A \ R 2 D, то A = (A \ R) [ (A \ R) = A0 [ R0 ,
т. е. A0 DSET-1 A. Следовательно, множество A является D-минимальным.
4) ) 1) аналогично 3) ) 1).
Таким образом, установлена эквивалентность 1), 3) и 4), а также имеем 2) ) 3). Для завершения доказательства достаточно показать 1) ) 2).
1) ) 2). Если A является D-минимальным, то в силу эквивалентности 1), 3) и 4) A также
D-минимально. Пусть A0 DSET-2 A, тогда по теореме 2 существуют такие R1; R2 2 D, что
A0 = (A \ R1) [ (A \ R2 ) = (A [ R2 ) \ (A [ R1 ):
Так как A D-минимально, то для множества B = A \ R2 выполнено либо a) B 2 D, либо
b) A SET-1 B .
a) Тогда A0 = (A \ R1 ) [ (A \ R2 ) = (A \ R1 ) [ B . Следовательно, A0 SET-1 A. По определению
D-минимальности множества A имеем A0 2 D или A0 SET-1 A. Следовательно, A0 SET-2 A0 .
b) Тогда по предложению 2 имеем A = (A 0\ R2 ) [ R0 , где R0 2 D. Очевидно, A [ R2 = R [ R2 .
Следовательно, A0 = (A [ R2 ) \ (A [ R1 ) = (R [ R2 ) \ (A [ R1 ). Таким образом, A0 SET-1 A. По
определению D-минимальности множества A, имеем A0 2 D или A0 SET-2 A.
Теорема 6 (критерий плотности). Пусть D | алгебра множеств, D T P (! ) и T |
решетка множеств, тогда следующие условия эквивалентны :
1) Te = T =
является плотным частично-упорядоченным множеством, т. е. для любых таких A; B 2 T , что A <DSET 1 B , существует такой C 2 T , что
A <DSET 1 C <DSET 1 B ;
2) T не содержит D-минимальных множеств ;
3) для любого множества A 2 T ;D существует такое множество R 2 D, что A \ R 2= D
и A \ R 2= D;
-
-
D
SET-1
-
-
64
-
4) для любого множества A 2 T ;D существует такое множество R 2 D, что A \ R 2= D
и A \ R 2= D.
e плотна,
Доказательство. По теореме 5 имеем 2) , 3) , 4). Очевидно, если решетка T
то T не содержит D-минимальных множеств. Таким образом, осталось доказать 3) ) 1).
Пусть A; B 2 T | такие множества, что A <DSET-1 B , тогда по следствию 3 существует такое
множество R 2 D, что A DSET-1 B \ R = A0 . Так как A0 B , то по предложению 3 имеем
B ; A0 2= D, где B ; A0 = B \ (B [ R) = B \ R.
По условию 0 существует такое множество R0 2 D, что B \ R \ R0 2= D и B \ R \ R0 2= D. Пусть
C = B \ (R [ R ) 2 Te , тогда C 0DSET-1 B . Так как C \ R 0= B \ R = A0 , то A0 DSET-1 C .
Имеем C ; A = B \ (R [ R ) \ (B [ R) = B \ (R [ R ) \ R = B \ R \ R 2= D. Следовательно,
по предложению 3 C 6DSET-1 A, т. е. A <DSET-1 C .
Аналогично, имеем B ; C = B \ (B [ (R1 \ R0 )) = B \ R1 \ R0 2= D. Следовательно, по
предложению 3 C <DSET-1 B . Таким образом, Te плотна.
Следствие 7. Пусть D | алгебра множеств, D T P (! ) и T | решетка множеств,
Te = T = является плотным частично-упорядоченным множеством, т. е. выполнено хотя бы
одно из условий теоремы 6. Тогда 1-теория Te разрешима.
e | плотное
Доказательство. Предположим, что D 6= T (иначе | очевидно). Пусть T
частично-упорядоченное множество и существует некоторое множество A 2 T ;D, тогда по теореме 4 начальный сегмент [DSET-1 A] является безатомной (т. к. Te плотна) булевой алгеброй. Таким образом, в начальный сегмент [DSET-1 A] вложимо любое конечное частично-упорядоченное
множество.
Теперь, чтобы проверить, верно ли некоторое 1 -предложение в Te , достаточно проверить
удовлетворяет ли это предложение аксиомам частичного порядка.
Далее, опишем все конечные начальные сегменты по SET-1-сводимости по алгебре множеств D. Из теоремы 4 следует, что любой конечный начальный сегмент является конечной
булевой алгеброй. Конечные булевы алгебры полностью характеризуются с точностью до изоморфизма числом своих атомов [4]. Обозначим через Bn конечную булеву алгебру с n атомами. Например, начальный сегмент D-минимального множества является тривиальной (двухэлементной) булевой алгеброй B1 .
Будем говорить, что множество A удовлетворяет условию Pn , n 1, если не существует
таких множеств R1 ; : : : ; Rn 2 D, что A \ R1 2= D, A \ R1 \ R2 2= D, A \ R1 \ R2 \ R3 2= D; : : : ; A \
R1 \ \ Rn;1 \ Rn 2= D и A \ R1 \ \ Rn;1 \ Rn 2= D.
Например, при n = 1 множество A удовлетворяет условию P1 , если не существует такого
множества R 2 D, что A \ R 2= D и A \ R 2= D. Таким образом, только D-минимальные множества
удовлетворяют условию P1 .
Для удобства скажем, что никакое множество не удовлетворяет условию P0 . Легко видеть,
что если множество удовлетворяет условию Pn , то оно удовлетворяет условию Pn+1 .
Определение 3. Множество A 2
= D называется D-n-минимальным (n 1), если оно удовлетворяет условию Pn , но не удовлетворяет условию Pn;1 .
Имеем, что множество D-минимально тогда и только тогда, когда оно D-1-минимально.
Теорема 7. Пусть D | алгебра множеств и A 2
= D. Множество A D-n-минимально
D
тогда и только тогда, когда начальный сегмент [SET 1 A] является конечной булевой алгеброй
D
SET-1
типа Bn .
-
Доказательство проведем по индукции. При n = 1 утверждение следует из теоремы 5.
Предположим, что для любого k n теорема справедлива, докажем ее для k = n + 1.
65
((). Пусть [DSET-1 A] | конечная булева алгебра типа Bn+1 (n 1), тогда A удовлетворяет
условию Pn+1 , т. к. иначе существуют такие множества R1 ; : : : ; Rn+1 2 D, что A \ R1 2= D; : : : ; A \
R1 \ \ Rn \ Rn+1 2= D и A \ R1 \ \ Rn \ Rn+1 2= D. Следовательно, в силу предложений 2 и 3
имеем ; <DSET-1 (A \ R1 \ \ Rn \ Rn+1 ) <DSET-1 (A \ R1 \ Rn ) <DSET-1 <DSET-1 (A \ R1 \ R2 ) <DSET-1
(A \ R1 ) <DSET-1 A, тогда [DSET-1 A] не является Bn+1 , противоречие.
Пусть A\R1 2= D является D-минимальным множеством для некоторого R1 2 D и A0 = A\R1 ,
тогда [DSET-1 A0 ] является конечной булевой алгеброй типа Bn . Следовательно, по предположению индукции A0 является D-n-минимальным, а именно, не удовлетворяет условию Pn;1 . Поэтому существуют такие R2 ; : : : ; Rn 2 D, что A \ R1 \ R2 2= D; : : : ; A \ R1 \ \ Rn 2= D. Так как
A \ R1 2= D, то A не удовлетворяет условию Pn . Таким образом, A является D-n+1-минимальным.
()). Пусть множество A D-n+1-минимально, тогда A удовлетворяет условию Pn+1 и не
удовлетворяет условию Pn . Таким образом, имеем
9R1; : : : ; Rn 2 D : A \ R1 2= D; A \ R1 \ R2 2= D; : : : ; A \ R1 \ \ Rn 2= D:
(5)
Пусть A0 = A \ R1 , где R1 из (5), тогда из формулы (5) следует, что A0 не удовлетворяет
условию Pn;1 . Так как A удовлетворяет условию Pn+1 , то A0 удовлетворяет условию Pn . Таким
образом, множество A0 является D-n-минимальным. Тогда по предположению индукции имеем,
что [DSET-1 A0 ] | конечная булева алгебра типа Bn .
Осталось доказать, что [A00 ]DSET-1 является атомом, т. е. множество A00 является D-минимальным, где A00 = A \ R1 , т. к. [A]DSET-1 = [A0 ]DSET-1 _ [A00 ]DSET-1 и, следовательно, [A DSET-1 ] является
конечной булевой алгеброй типа Bn+1 .
Пусть A00 не является D-минимальным, тогда по теореме 5 существует такое множество
R0 2 D, что A \ R1 \ R0 2= D и A \ R1 \ R0 2= D. Пусть R10 = R1 \ R0 2 D, R20 = R1 2 D,
R30 = R2 2 D; : : : ; Rn0 +1 = Rn 2 D, где R1; : : : ; Rn из формулы (5), тогда A \ R10 = A \ R1 \ R0 2= D,
0
0
A \ R01 \ R20 = A0 \ (R0 1 [ R0) \ R1 = A \ R0 \ R1 2= D. Имеем
R
\
R
= R1 . Следовательно, согласно
1
0
0 20
0
(5) имеем A \ R1 \ R2 \ R3 = A \ R1 \ R2 2= D; : : : ; A \ R1 \ \ Rn \ Rn+1 = A \ R1 \ \ Rn;1 \ Rn 2= D
и A \ R01 \ \ R0n+1 = A \ R1 \ \ Rn 2= D. Таким образом, множество A не удовлетворяет
условию Pn+1 . Получили противоречие. Рассмотрим условие P3 . В определении этого условия присутствуют три множества R1 , R2
и R3 из D. Покажем, что это условие эквивалентно другому, в котором присутствуют только
два множества из D. Нахождение такого нового условия позволяет более просто в конкретных
случаях проверить, выполняется это условие или нет.
Покажем, что множество A удовлетворяет условию P3 тогда и только тогда, когда не существует таких множеств R1 ; R2 2 D, что A \ R1 \ R2 2= D, A \ R1 \ R2 2= D, A \ R1 \ R2 2= D и
A \ R1 \ R2 2= D.
()). Предположим, что существуют такие множества R1 ; R2 2 D, что A \ R1 \ R2 2= D,
A \ R1 \ R2 2= D, A \ R1 \ R2 2= D и A \ R1 \ R2 2= 0 D. Пусть R10 = R1 \ R2 2 D, R20 = R1 2 D и
R30 = R0 2 2 D0 , тогда A \ R10 = A \ R1 \ R2 2= D, A0 \ R10\ R20 0= A \ (R1 [ R2 ) \ R1 = A \ R1 \ R2 2= D,
A \ R1 \ R2 \ R30 = A \ R1 \ R2 2= D и A \ R1 \ R2 \ R3 = A \ R1 \ R2 2= D. Таким образом,
множество A не удовлетворяет условию P3 . Получили противоречие.
((). Предположим, что множество A не удовлетворяет условию P3 , т. е. существуют такие
множества R1 ; R2 ; R3 2 D, что A\R1 2= D, A\R1 \R2 2= D, A\R1 \R2 \R3 2= D и A\R1 \R2 \R3 2= D.
Пусть0 R10 = R1 [ (R3 \ R2 ) 2 D и R0 20 = R1 [ R2 2 D, тогда A 0\ R100 \ R20 = A \ R1 2= D,
A \ R1 \ R20 = A \ R1 \ R2 2= D, A \ R10 \ R2 = A \ R1 \ R2 \ R3 2= D и A \ R1 \ R2 = A \ R1 \ R2 \ R3 2= D.
Получили противоречие.
Используя рассуждения, описанные выше для условия P3 , опишем все условия P2 ;1 . Пусть
число n фиксировано, тогда для любого k 2 f0; : : : ; 2n ; 1g сопоставим такую строку = (k) =
n
66
n : : : 1 длины n, состоящую только из 0 и 1 (т. е. i = 0 или = 1 для 1 i n), что k = P i 2i;1.
i=1
Таким образом, чтобы получить , надо записать число k в двоичной системе счисления, затем
добавить слева необходимое число нулей, чтобы длина стала равной n.
Пусть R1 ; : : : ; Rn 2 D, тогда определим множества Rjk 2 D следующим образом. Пусть Rjk =
Rj , если j = 0, и Rjk = Rj , если j = 1, для 1 j n, а (k) = n : : : 1 .
Теорема 8. Пусть D | алгебра множеств и A 2
= D. Множество A удовлетворяет условию P2 ;1 тогда и только тогда, когда не существует таких множеств R1 ; : : : ; Rn 2 D, что
A \ R1k \ \ Rnk 2= D для любого k 2 f0; : : : ; 2n ; 1g.
n
n
Литература
1. Мальцев А.И. Алгоритмы и рекурсивные функции. { М.: Наука, 1986. { 367 с.
2. Soare R.I. Recursively enumerable sets and degrees. { Heidelberg: Springer-Verlag, 1987. { 243 p.
3. Дегтев А.Н. Рекурсивно перечислимые множества и сводимости табличного типа. { М.:
Наука, 1998. { 176 с.
4. Гончаров С.С. Счетные булевы алгебры и разрешимость. { Новосибирск: Научная книга,
1996. { 364 с.
Казанский государственный
университет
Поступила
09.09.2003
67
Документ
Категория
Без категории
Просмотров
6
Размер файла
200 Кб
Теги
решетки, множества, множественном, сводимость, теоретико
1/--страниц
Пожаловаться на содержимое документа