WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 11 |

Исследования показали, что, с одной стороны, имеются “отрицательные” последствия принятия аксиомы выбора. Выяснилось, что её принятие влечет существование объектов с парадоксальными, на первый взгляд, свойствами: неизмеримого по Лебегу множества действительных чисел; такого разбиения шара на конечное число частей, что из них движениями в пространстве оказывается возможным составить два таких же шара и др. Отметим, что все рассматриваемые утверждения неконструктивны и являются теоремами чистого существования.С другой стороны, отклонение аксиомы выбора существенно обедняет содержание конкретных исследований, не связанных с вопросами оснований математики и теории множеств. Например, без её привлечения не удается доказать ни наличия базиса у произвольного векторного пространства, ни эквивалентности двух определений непрерывности функции в точке (на языке - и через пределы последовательностей), ни некоторых других важных и привычных свойств различных математических объектов. За принятие аксиомы выбора говорит и следующий, весьма сильный, аргумент. Как отмечалось выше, К. Гёдель показал, что присоединение аксиомы выбора к системе ZF не увеличивает опасности впасть в противоречие, т.е. если в полученной системе встретилось противоречие, то причина его в ZF, а не в аксиоме выбора. Более того, из доказательства Гёделя вытекает, что всякое свойство натуральных чисел, которое можно доказать с помощью аксиомы выбора, можно доказать и без неё. В силу этого, по крайней мере в теории натуральных чисел, аксиому выбора можно рассматривать как вспомогательное средство, нужное лишь для упрощения доказательств. Указанные соображения обычно перевешивают, и при конкретных математических исследованиях аксиому выбора (или эквивалентное ей утверждение, если это более удобно), как правило, принимают.

Заметим, что в данном пособии мы будем оставаться в рамках т.н. наивной теории множеств, которая позволяет рассматривать любое множество, точно определяемое каким-либо свойством. Последовательное применение этого принципа, как известно, может привести к противоречиям (парадоксам), однако мы не встретимся с ним в ходе наших рассмотрений.

def Для вполне упорядоченного множества определяют множество [o, a) = a {a}, которое называют начальным отрезком a (при этом [o, o) есть пустое множество). Справедлива Теорема 2.4 (О сравнении вполне упорядоченных множеств). Пусть A и B два вполне упорядоченных множества. Тогда имеется лишь одна из следующих возможностей:

1) A B;

= 2) A изоморфно начальному отрезку B ;

3) B изоморфно начальному отрезку A.

Естественно, при условии непротиворечивости самой системы ZF, что, как известно, является открытым вопросом.

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

Доказательство этой теоремы имеется, например, в [14].

Если между множествами A и B существует биекция, назовем их равномощными, что будем обозначать A = B. В противном случае будем говорить, что они неравномощны и писать A = B. Здесь под X понимается новый объект, связанный с множеством X; он называется кардинальным числом X или кардиналом.

Используя теорему 2.4, теорему Кантора-Шрёдера-Бернштейна (1.18) и аксиому о полном упорядочении, легко доказать справедливость следующего утверждения.

Теорема 2.5 (О сравнении множеств). Для любых множеств A и B имеется лишь одна из следующих возможностей:

1) A = B;

2) A = B для некоторого B B, но B = A для любого A A;

3) B = A для некоторого A A, но A = B для любого B B.

Данная теорема лежат в основе учения о мощности множеств. Она позволяет ввести порядок на множестве кардинальных числе, а именно считать, что A < B и A > B соответственно в случаях 2) и 3) данной теоремы.

Важно отметить, что на вполне упорядоченные множества можно обобщить метод математической индукции.

Утверждение 2.1 (Принцип трансфинитной индукции). Пусть P вполне упорядоченное множество с каждым элементом которого связано утверждение S, образующие совокупность S. Тогда, если из справедливости S для всех [o, ) следует справедливость S, то верны все утверждения из S.

Доказательство. Пусть среди S имеется неверное утверждение. Тогда непусто множество E неверных утверждений. Пусть наименьший элемент E, который всегда существует в силу полного порядка на P. Но тогда, поскольку S справедливо для всех [o, ), то справедливо и S. Противоречие.

