dm_tema_1

Пример

Рассмотрим множество A = fa; b; cg и бинарное отношение

R = f(a; b); (b; b); (c; a); (c; c)g:

1.5 Отношение порядка

Определение

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

Åñëè x y, то говорят, что x предшествует y.

Определение

Рефлексивное отношение порядка называется отношением нестрогого порядка. Обозначается .

Определение

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

Определение

Отношение порядка называется отношением полного (линейного) порядка, если для любых x; y èëè x y èëè y x. Иначе отношение

порядка называется отношением частичного порядка.

Определение

Множество A с заданным на н¼м отношением порядка называется упорядоченным и обозначается (A; ).

Пример На множестве целых чисел рассмотрим отношение делимости yjx. Это отношение является отношением нестрогого частичного порядка.

Пример На множестве точек окружности

A = f(x; y)j x2 + y2 = 1g

зададим отношение

(x1; y1) (x2; y2);

åñëè x1 < x2 è y1 < y2. Это отношение является отношением строгого частичного порядка.

Пример

Лексикографический порядок на множестве слов русского языка является отношением полного порядка.

Определение

Элемент x упорядоченного множества (A; ) называется максимальным, если

8y 2 A : x y ) y = x:

Определение

Элемент x упорядоченного множества (A; ) называется минимальным, если

8y 2 A : y x ) y = x:

Определение

Элемент x упорядоченного множества (A; ) называется наибольшим

(supremum), åñëè

8y 2 A : y x:

Определение

Элемент x упорядоченного множества (A; ) называется наименьшим

(in num), åñëè

8y 2 A : x y:

Теорема

Наибольший (наименьший) элемент упорядоченного множества (A; ), если существует, то является единственным.

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

Пусть существуют два наибольших элемента x è y. Тогда x y è y x. В силу антисимметричности получим x = y. Аналогично доказывается единственность наименьшего элемента.

Заметим, что максимальных (минимальных) элементов может быть несколько или бесконечно много.

Если существует наибольший элемент, то он является и максимальным элементом.

Аналогичное утверждение верно и для наименьшего элемента.

Конечное упорядоченное множество можно представить в виде диаграммы Хассе. В диаграмме Хассе элементы множества изображаются в виде точек на плоскости. Точки x è y соединяются

линией, если x y и не существует z такого, что x z y. При этом точка x находится ниже точки y.

Пример

Рассмотрим множество всех подмножеств трехэлементного множества A = fa; b; cg. Отношение включения подмножеств является

отношением частичного порядка.

Диаграмма Хассе

1.6 Функции

Определение

Функцией, отображающей множество A во множество B, называется бинарное отношение R A B такое, что DR = A è

8x 2 A 8y; z 2 B : xRy; xRz ) y = z:

Функцию принято обозначать f : A ! B èëè y = f (x). Областью определения функции является множество A, областью значений

множество

f (A) = fy 2 B j 9x 2 A : y = f (x)g: