Полные решетки

Содержание

 

Введение                                                                                 2          

                                

§ 1. Частично упорядоченные множества.                  3-7

 

§ 2. Трансфиниты                                                           8-16

 

§ 3. Полные решетки                                                    17-26       

    

Упражнения                                                                   27-30

 

Список  использованной литературы                              31

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение.

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

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

Появление понятия «решётка»  относится к середине XIX века. Чётко  его сформулировал Р. Дедекинд в  работах 1894 и 1897 годов. Термин «lattice», переведённый как «структура» был введён Биркгофом в 1933 году. В настоящее время в русской терминологии (из-за многозначности слова «структура») он вытеснен переводом «решётка». Исторически роль теории решёток объясняется тем, что многие факты, касающиеся множества идеалов кольца и множества нормальных подгрупп группы, выглядят аналогично и могут быть доказаны в рамках теории дедекиндовых решёток. Как самостоятельное направление алгебры эта теория сформировалась в 30-х годах XX века. Наиболее важные классы решёток, кроме дедекиндовых, — это полные решётки, дистрибутивные решётки и булевы алгебры.

 

 

 

 

§ 1. Частично упорядоченные множества.

Следует напомнить, что отношением на непустом множестве Р называется подмножество ρ прямого произведения РхР. Вместо (а,b) ρ часто пишется aρb. Отношение ≤ на множестве Р называется порядком, если:

1) а≤а для всех a P  (рефлексивность);

2) если а≤b и b≤c, то а≤с (транзитивность);

    3)если а≤b и b≤a, то а=b (антисимметричность).   
Запись а < b означает, что а <  b и а ≠b.

Порядок ≤ называется тривиальным, если а≤b в том и только в том случае, когда а = b.

Множество Р называется частично упорядоченным, если оно непусто и на нем зафиксирован некоторый порядок. Множество с тривиальным порядком называется тривиальным частично упорядоченным множеством. Всякое подмножество частично упорядоченного множества, очевидно, является частично упорядоченным множеством относительно того же самого порядка. Отображение φ частично упорядоченного множества Р в частично упорядоченное множество Р' называется  изотонным [антиизотонным], если а≤b влечет φ(a)≤φ(b) [φ(a)≥φ(b)].

Частично упорядоченные  множества Р иР' называются изоморфными [антиизоморфными], если существует изоморфизм [антиизоморфизм] Р на Р', т. е. такое взаимно однозначное отображение φ множества Р на множество Р', что а≤b имеет место тогда и только тогда, когда φ(a)≤φ(b) [φ(a)≥φ(b)].

Заметим, любой частичный  порядок можно представить изображением объединения множества диаграмм соответствующих линейно упорядоченных  подмножеств. Полученная таким образом  диаграмма называется диаграммой Хассе.

Пример1. Пусть A = {1, 2, 3}. На множестве всех подмножеств множества A рассмотрим отношение "быть подмножеством". Диаграмма этого упорядоченного множества приведена на рисунке (а).

Пример2. Пусть X = {1, 2, 3, 5, 6, 10, 15, 30}. Введем на этом множестве отношение "делится". Диаграмма этого упорядоченного множества приведена на рисунке  (б).

Пример3. На множестве X = {1, 2, 3, 4, 5, 6, 7, 8} рассмотрим отношение линейного порядка <. Его диаграмма изображена на рисунке (в).

 

Элементы а и b частично упорядоченного множества называются сравнимыми, если имеет место a≤b и b≤a. Два элемента тривиального частично упорядоченного множества, очевидно, сравнимы тогда и только тогда, когда они совпадают.

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

Элемент v частично упорядоченного множества Р называется наибольшим, если х ≤ v для всех х Р. Если же и≤ х для всех х Р, то элемент и называется наименьшим. Наибольший элемент часто называют единицей, а наименьший — нулем. Конечно, частично упорядоченное множество может не содержать ни нуля, ни единицы. Таким, в частности, будет неодноэлементное тривиальное частично упорядоченное множество. Однако более одного наибольшего элемента частично упорядоченное множество содержать не может.В самом деле, если v и v' — наибольшие элементы частично упорядоченного множества Р,то v ≤v' и v' ≤v, а, следовательно, v = v' по свойству антисимметричности. Аналогично устанавливается единственность наименьшего элемента. Элемент ω частично упорядоченного множества Р называется максимальным, если из ω≤ х для некоторого х Р вытекает x = ω. Если из x≤m для некоторого х Р следует, что х = т, то т называется минимальным элементом. Легко проверяется, что всякий наибольший элемент является максимальным, а всякий наименьший элемент —минимальным. Обратное, вообще говоря, места не имеет.Так, например, в тривиальном частично упорядоченном множестве всякий элемент является как максимальным, так и минимальным. Заметим, что определение наименьшего элемента получается из определения наибольшего элемента простой заменой символа ≤  на  ≥. Точно таким же образом связаны понятия минимального и максимального элементов. Вообще, имея какое-либо высказывание о частично упорядоченном множестве и заменяя ≤  на  ≥, получаем новое высказывание. Высказывания, связанные таким образом, называются двойственными.

