Отношения на множестве

A={1,2,3,4} S4={(1,1),(1,2),(3,3),(4,1)} D(S4)={1,2,3,4}=A

Замечание. На стрелочной диаграмме всюду определенного соответствия из кажд. т-ки обл. отправления выходит хотя бы одна стрелка.

2. Соответствие S наз-ют сюрьективным, если его обл. значения совпадает с обл. прибытия.

Соответствие S действующее из А в В наз-ся сюрьективным, если выполняется след. условие:

(VyЄB)( ExЄA)((x, y)ЄS)

A={1,2,3,4} S5={(1,2),(3,1),(3,3),(3,4)} E(S5)={1,2,3,4}=A

Замечание. На стрелочной диаграмме сюрьективного соответствия к кажд. т-ке обл. прибытия подходит хотя бы одна стрелка.

3. Соответствие наз-ют функциональным если оно не содержит двух пар с одинаковыми первыми и различными вторыми компонентами, т. е. должно выполняться след. условие: (x1,y1),( x2,y2) ЄS=> y1= y2

A={1,2,3,4} S8={(1,1),(2,3),(3,3)}

Замечание. На стрелочной диаграмме функционального соответствия из кажд. т-ки обл. определения выходит только одна стрелка.

4. Соответствие S наз-ют инъективным, если оно не содержит пар с одинаковыми вторыми и различными первыми компонентами, т. е. если выполняется след. условие: (x1,y1),( x2,y2) ЄS=> х1= х2

A={1,2,3,4} S8={(1,1),(1,3),(3,4)}

Замечание. На стрелочной диаграмме инъективного соответствия к кажд. т-ке обл. значения подходит только одна стрелка.

5. Соответствие S наз-ся функцией (отображения), если оно всюду определено, функционально.

Замечание. Поскольку ф-ция яв-ся соответствием, то способы заданий ф-ций аналогичны способам заданий соответствий. Удобно задавать ф-цию с пом-ю формулы (аналитич. способом) f(x)=х-3

6. Инъективная ф-ция наз-ся инъекцией, если оно всюду определенное, функциональное, инъективное соответствие.

7. Сюрьективная ф-ция яв-ся инъекцией, если оно всюду определенное, функциональное, сюрьективное соответствие.

8. Соответствие S наз-ся биекцией (взаимооднозначное отображение), если оно всюду определенное, функциональное, сюрьективное, инъективное. Иначе: биекция – сюрьективная, инъективная ф-ция.

S={(x, y)ЄR2/y=x2} D(S)=R=> S – всюду определено E(S)=[0;+ ∞]≠R – S не сюрьективное.

(x1,y1),(x2,y2)ЄS=> х2= y1, x2=y2=> y1= y2=>S – функция (1,1),(-1,1) ЄS=>S – не инъекция – соответствие яв-ся ф-цией, но не яв-ся биекцией.

Соответствие Т наз-ся обратным соответствием S, если оно состоит из пар вида (y, x) такие, что пары (x, y)ЄS. T=S T={(y, x) ЄR|BxA|(x, y)ЄS }

Замечание. Из определения следует, что для люб. соответствия можно построить ему обратное соответствие.

A={1,2,3,4} S={(1,2),(3,1),(3,4)} S-1={(2,1),(3,1),(4,3)}

Т. к. соответствие яв-ся мн-вом, то все операции, к-ые выполн-ся над мн-вами можно выполнить и над соответствиями (объединение, пересечение, разность, дополнение до соответствия).

Композицию соответствий S и T обозначают композицией, к-рое можно задать след. образом: T0S={(x, y)ЄAxC|(EzЄB)(x, z) ЄS и (z, y)ЄT} S:А=>В T:B=>A

Замечание. Композиция соответствий S и T существует, если выполняется след. условие E(S)∩D(T)≠Ø

Если между элементами двух множ-в можно установить биективное соответствие(всюдуопред, сюрьективное, функц, инъективное), то такие множ-ва наз-ся равномощными.

В случае конечн множ-в равномощность означает, что множ-во содержит

одинак кол-во эл-тов.

S:N=>M M={xn2,n} S:n=>n2

MCN

Т. к соотв S биекции, M N равномощны

Графом наз-ют совокупность вершин и ребер. Вершины изображ-ся т-ками на плоскости яв-ся эл-тами мн-ва А. Ребра изображ-ся стрелками (односторонними, двусторонними). Ребра изображают эл-ты бинарных отнош-ий ρ, т. е. если пары x, y Єρ то от вершины х к вершине у выходит стрелка.

4. Отношения на множестве. Способы их задания и св-ва. Отношение эквивалентности и порядка.

Бинарным отношением называют бинарное соответствие действующее из мн-ва А в мн-во В, тогда когда эти мн-ва совпадают. АàВ, А=В. Бинарное отнош R действует на мн-во Х, наз. упроряд. Пара (х1, ГR), где х – мн-вом задан отнош., а ГR – график отношения R, которое является подмножеством декартова квадрата мн-ва Х.