2.2 Алгебраические решётки 2.2.1 Решёточно упорядоченные множества и решётки Определение 2.11. Ч.у. множество, в котором для любых элементов a и b существуют inf { a, b } и sup { a, b } называют решёточно упорядоченным.

Ясно, что в решёточно упорядоченном множестве точные верхние и нижние грани существуют для любого конечного подмножества элементов.

Пример 23. 1. Модели, изображённые на рис. 4 (см. c. 30) суть решёточно упорядоченные множества.

2. Любая цепь решёточно упорядочена. Модели R,, N, | и P(A), суть решёточно упорядоченные множества. Операциями объединения будут здесь max, (НОК) и, а операциями пересечения min, (НОД) и соответственно.

3. На рис. 7 представлены два ч.у. множества, причем лишь первое из них является решетчато упорядоченным, т.к. во втором не существуют sup { a, b } и inf { c, d }.

a c d c a b d b o o Рис. 7: Диаграммы Хассе двух ч.у. множеств с 6-ю элементами Мы ввели понятие решёточно упорядоченного множества, отталкиваясь от отношения порядка. Однако возможен другой, эквивалентный данному, подход, опирающийся на алгебраические операции.

Определение 2.12. (Алгебраической) решёткой L называется непустое множество L с заданными на нём двумя бинарными операциями: объединения ( ) и пересечения ( ), подчиняющимися двойственным парам законов коммутативности, ассоциативности, идемпотентности и поглощения (см. с. 4).

Отметим, что раньше вместо термина решётка часто употреблялся термин структура. Теперь под структурой обычно понимают алгебраическую систему.

Приведённое выше определение утверждает, что алгебраическая решётка есть AC L = L,,, двуместные операции и которой удовлетворяют указанным законам.

Следствием их двойственности является Принцип двойственности (для решёток). Любое утверждение, истинное в некоторой решётке, остаётся истинным, если в нём произвести замены символов.

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

Для универсальных граней o и решёток выполняются законы o, (см. определение 1.1). Ясно, что бесконечная решётка может содержать, а может и не содержать универсальных граней, а конечная решётка их обязательно содержит.

Пример 24. 1. Очевидно, любая булева алгебра есть алгебраическая решётка. С другой стороны, любая цепь есть решётка, являясь булевой алгеброй лишь при числе элементов, равном 2.

2. На рис. 8 изображены диаграммы Хассе всех, за исключением линейного порядка, решёток с пятью элементами. Последние две решётки называют “пятиугольник” и “ромб” и обозначают, соответственно, N5 и M3.

3. Ч.у. множество E(A), всех отношений эквивалентности на множестве A, рассмотренное в примере 14.2 есть решётка с универсальными гранями o = и A c a b a c b o o a) b) c a c b o b a o c) N5 d) MРис. 8: Диаграммы Хассе всех решёток с 5-ю элементами (линейный порядок опущен).

=. Здесь для эквивалентностей и в качестве выступает их экA вивалентное замыкание (случае перестановочности и совпадающее с их произведением и объединением см. на c. 20 следствие 2 утверждения 1.2), а в качестве теоретико-множественное пересечение. Эту решётку называют также решёткой всех разбиений множества A.

4. Множество Sub (G) всех подгрупп группы G с операциями x y = x, y (подгруппа порожденная объединением подгрупп x и y ) и x y = xy (это множество, как известно, всегда является группой) есть решётка. Здесь o = E (единичная группа) и = G.

В ч.у. множестве L = N, | для любой пары натуральных чисел m и n существуют наименьшее общее кратное m n и наибольший общий делитель m n, из определений которых следует, что mn = sup { m, n } и mn = inf { m, n }. Таким образом, L решёточно упорядоченное множество. С другой стороны, операции и удовлетворяют законам коммутативности, ассоциативности и идемпотентности, и поэтому N,, алгебраическая решётка. Наконец, если в данной решётке ввести отношение по праdef вилу mn = m n = m, то оказывается отношением делит, и, таким образом, N, = L ч.у. множество.

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

