11-12

№11

Соответствия между множествами

Пусть даны два множества A={a1; a2; a3;… an} и B ={b1; b2; b3;… bm}. Декартово произведение K= AxB их есть множество пар вида (ai;bj), где i=1,2,3,…n и j=1,2,3,…m. Выбирая из него любое подмножество R, получаем соответствие между некоторым подмножеством X множества A, состоящего из первых компонентов выбранных пар и некоторым подмножеством Y множества B, состоящего из вторых компонентов выбранных пар. X – называется областью определения, а Y – множеством значения соответствия R. Причем, возможны случаи, когда X=A и Y=B одновременно или один из них.

Соответствием между двумя множествами является любое подмножество декартового произведения этих множеств.

Соответствием между двумя множествами называется правило, по которому каждому элементу множества X выбирается (устанавливается, определяется) элемент из множества Y.

Если рассматривать все пары декартового произведения, то пара (ai;bj) задает соответствие между элементами множества A={a1; a2; a3;… an} и множества B ={b1; b2; b3;… bm}. с соответствующими областями определения и значения.

Вторая компонента bj пары (ai;bj) называется образом элемента ai.

Первая компонента ai пары (ai;bj) называется прообразом элемента bj

Соответствие задается всеми способами, которыми задается декартово произведение двух множеств. Если соответствие задается на координатной плоскости, то область определения соответствия указывается на оси абсцисс, множество значений – оси ординат.

Если во всех парах, задающих соответствие R, компоненты поменять местами, то получится соответствие R-1, обратное данному соответствию.

Примеры соответствий:

График дежурства учащихся на неделю (месяц). Область определения – список учащихся. Множество значений – день недели (месяца) дежурства..

Таблица квадратов (кубов …) натуральных чисел. Область определения – натуральные числа. Множество значений – их квадраты (кубы …)

Формула y=x2 +3x-7 задает соответствие между множеством действительных чисел (ось CX) – область определения и множеством действительных чисел, являющиеся значениями этой формулы (ось OY).

Соответствие R задано кругами и стрелками. A – область определения, B – множество значений. Число элементов в области определения в и множестве значений могут быть различными., как в рассматриваемом примере.

Образ и прообраз множества при заданном отображении

Пусть задано отображение и множество .

Множество элементов из F, каждый из которых является образом хотя бы одного элемента из D при отображении f, называется образом множества D и обозначается f(D).

Очевидно, .

Пусть теперь задано множество .

Множество элементов таких, что , называется прообразом множества Y при отображении f и обозначается f -1(Y).

Если , то . Если при каждом множество f -1(y) состоит не более чем из одного элемента , то f называется взаимно однозначным отображением E в F. Впрочем, можно определить взаимно однозначное отображение f множества E на F.

№12

Если область определения [D(G)=A], то G – всюду определённое соответствие.

Соответствие называется полностью определённым, если каждый элемент множества имеет хотя бы один образ во множестве; в противном случае соответствие называется частичным.

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

Если область значений совпадает с В [Im(G)=B], то G – сюръективное соответствие. Соответствие называется сюръективным, если каждому элементу множества соответствует хотя бы один прообраз во множестве.

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

Функцией называется любое функциональное соответствие между двумя множествами. Если функция устанавливает соответствие между множествами А и В, то говорят, что функция имеет вид (обозначение ). Каждому элементу из своей области определения функция ставит в соответствие единственный элемент из области значений. Это записывается в традиционной форме . Элемент называется аргументом функции, элемент - её значением.

Полностью определённая функция называется отображением А в В. Если при этом есть соответствие сюръективно, говорят, что имеет отображение А на В.

Пример: Функция является отображением множества натуральных чисел в себя (функциональное соответствие). Эта же функция при всех является отображением множества целых чисел в множество рациональных чисел.

Отображение множество А в множество В - это соответствие которое

1) Является функцией

2) Всюдо определенное

- инъективным (или инъекцией, или взаимно однозначным отображением множества E в F), если , или если уравнение f(x) = y имеет не более одного решения;

биективным (или биекцией, или взаимно однозначным отображением множества E на F), если оно инъективно и сюръективно, или если уравнение f(x) = y имеет одно и только одно решение.