WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 11 |

Для Nf нижние единицы (1, 0, 0, 0, 0), (0, 1, 1, 0, 0) и (0, 0, 1, 1, 1) функции f бу дут минимальными элементами, 1 = (1, 1, 1, 1, 1) максимальным элементом, а наименьший элемент в Nf отсутствует.

2. Ч.у. множество { 1, 2, 3, 4, 5, 6 }, | имеет следующую диаграмму Хассе:

4 2 3 Здесь 1 наименьший элемент, 4, 5 и 6 максимальные, а наибольшего элемента нет.

3. В ограниченном ч.у. множестве P(A), наименьшим элементом является пустое подмножество,, а наибольшим само множество A.

Будем обозначать через P(A) совокупность всех непустых подмножеств множества A. В ч.у. множестве P(A), при |A| 2 нет наименьшего элемента, а минимальными являются все одноэлементные подмножества.

Будем обозначать через P0(A) совокупность всех конечных подмножеств бесконечного множества A. В ч.у. множестве P0(A), наименьшим элементом будет пустое подмножество, а максимальных (следовательно, и наибольшего) элементов нет.

Если ч.у. множество имеет наименьший элемент, то элементы, непосредственно следующие за ним называют атомами. Понятно, что таковых может и не оказаться. Данное определение атома ч.у. множества совпадает с определением 1.4 атома булевой алгебры, def если в ней принять x y = (x = x y). Двойственно определяются дуальные атомы или коатомы: это элементы, непосредственно предшествующие наибольшему элементу (предполагается, что таковой существует).

Пример 16. В ч.у. множестве { 0, 1,... }, | наименьшим элементом является 1, наибольшим 0, атомы суть простые числа, а коатомы отсутствуют.

Определение 2.4. Пусть P, ч.у. множество и A P. Множества A и A определяемые условиями A def x P | a ( a x) и A def x P | a ( x a) = = A A называются верхним и нижним конусами множества A, а их элементы верхними и нижними гранями множества A соответственно. Верхним и нижним конусами пустого подмножества элементов P считают само множество P.

Ясно, что любая верхняя грань подмножества A элементов некоторого ч.у. множества содержит любой из элементов A, и если A имеет наибольший элемент, то он одновременно является и наименьшим элементом A. Аналогично для нижних граней.

Теорема 2.2 (Свойства верхнего и нижнего конусов). Верхний и нижний конусы обладают следующими свойствами.

1. A B влечёт B A и B A.

2. A A A.

3. A = A.

4. A = A.

5. (A B) = A B.

6. (A B) = A B.

Доказательство. 1. Это свойство вытекает непосредственно из определения.

2. Так как для любых x A и y A справедливо x y, то A A. Аналогично проверяется, что A A.

3, 4. В приводимом ниже соотношении первое включение следует из свойства (2), а последнее из (2) и (1).

A (A ) = (A ) A, откуда вытекает свойство (3). Аналогично для (4).

5, 6. Эти свойства вытекает непосредственно из определения верхнего и нижнего конусов ч.у. множества.

Определение 2.5. Если в A существует наименьший элемент, то он называется точной верхней гранью множества A и обозначается sup A. Если в A существует наибольший элемент, то он называется точной нижней гранью множества A и обозначается inf A.

В частности, точной верхней [нижней] гранью пустого множества является наименьший [наибольший] элемент ч.у. множества.

Пример 17. 1. Пусть P = { a, b, c, d } и два различных порядка на P задаются следующими диаграммами Хассе:

d d c c a a b b Для A = { a, b } имеем A = { c, d } в обоих случаях, но в первом случае sup A отсутствует, а во втором sup A = c.2. Для элемента ч.у. множества Bn, имеем = B(, 1), = B( ); sup = inf =, 0, где B(, ) подкуб Bn, натянутый на вершины и.

Строго говоря, вторая диаграмма не есть диаграмма Хассе: линии, соединяющие элемент d с элементами a и b здесь излишни.

Непосредственно из определений вытекает также справедливость следующих соотношений.

1. Если a b, то sup { a, b } = a, inf { a, b } = b.

2. Пусть P, ч.у. множество и A B P. Если существуют sup A и sup B ( inf A и inf B ), то sup A sup B (inf A inf B ).

3. Если A P(M), то sup A совпадает с пересечением всех надмножеств A, а inf A с объединением всех подмножеств A.

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

На рис. 4a ) приведена диаграмма Хассе четырёхэлементной цепи.

Ч.у. множество может содержать цепи в качестве ч. у. подмножеств. Цепь в ч.у. множестве называется максимальной, если её объединение с любым не принадлежащим ей элементом цепью не является. В ч.у. множестве N, | для любого M N цепью является, например, подмножество { 2n | n M }; при M = N имеем максимальную цепь.

