Пересечение и объединение отношений

Определение:Пустьиотношения на множестве . Пересечение отношенийи объединениеесть некоторое подмножество .

Теорема:Пусть и отношения на множестве . Если и рефлексивны, то и так же обладают свойством рефлексивности. Если и симметричны, то и так же обладают свойством симметричности. Если и антисимметричны, то – антисимметрично, а может не обладать свойством антисимметричности. Если и транзитивны, то – транзитивно, а может не обладать свойством транзитивности.

Доказательство:Еслиирефлексивны, то. Следовательно.

Композиция отображений и отношений

Определение:Пусть– отображение множества на множество иотображение множества на множество . Композицией отображенийназывается отображение множества на множествоесли и только еслии.

Замечание:Аналогичное определение следует сформулировать и для композиции отношений.

Пример 6.9:Пустьи– отношения на множестве людей.– если и только если– матьи– если и только если– отец. Тогда отношениеесли и только если– бабушка по отцовской линии для. Отношение жеесли и только если– дедушка по материнской линии для.

Тема 6.5. Решётки

До сих пор нами рассматривались множества, на которых заданы операции. Множества, на которых кроме операций, заданы отношения, называются алгебраическими системами.Таким образом, алгебры можно считать частным случаем алгебраических систем, у которых множество алгебраических отношений пусто. Другим частным случаем алгебраических систем являются модели – множества, на которых заданы только отношения.

Рассмотрим здесь лишь один пример алгебраической системы, который наиболее часто встречается в теоретической алгебре и её приложениях – решётки.

Определение:Решёткойназывается множество, частично упорядоченное отношением нестрогого порядка, с двумя бинарными операциямии, такое что выполнены следующие условия (аксиомы решётки):

1. (идемподентность);

2. (коммутативность);

3. (ассоциативность);

4. (поглощение).

Решётка называется дистрибутивной, если выполняются два следующих условия и.

Определение:Если в решётке существует элемент 0, такой что для любоговыполняется, то он называетсянижней гранью(нулём) решётки.

Определение:Если в решётке существует элемент 1, такой что для любоговыполняется, то он называетсяверхней гранью(единицей) решётки.

Определение:Решётка, имеющая верхнюю и нижнюю грани, называетсяограниченной.

Теорема:Если нижняя (верхняя) грань решётки существует, то она единственная.

Определение:В ограниченной решётке элементназываетсядополнением элемента, еслии.

Пример 6.10:

а) Любое полностью упорядоченное множество, например, множество целых чисел, можно превратить в решётку, определив для любых , чтои.

б) Определим на множестве натуральных чисел отношение частичного порядка следующим образом: , еслиявляется делителем. Тогдаесть наименьшее общее кратное этих чисел, аих наибольший общий делитель.

Решётка, в которой пересечение и объединение существуют для любого подмножества её элементов, называется полной. Конечная решётка всегда полна.

Тема 6.4. Верхняя и нижняя границы множества.

Эти понятия введены на любом множестве, на котором установлено отношение порядка.

Определение: называется верхней граньюнекоторого множества , если

Определение:Точной верхней граньюмножества называется наименьшая из верхних граней множества и обозначается .

Определение:называетсянижней граньюнекоторого множества, если.

Определение:Точной нижней граньюназывается наибольшая из нижних граней множества и обозначается.