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

Если φ— оператор замыкания, то φ (х) называется φ-замыканием элемента х. Элемент, совпадающий со своим φ-замыканием, называется φ-замкнутым. В рассмотренных выше примерах φ-замкнутыми элементами оказываются, соответственно, замкнутые подпространства, линейные подпространства и единица.

Теорема 4. Если φ — оператор замыкания на частично упорядоченном множестве Р, подмножество состоит из φ-замкнутых элементов и а = infA -существует,   то  а — φ-замкнутый элемент.

Доказательство. Так как a≤x для всех x A, то для всех x A, следовательно, . Обратное неравенство вытекает из определения оператора замыкания.   

Теорема 5. Если φ—оператор замыкания на полной структуре Р, то частично упорядоченное множество L, всех φ-замкнутых элементов, рассматриваемое как подмножество частично упорядоченного множества Р, также является полной структурой. При этом для всякого непустого   подмножества А   множества L   имеет место и .

Доказательство. Пусть 1 — единица полной структуры Р. Поскольку 1φ(1) > 1 > φ(1), то 1 принадлежит L и, очевидно, является единицей этого частично упорядоченного множества. Если, далее, А — непустое подмножество множества L, то элемент

 а = inf_pA, согласно теореме 4, φ-замкнут. Конечно, а≤ х для всех  x А. Если v L и   для всех х А, то v ≤ а. Так что а = inf_L А. Теперь теорема 1 позволяет заключить, что L — полная структура. Пусть, далее,   и = . Ясно, что L .и что , поскольку , для всех х A. Отсюда . Неравенство ≤ справедливо потому, что для всех x А . Так что , что и требовалось доказать.

Теорема 6. Пусть Р = , где М — некоторое частично  упорядоченное множество. Тогда  отображение

является оператором замыкания на полной структуре Р.

Доказательство. Изотонность отображения φ сразу следует из  свойства (i) теоремы. Соотношение А также содержится в этой теореме.Равенство A^{∆ ∆} вытекает из свойства (iii) теоремы.

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

 

Предложение 3 (обобщенная ассоциативность). Если — непустое множество непустых подмножеств полной структуры и , то

Доказательство. Положим и . Поскольку а ≥ х для всех х то a≥a_{i ,} для каждого ,откуда а≥b.

С другой стороны, b ≥ для всех , ≥x для всех х . Следовательно, b≥x для всех х , откуда b≥а. Таким образом, а = b. Второе утверждение доказывается двойственным рассуждением.

 

Следствие. Операторы замыкания φ и ψ на полной структуре Р совпадают тогда и только тогда, когда совпадают множества φ и ψ-замкнутых элементов.

Предложение 4. Подмножество L полной структуры Р совпадает с множеством всех φ-замкнутых элементов для некоторого оператора замыкания φ на Р в том и только в том случае, когда 1 L u inf_p A L для любого подмножества A L.

Доказательство. Необходимость указанных условий вытекает из теоремы5. Если же они выполнены, то для каждого х Р , положим

 и φ (х) = inf_p А (х).

Ясно, что φ(x) L и x≤φ(x). Отсюда

т. е. φ (φ (х))=φ(х). Если х≤ у, то, очевидно, . Отсюда А(х) A(y), а значит, наименьший элемент множества А(х) меньше или равен наименьшего элемента множества А (у), т. е.

Таким образом, φ —оператор замыкания. Если х = φ(х),то, как было отмечено, х=φ (x) L. Если x L, то х А(х) и, следовательно, φ(х)≤х≤φ(х), т. е. x=φ(x). Таким образом, L совпадает с множеством φ-замкнутых элементов.

Оказывается, что любое  частично упорядоченное множество М можно вложить в полную структуру. Требование существования нуля и единицы в доказываемой ниже теореме несущественны, так как при отсутствии в частично упорядоченном множестве М нуля или единицы соответствующий элемент может быть присоединен с соблюдением условий 0 < х для всех х М и х < 1 для всех х М.

 

Теорема. Пусть М —частично упорядоченное множество с наименьшим элементом 0 и наибольшим элементом 1, Р—полная структура всех подмножеств множества М, содержащих 0,

.

Для каждого х М положим (здесь и дальше не различаются х и {x}). Тогда L—полная структура,  а θ —изоморфизм  частично упорядоченного множества М на  подмножество  полной структуры L. При этом справедливы следующие свойства:

 

(i) если и существует, то

 

(ii) если и существует, то ;

 

(iii) если X L, то найдутся такие подмножества А и В множества М, что

Доказательство.  Предварительно установим:

Лемма  1.   Если , В М, то:

(а) A B влечет и ;

(б) ;

(в) .

В самом деле, (а) и (б) сразу  следует из определения конусов. Используя (а) и (б), получаем , т. е.

Положим для каждого А Р.

Лемма 2. φ—оператор замыкания на Р.

Действительно, из леммы1(a) вытекает, что φ(A) φ(B), если A В, а из леммы1(б) —что A φ(A)для любых A, B P. Наконец,  из  леммы1(в) следует, что

Ввиду леммы1 и теоремы5, множество L всех φ-замкнутых элементов из Р является полной структурой. Справедливость теоремы является следствием доказываемых ниже лемм 5, 6, 8 и 9.

Лемма 3. Если v M, то t тогда и только тогда, когда t≤v.

Действительно, если t ≤ v, то для всякого х имеем t≤ v≤ х, что и означает справедливость соотношения t . Если, наоборот, , то t≤ x для всех х В частности, t≤ v, ибо v .

Лемма 4. Если x, y М, то х ≤ у тогда и только тогда, когда  .

В самом деле, если х≤у, то, в силу леммы3, . Ввиду лемм 1(a) и 1(в), отсюда вытекает, что  .