2.1.3 Изотонные отображения и порядковые идеалы Определение 2.7. Пусть P и P ч.у. множества. Отображение : P P называется порядковым гомоморфизмом или изотонным отображением, если следование x y (x) (y), и обратно изотонным отображением, если следование (x) (y) x y выполняются для любых x, y P.

Если изотонно, обратно изотонно и инъективно, то его называют вложением или мономорфизмом ч.у. множества P в ч.у. множество P, что обозначают P P.

Сюръективный мономорфизм ч.у. множеств называют порядковым изоморфизмом. Если ч.у. множества P и P (порядково) изоморфны, то пишут P P.

= Пример 18. 1. Ч.у. множество a ) изображённое на рис. 4 является изотонным образом ч.у. множества b ), если в качестве отображения взять функцию (x) = |x|. Это отображение не инъективно и, следовательно, вложением не является.

2. Тождественное отображение какого-либо подмножества ч.у. множествва N, | во множество натуральных чисел с естественным порядком изотонно, но не обратно изотонно и, следовательно, вложением также не является.

3. Если Q неодноэлементное ч.у. множество с тривиальным порядком, а Q то же самое множество с нетривиальным порядком, то тождественное отображение Q на себя является изотонным и взаимнооднозначным, но не обратно изотонным и, следовательно, не изоморфизмом между данными ч.у. множествами.

4. Естественное вложение nZ в Z, где n N0, есть их вложение как ч.у. множеств с естественным порядком.

Пусть P и P ч.у. множества. Отображение : P P называется антиизотонным, если следование x y (x) (y) выполняется для любых x, y P. Отображение булеана непустого множества X в себя такое, что для A X (A) = X, есть антиизотонное отображение.

Легко видеть, что для ч.у. множеств P и P биекция : P P есть порядковый изоморфизм, если и только если для любых a, b P имеет место a b (a) (b).

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

Доказательство. Пусть P, ч.у. множество. Сопоставим каждому x P его нижний конус x. Объединение всех нижних конусов элементов P образует множество U P(P ). Понятно, что введённое соответствие есть биекция между P и U. С другой стороны, по свойству нижнего конуса, x y x y и есть изоморфизм между P, и U,. Таким образом, показано P, P(P ),.

К ч.у. множествам можно применять различные операции. Рассмотрим некоторые из них.

Определение 2.8. Если P = P, и Q = Q, два ч.у. множества с непеp q ресекающимися носителями, то их прямой суммой или дизъюнктивным объединением P + Q называется множество P Q с частичным порядком таким, что x y когда либо x y, либо x y. Ч.у. множество, не являющийся прямой суммой некоторых p q двух других ч.у. множеств называется связанным.

Если P = P, и Q = Q, два ч.у. множества, то их прямым или декарp q товым произведением P Q называется множество P Q с частичным порядком таким, что (x, y) (x, y ) только когда x x и y y. Прямое произведение n p q экземпляров ч.у. множеств P обозначают Pn.

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

множеств P и Q рисуют диаграмму Хассе ч.у. множества P, отбрасывая соединения между элементами P заменяют каждый элемент x P копией Qx ч.у. множества Q и соединяют соответствующие элементы множеств Qx и Qy, если элементы x и y были соединены в диаграмме Хассе ч.у. множества P.

Пример 19. На рис. 5 показан пример прямого произведения двух ч.у. множеств вида “зигзаг”.

Из определения ясно, что для ч.у. множеств P и Q справедливо P Q Q P, = хотя соответствующие диаграммы Хассе обычно выглядят совершенно не похожими друг на друга.

Легко убедиться, что для операций + и над ч.у. множествами (с точностью до изоморфизма) выполняются законы ассоциативности и коммутативности и первый дистрибутивный закон:

P (Q + R) (P Q) + (P R).

= Здесь предполагается, что Q + R существует.

Если P = P, и Q = Q, два ч.у. множества, то обозначим через QP p q множество всех изотонных отображений из P в Q. Введём на QP порядок, положив f g, если f(x) g(x) для всех x P. Таким образом, QP, есть ч.у. множество.

q Можно проверить, что для +, и введенной выше операции “возведения в степень” над ч.у. множествами выполняются соотношения RP +Q RP RQ; (RQ)R RQR = = (здесь также предполагается, что Q + R существует).

Определение 2.9. Пусть P, ч.у. множество. Подмножество I элементов P называется порядковым идеалом, если из x I и y x следует y I. Подмножество F элементов P называется порядковым фильтром, если из x F и x y следует y F.

Z3 Z Z3 ZРис. 5: Диаграммы Хассе двух ч.у. множеств и их прямого произведения Таким образом, порядковые идеалы [фильтры] ч.у. множества суть такие его подмножества, которые вместе с каждым своим элементом a содержат все элементы, предшествующие [следующие за] a. Ясно, то есть порядковый идеал любого ч.у. множества множества P,. Если x элемент ч.у. множества, то x и x являются порядковыми идеалом и фильтром соответственно. Такие идеалы и фильтры называют главными;

