XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 12
Текст из файла (страница 12)
Но на множестве целых чисел (опять-таки с естественным числовым порядком) отношение доминирования не пусто. Так, 11 2, — 5< -4, но, конечно, неверно, что 1 < 3, поскольку между единицей и тройкой существует „промежуточный" элемент — двойка. б. На множестве всех подмножеств трехзлементного множества (а, Ь, с), где в качестве отношения порядка взято отношение теоретико-множественного включения С, подмножество (а, Ь) доминирует над подмножествами (а) и (Ь), но не доминирует над пустым множеством. В свою очередь, все множество 77 1.В. Упорлдоченвые множества (а, Ь, с) доминирует над любым своим двухэлементным подмножеством, но не доминирует над одноэлементным и над пустым.
в. По отношению делимости на множестве натуральных чисел 15 доминирует над 3 и 5, но 20 не доминирует над 5, так как существует „промежуточный" элемент — 10, делитель 20, который делится на 5, но не равен ни 20, ни 5. Рассмотрим упорядоченное множество (М, <) и его произвольное непустое подмножество В С М. Упорядоченное множество (В, <~в), где <~в — ограничение отношения < на подянохеестпво В, называют упорядоченным подмножеством упорядоченного множества (М, (). Таким образом, можно переносить отношения порядка на непустые подмножества исходного упорядоченного множества. Как правило, вместо < ~в будем писать просто ( (если ясно, о каком подмножестве В идет речь).
Порядок ( (~в на подмножестве В называют также порядном, индуиированным исходным порядком < на всем множестве А. Часто прибегают к такому выражению: „рассмотрим подмножество В упорядоченного множества (М, () с индуцированным порядком", понимал под этим порядок < ~в. Элементы х и у упорядоченного множества (М, (() называют сравнимыми по отношению порядка (, если х < у или у < х. В противном случае элементы х и у называются несравнимыми. Упорядоченное множество, все элементы которого попарно сравнимы, называют линейно упорядоченным, а соответствующее отношение — отношением линейноео порядка (или просто линейным порядном). Если индуцированный порядок на подмножестве упорядоченного множества является линейным, то это линейно упорядоченное подмножество называют пенью. Любое подмножество попарно не сравнимых элементов данного упорядоченного множества называют антииепью.
78 Е МНОЖЕСТВА Н ОТНОШЕНИЯ Замечание 1.5. Обратим внимание на то, что термину „упорядоченное множество" (в смысле приведенного определения) в [1] отвечает термин „частично упорядоченное множество", а то, что мы называем линейно упорядоченным множеством, в [1] называется просто упорядоченным множеством.
Терминология этого вьшуска более принята в алгебраической литературе и литературе по дискретной математике. Употребление в [Ц термина „частично упорядоченное множество" мотивировано желанием подчеркнуть, что в общем случае в упорядоченном множестве существуют не сравнимые элементы. Пример 1.16. а. Отношение естественного числового порядка на множестве Й действительных чисел является отношением линейного порядка, поскольку для любых двух чисел а, Ь имеет место или неравенство а < Ь, или неравенство 6 < а. б. Отношение делимости (см. пример 1.13.г) на множестве М и отношение включения С на 8(А) (см. пример 1.13.д) не являются линейными порядками, за исключением случая, когда А — однозлементное множество. Пусть (А, <) — упорядоченное множество. Элемент а Е А называют наибольшим элементпом множества А, если для всех х е А выполняется неравенство я ( а.
Элемент Ь называют максима.яьнььм элементпом множества А, если для всякого х Е А имеет место одно вз двух: или х ( Ь, или я и 6 не сравнимы. Аналогично определяются наименьший и мими.иальиыб элемешпы упорядоченного множества, а именно: наименьший элемент упорядоченного множества А — это такой его элемент а, что а < я для каждого х Е А, а минимальный элемент — это такой элемент Ь Е А, что для любого я Е А элементы Ь и я не сравнимы или 6 < я. Покажем, что наибольший (наименьший) элемент множества, если он существует, является единственным.
Действительно, полагая, что а и а' — наибольшие элементы А по 79 1.8. Упорядоченные множества отношению порядка <, получаем, что для всякого х Е А выполняется х ~ ~а и х< а'. В частности, а'<а и а<а', откуда ввиду антисимметричности любого отношения порядка следует, что а = а'. Аналогично доказывается единственность наименьшего элемента. Замечание 1.6.
Поскольку на одном и том же множестве могут быть определены разные отношения порядка (например, на множестве натуральных чисел — естественный числовой порядок и отношение делимости), то, когда зто необходимо, мы будем говорить о наибольших, наименьших (соответственно максимальных и минимальных) элементах по данному отношению порядка, уточняя тем самым, о каком отношении порядка идет речь.
ф Следующие примеры показывают, что максимальных (минимальных) элементов может быть сколько угодно". Пример 1.17. Рассмотрим множество точек плоскости с некоторой фиксированной прямоугольной декартпоеой систпемой координат. Координаты каждой точки плоскости задаются упорядоченной парой (х, у) действительных чисел. Отношение порядка на множестве точек плоскости определим следующим образом: (а, Ь) < (с,И), если и только если а < с и 6 < И.
Рассмотрим множество точек треугольника ОАВ (рис. 1.11, а). Точка с координатами (О, 0) является наименьшим элементом этого множества. Максимальными элементами яввпотся все точки, лежащие на стороне АВ. Наибольшего элемента нет. ф Пусть (А, <) — упорядоченное множество и В С А.
Зле. мент а Е А называется верхией (соответственно пижмей) гранью множестпва В, если для всех элементов х Е В имеет место (х < а) (соответственно (х > а)). "Но заметим, что если у множества есть наиболыпий (соответственно иаимеиьппй) элемент, то он является единственным максимальным (соответственно минимальным) элементом данного множества. 80 1. МНОЖЕСТВА И ОТНОШЕНИЯ Максимальные аирРЕР Наименьший элемент 1н1РЕР 1пФР Р Рис. 1.11 Наименьший элемент множества всех верхних граней (соответственно наибольший элемент множества всех нижних граней) множества В называют пьочной верхней вранью В (соответственно пьочмой нижней громью В) и обозначают вар В (шГВ). Множество всех верхних (нижних) граней множества В называют верхним (ммжмим) конусом В и обозначают В ~ (соответственно В~).
В отличие от наибольшего и наименьшего элементов множества В элементы апрВ и шГВ не обязаны принадлежать множеству В. Точная верхняя (нижняя) грань множества существует не всегда. Пример 1.18. а. Рассмотрим множество Р точек прямоугольника ОАВС (рис. 1.11, б) с заданным в примере 1.17 отношением порядка. Точка О является точной нижней гранью, а точка  — точной верхней гранью этого множества. Обе точки принадлежат множеству. Если рассмотреть множество г (рис. 1.11,в) с тем же отношением порядка, то увидим, что точная нижняя грань (точка О) и точная верхнял грань (точка Е) множества г' существуют, но не принадлежат множеству. б. На числовой прямой с „выколотой" точкой Ь для полуинтервала (а, Ь) множество верхних граней есть (Ь, +со), но точной верхней грани нет.
1.8. Уяо1жяочеяные множества 81 Упорядоченное множество (М, <) называют впо вне упорядоченным, если его любое непустое подмножество имеет наименьший элемент. Множество натуральных чисел с отношением естественного числового порядка вполне упорядоченное. Множество целых чисел не вполне упорядоченное, поскольку оно не имеет наименьшего элемента. Аналогично множества рациональных и действительных чисел не являются вполне упорядоченными. Можно показать, что справедлив принцип двойстпвенносюпи дяя упорядоченных мнохсестпв.
Пусть (М, (()— произвольное упорядоченное множество. Тогда любое утверждение, доказанное для порядка <, останется справедливым для двойственного порядка >, если в нем: 1) порядок < заменить на порядок > и наоборот; 2) наименьший (минимальный) элемент заменить наибольшим (максимальным) элементом и наоборот; 3) ш1 заменить на впр и наоборот. Например, если для некоторого а Е М и для В С М мы доказали, что а = впрВ при заданном отношении порядка, то для двойственного порядка а = 1п1 В. Говорят также и о взаимно двойственных опредеяенияж если в любом определении, связанном с упорядоченным множеством, произвести взаимные замены согласно принципу двойственности, то получится новое определение, называемое двойственным к исходному. Так, определение наибольшего (максимального) элемента множества двойственно к определению наименьшего (минимального) элемента, и наоборот.
Часто употребляют оборот речи: „двойственным образом..." (или „двойственно..."), понимая под этим переход к утверждению или определению, которое двойственно к исходному. Рассмотрим теперь некоторые способы наглядного представления упорядоченных множеств. Конечное упорядоченное множество можно графически изобразить в виде так называемой диаграммы Хассе. На этой диаграмме элементы множества изображаются кружочками. 82 1. МНОЖЕОТВА И ОТНОШЕНИЯ 30 36 3 2 1 „6' 1 „36" „30" н2 Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
