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

Лекция 14: Соответствие и функции

Проекция множества.

Операция программирования множества тесно связана с операцией проектирования кортежа и может применяться лишь к таким множествам, элементами которых являются кортежи одинаковой длины.

Пусть M — множество, состоящее из кортежей длины S. Тогда пролинией множества M будем называть множество пролиний всех кортежей из М

Пример. Пусть М={<1,2,3,4,5>,<2,1,3,5,5>,<3,3,3,3,3>,<3,2,3,4,3>}

тогда Пр₂М={2,1,3}, Пр₃M={3}, Пр₄M={4,5,3}, Пр₂₄M={<2,4>,<1,5>,<3,3>}, Пр₁₃M={<1,3>,<2,3>,<3,3>}, Пр₁₅M={<1,5>,<2,5>,<1,3>}, Пр₂₅M={<2,5>,<1,5>,<3,3>,<2,3>}.

Очевидно что если М=Х*Y то Пр₁М=Х, Пр₂М=Y

и если Q⊆Х*Y то Пр₁Q⊆Х и Пр₂Q⊆Y

Пример. V={<a,b,d>,<c,b,d>,<d,b,b>}

Пр₁V={a,c,d}

Пр₂V={b}

Пр₃V={d,b}

Пр₁2V={<a,b>,<c,b>,<d,b>}

Пр₂3V={<b,d>,<b,b>}

Пр₁3V={<a,d>,<c,d>,<d,b>}

Пусть V — множество векторов одинаковой длины S.

Пр_iV ={Пр_iv/v∈Y}, Пр_ii...ikv = { Пр_ii...ikv/v∈Y}.

Если V =A₁*A₂*...*A_n, то Пр_ii...ikV=A_i1*A_i2*...*A_ik.

В общем случае Пр_iV — вовсе не обязательно прямое произведение: оно может быть подмножеством.

Соответствием между множествами А и В называется подмножество G⊆A×B.

Если (a, b) ∈ G, то говорят, что b соответствует а при соответствии G. Множество np₁G называется областью определения соответствия, множество np₂G — областью значений соответствия. Если np₁G = А, то соответствие называется всюду определенным (в противном случае соответствие называется частичным); если np₂G = В, то соответствие называется сюръективным.

Множество всех b ∈ B, соответствующих элементу а ∈ А, называется образом а в В при соответствии G. Множество всех а, которым соответствует b, называется прообразом b в А при соответствии G. Если С ∈ np₁G, то образом множества С называется объединение образов всех элементов С. Аналогично определяется прообраз множества D для любого D ⊆ np₂G.

Соответствие G называется функциональным (или однозначным), если образом любого элемента из np₁G является единственный элемент из np₂G. Соответствие G между А и В называется взаимно-однозначным (иногда пишут «1-1-соответствие»), если оно всюду определено, сюръективно, функционально и, кроме того, прообразом любого элемента из np₂G является единственный элемент из np₁G.

Так, например, англо-русский словарь устанавливает соответствие между множеством английских и русских слов. Это соответствие не является функциональным (так как одному английскому слову, как правило, ставится в соответствие несколько русских слов); кроме того, оно практически никогда не является полностью определенным: всегда можно найти английское слово, не содержащееся в данном словаре.

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

Различные виды кодирования — кодирование букв азбукой Морзе, представления чисел в различных системах счисления, секретные шифры, входящие и исходящие номера в деловой переписке и другие — являются соответствиями между кодируемыми объектами и присваиваемыми им кодами. Эти соответствия, как правило, обладают всеми свойствами взаимно-однозначного соответствия, кроме, быть может, одного — сюръективности. Единственность образа и прообраза в кодировании гарантирует однозначность шифровки и дешифровки. ∈тсутствие сюръективности означает, что не всякий код имеет смысл, т. е. соответствует какому-либо объекту. Например, кодирование телефонов г. Москвы семизначными номерами не сюръективно, так как некоторые семизначные номера не соответствуют никаким телефонам.

Если между конечными множествами А и В существует взаимно-однозначное соответствие, то |А| = |В|.