Соответствия и отношения

(a, b), где a — элемент A , а b

— элемент B.
Декартово или прямое произведение множеств A и B — A  B — множество всех таких упорядоченных пар элементов этих множеств.

Декартово (прямое) произведение множеств

множество
А1  А2 … An = {(а1,

а2, ..., ап) : аi  Аi, i = 1, 2, ...,n}.

Если А1 = А2 =…= An = А, то А  А … A = An

произвольное подмножество R декартова произведения A  B.

Если a 

A, b  B и (a, b)  R, то пишут также R(a, b) или aRb. Если R =  — пустое множество, то соответствие называется пустым, а если R = A  B, то соответствие называется полным.
Пусть R  A  B. Областью определения Dom R называется множество элементов a  A, для каждого из которых найдется хотя бы один элемент b  B такой, что aRb. Областью значений, или образом, Im R соответствия R называется множество элементов b  B, для каждого из которых найдется хотя бы один элемент a  A такой, что aRb. Соответствие R называется всюду определенным, если Dom R = A, и сюръективным, если Im R = B.
Для каждого a  A множество элементов b  B таких, что aRb, называется образом a относительно R и обозначается im R a. Прообразом элемента b  B относительно R называется множество элементов a  A таких, что aRb; прообраз обозначается coim R b. Ясно, что
Im R =  a  A im R a, Dom R =   b  B coim R b.

Dom R - это такие элементы а  A, для каждого

из которых найдется хотя бы один элемент b  B, такой что (a,b)  R. Dom R = {a: (a,b)  R}
Область значений (образ) соответствия Im R – это множество элементов b  B, для каждого из которых найдется хотя бы один элемент a  A такой, что (a,b)  R .

Dom R = {Лена, Петя, Маша, Вася, Женя}
Im R = {Горький, Достоевский, Лермонтов, Некрасов, Пушкин, Толстой, Фет}

(im R a) – это множество элементов b  B таких, что

(a,b)  R
Прообраз элемента b  B относительно R (coim R b) – это множество элементов a  A таких, что (a,b)  R
Im R =  a  A im R a, Dom R =   b  B coim R b.

im R Лена = {Некрасов, Фет} coim R Горький = {Петя, Женя}

соответствие, у которого Dom R = A (каждый элемент множества

А включен в соответствие). В противном случае – частично определенное.
Сюръективное соответствие – это соответствие, у которого
Im R = B (каждый элемент множества В включен в соответствие)

Частично определенное ( элемент Эллочка не имеет образа)
Сюръективное

B называется функциональным, если для любого элемента (a1, a2, …,

an) из A1  A2  …  An существует не более одного элемента b из B такого, что (a1, a2, …, an, b)  F. Если такой элемент b из B существует для некоторого (a1, a2, …, an) , то он обозначается F(a1, a2, …, an) и записывается так: b = F(a1, a2, …, an) .
В случае, если Dom(F) = A1  A2  …  An , F называется полностью определенным, когда Dom(F)  A1  A2  …  An — частично определенным или просто частичным.
Соответствие F, заданное на множествах A1, A2, …, An, B называется отображением или функцией из A1  A2  …  An в B (F: A1  A2  …  An  B), если F функциональное и полностью определенное. Соответствие F называется частичным отображением или частичной функцией, если F функциональное и частичное. Число n называют арностью функции F.

Функциональные соответствия

соответствие, у которого если элемент a  A имеет образ

при соответствии R, то он единственный элемент b  B (im Ra = ! b B)
Инъективное соответствие – это соответствие, у которого у которого если элемента b  B имеет прообраз при соответствии R, то он единственный элемент a  A (coim R b = ! a  A)

Не функциональное (т.к. im R Лена = {Некрасов, Фет} )
Не инъективное (т.к. coim R Горький = {Петя, Женя}

подмножествами множества A и подмножествами множества B.
Именно, если X  A,

то через  (X) обозначается пересечение   a  X im R a;
Аналогично, для Y  B вводится множество –1(Y)=  b  Y coim R b.

Из X1  X2 следует  (X1)   (X2);
из Y1  Y2 следует

–1(Y1)  –1(Y2);
X** = X*; Y** = Y*.
Подмножество X  A  (Y  B) называется замкнутым, если X = X* (Y = Y*). Соответствие Галуа устанавливает биективное соответствие между замкнутыми подмножествами в A и B.

Некрасов, Пушкин, Толстой, Фет}
Множество R (подмножество множества AxB): (Лена, Некрасов);

