Свойства отношений

Пусть $$\rho$$ - отношение на множестве $$A$$.

Тогда

а) $$\rho$$ рефлексивно, если $$x \rho x$$ для $$\forall x \in A$$ ;

б) $$\rho$$ симметрично, если $$x \rho y$$ влечет $$y \rho x$$ ;

в) $$\rho$$ транзитивно, если $$x \rho y$$ и $$y \rho z$$ влечет $$x \rho z$$ ;

г) $$\rho$$ антисимметрично, если $$x \rho y$$ и $$y \rho x$$ влекут $$x = y$$.

Пример 1. Пусть $$\rho = \left\{ {(x, y) : x, y \in N \mbox{ и x - делитель y }} \right\}$$, $$N = 1, 2, …, 9$$.

В явном виде$$\rho = \left\{ {(1, 1), (1, 2), (1, 3), …, (1, 9), (2, 2), (2, 4), (2, 6), (2, 8), (3, 3), (3, 6), (3, 9), (4, 4), (4, 8), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9) \right\}$$

Тогда $$\rho$$

Пример 2. Пусть $$P$$ - множество всех людей, $$A$$ и $$S$$ определяются cледующим образом: $$A = \left\{ {(x, y) : x, y \in P \mbox{ и x - предок y }} \right\}\\ S = \left\{ {(x, y) \in P \mbox{ и x и y имеют одних и тех же родителей }} \right\}$$.

Очевидно, что $$A$$ транзитивно, а $$S$$ рефлексивно, симметрично и транзитивно.

).

В семье, состоящей из двух братьев $$p$$ и $$q$$ и сестры $$r$$, имеем ситуацию: отношение $$B$$ не симметрично, так как $$p B r$$, но не $$r B p$$ ; $$B$$ не антисимметрично, так как $$p B q$$ и $$q B p$$, хотя и $$p$$ и $$q$$ различны.

В более общей ситуации мы можем интерпретировать рассмотренные выше характеристики отношений путем построения диаграмм:

a) отношение рефлексивно тогда и только тогда, когда для каждого узла на диаграмме существует стрелка-петля;

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

в) отношение транзитивно тогда и только тогда, когда для каждой пары узлов $$x$$ и $$y$$, связанных последовательностью стрелок от $$x$$ к $$a_1$$ и от $$a_1$$ к $$a_2$$..., от $$a_{n-1}$$ к $$a_n$$, от $$a_n$$ к $$y$$, существуют также стрелки от $$x$$ к $$y$$.

г) отношение антисимметрично тогда и только тогда, когда не существует двух различных узлов, связанных парой стрелок (рис 4.2).

Для примера 1 (рис 4.3) $$\rho = \left\{ {(x, y): x, y \in N \mbox{ и x - делитель y }} \right\}, \\ N = 1, 2, …, 9$$.

В явном виде$$\rho$$ = {(1, 1), (1, 2), (1, 3), …, (1, 9), (2, 2), (2, 4), (2, 6), (2, 8), (3, 3), (3, 6), (3, 9), (4, 4), (4, 8), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9)} отношение $$\rho$$ рефлексивно, несимметрично, транзитивно и антисимметрично.

). $$\tau = \left\{ {(x, y) : x, y \in N \backslash \left\{ 1 \right\} \mbox{ и x и y имеют общий делитель }} \right\}$$, $$\tau $$ = {(2, 2), (2, 4), (2, 6), (2, 8), (3, 3), (3, 6), (3, 9), (4, 4), (4, 8), (4, 6), (5, 5), (6, 3), (6, 2), (6, 6), (7, 7), (8, 2), (8, 4), (9, 3), (9, 9), (6, 4), (8, 6), (6, 8), (9, 6), (6, 9)} .

Отношение $$\tau$$ рефлексивно, симметрично, но не транзитивно и антисимметрично.

Отношения эквивалентности и порядка

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

Пример 1. На множестве всех треугольников отношение, определяемое как $$\left\{ R_1 = {(x, y) : \mbox{ x и y имеют одинаковую площадь }} \right\}$$, является тривиальным отношением эквивалентности.

Пример 2. Отношение, определяемое на множестве всех программ$$R_2 = {(a, b) :$$ $$a$$ и $$b$$ вычисляют одну и ту же функцию на определенной машине, это является отношением эквивалентности.

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

Частичным порядком на множестве $$A$$ назовем отношение, которое рефлексивно, антисимметрично и транзитивно. Порядок (называемый также отношением порядка) - это обобщение отношения $$\le $$ на $$N$$ . Поэтому можно легко проверить требуемые три свойства. Заметим, что мы могли бы в качестве определения взять отношение $$<$$. Тогда отношение порядка было бы только транзитивно. Следовательно, свойство транзитивности является наиболее важным для отношения порядка.

Определив отношение $$\le ,$$ можно определить отношение $$<$$ следующим образом: $$a \le b \leftrightarrow a < b \mbox{ и } a \ne b$$.

Аналогично, если задано $$<$$, то $$a \le b \leftrightarrow a = b \mbox{ или } a < b$$. Пример 1. Порядок чисел на действительной оси $$R$$ является полным.

). Отношение $$\sigma = \left\{ {(x, y) : x, y \in N \mbox{ и } x \le y} \right\}$$ рефлексивно, антисимметрично, транзитивно.

Функции

Подмножество $$F \subset M_x \times M_y$$ называется функцией, если для каждого элемента $$x, x \in M_x$$, найдется не более одного элемента $$y \in M_y$$ вида $$(x, y) \in F$$ ;

При этом если для каждого элемента $$x$$ имеется один элемент $$y$$ вида $$(x, y) \in F$$, то функция называется всюду (полностью) определенной, в противном случае - частично определенной (недоопределенной).

Множество $$M_x$$ образует область определения функции $$F$$, множество $$M_y$$ - область значения функции $$F$$. Часто вместо записи $$(x,y) \in F$$ используют запись $$y = F(x)$$ ; при этом $$x$$ называют аргументом или переменной, а $$y$$ - значением функции.

).

(рис 4.6)

Функция $$f: A \rightarrow B$$ является отображением, если область ее определения совпадает с $$A$$, т. е. $$D_f=A$$. Отображение на множество называют трансформацией (преобразованием).