мы будем обозначать их J(x) и F (x) соответственно.

Множество всех порядковых идеалов ч.у. множества P, упорядоченное по включению, образует ч.у. множество, которое мы будем обозначать J(P ). Теорема 2.3 утверждает, что P J(P ) и (x) = x = J(x).

Антицепь есть подмножество A ч.у. множестве P, в котором все элементы попарно несравнимы. Например, в ч.у. множестве N, | антицепью является произвольное подмножество взаимно некратных чисел, а в множестве Bn, совокупности верхних нулей либо нижних единиц некоторой монотонной булевой функции.

Если P, конечное ч.у. множество, то существует взаимнооднозначное соответствие между его анитцепями и порядковыми идеалами. Действительно, с одной стороны, множество M максимальных элементов идеала I есть антицепь, а с другой I = a. Если некоторое подмножество A ч.у. множества P и его идеал I связаaM ны таким соотношением, то говорят, что A порождает I. В случае A = { a1,..., ak } пишут I = a1,..., ak ; например, J(a) = a.

Пример 20. На рис. 6 показаны диаграммы Хассе четырёхэлементного ч.у. множества P и множества его порядковых идеалов J(P ). Каждому порядковому идеалу из J(P ) соответствует антицепь P.

d a, c a, b c d c a b a b J(P ) P Рис. 6: Диаграммы Хассе ч.у. множеств P и J(P ). Главные идеалы выделены 2.1.4 Вполне упорядоченные множества и смежные вопросы В ходе исследований ч.у. множеств были сформулированы следующие утверждения.

Лемма Куратовского-Цорна. Если в ч.у. множестве P любая цепь имеет верхнюю грань, то каждый элемент из P содержится в некотором максимальном.

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

Оказалось, что эти утверждения эквивалентны. Более того, они также эквивалентны фундаментальной теоретико-множественной аксиоме выбора и аксиоме о полном упорядочении.

Аксиома выбора (AC). Для любого непустого множества A существует отображение f, сопоставляющая каждому непустому подмножеству B множества A элемент из B : f(B) B для любого B P(A).

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

Для формулировки следующей аксиомы нам потребуются новое понятие.

Определение 2.10. Линейный порядок P называется полным, если каждое его непустое подмножество содержит наименьший элемент. В этом случае множество P называют вполне упорядоченным, а его элементы трансфинитами.

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

Пример 21. 1. Очевидно, вполне упорядочены все конечные цепи, а так же цепь N с естественным порядком.

Множество целых чисел Z не является вполне упорядоченным относительно естественного порядка, поскольку оно не имеет наименьшего элемента. Если же на Z задать порядок 0 1 2... n... -n... -2 -1, то получим цепь, в которой не все подмножества будут иметь наименьшие элементы, и поэтому это ч.у. множество не приобретёт свойства полной упорядоченности.

2. Множество 1 1 2 3 1 { m - | m, n N } = { 0,,,,..., 1, 1 +, 1 +,..., n 2 3 4 2 1..., m, m +, m +,... } 2 с естественным порядком является вполне упорядоченным. Его предельные элементы суть натуральные числа.

Аксиома о полном упорядочении. Любое непустое множество можно вполне упорядочить.

Пример 22. Множество целых чисел Z можно вполне упорядочить считая, например, что 0 1 -1 2 -2 3... или 1 2... 0 -1 -2....

В последнем случае 0 предельный элемент.

Покажем, к примеру, как аксиому выбора можно получить из аксиомы о полном упорядочении. Пусть A непустое множество; по аксиоме о полном упорядочении его можно считать вполне упорядоченным. Тогда в качестве f можно взять отображение, ставящее в соответствие каждому непустому подмножеству A его наименьший элемент.

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

Таким образом, истинными или ложными все эти утверждения могут быть только одновременно. Что же имеет место “в действительности” Ответ на поставленный вопрос зависит от того, какими свойствами мы наделяем понятие множество. В наиболее общей форме проблема выражена в аксиоме выбора, предложенной Э. Ц ермело в 1904 г.

при разработке аксиоматической теории множеств. Для конечных множеств её справедливость очевидна. Однако при рассмотрении бесконечных совокупностей бесконечных множеств эта очевидность теряется. Все же попытки свести указываемое утверждение к фундаментальным принципам теории множеств оказались безуспешными: в аксиоматике ZF Цермело-Френкеля теории множеств13 не выводимы ни отрицание аксиомы выбора См., например, Френкель А., Бар-Хиллел И. Основания теории множеств. М.: Мир, 1966.

(К. Гёдель, 1939), ни она сама (П. Коэн, 1963). Таким образом, аксиома выбора является независимым от ZF утверждением, и добавление к ZF как самой этой аксиомы, так и её отрицания порождает две равноправные непротиворечивые аксиоматики теории множеств.14 Поэтому в практической работе можно как принять аксиому выбора, так и отказаться от неё.

Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 11 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.