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

Соответствие. Отображение. функция.

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

1) С точки зрения правил ГАИ каждому дорожному правонарушению соответствует определенная сумма штрафа. Здесь можно рассмотреть два множества: A – множество видов правонарушений, B – множество штрафов. При этом каждому элементу множества A соответствует один (или несколько) элементов множества B.

2) Для различных моделей огнестрельного оружия используются различные типы патронов. Если A – множество типов патронов и B – множество моделей оружия, то элементу множества A может быть поставлен в соответствие один или несколько элементов множества B, то есть между элементами множества A и элементами множества B может быть установлено соответствие.

3) В школе каждый ученик сидит в классе за строго определенной партой. Если A – множество учеников и B – множество парт, то элементу множества A может быть поставлен в соответствие один элемент множества B, то есть между элементами данных множеств может быть установлено соответствие.

Если элементы двух множеств A и B различной природы сопоставить между собой по какому-либо правилу, т.е. для некоторых элементов aÎA указать один или несколько элементов множества B, то может быть сформировано множество R пар <a, b>, являющееся подмножеством прямого произведения множеств A и B, т.е.

R = {<a, b> | aÎA, bÎB} Í (A´B).

При этом не обязательно, чтобы в сопоставлении участвовали все элементы множеств A и B.

С математической точки зрения соответствием называется тройка множеств: <A, B, R>. Множество A называют областью отправления соответствия R, множество B – областью прибытия, множество R – называют законом соответствия или графиком соответствия между множествами A и B.

Множество A_R, такое что,

A_R, = {aÎA | $ bÎB <a, b>ÎR}

называется областью определения соответствия R, или прообразом.

Множество B_R, такое что,

B_R = {bÎB | <a, b>ÎR}

называется областью значений соответствия R, или образом.

Термины «образ» и «прообраз» применяются не только ко множествам, но и к отдельным элементам. Так, если элементу a_i соответствует элемент b_j, то a_i является прообразом элемента b_j, а элемент b_j является образом элемента a_i.

В графическом виде соответствие показано на рис. 4.1.

Способы задания соответствий:

1. Графический. При данном способе области отправления и прибытия изображаются в виде овалов или прямоугольников, их элементы изображаются в виде точек внутри соответствующих областей. Соответствия между элементами – стрелками. Пример показан на рис. 4.1.

2. Перечисление пар. Для небольших множеств можно перечислить все пары, образующие данное соответствие. Например, если A – множество мальчиков некоторой студенческой группы, а B – множество девочек этой группы, то соответствие, показывающее, кто из мальчиков влюблен в какую девочку, может быть задано перечислением:

R = {<Иванов, Петрова>, <Смирнов, Павлова>, <Карпов, Семенова>}.

3. Табличный способ. Строится таблица (матрица), в которой строкам соответствуют элементы множества A, а столбцам – элементы множества B. На пересечении строки a_i и столбца b_i ставится единица, если элемент b_i соответствует элементу a_i, и ноль в противном случае. Полученная таким образом таблица называется матрицей инциденций (инциденция – соответствие). Например, чтобы отобразить, кто из мальчиков студенческой группы влюблен в девочек, можно составить следующую матрицу инциденций:

В данной таблице единиц немного, и в подавляющем большинстве клеток записаны нули. Чтобы улучшить читабельность таблицы, нули не показаны, но подразумевается, что они записаны во всех пустых клетках.

4. Словесный способ. В некоторых случаях удается описать соответствие несложной словесной фразой. Фраза должна быть составлена таким образом, чтобы однозначно определить все связи (или их отсутствия) между элементами множеств.

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

Словесный способ может быть применен, например, в следующем случае. При подготовке выпускного школьного бала был запланирован танец вальс. Чтобы пары танцующих смотрелись гармонично, было решено расположить всех мальчиков и девочек по росту (полагая, что в классе нет двух мальчиков и двух девочек с абсолютно одинаковым ростом), и самый высокий мальчик должен был танцевать с самой высокой девочкой, второй по росту мальчик – со второй по росту девочкой и т.д. Такая расстановка пар есть ни что иное, как задание соответствия между элементами множества мальчиков и множества девочек, причем соответствие задано словесным способом.

Очевидно, что если задание соответствия словесным способом возможно, то мы получаем наиболее краткое задание соответствия, что особенно эффективно для множеств большой мощности.

5. Аналитический способ. По своему принципу подобен словесному способу, но опирается не на слова, а на математические действия. Применение этого способа возможно тогда, когда элементами множеств являются числа.

Например, преподаватель намерен провести контрольную работу в группе из 30 студентов. Однако у преподавателя есть только 8 вариантов заданий, которые нужно каким-то образом распределить между студентами (то есть задать соответствие между множеством студентов и множеством вариантов заданий). Преподаватель нумерует студентов от 1 до 30 (собственно, студенты уже пронумерованы в журнале группы) и нумерует варианты заданий от нуля до семи. Преподаватель рисует на доске все варианты заданий и говорит: «Каждый студент, зная свой номер по журналу N, вычисляет число V = N mod 8, где mod – операция получения остатка от целочисленного деления числа N на 8. Полученное число V и есть номер варианта задания».

В данном примере фраза «V = N mod 8» является аналитическим (вычисляемым) выражением и представляет собой аналитический способ задания соответствия. Если у преподавателя возникнет необходимость провести такую же контрольную среди 1000 студентов, то способ выбора варианта задания не изменится.

Свойства соответствий:

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

2. Соответствие называется сюръективным (полным справа), если каждому элементу множества B может быть сопоставлен хотя бы один элемент во множестве A (рис. 4.3).

3. Соответствие называется функциональным (однозначным), если каждому элементу множества A соответствует не более одного элемента множества B (рис. 4.4).

4. Соответствие называется инъективным, если оно является функциональным, и при этом каждому элементу множества B может быть сопоставлено не более одного элемента из множества A (рис. 4.5).

5. Соответствие называется взаимнооднозначным (биективным), если любому элементу множества A соответствует единственный элемент множества B, и наоборот (рис. 4.6). Можно сказать также, что соответствие является взаимнооднозначным, если оно является полностью определённым, сюръективным, функциональным и инъективным.

Рассмотрим несколько примеров.

1. Англо-русский словарь устанавливает соответствие между множествами слов русского и английского языка. Оно не является функциональным, так как почти каждому русскому слову соответствует несколько английских вариантов слов. Также оно не является, как правило, полностью определённым соответствием, так как всегда существуют английские слова, не включённые в данный словарь. Таким образом, это частичное соответствие.

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

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

4. Соответствие между телефонами города Донецка и их семизначными номерами обладает, на первый взгляд, всеми свойствами взаимно-однозначного соответствия. Однако оно, например, не сюръективно, поскольку существуют семизначные числа, не соответствующие никаким телефонам.

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

Так сложилось, что некоторые из рассмотренных типов соответствий нашли достаточно широкое распространение и получили собственные названия. Рассмотрим их.