Частичный порядок

Отношение на множестве А называется частичным порядком на А, если оно рефлексивно, транзитивно и антисимметрично.

Частичный порядок на А называется линейным порядком на А, если для любых выполняется хотя бы одно из следующих двух условий: , .

Примеры частичных порядков.

1. Отношение равенства для чисел.

2. На множестве рассмотрим отношение и , где - некоторое натуральное число}. Так как для любого , то является рефлексивным. Пара тогда и только тогда, когда (т.е. ) и (т.е. или ), следовательно, , откуда и , что и означает антисимметричность . Если (т.е. ) и (т.е. ), то , т.е. - транзитивность . Поэтому рассматриваемое отношение является частичным порядком на множестве А. Так как ни пара , ни пара , то не является на А линейным порядком.

3. Важным примером частичного порядка на множестве М некоторых подмножеств множества А является отношение включения: .

4. Примером линейного порядка является отношение и , где Х – некоторое подмножество действительных чисел .

Контрольные вопросы и упражнения

1. Доказать, что для любых множеств А, В и С справедливы равенства: а) ; б) .

2. Проиллюстрировать на содержательном примере некоммутативность операции разности множеств: .

3. Пусть Найти множества: , , , , , , , .

4. Пусть универсальное множество - множество всех студентов факультета математики и информационных технологий ДонНУ, - множество всех студентов факультета старше 18 лет, - множество всех студентов, проучившихся на факультете более 3 лет, - множество отличников факультета. Каков содержательный смысл (характеристическое свойство) каждого из следующих множеств:

а) ; б) ; в) ; г) ; д) ; ж) ;

з) ; и) ; к) ; л) ; м) ?

5. Выписать все двуместные отношения на множестве .

6. На множестве построить 3 различных отношения эквивалентности и соответствующие им разбиения множества А.

7. Построить примеры двух отношений частичного порядка на множестве .

8. Доказать:

· (рефлексивность)

· если и , то (транзитивность)

·

·

·

ТЕМА II

Дата добавления: 2015-11-14