Упорядоченные множества (стр. 2 из 8)

в) Антисимметричность отношения

следует из того, что два натуральных числа, кратных друг другу, равны между собой, т.е. если а
в, в
а, то существуют такие q₁,q

N, что

а=вq₁,

в=аq

откуда

а=аq₁q

то есть q₁q

=1. Но, q₁,q

N,следовательно q₁=q
=1, откуда следует, что

а = в. Следовательно

антисимметрично.

Поэтому

есть частичный порядок и , стало быть, < N,

> - ЧУМ(частично упорядоченным множеством).

Элементы a,в ЧУМа А называются несравнимыми и записываются

а‌‌‌‌‌‌‌‌‌‌‌||в , если a ≤ в и в ≤ а.

Элементы a,в ЧУМа А называются сравнимыми если a ≤ в или в ≤ а.

Частичный порядок ≤ на A называется линейным, а само ЧУМ линейно – упорядоченным или цепью, если любые два элемента из А сравнимы , т.е. для любых a,в

A, либо a ≤ в, либо в ≤ a.

Пример 4.

< N, ≤ >, <R, ≤ > - являются цепью. Однако <В(М) ;

> ,где В(М) - множество всех подмножеств множества М или В(М) называется булеаном на множестве М, не является цепью , т.к. не для любых двух подмножеств множество М одно является подмножеством другого.

Пусть < А, ≤ > - произвольный ЧУМ.

Элемент m

A называется минимальным, если для любого x
A из того, что x ≤ m следует x = m.

Смысл этого понятия в том, что А не содержит элементов строго меньших этого элемента m. Говорят , что х строго меньше m и записывают х < m, если x ≤ m, но притом x ≠ m. Аналогично определяется максимальный элемент этого ЧУМ. Ясно, что если m

, m
- разные минимальные (максимальные) элементы ЧУМ, то m
|| m
.

В теории частично упорядоченных множеств условие a ≤ в иногда читают так: элемент а содержится в элементе в или элемент в содержит элемент а.

Лемма.

Каждый элемент конечного ЧУМа содержит минимальный элемент и содержится в максимальном элементе этого ЧУМа.

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

Пусть а – произвольный элемент конечного ЧУМа S. Если а – минимальный элемент, то в силу рефлексивности, лемма доказана. Если А не минимален, то найдется элемент а

такой, что

< а (1)

Если а

минимален, то всё доказано. Если же элемент а
не является

минимальным, то для некоторого а

получим

< а
(2)

Если а

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

< а
(3)

для некоторого а

S. И так далее. Указанный процесс не может быть бесконечным в виду конечности самого множества S.

Таким образом, на некотором n – ом шаге рассуждений процесс оборвется, что равносильно тому, что элемент а

минимален. При этом

< а
<
< а
< а
< а

За счет транзитивности отсюда следует, что элемент а содержит минимальный элемент а

. Аналогично, элемент а содержится в максимальном элементе. Лемма доказана.

Следствие.

Конечное ЧУМ содержит, по меньшей мере, один минимальный элемент.

Сейчас мы введем важное для дальнейшего изложения понятие диаграммы конечного ЧУМа S.

Вначале берем все минимальные элементы m

, m
,

, m
в S. Согласно следствию такие найдутся . Затем в частично упорядоченном множестве

= S \ {m
, m
,

, m
},

которые , как и S , является конечным , берем минимальные элементы,

,
,

и рассматриваем множество

= S
\ {

,
,

}

Элементы “ первого ряда “m

, m
,

, m
изображаем точками. Несколько выше отмечаем точками элементы “ второго ряда”

,
,

и соединяем отрезками точки

в том и только том случаи, если m
<