Колмогоров, Драгалин - Введение в математическую логику (947386), страница 7
Текст из файла (страница 7)
2 зв«. 478 33 (> Если Ь вЂ” атом, то положим а=Ь. Если 6 — не атом,' то найдется элемент Ьь Ьг~Ь, Ьгчьй, Ьгчьо, т. е. о; Ь, .-.Ь. Если Ьг — атом, то все доказано, если нет, то найдется' элемент Ьг, что о(Ьг(Ьь и т. д..... Цепочка ...Ь Ь ~6~6 состоит из попарно различных элементов, и так как только В конечно, то на некотором шаге последовательность Ьь<Ьг г< ... <Ьг<Ь обрывается, и элемант Ьь(Ь является атомом.
П (10) Если аь аг — различные атомы, то агаг=о. ~> Из (9) следует, что агаг~аь агаг~аг, Если агаг~о, то, поскольку аь аг — атомы, необходимо а,аг а, и а~аг=аг, т. е. аг= аз, чего не может быть, так как аг~ьаг. П 4. Т ео р ем а. Всякое конечное булеза кольцо изоморфно стандартному булевому кольцу 0 при подходящем пг. (> Пусть  — конечное булево кольцо. Так как множество В конечно, то число всех атомов конечно. Расположим их в определенйой последовательности: аь аг, ..., а . Докажем, что для каждого элемента Ь~В, ЬФо имеет место представление Ь= Яао ам Ь где сумма берется по всем афпг, таким, что аг~Ь. Положим пока Ь = ~~ а;.
Так как агм:6 для всех членов в сумме Ь; агкь то согласно (8) Ь'к:Ь. Пусть Ь'ФЬ. По свойству кольца тогда найдется и единственный элемент г(~о Ь'+Н=Ь, Умножая это равенство на Ь' и замечая, что Ь'~6 (что означает ЬЬ=Ь'), получим Ь'+Ь'с(=6', откуда Ь'с(=о. Далее, Ы= = (Ь'+сг)с(=6'с1+Ы=с1, т. е. И~Ь, Так ках с(Фо, то найдется атом а~Н. Ввиду ач.'6 отсюда следует, что а<6 и, значит, атом а фигурирует в сумме Ь' = ~г' а;. Отсюда аЬ' = ~гчь г,Сь ааг —— а (см. (10)), т.
е. аЬ'чьо. С другой стороны, ввиду того, что акН; аЬ= (ас()6'=а(с(6') =ао =о, и мы приходим к противоречию. Таким образом,' Ь'=Ь, и наше представление установлено. Заметим теперь, что для каждого элемента Ь~В найдут-ся рь , р„, где )г<=е или рч=о, такие, что 6=)г,аг+1ггаг+ ... +гг„а„. В самом деле, по доказанному 6=Хан и достаточно поло- а~СЬ жить р;=е для всех аь для которых а;-аб, и р;=о — для остальных аь 'Теперь отметим, что указанные рь ..., р находятся по элементу 6 единственным образом. Действительно, пусть имеем представления й=р1а~+ -+р а ь=р'~а1+ ...
+р',„а . Складывая эти равенства, получаем (см. (1)) о = (~и-г1 '~) а~+ ... + (Р„,+Р', ) а . Далее, умножая на аь имеем о= (р;+р'~)аь откуда р;+р'~=0 или р;=р'» (см. (2)). Если 0=р~а~+ ... +р а н, а'=р'1а~+ ... +р', а, .то, очевидно, 0+й'= (р1+р'~)а~+ ... +(р +р; )а, И'= (р|р'1) а1+ ... + (у р',„) ат. Определим функцию ~1, если р=е, ( О, если р=о, и поставим в соответствие каждому элементу б=р~а~+ ... + р а кольца В т-ку (~(р~),...,1'(р„)) е=-0 . Описанные выше свойства этого соответствия показывают, что оно есть изоморфизм кольца В в Р, П 5.
Полученное нами представление конечных булевых колец не обобщается непосредственно на бесконечные кольца. Неверно, что всякое булево кольцо изоморфно кольцу всех подмножеств некоторого множества. Однако верно, что для каждого булева кольца можно подобрать некоторую систему подмножеств (не всеХ) некоторого множества, которая атно. сительно обычных теоретико-множественных операций образует кольцо, изоморфное исходному. Мы ограничимся схематичным рассмотрением интересного примера такого булева кольца. Возьмем канторовское множество иа отрезке (О, 11— множество, остающееся от отрезка, если из него выбросить систему интервалов и т. д Полученное множество, которое мы обозначим К, обладает' рядом замечательных свойств. Среди них отметим два: множество К вЂ” замкнутое множество действительной прямой (дополнение к открытому множеству, состоящему из объединения описанных выше интервалов и ( — сс, О), (1, +со));.
множестбо К имеет мощность континуума. Выделим в К систему Р всех подмножеств, являющихся одновременно открытыми и замкнутыми относительно К Такие подмножества в К существуют. Например, часть К, лежащая на отрезке (О, 1/2), с одной стороны, замкнута отйосительно действительной прямой и, следовательно, относительно К С другой стороны,'дополнение к этой части относительно К снова замкнуто в К, так как это есть часть К, лежащая на отрезке 11/2, 1). Следовательно, .выделенная часть К является, как - говорят, открыто-замкнутым под-множеством К Итак, система Р состоит из подмножеств К, которые замкнуты и дополнение относительно которых также замкнуто.
Нетрудно проверить, что операции пересечения и симметрической разности не выводят нас из системы г( и, следовательно, порождают в Р структуру булева кольца. Понятно, что система Р не совпадает с системой всех подмножеств К: например, подмножество, состоящее из одного числа О, не принадлежит Р, так как дополнение этого подмножества в К не замкнуто (справа от О в любой близости к'О имеются точки из-К). В нашем кольце Р вообще не существует атомов; нми могли бы быть лишь одноэлементные подмножества К вЂ” ' точки, но они не принадлежат Р. 6. С булевыми кольцами тесно связаны булееы решетки.
По существу, теория булевых колец и теория булевых. решеток являются лишь двумя формами изложения одних и тех же математических идей. Булевой решеткой мы называем множество с тремя операциями (В,й,О,-). где й и 0 — бинарные (двуместные) операции, называемые пересечением и объединением в решетке, — есть унарная (од- номестная) операция — дополнение.  — непустое множест- во элементов решетки. При этом выполняются следующие требования: А1.
айЬ=Ьйа, а0Ь=Ь()а, А2. ай(Ьйс) =(айЬ)йс, аЯЬос) = (а()Ь) ()с, АЗ. (айЬ)()Ь=Ь, (а()Ь) йь=ь,' А4. ай(Ьос) = (айЬ)()(айс), а0(Ьйс) = (а0Ь) й(а0с), 36 А5. (аПа)ЦЬ=Ь, (аЦатЬ=Ь, Типичным примером булевой решетки является сиете44а.:. Р(Е) всех подмножеств какого-либо множества Е с опера- циями а()Ь, аЦЬ, а, понимаемыми. теоретико-множественно (как теоретико-множественное пересечение, объединение и дополнение соответственно) .
Более общб, на некотором множестве Е может быть вы. делена некоторое семейство 5:-Р(В) (не обязательно всех), подмножеств, замкнутое относительно теоретико-множествен- ных операций пересечения, объединения и дополнения. По- следнее означает, что из а, Ьен5 следует аПЬ~5 и аналогич- но для других операций. В этом случае 5 также является булевой решеткой, ее называют полем множеств на Е. Так, в п. 5 открыто-замкнутые подмножества составляют поле мно- жеств на К.
Определим булеву решетку из двух элементов (О, 14„ задав операции следующим образом: аПЬ=ш1п(а, Ь), аЦЬ=гпах(а, Ь), а=1 — а. Наконец, если дана булева решетка В, то можно образо- вать решетку В'", элементы которой суть наборы (аь ..., а„) с почленными операциями. 7.
Приведем некоторые простейшие следствия аксиом бу- левой решетки. Как легко видеть, система аксиом А1 — А5 симметрична относительно операций аПЬ и аЦЬ; вместе с каж- дой аксиомой содержится двойственная аксиома, в которой операции () и Ц заменены друг иа друга. Такая двойственная система аксиом позволяет доказывать утверждения парами: если мы доказали некоторое утверждение, то ' совершенно симметрично' можно доказать и двойственное утверждение.
Практически мы часто'будем ограничиваться доказательством лишь одного из двойственных утверждений, оставляя второе читателю. В любой булевой решетке верно следующее: (1) аЦа=а, (2) айа=а. ~> (1)а = аЦ(аПЬ) =(аЦа)П(а ЦЬ) = АЗ А4 А4 = (а П (а П Ь)) Ц (а П (а Ц Ь)) = а Ц а АЗ Здесь под каждым равенством написано, на основании какой аксиомы оно получено. (2) доказывается симметрично.
С) (3) аПЬ=а4=ьаЦЬ=Ь. > Пусть аДЬ=а. Ввиду АЗ и А1 имеем (аПЬ)ЦЬ=Ь. По допущению отсюда следует, что аЦЬ=Ь. В обратную сторону доказательство проводится симметрично.' С.) 37 Положим по определению а<Ь вЂ” а()Ь=а, что ввиду (3) равносильно аоЬ=Ь. Следующие трн свойстве означают, что < есть «частичный порядок» на булевой ре- шетке (4) а«:а; (5) а<ЬЛЬ«:с=:-а<с; (6) а<',ЬЛЬ«',а=»а=Ь. (~ (4) см. (1). (5) Дано а()Ь=а, и Ь()с=Ь, необходимо показать, что а()с='а.
Но а()с=(а(1Ь)Пс=а()Ь=а. Мы использовали А2. (6) Ввиду а<Ь и Ь<а имеем а=а()Ь и а=а()Ь, Подстав- ляя в первое из этих .равенств вместо а выражение а()Ь, по лучи а= (а()Ь)ОЬ Ь ввиду АЗ. П Г = войства (7) — (12), перечисленные ниже, называются ре- шеточными свойствами объединения и пересечения. (7) а«:а()Ь; (8) Ь <аОЬ; (9) а<сЛЬ<с=»а()Ь«.с; (10) а()5<а; (11) а()5<Ь; (12) с <асс<.Ь=~-с <а()Ь. (> (7) а-.<а()Ь означает, что а()(а()Ь) =а, и следует из АЗ и А1.
(9) Дано: а()с=с и Ь()с=с. Поэтому (а()с) () (Ь()с) =с()с=с (см. (1)). Используя А1 и А2, отсюда имеем (аЦЬ) 0(с()с) =с, т. е. (а()Ь)()с=с, что означает аЦЬ<с. П (13) а()а=Ь()5; (14) а()а= 5()5. 6> (13) Аксиома Аб имеет вид а()а<Ь. Заменяя Ь на Ь()б„ получим а()а<Ь()Б. Так как а и Ь произвольны, то а()а= =Ь()5. П Ввиду (13) и (14) элементы а()а» и а0а не зависят от вы- бора а. Определим «нуль» решетки о=а()а и «единицу» ре- шетки е=а()а. Из определения и ввиду А5: (15) о=а()а; (16) е=а()а; (17) о<а; . (18) а<:е. Таким образом„о — наименьший, а е — наибольший элементы в решетке.
Далее, (19) а()о=а, а()о=о; (20) а()е е, а()е=а. Важная характеристика дополнения определяется следую- щим свойством: 38 (21) а П с = оЛа 0 с = е > с =' а. (>с=оЦс=(аПа) Цс=(аЦс) П (аЦс) = [19) (16) А4 = еП(аЦс) = аЦс, т. е. а<;с. (29) с=еПс=(аЦа)Пс =(аПс) 0(аПс) = (29) А4 =оЦ(аПс) =аПс, т. е. с<а. [Л (!9) (22) а=а. (>Подставим в (21) вместо а элемент а и вместо с элемент а. Тогда ввиду (15) и (18) имеем а=а.
П Следующие два равенства называются законами де Мореана: (23) аЦ Ь=аП Ь; (24) а П Ь = а 0 Ь. (> (23).'Используем (21). Пусть с=аПб, тогда (аЦЬ)Пс = (аЦЬ)П(аПб) = (аПаПб)Ц(ЬПаПб) =оЦо=о. Далее, (аЦЬ) 0 Цс= (аЦЬ)0(аПб) = (аЦЬЦа) П(аЦЬЦб) =еПе=е. П Следующая эквивалентность называется законом контралозиции( (25) а.я'.Ь 44-б~а. 1> Пусть а~Ь, т. е. аЦЬ=Ь, тогда аЦЬ=б, т. е. (см. (23) ) аПб=б, что означает бч.:а. Обратно, если б-.ка, то аПб=б, тогда а П Ь =Ь и ввиду (24) и (22) аЦЬ=Ь, т. е. а~Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
