Отношение строгого неравенства антирефлексивно.

3.Бинарное отношение на множестве А называется симметричным,

если вместе с каждой парой (х,у) в отношение входит и симметричная пара

(у, х): х, у А из хRу следует уRх.

Отношение сравнимости симметрично при любом натуральном m и на любом множестве целых чисел.

4.Бинарное отношение R на множестве А называется асимметричным, если ни одна пара не входит в отношение вместе с симметричной парой.

Отношение строгого неравенства на множестве вещественных чисел асимметрично.

5.Бинарное отношение R на множестве А называется антисимметричным, если никакая пара, состоящая из разных элементов, не входит

вотношение вместе с симметричной ей: х, у А, если хRу и уRх, то x y.

Отношение нестрогого неравенства R = {(х, у), где x y } на множест-

ве вещественных чисел антисимметрично.

6. Бинарное отношение R на множестве А называется транзитивным, если для любых трех элементов х, у и z из А, таких, что (х, у) и (у, z) входят в отношение R, в него входит и пара (х, z), т. е. х, у, z А, если

хRу и уRz, то хRz.

Отношения сравнимости транзитивно при любом натуральном m и на любом множестве целых чисел. Отношение строгого неравенства транзитивно на любом подмножестве вещественных чисел.

Следствия:

–асимметричное отношение всегда антирефлексивно;

–асимметричное отношение всегда антисимметрично.

1.3.Способы задания бинарных отношений

1.Явное перечисление пар, определяющих бинарное отношение.

2.Задание процедурой проверки. Этой процедурой проверяется, например, отношение сравнимости (отношение равенства остатков при

делении на m):

если (x y) 0 (mod m), то (х, у) входит в отношение.

3.Задание матрицей смежности.

Определим матрицу C размера A A , где A – количество элементов множества A. Тогда сij 1, если iRj, т. е. элемент с номером i находится в отношении R с элементом с номером j; иначе сij 0 .

Пример. Матрица смежности отношения сравнимости по модулю три

(mod 3) на множестве А = {1, 2, 3, 4, 5, 6, 7, 8} имеет вид:

10

Диагональ матрицы смежности рефлексивного отношения состоит из единиц, антирефлексивного отношения – из нулей.

Матрица смежности симметричного отношения симметрична относительно диагонали, С СT .

Можно доказать, что для того, чтобы отношение было транзитивным, необходимо и достаточно, чтобы его матрица смежности удовлетворяла неравенству С2 ≤ С.

4. Задание графом. Элементы множества изображаются точками плоскости и образуют множество вершин графа. Отношения изображаются ребрами графа: если пара (х, у) входит в отношение, то из вершины х проводится ориентированное ребро в вершину у.

Граф рефлексивного отношения имеет петли в каждой вершине.

Граф симметричного отношения вместе с ребром, соединяющим х с у, содержит ребро, соединяющее у с х.

Граф транзитивного отношения обладает следующим свойством: если из вершины х, двигаясь вдоль ребер, можно попасть в вершину у, то в графе должно быть ребро, непосредственно соединяющее х с у.

Пример. Граф для отношения сравнимости по модулю три (mod 3) на множестве А = {1, 2, 3, 4, 5, 6, 7, 8} состоит из трех компонент связно-

сти: {1, 4, 7}, {3, 6} и {2, 5, 8}. Граф пред-

ставлен на рис. 1.4.

Для симметричных и рефлексивных отношений петли обычно не изображаются, а пары ориентированных ребер, соединяющие данные вершины, заменяются одним – неори-

ентированным ребром. Такой граф изображен Рис. 1.4 в примере.

5. Задание списком смежностей. Для каждого элемента множества перечисляются элементы, находящиеся с ним в данном отношении.

11

Пример. Список смежности для отношения сравнимости по модулю 3:

1.4. Функции

Определение. Функцией (или отображением) называют бинарное отношение f Х × Y, обладающее следующим свойством: если (х, у1) f и (х, у2) f, то у1 = у2. Это означает, что если определен первый элемент упорядоченной пары, то второй элемент определяется единственным образом. Это свойство функции называют однозначностью. Обозначают функцию f: Х → Y, или у = f(х). Говорят, что функция f отображает множество Х в множество Y. Если у = f (х), то элемент х из множества Х называют

аргументом функции, или прообразом элемента у, а элемент у – значением

функции, или образом элемента х. В силу условия однозначности у всякого прообраза имеется единственный образ.

Аргументы функции – элементы произвольной природы, в частности, они могут быть упорядоченными последовательностями x (x1,..., xn ) . В этом случае функцию f называют функцией n переменных y f (x1,..., xn ) .

Определение. Областью определения f x функции f называют множество ее прообразов, f x ={х Х ǀ ( у Y): у = f (х)}. Если область определения совпадает с Х, то функция называется тотальной.

Определение. Областью значений f y функции f называют множество

ее образов, f y ={у Y ǀ ( х Х): у = f (х)}.

Определение. Если область значений функции совпадает с множеством Y, функция называется сюръективной, или сюръекцией.

О сюръективной функции говорят, что она отображает множество Х на множество Y.

Определение. Функция f : Х → Y называется инъективной, или инъек-

цией, если из (х1, у) f и (х2, у) f следует, что х1 = х2 , т. е. у каждого образа есть единственный прообраз.

Определение. Функция f : Х → Y называется биективной, или биекцией, если она одновременно инъективна и сюръективна. Биекцию еще назы-

вают взаимно однозначным соответствием или 1-1-соответствием.

Таким образом, биекция означает взаимно однозначно соответствие между областью определения Х и областью значений Y; каждому элементу из области определения функция f ставит в соответствие единственный элемент из множества Y, и, наоборот, для каждого у Y существует и при-

12

том единственный х Х. Введенные определения иллюстрирует рис. 1.5.: бинарное отношение, но не функцию (рис. 1.5, а), сюръекцию, но не инъекцию (рис. 1.5, б), инъекцию, но не сюръекцию (рис. 1.5, в), тотальную биекцию (рис. 1.5, г).

Рис. 1.5

Пример. Пусть Х – множество пальто в гардеробе, Y – множество крючков. Отображение, при котором каждому пальто сопоставляется крючок, на котором оно висит, является инъективным, если на каждом крючке висит не более одного пальто (некоторые крючки могут быть пустыми). Отображение является сюръективным, если на каждом крючке висит хотя бы одно пальто (на некоторых крючках может быть несколько пальто). Отображение является биективным, если на каждом крючке висит ровно одно пальто.

Если существует биективное отображение конечного множества А

вконечное множество В, то в множествах А и В поровну элементов. Если

вмножестве А больше элементов, чем в множестве В, то не существует инъективного отображения А в В. Если существует сюръективное отображение А в В , то в А не меньше элементов, чем в В.

Так как функция – бинарное отношение, то можно построить обратное

бинарное отношение f 1 , которое не обязательно будет функцией. Условие однозначности может быть нарушено.

13