Операции над соответствиями

Понятие бинарного соответствия тесно связано с понятием двухме­стного предиката. Если Р(х,у) ― двухместный предикат, в котором перемен­ная х пробегает множество X, переменная у ― множество У, а Т ― множество истинности этого предиката, то тройка множеств будет задавать соответствие между X и У.

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

Пусть даны два соответствия: ,  . Эти соответствия называются противоположными, если их графики взаимно дополняют друг друга в множестве ХУ, или на «языке» предика­тов ― соответствующие им предикаты Р(х,у) и Q (х,у), взаимно отрицают друг друга.

Например, для соответствия «х f у ⇔ х < у» противоположным бу­дет соответствие    «х f у ⇔ х ≥ у».

Действительно, графики этих соответствий ― взаимно дополняющие множества ― и отрицание предиката «x<y» есть предикат «x≥y».

Объединением соответствий f и g называют соответствие, графиком которого является объединение графиков А и В и которому соответствует дизъюнкция предикатов Р(х,у) и Q(x,y): (Р(х,у)Q(x, у)).

Аналогично определяется пересечение соответствий.

Например, для соответствий «хfу х у» и «хfу⇔ ⇔ х≥ у» их объединением будет соответствие «хhу⇔ ⇔ ((х у) ⋁ (x  у)) с графиком RR, а пересечением ― «х S у ⇔ (х  у) & (х  у)» с графиком А ={{х, х} / хR}.

Для каждого соответствия    можно определить обратное соответствие f между У и X следующим образом: у f ^-1 x x f у, иначе ― пара  принадлежит графику соответствия f ^-1 тогда и толь­ко тогда, когда пара .

Можно сказать, что граф соответствия f ^-1 получается из графа соответствия f изменением направления всех стрелок.

Например, если х f у ⇔«прямая х касается окружности у», то у f ^-1 x ⇔ «окружность у касается прямой х».

Определим операцию композиции двух соответствий ,  :

Обозначим через С график композиции соответствий f и g.

Тогда

.

На «языке» графов это означает, что точки (х) и (z) соединяются стрелками в том случае, если соединены стрелками точки (х) и (у), (у) и (z).

Короче ―   .

П р и м е р: Пусть хfу⇔«у=х²», ygz⇔ «z=y+2».

Тогда х(fg)z ⇔ «z = х² + 2».

Упражнения

1. Даны два множества: N и R. Задать различные бинарные соответствия между этими множествами различными способами.

2. Дано соответствие . Изобразить график соответствия. Определить область отправления, область прибытия, область значений, область определения.

3. Даны два соответствия

и

.

Найти композицию и построить ее график.

Свойства и типы соответствий Виды соответствий

Соответствие называется всюду определенным на множестве X, если:

а)  , то есть: : у=f(x), или на «языке» полного образа элемента;

б)   , или на «языке» графов;

в)   из каждого элемента множества X выходит стрелка и приходит в Y.

Соответствие называют сюръективным, если:

а)  , то есть : хfу ⇔ у=f(x), или на языке полного прообраза;

б)  , или на «языке» графов;

в)   в каждый элемент множества Y приходит стрелка из X.

Если f  ― всюду определенно на X,  то f ^-1 ― сюръективное соответствие Y на X, если f ― сюрьективно, то f ^-1   всюду определенно на Y.

Соответствие f называют функциональным, если:

а)   R(x) содержит не более одного элемента, то есть   ; б)   на языке графов это означает, что из каждого элемента множества X не выходит две стрелки и более.

Соответствие f называется инъективным, если:

а)  содержит не более одного элемента, то есть  ;

б)  на «языке» графов это означает, что в каждый элемент множества Y приходит не более одной стрелки.

Из этих определений следует, что соответствие, обратное функциональному, ― инъективно, а обратное инъективному ― функционально.

Если f и g ― всюду определенные, функциональные, инъективные и сюръективные соответствия, то ― тоже будет обладать всеми этими свойствами.

П р и м е р 1:   Соответствие на рисунке

а)  не всюду определено;

б)  функционально; в)  инъективно;

г)  сюръективно.

П р и м е р 2:  Пусть X ― множество студентов в аудитории. Y ― множество стульев. Зададим соответствие x f y «студент x сидит на стуле y».

Это соответствие будет:

а)   всюду определенным, если каждый студент будет сидеть;

б)   сюрьективным, если все стулья заняты;

в)  функциональным, если каждый студент не сидит на двух стульях;

г)  инъективным, если на каждом стуле не сидят два студента.

П р и м е р 3: Пусть х f у   (у = sin х),  X = R, Y = R. Тогда графиком этого соответствия будет синусоида:

Соответствие это будет:

а) всюду определено, так как : (у = sin х) (любая прямая, параллельная оси ОY, пересекает график функции хотя бы в одной точке).

б)  функционально, так как  состоит из одного элемента (лю­бая прямая, параллельная оси ОУ, пересекает график функции в единственной точке).

в)  не инъективно, так как , для которых R ^-1(у) состоит более чем из одного элемента (существуют прямые, параллельные оси ОХ, которые пересекают график множество раз).

г)  не сюръективно, так как , для которых не существует х: у=sinx (существуют прямые, параллельные оси ОХ, которые не пересекают график ни в одной точке).

Рассмотренные выше свойства соответствий (инъективность, сюръективностъ и т.п.) позволяют классифицировать все соответствия на опре­деленные типы. Приведем классификацию соответствий по свойствам в ви­де таблицы:

Функциональность	Всюду определенность	Инъективность	Сюръективность	Название
+				Функция типа
+	+			Отображение из X в Y
+	+	+		Вложение (инъекция) X в Y
+	+		+	Наложение (сюръекция) X на Y
+	+	+	+	Биекция X на Y

 

Из этой таблицы видно, например, что отображение ― это всюду определенное функциональное соответствие.

П р и м е р 4: Отображение сюръективно и инъективно, так как:  из того, что

и . Следовательно, соответствие ― биекция.