WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Соответствия А.А.Новоселов Лекция для студентов Института математики СФУ Аннотация В лекции рассматривается понятие соответствия, обобщающего понятие функции, а также связанные с ним понятия поляры и компоненты. Изучаются свойства этих объектов и их связь с понятием отношения. Основная часть материала почерпнута из монографии [1].

1 Соответствие Определение 1.1 Пусть X, Y – произвольные множества. Соответствием :

X Y называется произвольное подмножество X Y.

В частном случае, когда каждый элемент x X входит не более, чем в одну пару (x, y), получается обычное однозначное отображение из X в Y, или функция.

Таким образом, понятие соответствия обобщает понятие функции.

Рассмотрим пример соответствия. Пусть X = {x1, x2, x3}, Y = {y1, y2, y3, y4}. Декартово произведение X Y показано на следующем рисунке в виде прямоугольной таблицы, а элементы = {(x1, y1), (x2, y1), (x2, y2), (x2, y3)} представлены заполненными точками.

y4 y3 • y2 • y1 • • x1 x2 x3 Рис. 1: Пример соответствия Образом (A) множества A X при соответствии называется множество (A) = {y Y | x A : (x, y) } точек y Y, входящих в в паре с некоторым x A. Для x X образ одноточечного множества будем также обозначать ({x}) = (x).

Сибирский Федеральный Университет, Свободный пр. 79, 660041, Красноярск, e-mail:

arcady@novosyolov.ru 2 А.А. Новоселов x3 x2 • • • x1 • y1 y2 y3 y4 Рис. 2: Пример обратного соответствия Обратным к соответствием -1 : Y X называется подмножество -1 Y X, определяемое следующим образом:

-1 = {(y, x) Y X| (x, y) }.

Соответствие, обратное к изображенному на рисунке 1, показано на рисунке 2, который, очевидно, является "транспонированной"версией рисунка 1. Образ -1(B) множества B Y при соответствии -1 называют также прообразом B при соответствии. Для обозначения прообразов одноточечных множеств {y} используется то же соглашение, что и для образов: -1({y}) = -1(y), y Y.

Понятие соответствия оказывается особенно удачным в том смысле, что обратное соответствие всегда существует, и (-1)-1 =.

Как видно из рассмотренных примеров, некоторые элементы x X могут иметь пустые образы при соответствии, и, аналогично, для некоторых y Y возможно -1(y) =. Поэтому являются содержательными понятия области определения D() и области значений R() соответствия, задаваемые посредством D() = {x X| y Y : (x, y) }, R() = D(-1).

В рассмотренных на рисунках 1, 2 примерах D() = R(-1) = {x1, x2}, R() = D(-1) = {y1, y2, y3}.

Множества X, Y называются областью отправления и областью прибытия, соответственно. В большинстве случаев можно без ущерба для существа дела избавиться от "лишних"точек, и считать X = D(), Y = R(), что мы и будем делать в дальнейшем.

Для подмножества Z X сужением соответствия на Z называется соответствие |Z : Z (Z), задаваемое соотношением |Z = {(x, y) | x Z}. Например, для соответствия, показанного на рисунке 1, сужение на Z = {x1} имеет вид |{x } = {(x1, y1)}.

Пусть заданы соответствия : X Y и : Y Z. Композицией этих соответствий = называется соответствие : X Z, задаваемое соотношением = {(x, z) X Z| y Y : (x, y), (y, z) }.

Далее приведены свойства соответствий, доказательство которых предоставляется читателю в качестве упражнения. При описании этих свойств используются следующие обозначения: : X Y, : Y Z, : Z U – соответствия между указанными множествами, {A, } – произвольное семейство подмножеств X, проиндексированное элементами множества. Для произвольного множества Z используется обозначение IZ = {(z, z), z Z} – "главная диагональ"декартова произведения Z Z.

Соответствия 1. Монотонность по включению A B X = (A) (B).

2. Образ объединения и пересечения A = (A), A (A).

3. Выражение образа множества через образы его элементов (A) = (x), A X.

xA 4. Действие композиции соответствий на множество ( )(A) = ((A)).

5. Ассоциативность операции композиции соответствий ( ) = ( ).

6. Области определения и значений взаимно обратных соответствий D() = R(-1), R() = D(-1).

7. Композиция прямого и обратного соответствий -1 IX.

8. Представление композиции = -1(y) (z).