Способы задания отношений не отличаются от способа задания соответствий. Но граф отношений отношен отлич от графа соответств-я. На нем мн-во не изображ точками, элементы мн-ва Х изображаются точками, расположенными по кругу.

Стрелка у которой начало и коней совпадают наз-ся пятлёй.

Х={1,2,3,4,5} R:”x <или=y”.

Т. к. отношение – это частный случай соответствия, все сказанное для соответствия верно и для отношения.

Св-ва отношений:

-Отношение R заданное на множестве Х, называется рефлексивным, если любой элемент данного множества находится в данном отношении сам с собой.

x </=y, Z –рефлексивные R

x < y, Z –нерефлексивные R

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

— Отношение R заданное на множестве Х, называется антирефлексивным, если не один элемент мн-ва Х не находится в данном отношении сам с собой.

x < y, Z –нерефлексивные R.

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

— Отношение R заданное на множестве Х, называется симметричным, если справедливо, что если хRy àyRx (должны быть обратные стрелки. Достаточно одного нарушения и св-во не будет выполнено. Отношение а ll b на мн-ве прямых в плоскости. а ll b; a/b=c/d.

Замечание:Граф содержи только двусторонние ребра.

— Отношение R заданное на множестве Х, называется асимметричным, если для любых двух х, у принадл мн-ву Х справедливо, что если хRy àзачеркнуть yRx. Пример: x < y, Z –ассиметричное R. Замечание: обратных стрелок быть не должно, аличие любой петли уже нарушение.

— Отношение R заданное на множестве Х, называется антисимметричным, если для любых двух х, у принадл мн-ву Х, из того, что (хRy, а yRx à x=y), т. е. х находится в отношении R c y.

З.: можно петли, но нельзя обратные стрелки. Пример: x </=y, Z –антисимметричное R.

— Отношение R заданное на множестве Х, называется транзетивным, если для любых трех х, у,z принадл мн-ву Х (xRy, yRz =>xRz)

Пример: a ll b — транзетивное R.

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

Отношение эквивалентности: рассмотрим множество студентов нашего вуза. Введем отношение –«быть однокурсником»разобьем это мн-во на 5 попарно-н6епересекающихся подмн-ств: 1 курсн,…5-курсн. Можно также ввод другие отношен, но сущ. Такие которые не позволят разбиения % «быть знакомым».

Пусть дано мн-во Х. Будем говорить, что зад на разб мн-ва Х на попарно-непересек подмнож х1,х2, …, хn, если оказывается выполненным условия: 1. Любое из этих подмножеств не пустое (люб i € N, i =1 ñ) (xi ≠ø) 2. Полярно не пересекаются: (люб i, k € N

i, k = 1 ñ) (xi∩xk=ø) 3. объединение подмножеств дает само множество x=x1 объед. x2 объед…хn. Т. е. рефлексивное, симметричное и транзетивное отнош-я наз-ся отношен эквивален-сти. Теорема: для того, чтобы отношение R задан на мн-ве Х позволяло разбить это мн-во на попарно-непересек подмн-ва необходимо и достаточно, чтобы отношен R-было отношением эквив-сти.

I. х=х1 объед х2 объед … объед хn

Зададим отношение К связвнное с данным разбиением => образом: будем говорить, что 2 элемента находятся в данном отношении R, если эти элементы принадлежат одному данному разбиению. xRy ßà x, y € X, i=1, ñ. Отношение R-рефлексивно. R-симметрично, т. к. если элементы х и у плпадают в одно и тоже подмножество, то эти элементы у и х также попадают в одно и тоже подмножество.

хRy, yRz => xRz. Отношение R-транзетивно, т. к. если элементв х и у принадлежат одному и тому же подмножеству, элементы у и z одному р тому же подмножеству, то все 3 элемента xyz окажутся в одном подмножестве => элементы x z будут одновременно принадлежать одному подмножеству. Т. О. отношение R –отношение эквивалентности.

Обратная теорема:

II. х=х1 объед х2 объед … объед хn (любое а принадлежит Х) a àR(a) = {X €X ׀ aRx}. Проверим, что мы получили разбиение мн-ва на попарно-непересек подмн-ва, т. е. оказываются выполненными все условия разбиения. В полученном разложении мн-ва Х ни одно подмножество R от а не может быть пустым, т. е. отношение R – является отношением эквивалентности.

1)  Рефлексивно и поэтому содержи хотя бы один элемент а. R (a) ≠ø R(a) э a

Ввиду док-ва теорем, каждое подмножество разбиения будем называть — класс эквивалентности, а само разбиение – разбиением на классы эквивалентности. Кроме того, каждый класс получившийся в рез-те разбиения получает название по назнанию отношения. Ассимитричное и транзетивное –отношение строгого порядка, х<y, Z. Рефлексивное, антисимметричное и транзетивное –оншошение нестрогого (частичного) порядка. Мн-во на котором задано отношение какого-лиьо порядка –наз-ся упорядоченным. Мн-во наз-ся линейно-упорядоченным, если на нем задано отношение порядка подчиняющ условию: для любых х, у принадл Х хRy или yRx или x=y –св-во связности.