Если  A —непустое подмножество частично  упорядоченного множества Р,то верхним (нижним) конусом множества А называем множество всех таких элементов x Р, что  а≤х   [х≤а] для   всех а А.   Верхним  (нижним) конусом пустого множества будем считать само множество Р. Верхний  и нижний конусы множества А будем обозначать символами A^∆ и A ,соответственно. Наименьший  (наибольший)  элемент верхнего  (нижнего) конуса множества А (если он существует) называется  точной верхней (нижней) гранью множества А. В частности, точной верхней (нижней) гранью пустого множества является наименьший (наибольший) элемент частично упорядоченного   множества Р. Точную верхнюю(нижнюю)  грань множества А в  частично   упорядоченном   множестве  Р будем обозначать sup_p A [inf_p А]. Впрочем, индекс часто будет опускаться. Подчеркнем, что sup_pA и inf_pA (если они   существуют) —однозначно   определенные   элементы множества Р, ибо,  как было отмечено выше, A^∆ [A ] содержит не более  одного  наименьшего (наибольшего) элемента. Определение точной верхней грани множества A можно перефразировать так: и = supA в том и  только в том случае, если и≥а для всех а А и х≥и всякий раз, когда х≥а для всех  а А.   Аналогичную   перефразировку  допускает  и определение точной нижней грани.

Трансфинитная индукция  базируется на следующем факте:

Теорема 1. Следующие свойства частично упорядоченного множества Р эквивалентны:

(1)  (условие минимальности). Всякое непустое подмножество множества Р является частично упорядоченным множеством, содержащим минимальные элементы.

(2)   (условие индуктивности). Если все минимальные элементы множества Р обладают некоторым свойством и ' из того, что все элементы х из Р, удовлетворяющие условию х <а, обладают свойством , вытекает, что элемент а также обладает свойством , то свойством обладают все элементы множества Р.

(3)  (условие обрыва убывающих цепей). Для всякой цепи

а₁ ≥a₂ ≥ ... ≥а_k ≥ ...

элементов из Р найдется такой номер п, что

a_n = а_п+1 = а_п+2=...

Доказательство.

 (1) (2). Допустим, что выполнены посылки условия индуктивности, и рассмотрим множество М всех элементов из Р, не обладающих свойством . Если заключение условия (2) места не имеет, то М не пусто. Ввиду (1) в М имеется минимальный элемент а. По условию этот элемент не может быть минимальным элементом множества Р. Если х < а, то

x М, и, следовательно, х обладает свойством по условию. Противоречие.

(2) (3). Условимся считать, что элемент а Р обладает свойством , если всякая убывающая цепь, начинающаяся с элемента а, обрывается, т. е. удовлетворяет условию (3). Всякий минимальный элемент т Р обладает свойством , так как для соответствующей цепи обязательно

т = а₁=а_г= ...

Если а Р таков, что все х<а обладают свойством , то рассмотрим цепь

a ≥ a₁ ≥ a₂≥…

Если знаки равенства  стоят не всюду, то найдем такой номер i, что а = а₁= ... = a_i-1 и a_i-1 >a_i. Но тогда элемент a_i  обладает свойством , т.е. цепь

a_i ≥ a_i+1 ≥ … ,

а, значит, и цепь

a₁ ≥ … ≥ a_i ≥  a_i+1 ≥ …

обрывается. Таким образом, элемент a обладает свойством  . Ввиду (2) все элементы из Р обладают свойством  , а это и означает, что Р удовлетворяет условию (3).

(3) (1). Допустим, что непустое подмножество М множества Р является частично упорядоченным множеством без минимальных элементов. Выберем в качестве a₁ произвольный элемент из М и допустим, что построена цепь