(y,z) 2 Поляра Пусть : X Y – некоторое соответствие.

Определение 2.1 Полярой соответствия называется отображение : 2X 2Y, ставящее в соответствие каждому множеству A X множество (A) = {y Y | -1(y) A}.

Если соответствие фиксировано, то удобно писать вместо ; кроме того, для одноэлементных множеств {x}, x X будем использовать сокращенную форму записи ({x}) = (x).

Поляра обратного соответствия -1 называется обратной полярой и обознача-ется -1 = = -1.

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

4 А.А. Новоселов 1. Поляра одноточечного множества (x) = (x).

2. Выражение поляры множества через поляры элементов (A) = (x), A X.

xA 3. Поляра объединения множеств A = (A) 4. Монотонность поляры по включению A B X = (A) (B).

5. Связь прямой и обратной поляр A X, B Y, A B = A -1(B), B (A).

6. Композиция прямой и обратной поляр A X, B Y = A -1((A)), B (-1(B)).

3 Теорема отделимости Не всякое подмножество B Y может быть значением поляры, равно как и не всякое подмножество A X может являться значением -1. В следующей теореме характеризуются множества, которые являются значениями -1. Ввиду симметрии понятий прямого и обратного соответствий эта теорема легко переформулируется и для прямой поляры.

Теорема 3.1 Пусть A X – фиксированное подмножество. Для того, чтобы существовало подмножество B Y такое, что A = -1(B), необходимо и достаточно, чтобы для всякого x X \ A = Ac существовал такой элемент y = yx Y, что -1(yx) A и x -1(yx) (при этом A = -1((A))).

Замечание 3.1 Эта теорема в какой-то мере напоминает теоремы отделимости из выпуклого анализа, поскольку значение поляры -1 в точке yx "разделяет"точку x и множество A. Это обстоятельство и обусловило название пункта.

Доказательство. Достаточность. Зададим множество B следующим образом:

B = {yx}, xAc Соответствия и покажем, что -1(B) = A. Действительно, используя третье свойство поляры, получаем (B) = {yx} = (yx) A, xAc xAc поскольку по условию каждое из множеств (yx), x Ac содержит A. Если же последнее пересечение в этой формуле шире A, то в нем найдется x A, для которого, по условию теоремы, можно найти yx такое, что x -1(yx), что противоречит способу построения B. Таким образом, -1(B) совпадает с A, и достаточность условий теоремы доказана.

Необходимость. Пусть существует B Y такое, что A = -1(B), или, по определению поляры, A = {x X| (x) B}.

Отсюда вытекает, что для любого x A имеет место (x) B, то есть, найдется y = yx B такой, что yx (x), что эквивалентно x -1(yx) = -1(yx). Кроме того, ввиду монотонности поляры, -1(yx) -1(B) = A. Теорема доказана.

4 Компонента Пусть : X Y – соответствие из X в Y, а : 2X 2Y – его поляра. Как уже отмечалось, для произвольного множества A X выполняется включение A -1((A)). (1) Ввиду монотонности поляр, -1 для композиции = -1 имеем : 2X 2X и A B X = (A) (B). (2) Особый интерес представляют множества, для которых включение (1) обращается в равенство. Такие множества называются компонентами соответствия, они в некотором роде являются "неподвижными точками"отображения.

Определение 4.1 Множество H X называется компонентой, если выполняется равенство H = -1((H)).

По теореме 3.1 множество H X является компонентой в том и только в том случае, когда H = -1(B) при некотором B Y. Отсюда вытекает, что -1((A)) является наименьшей (по включению) компонентой, содержащей A X. Обозначим эту наименьшую компоненту A:

A = -1((A)).

Сформулируем несколько свойств компонент в виде предложений.

Предложение 4.1 Пересечение произвольной совокупности компонент является компонентой.

6 А.А. Новоселов Доказательство. Действительно, пусть {H, } – совокупность компонент соответствия. По свойству 3 из 2 имеем H = H = -1((H)) = -1 (H), так что, по теореме 3.1, H является компонентой.

Из предложения 4.1 вытекает, что можно говорить о наименьшей компоненте, как пересечении всех компонент соответствия. Она, очевидно, совпадает с -1(Y ) и называется центром соответствия.

Предложение 4.2 X является (наибольшей) компонентой.

Доказательство вытекает из соотношения X = -1() и теоремы 3.1.