Если же ,  то, учитывая лемму3, получим ,  и  вторичное применение  леммы3 дает x≤y

Из леммы4 и предложения 1 вытекает:

Лемма 5. θ — изоморфизм частично упорядоченного множества М на подмножество полной структуры L.

Лемма 6. Если , то .

Для доказательства, ввиду теоремы5, достаточно установить,   что Но в силу леммы 3, из вытекает, что t≤a. Отсюда t≤x для всех х A. Согласно лемме3, для всех х А, т.е.

Таким образом,

Обратное включение является следствием следующей цепочки импликаций, вытекающей из леммы 3 и определения inf_MA:

 

 

Лемма 7. Если , mo v≥a тогда и только тогда, когда

 

В самом деле, если v≥a, то,   ввиду леммы 5, имеем

для всех x A. Отсюда   и, используя леммы 1(a) и 1(в), получаем

Если же , то для всех x A и, следовательно,

 

Лемма 8. Если a = sup_MA, то .

В   самом   деле,   из   леммы7  вытекает,   что   , откуда, учитывая теорему5, получаем

Лемма 9.  Если А L, то

 

Для доказательства, воспользовавшись леммой 1, получим

 

Следовательно,  ,. откуда, принимая  во внимание теорему5 и лемму 1(в), выводим

Если,  далее,  , то согласно лемме 3,  t≤.x, для всех

Если же , то t≤.x, для всех   и в силу леммы 3. Таким образом, учитывая теорему5, получаем

 

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

 

 

 

 

 

 

 

 

 

    Упражнения.

1. Пусть на множестве S={1,2,3,4,6,10,12,20} задано отношение ρ={(x, y): х делитель y}. Выделим все линейно упорядоченные подмножества.

S:(1, 3, 6, 12), (1, 2, 6, 12), (1, 2, 4, 12), (1, 2, 4, 20), (1, 2, 10, 20). Объединение диаграмм, построенных для этих подмножеств, дает диаграмму Хасса

 

Если задано (S, ≤) и B –  подмножество S: B ⊆ S, можно определить верхнюю и нижнюю грани подмножества В.

Например, подмножество B={3,6} имеет две верхние грани: h₁=6 и h₂=12, одна из которых является наименьшей: H=sup({3,6})=h₁=6. Это же подмножество имеет две нижние грани: l₁=1 и l₂=3, одна из которых является наибольшей: L=inf({3,6})=l2=3.

Подмножество B={6,4} имеет одну верхнюю грань h₁=12, которая, естественно, будет наименьшей верхней гранью H=sup ({6,4})=12, и две нижние грани l₁=2, l₂=1, одна из которых будет наибольшей: L=inf ({6,4})=l1= 2.

Подмножество B={6,10} имеет те же две нижние грани l₁=2, l₂=1 и ту же наибольшую нижнюю грань L=inf ({6,10})=l1= 2, однако не имеет ни одной верхней грани.

 

2. Пусть задано множество S из трех различных целых чисел a, b, c. На этом множестве отношение ≤  задает частичный порядок. Предположим, что значения a, b, c таковы, что линейный порядок на множестве можно изобразить диаграммой :

Если на множестве целых  чисел S = {a, b, c} можно определить для  любых x, y ∈ S две бинарные операции:

x ∧ y = inf ({x,y}) = min (x,y),

x ∨ y = sup ({x,y}) = max (x,y),

то это множество представляет собой решетку. Но данное ЧУМ может не являться решеткой. Этому может способствовать одна из двух причин:

1. Существует хотя бы одно из двухэлементных подмножеcтв B ⊆ S, не имеющее верхней или нижней грани. На диаграмме

подмножества {d, e},{d, c} не имеют  верхней грани, подмножество {b,c} не имеет нижней грани. Как следует из диаграммы Хасса:  для любого двухэлементного подмножества B ⊆ S существует единственная наибольшая нижняя грань, однако для подмножеств {3,10},{3,20},{6,10},{6,20},{12,10},{12,20} не существует верхняя грань и, следовательно, для этих пар элементов не определена операция ∨.

 

2. Существует хотя бы одно из двухэлементных подмножеств B ⊆ S, для которого наибольшая нижняя (наименьшая верхняя) грань не единственна.

 На этой диаграмме  се двухэлементные подмножества B ⊆ S имеют наименьшие верхние и наибольшие нижние грани, однако подмножество {b,c} имеет две несравнимые (не связанные отношением ≤) наименьшие верхние грани d и e; подмножество {d,e} имеет две несравнимые наибольшие нижние грани b и c.

 

3. Например, отношение "старше" на множестве людей является линейным порядком.

Рассмотрим множество людей. Их можно упорядочить различным образом, например, по росту

                                      

Упорядочение элементов  множества X с помощью отображения  его элементов на какое-нибудь упорядоченное  множество Y - довольно типичный пример определения порядка.

Соответствующий общий прием  упорядочения некоторого множества  состоит в следующем. Пусть на множестве X определена инъективная  функция: f: X→R, принимающая вещественные числовые значения. Зададим отношение < на X условием: x < y, если f(x) < f(y). Так определенное отношение < антирефлексивно, так как не может быть f(x) < f(x). Транзитивность и антисимметричность отношения < столь же очевидна. Наконец, для любой пары различных элементов x, y из X верно либо f(x) < f(y), либо f(y) < f(x), так как f - инъекция. Значит порядок < является линейным. Функция f взаимно однозначно отображает наше множество X на некоторое подмножество множества R вещественных чисел, так что соотношение x < y для любых элементов множества X равносильно неравенству f(x) < f(y).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

1. Скорняков Л.А. - Элементы общей алгебры (М. Наука, 1983).
2. Скорняков Л.А. - Элементы теории структур (М. Наука, 1982).