Теорема 2.6.

1. Пусть P, решёточно упорядоченное множество. Если для любых элементов x и y из P положить def def x y = sup {x, y}, x y = inf {x, y}, то P,, будет алгебраической решёткой.

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

Доказательство. Доказательство (1) сводится к проверке законов коммутативности, ассоциативности и поглощения в полученной АС P,,.

Доказательство (2) сводится к проверке рефлексивности, антисимметричности и транзитивности у введённого отношения и установлению, что sup { x, y } = x y, а inf { x, y } = x y.

Теорема 2.6 устанавливает взаимнооднозначное соответствие между решёточно упорядоченными множествами и алгебраическими решётками: из одной АС всегда можно получить другую. Поэтому термин решётка применяют для обоих понятий, имея в виду, что любую решётку можно представить либо как ч.у. множество, либо как алгебру.

Например, решёточно упорядоченные множества R,, N, | и P(A), из примера 23 можно записать в виде алгебраических решёток соответственно как R, max, min, N,, и P(A),,. Возможность такого рассмотрения решёток позволяет вводить в них как порядковые, так и алгебраические операции, что приводит к богатой и многообразной в приложениях теории. Отметим очевидную изотонность решётчатых операций и : если a1 b1 и a2 b2, то a1 a2 b1 b2 и a1 a2 b1 b2.

2.2.2 Основные свойства решёток Теорема 2.7. Элементы x, y и z любой решётки удовлетворяют следующим неравенствам полудистрибутивности Dtr1 : (x y) z (x z) (y z) ;

Dtr2 : (x y) z (x z) (y z) ;

и полумодулярности Mod : x y x (y z) y (x z) = (x y) (x z) ;

Mod : x y x (y z) y (x z) = (x y) (x z).

Доказательство. Имеем x z x x y x z (x y) z x z z и y z y x y y x (x y) z.

y z z Таким образом (x y) z есть верхняя грань для x z и y z. Это означает, что (x z) (y z) (x y) z, и следование Dtr1 доказано. Второе неравенство дистрибутивности следует из только что доказанного по принципу двойственности.

Неравенства полумодулярности есть частный случай неравенств дистрибутивности.

Определение 2.13. Отображение решётки L в решётку L называется алгебраическим или решёточным гомоморфизмом, если для любых x, y L справедливы равенства (x y) = (x) (y) и (x y) = (x) (y), что записывают = Hom (L, L ).

Биективный решёточный гомоморфизм есть решёточный изоморфизм. Изоморфизм решётки в себя называется автоморфизмом.

Инъективные и сюръективные решёточные гомоморфизмы называют решёточными (или алгебраическими) мономорфизмами и эпиморфизмами соответственно.

Порядковые гомоморфизмы решёток как ч.у. множеств, вообще говоря, не являются алгебраическими: отображение P0(M) N0, (X) = |X| являясь изотонным, не сохраняет ни одну из решёточных операций. Напротив, алгебраический гомоморфизм решёток будет и их порядковым гомоморфизмом. Действительно, если алгебраический гомоморфизм решётки A,, на некоторую другую решётку, то, поскольку сохраняет пересечение, для любых x, y A имеем x y x = x y (x) = (x y) = (x) (y) (x) (y), (2.1) и, значит, изотонно. Аналогично изотонность следует и из сохранения объединения.

Поэтому можно сказать, что алгебраический гомоморфизм решёток, “сильнее” порядкового.

В случае изоморфизма проблемы снимаются.

Теорема 2.8. Две решётки алгебраически изоморфны, если и только если они изоморфны как порядки.

Доказательство. () Пусть алгебраический изоморфизм решётки A,, на некоторую другую решётку. Так как отображение взаимнооднозначно и изотонно, остаётся показать его обратную изотонность. Обратная изотонность устанавливается обращением следования в (2.1) что можно сделать, поскольку взаимнооднозначно.

() Пусть A и B две решётки, изоморфные как порядки. Докажем устойчивость операции относительно порядкового изоморфизма, т.е. что (x y) = (x) (y).

Устойчивость операции относительно будет справедлива по двойственности.