Если H является компонентой, то H = (H) будет, очевидно, компонентой -1; она называется дополнением H. Обозначив K 2X совокупность всех компонент соответствия, нетрудно заметить, что сужение на K является взаимнооднозначным отображением K на K-1, обратным к которому является сужение -на K-1.

Компонента H K называется главной, если для некоторого элемента x X справедливо H = {x}, при этом H = -1((x)), и говорят, что компонента H порождена элементом x. Если максимальная компонента X является главной, то порождающий ее элемент называется единицей. Сопоставляя элементу x X порожденную им главную компоненту -1((x)), получаем отображение из X в K, называемое каноническим.

5 Примеры: отношения Напомним [2], что отношением R на множестве X называется любое подмножество R X X декартова произведения X на себя. Поэтому отношения являются частным случаем соответствий при совпадении областей отправления и прибытия:

Y = X. Рассмотрим содержательный смысл введенных понятий на примере отношений.

Сначала укажем некоторые общие свойства соответствий, как отношений R на множестве X.

1. R X X симметрично тогда и только тогда, когда R-1 = R.

2. R X X транзитивно тогда и только тогда, когда R R R.

3. R X X рефлексивно тогда и только тогда, когда R IX.

4. R X X антисимметрично тогда и только тогда, когда R-1 R IX.

Соответствия 5.1 Отношение эквивалентности Пусть (X, ) – множество с заданным на нем отношением эквивалентности, то есть, симметричным, рефлексивным, транзитивным отношением [2]. Для удобства наряду с символом будем использовать для этого отношения обозначение R. По свойству 1 из 5 обратное отношение R-1 совпадает с R, поэтому обратная поляра совпадает с прямой: = -1. Значение поляры на одноточечном множестве {x} является классом эквивалентности K(x), содержащим заданную точку. Если множество A X целиком содержится в некотором классе эквивалентности C X/R, то (A) = C.

Если же в A встречаются хотя бы две точки из различных классов эквивалентности, то (A) =. Таким образом, значениями поляры для R могут служить только пустое множество и классы эквивалентности.

Классы эквивалентности C X/R являются, очевидно, и компонентами R. Для тривиального отношения эквивалентности (R = X X, все элементы X эквивалентны друг другу) X является единственным классом эквивалентности, а также максимальной и минимальной (и, следовательно, единственной) компонентой R. Эта компонента является главной, а единицей может служить любой элемент x X.

Для любого нетривиального отношения эквивалентности R минимальной компонентой (центром) является, максимальной – X, а все остальные компоненты совпадают с классами эквивалентности, и являются главными; порождающим может служить любой элемент из соответствующего класса эквивалентности.

Понятие канонического отображения (см. [2]) из X в фактор-множество X/R совпадает в случае отношения эквивалентности с одноименным понятием из 4.

5.2 Отношение порядка Пусть (X, ) – упорядоченное множество, то есть, множество с заданным на нем отношением порядка [2]. Для x, y X определим порядковые отрезки:

(, x] = {z X| z x}, [x, ) = {z X| x z}.

Ясно, что в этом случае (x) = (x) = [x, ), -1(x) = -1(x) = (, x], x X.

Для обычного порядка на вещественной прямой только такие отрезки (обозначаемые в этом случае (-, x] и [x, )) и могут быть компонентами отношения порядка. В случае частичного порядка "возможны варианты разобраться в которых читателю предлагается самостоятельно (см. упражнение 6.5).

6 Упражнения Упражнение 6.1 Вывести формулу для обращения композиции соответствий, в которой ( )-1 выражается через -1 и -1 с помощью операции композиции.

Упражнение 6.2 Доказать свойства соответствий 1–8 из 1.

Упражнение 6.3 Доказать свойства поляры 1–6 из 2.

8 А.А. Новоселов Упражнение 6.4 Доказать свойства отношений 1–4 из Упражнение 6.5 Пусть X = R2, элементы X представляются парами вида x = (x1, x2), а частичный порядок на X задан соотношениями x y x1 y1, x2 y2.

Описать совокупность всех компонент этого порядка.

Список литературы [1] Акилов Г.П., Кутателадзе С.С. (1978) Упорядоченные векторные пространства. Новосибирск: Наука, 368 с.

[2] Новоселов А.А. (2001) Отношения. Лекция для студентов КГУ. Красноярск, 12 с., http://anov.narod.ru/lectures.htm#Rel











© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.