a₁ > a₂ > _… > a_n

элементов из М. Так как а_п не минимален в М, то в М существует элемент а_п+1 < а_n.

Таким образом, возникает  бесконечная цепь а₁ > a₂ > … > a_n >… , не удовлетворяющая условию (3).

Цепь, удовлетворяющая условию минимальности (а значит, и остальным условиям теоремы 1), называется вполне упорядоченным множеством.

 

 

 

§ 2. Трансфиниты.

Элементы вполне упорядоченного множества носят название трансфинитов или трансфинитных чисел. Вполне упорядоченным множеством является всякая конечная цепь. Естественным образом упорядоченное множество натуральных чисел также вполне упорядочено. Множество всех целых чисел не является вполне упорядоченным относительно естественного порядка, так как оно не имеет наименьшего элемента. Однако оно становится вполне упорядоченным, если установить порядок следующим образом:

1 < 2 < 3 <... < 0 < —1 < —2 < —3 <...

Другим примером не вполне упорядоченной цепи служит отрезок  действительных чисел [0, 1].

Из определения вполне упорядоченного множества вытекает, что оно всегда содержит наименьший элемент 0. Последующие элементы естественно  обозначать через 1, 2, ... и т. д. Если α —некоторый трансфинит, то нижний конус α , из которого удален элемент α, называется начальным отрезком и обозначается через [0, α). Символ [0, 0) понимается как пустое множество. Если α≠0 и начальный отрезок [0, α) не содержит наибольшего элемента, то трансфинит а называется предельным. Примером предельного трансфинита может служить число 0 в рассмотренном выше вполне упорядоченном множестве целых чисел. Для всякого трансфинита α среди трансфинитов верхнего конуса α^∆, отличных от α, существует наименьший, который будем обозначать через α + 1.

 

Предложение 2. Если α —предельный трансфинит, то

[0, α)= U [0, β)

  β<α

Доказательство. Если γ [0, α), то, поскольку между γ и γ + 1 элементов нет, γ +1 ≤ α. Однако равенство, в силу предельности α, невозможно. Таким образом,

γ

[0,γ+1)   U [0, β) , т.е. [0,α) U [0, β)

                                           β<α                                               β<α                                                                                  

 

Обратное включение очевидно.

Предложение 3. Если Q —вполне упорядоченное множество и = Q, то или

U [0, ξ)= Q , или U [0, ξ)= [0, α] , для некоторого α

Q

              ξ                       ξ

 

Доказательство.   Положим  Q' = U [0, ξ)= Q

                                                         ξ     

Если Q' ≠ Q, то множество Q\ Q' не пусто и, следовательно, содержит наименьший элемент α. Если α≤γ, где γ Q' , то γ [0,ξ), для некоторого ξ .

Следовательно, α ≤ γ < ξ , откуда, α Q' вопреки выбору элемента α. Таким образом,Q' [0, α). Если же β<α, то β Q', в силу выбора элемента α, т. е. [0, α) Q' .

Примем в качестве аксиомы  следующее  утверждение:

Аксиома о полном упорядочении. На всяком непустом множестве можно задать порядок, превращающий его во вполне упорядоченное множество.

Теорема 2 (лемма  Куратовского — Цорна). Если верхний конус любой цепи частично упорядоченного множества Р не пуст, то Р содержит максимальные элементы.

Доказательство. В соответствии с общим определением назовем цепь С частично упорядоченного множества Р максимальной, если для всякого элемента х из Р, не принадлежащего C, подмножество С U {x} уже не является цепью. Пусть ≤ — порядок на Р.

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

Для доказательства рассмотрим цепь С в частично упорядоченном множестве Р. Если С = Р, то все доказано.

В противном случае рассмотрим множество L = P\C и, воспользовавшись аксиомой о полном упорядочении, зададим на нем порядок , превращающий его во вполне упорядоченное множество. Будем говорить, что трансфинит   α L   обладает   свойством  ,  если   существует цепь С_α, обладающая следующими свойствами:

а) С С_α ;

б) (γ  С_α) (γ α и γ сравним со всеми элементами из CU(C_α∩[0, γ)) в смысле порядка ≤ ). Для наименьшего трансфинита 0 L положим

Ясно, что 0 автоматически  обладает свойством . Допустим, что все трансфиниты, меньшие α, обладают свойством . Если γ β α, то, ввиду б), C_γ C_β. Поэтому множество = U C_β является цепью. Положим β α