(Лена, Фет); (Петя, Горький); (Петя, Пушкин); (Петя, Толстой); (Маша, Пушкин); (Маша, Лермонтов);(Вася, Пушкин); (Вася, Достоевский); (Женя, Фет); (Вася, Толстой); (Женя, Горький)

R Маша: {Пушкин, Лермонтов}
Множество im R Вася: {Достоевский, Толстой,
Пушкин}
Кстати,

множество im R Эллочка: 
Множество Г(Х) = im R Маша  im R Вася: {Пушкин}
Найдем подмножество со сходными интересами:
Множество Х* = Г-1(Г(Х)) = Г-1({Пушкин}) =
coim R Пушкин: {Петя, Маша, Вася}

одного и того же множества A  B, можно говорить

об их объединении, пересечении и дополнении.
Операция инволюции, или обращения соответствия: если R  A  B, то инволюция R# состоит из таких пар (b, a), что (a, b)  R. Иногда вместо R# пишут R–1. Ясно, что R## = R.
Операция умножения. Если R  A  B, S  B  C, то произведение RS состоит из таких пар (a, c), для которых найдется элемент b  B такой, что (a, b)  R, (b, c)  S. Умножение соответствий ассоциативно и обладает следующими свойствами: если R1  R2, то R1S  R2S; (RS)#  = R#S#.
Специальные соответствия — отношения тождества, или диагонали, A, состоящие из всех пар (a, a), a  A, играют роль единиц для умножения соответствий. Именно, если R  A  B, то AR = R = RB.
Для всякого соответствия R выполнено включение R  RR#R. Если вместо включения выполняется равенство, то соответствие называется дифункциональным. Соответствие R  A  B называется функциональным, если RR#  A и R#R  B. Функциональные соответствия — это в точности графики функций из A в B. Всякое соответствие R представимо в виде R = F#G, где F, G — функциональные соответствия.

развитую систему алгебры отношений
Интерес к бинарным отношениям был связан с

развитием ординального подхода к поведению экономических агентов
Частичный порядок ввел в рассмотрение Чарльз Сандерс Пирс, обосновавший логику отношений, а описал в современном виде Феликс Хаусдорф

асимметричным, если R  R#  = ;
d) рефлексивным, если R  A;
e) антирефлексивным (иррефлексивным),

если R   A = ;
f) транзитивным, если R2  R;
g) полным, если ab (aRb  bRa)

Пусть R  A  A. Отношение R называется:

b) толерантностью, если оно рефлексивно и симметрично;
c) предпорядком, если

оно рефлексивно и транзитивно;
d) порядком, если оно транзитивно и антисимметрично;

классы эквивалентных элементов, или на классы эквивалентности. Множество классов эквивалентности

называется фактор-множеством множества A по отношению R. Число классов эквивалентности отношения эквивалентности R называют индексом множества A.

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

P, если
R* обладает свойством P;
R   R*;
R* является подмножеством любого

другого отношения, содержащего R и обладающего свойством P.

замыканием R отношения R называется отношение R  A.
Симметричным замыканием RS отношения

R называется отношение R  R#.
Транзитивным замыканием Rt отношения R называется отношение
Rt = R  R2  R3 …  Rn …
Если некоторое отношение включает свое симметричное, рефлексивное и транзитивное замыкания, то оно является отношением эквивалентности и наоборот.

Если R — частичный порядок на A, то построение

диаграммы Хассе осуществляется следующим образом:
элементы множества A изображаются точками плоскости;
две произвольные точки a и b соединяются отрезком прямой или дугой, если aRb и x (x  a  x  b  aRx  xRb);
для того, чтобы различать случаи aRb и bRa при выполнении aRb на прямой или дуге от a к b рисуют стрелку или изображают b выше точки a или справа от нее

каждому элементу множества A сопоставляется один или несколько элементов множества

B
: A  B.
Т.о. фактически, отображение — всюду определенное соответствие.
Никола Бурбаки: функция и отображение — одно и тоже