2014-02-12
1851ДМ. Лекция № 4.
def. Отношение Р Í А2 называется предпорядком или квазипорядком, если Р
рефлексивно и транзитивно.
Пример 1. Отношение Р = {(1,1),(2,2), (3,3), (1,2), (2,1,), (2,3),(1,3)} на множестве {1,2,3} является предпорядком (см.рис.1).
Рис.1
Отметим, что симметричный предпорядок является отношением эквивалентности.
def. Отношение Р Í А2 называется частичным порядком, если Р рефлексивно, транзитивно и антисимметрично. Таким образом, частичный порядок – это антисимметричный предпорядок. Частичный порядок обычно обозначается символом £, а обратное ему отношение £ -1 - символом ³. Отношение ³ также является частичным порядком и называется двойственным порядку £. Используя отношение £, определим отношение <, называемое строгим порядком, по следующему правилу: х < у Û х £ у и х ¹ у. Заметим, что отношение строгого порядка не является частичным порядком, так как не выполняется условие рефлексивности (неверно, что х < х).
Пример 2. Частичным порядком является обычное отношение £ на множестве N. Действительно, это отношение рефлексивно (х £ х), транзитивно (х £ у, у £ z Þ х £ z) и антисимметрично (х £ у, у £ х Þ х = у).
Пример 3. Отношение, изображённое на рисунке 2, является частичным порядком, а отношение из примера 1 – нет.
Рис. 2.
Пример 4. Отношение включения Í на булеане Р(U) образует частичный порядок.
Заметим, что в примерах 3 и 4 имеются элементы х и у, про которые нельзя сказать, что х £ у или у £ х (например, при а = х; у = с из примера 3). Такие элементы называются несравнимыми.
def. Частичный порядок называется линейным порядком, если любые два элемента х и у из множества А сравнимы, то есть х £ у или у £ х (линейным является частичный порядок из примера 2).
def. Непустое множество А, на котором зафиксирован некоторый частичный (линейный) порядок, называется частично (линейно) упорядоченным множеством (сокращённо ч.у.м или л. у. м.).
Пример 5. Пары < N,£ >, < [0;1], £ > с обычными отношениями £ образуют л.у.м.
Пусть <А, £ > - частично упорядоченное множество. Определим на множестве А2 отношение П условием (а1 , b2 ) П (а2 , b2 ) Û а1 £ а2 Ù b1 £ b2 .Отношение П есть отношение частичного порядка. Оно называется отношением Парето. Пара < А2 , П > образует частично, но не линейно упорядоченное множество, если½А½>1.
def. Элемент аÎА частично упорядоченного множества А = < А, £ > называется максимальным (минимальным), если для всех хÎ А из а £ х (х £ а), следует х = а.
def. Элемент аÎА наибольший (наименьший) элемент ч.у.м. А (если он существует) обозначается через max A (min А). Наибольший элемент часто называют единицей, а наименьший – нулём множества А.
Заметим, что всякий наибольший элемент является максимальным, а всякий наименьший элемент - минимальным. Обратное утверждение, вообще говоря, неверно. Всякое конечное ч.у.м. содержит, как максимальные, так и минимальные элементы.
Пример 6. Ч.у.м., изображённое на рисунке 3 имеет наибольший элемент 2, минимальные элементы 1,3, но не имеет наименьшего элемента.
Рис. 3
Пример 7. Л.у.м. < [0; 1], £ > имеет наименьший элемент 0, но не имеет наибольшего элемента.
def. Пусть А = > А, £> - ч.у.м., В – подмножество А. Элемент аÎА называется верхней (нижней) гранью множества В, если b £ a (a £ b) для всех bÎ В.
Пример 8. Рассмотрим ч.у.м. < R, £ > и интервал В = (0;1]. Тогда любое число х £ 0 – нижней гранью В.
def. Элемент аÎА называется точной верхней гранью (супремумом) множества В (обозначается sup B), если а – наименьшая из верхних граней множества В.
def. Элемент аÎА называется точной нижней гранью (инфимумом) множества В (обозначается inf B), если а – наибольшая из нижних граней множества В.
В примере 8 имеем sup В = 1, inf В = 0.
def. Линейный порядок £ на множестве А называется полным, если каждое непустое подмножество множества А имеет наименьший элемент.
def. Пара < А, £ >, в которой отношение является полным порядком на множестве A, называется вполне упорядоченным множеством (сокращённо в.у.м.).
Пример 9. Пара < N, £ > является в.у.м., в то время, как пара <[0;1],£> - нет, поскольку, например, полуоткрытый интервал (1/2;1], являющийся подмножеством [0;1], не содержит наименьшего элемента.
Рассмотрим частично упорядоченное множество < А, £ >. Говорят, что элемент у покрывает элемент х, если х £ у и не существует такого элемента z, что х < z < y. Если множество А конечно, частично упорядоченное множество < А, £ > можно представить в виде схемы, в которой каждый элемент изображается точкой на плоскости, и если у покрывает х, то точки х и соединяют отрезком, причём точку, соответствующую х, располагают ниже у. Такие схемы называются диаграммами Хассе. На рисунке 4 показаны две диаграммы Хассе. Вторая диаграмма соответствует линейно упорядоченному множеству.
Рис. 4
Замечание. Диаграмма Хассе для конечных частично упорядоченных множеств ясно показывают наибольший и наименьший элементы. Если таковые существуют, а также все максимальные и минимальные элементы. Наименьший элемент обладает тем же свойством, что из него, проходя по восходящим линиям, можно перейти к любому элементу. Аналогично, к наибольшему элементу можно перейти по восходящим линиям из любого элемента. Минимальные элементы это такие, к которым не подходят восходящие линии. Они, как правило, располагаются внизу диаграммы Хассе, и из них либо только выходят восходящие линии, либо они являются изолированными точками, не связанными ни с какими другими элементами, из них не выходят восходящие линии. Они обычно располагаются в верхней части диаграммы или же являются изолированными точками.
Теорема 1. Пусть А – конечное, непустое, ч.у.м. Тогда А содержит, по крайней мере, один минимальный элемент и, если он является единственным, то он также является и наименьшим. Аналогично, А должно содержать по крайней мере один максимальный элемент и, если он является единственным, то он также является наибольшим.
Из диаграмм Хассе легко выделить цепи (линейно упорядоченные подмножества). То есть такие части диаграммы Хассе, которые состоят из единственной линии без разветвлений.
Пример 10. 1) Рассмотрим ч.у.м. < Р(А), Í >, где А = {1,2,3}. Множество Р(А) содержит восемь элементов: {0;{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}. На рисунке
5(а) изображена диаграмма Хассе, соответствующая < Р(А), Í >.
Рис. 5
2) Пусть А = {1,2,3,5,6,10,15,30}. Рассмотрим отношение частичного порядка £ на множестве А, задаваемое по правилу: х £ у Û у делится на х. Диаграмма Хассе для ч.у.м. < А, £ > изображена на рисунке 5(б).
3) На рисунке 5(в) изображена диаграмма Хассе линейно упорядоченного множества
< {0,1,2,3,4,5,6,7}, £ > с обычным отношением порядка на множестве N, не превосходящих семи.
Заметим, что диаграммы первых двух отношений совпадают. Это означает, что эти частично упорядоченные множества имеют одинаковую структуру, причём отличную от структуры третьего ч.у.м., хотя оно тоже содержит восемь элементов. Формально такая общность структуры определяется понятием изоморфизма.
def. Пусть А = < A, ≤ А >, B = < B, ≤ B > - частично упорядоченные множества. Отображение f: A→B называется изоморфизмом упорядоченных множеств А и B, если выполняются следующие условия:
1) f - взаимно-однозначное соответствие между элементами множествами А и В;
2) для любых а1,а2 Î А, а1 ≤ А а2 Û f(a1) ≤ B f(a2).
Если существует изоморфизм между А и B, то частично упорядоченные множества А и B называются изоморфными и этот факт обозначается через А @B.
Теорема 2. Всякое частично упорядоченное множество А = < A, ≤ > изоморфно некоторой системе подмножеств множества А, частично упорядоченной отношением включения.