Для произвольных элементов x, y A в силу изотонности в решётке B справедливым (x y) { (x), (y) }. Пусть b есть элемент { (x), (y) }. Тогда, в силу сюръективности, в A найдется элемент a, такой, что (a) = b. Но тогда (a) (x) (a) (y) a x a y a (x y) (a) (x y) (первое следование здесь возможно в силу обратной изотонности ). Таким образом, (x y) = inf { (x), (y) }, или (x y) = (x) (y).

Данная теорема позволяет не различать типы изоморфизма решёток и использовать.

для него традиционный символ = Имея исходные решётки, можно строить новые, используя их гомоморфные образы и операции + и над ч.у. множествами. При этом можно показать, что для построения диаграммы Хассе декартова произведения конечных решёток остается верным способ её построения для них, как для ч.у. множеств.

Определение 2.14. Подрешёткой решётки L называется решётка L такая, что L устойчивое относительно операций и подмножество L. При этом используется обозначение L L.

Пример 25. 1. Каждое подмножество решётки L является подрешёткой, если и только если L цепь.

2. Пересечение подрешёток либо пусто, либо является подрешёткой. Для любых элементов x и y решётки L интервал [ x, y ] либо пуст, либо является подрешёткой L.

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

3. Если = Hom (L, L ), то Im L.

4. Обозначим через N множество натуральных чисел, свободных от квадратов (см. пример 3.4). Тогда N,, N,,.

5. С помощью теоремы 2.8 устанавливается, что решётка N изоморфна решётке P0(A) всех конечных подмножеств счётного множества A (считая, что 1 свободно от квадратов).

Рассмотрим любую биекцию между множеством простых чисел (которые все содержатся в N, и множество которых, как показал Евклид, счётно) и A. Таким образом, определено частичное инъективное отображение для простых чисел из N в A. Полагаем (1) =. Далее, для остальных элементов n = p1... pk, k > 1 из N, где p1,..., pk различные простые числа, положим (n) = { (p1),..., (pk) }.

Нетрудно проверить, что полученное отображение есть изоморфизм указанных решёток.

Легко проверяется, что прямое произведение решёток является решёткой. Ясно также, что совокупность Sub(L) подрешёток решётки L является ч.у. множествм (упорядоченным по включению).

Определение 2.15. Пусть L,, решётка. Подмножество I элементов L называется решёточным идеалом, если x I y x y I и x, y I x y I.

Подмножество F элементов L называется решёточным фильтром, если x F x y y F и x, y F x y F.

Очевидно, идеалы [фильтры] решёток суть их устойчивые относительно операций [ ] порядковые идеалы [фильтры]. Непустое подмножество I [ F ] оказывается идеалом [фильтром] решётки L, если и только если для любых её элементов x и y справедлива эквивалентность x, y I x y I [x, y F x y F ].

Легко видеть, что если L решётка, а I и F соответственно идеал и фильтр на ней, то для произвольного её элемента x если y I, то x y I, а если y F, то x y F.

Сама решётка L всегда будет своим идеалом и фильтром. Все другие идеалы [фильтры] L называют собственными. Если L имеет наименьший o [наибольший ] элемент, то он будет идеалом [фильтром] L. В случае, когда в решётке нет наименьшего [наибольшего] элемента, то в число её идеалов [фильтров] договариваются включать пустое подмножество.

Если x элемент решётки, то главные порядковые идеал J(x) = x и фильтр F (x) = x являются, очевидно, также и (главными) решёточными идеалом и фильтром.

В конечной решётке все решёточные идеалы и фильтры главные. Для бесконечных решёток это не так. Например, для бесконечного множества A совокупность P0(A) всех его конечных подмножеств будет неглавным идеалом в решётке P(A).

Если гомоморфизм решётки L на решётку с нулём [единицей], то полный прообраз нуля [единицы] является идеалом [фильтром] в L. Такой идеал [фильтр] называется ядерным. Не всякий идеал [фильтр] является ядерным: например, идеал { o, a, b, e } решётки, изображённой на рис. 9, ядерным не является.

Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 11 |






















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

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