Соответствия и бинарные отношения

Отображение f из множества А в множество В считается заданным, если каждому элементу x ∈ А сопоставлен единственный элемент у ∈ В. Отображение f из множествау А в множество В обозначают записью f: А → В. Элемент у ∈ В, который отображением f сопоставляется элементу x ∈ А, называют образом элемента x при отображении f и обозначают f(x).

Каждое отображение однозначно определяет множество упорядоченных пар {(х,у): х ∈ А, у = f(x)}, являющееся подмножеством декартова произведения А × В множества А на множество В и называемое графиком отображения f.

Наоборот, пусть в декартовом произведении А × В задано такое подмножество f, что: 1) для любого x ∈ А существует у ∈ В, для которого (x, у) ∈ f; 2) для любых двух пар (x, у) и (х', y') множества f из равенства х = х следует равенство у = y'. Тогда множество f единственным образом определяет некоторое отображение из А в В. Это отображение, обозначаемое также f, элементу x ∈ А сопоставляет элемент у ∈ В, удовлетворяющий условию (x, у) ∈ f. Таким образом, мы можем отождествить отображения с их графиками и считать, что отображение есть подмножество декартова произведения.

Отображение f множества А в себя называют тождественным, если f(x) = х при всех х из А.

В общем случае для отображения f: А → В может существовать несколько различных элементов множества А, образы которых совпадают. Множество всех элементов х ∈ А, для которых f(x) = у₀ называют прообразом элемента у₀ ∈ В при отображении f.

Так, прообраз числа а, |а| ≤ 1, при отображении у = sinx есть множество всех решений уравнения sinx = а, т.е. множество

{х: х = arcsina + 2πn, n ∈ ℤ} ∪ {х: х = π - arcsina + 2πn, n ∈ ℤ}.

Прообраз элемента y₀ ∈ В может быть пустым множеством. Это имеет место, например, для числа 2 при отображении у = sinx.

Множество всех у ∈ В, таких, что найдется x ∈ А, для которого y=f(x), называют областью значений отображения f. Область значений отображения f будем обозначать R(f).

Отображение f: A → B называют инъективным (инъекцией), если каждый элемент из области его значений имеет единственный прообраз, т.е. из f(x₁) = f(x₂) следует x₁ = x₂.

Отображение f: A → B называют сюръективным (сюръекцией), если его область значений совпадает со всем множеством В. Сюръективное отображение из А в В называют также отображением множества А на множество В.

Отображение f: A → B называют биективным (биекцией), если оно одновременно инъективно и сюръективно.

Таким образом, если отображение f: A → B биективно, то каждому элементу множества А отвечает единственный элемент множества В и наоборот. Тогда говорят, что множества А и В находятся между собой во взаимно однозначном соответствии.

Биекцию множества А на себя называют автоморфизмом множества А. Используют также термин* „ подстановка множества".

Пример 1.2. а. Отображение, заданное равенством v(n) = = n + 1, есть, как нетрудно показать, биекция множества натуральных чисел ℕ на его подмножество ℕ\ {1}.

б. Отображение v(n) ↦ 2n есть биекция множества всех натуральных чисел на множество всех четных натуральных чисел.

в. Любая показательная функция у = а^x, а > О, есть биекция множества ℝ всех действительных чисел на множество ℝ⁺ всех положительных действительных чисел.

г. Функция у = arctga; есть биекция множества ℝ на интервал (-π/2, π/2).

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

Пусть задано отображение f: A → B и С ⊆ А — некоторое множество. Множество f(C) элементов у ∈ B, таких, что

* Иногда этот термин употребляют только для автоморфизма конечного множества.

у = f(x), х ∈ С, называют образом множества С при отображении f. Например, при отображении у = sin а: отрезок [0,1] является образом множества (отрезка) [0, π], равно как и любого объединения отрезков вида [2πk, (2k + 1)π] (для произвольного целого k). При k = 0 это можно записать следующим образом: sin([0, π]) = [0,1].

Заметим, что для любого отображения f: A → B В образ f(A) всего множества А есть область значений данного отображения.

Для произвольного множества D ⊆ B множество всех элементов х ∈ А, таких, что f(x) ∈ D, называют прообразом множества D при отображении f.

Например, для любого действительного числа а ∈ [0,1) множество, которое является объединением всех отрезков вида [arcsina + 2πk, π — arcsina + 2πk], k ∈ ℤ, есть прообраз отрезка [а, 1] при отображении у = sinx.

Прообраз области значений произвольного отображения f: A → B совпадает со всем множеством А.

Множество всех отображений из А в В будем обозначать как В^A.

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

Многие элементарные функции являются частичными отображениями множества ℝ всех действительных чисел в себя. Например, функция у = tgx есть частичное отображение с областью определения ℝ {x: x = π/2 + πk,k ∈ Z}.

Во-вторых, можно отказаться от однозначности отображения, полагая, что данному х∈А сопоставлен не один, а ко образов (множество образов) в множестве В. В этом случае говорят, что задано соответствие* из множества А в множество В.

Примером могут служить обратные тригонометрические функции: скажем, „большой" арксинус [I], сопоставляющий каждому х ∈ ℝ множество всех таких чисел у, что siny = x, т.е. множество, являющееся прообразом элемента х при отображении, определяемом графиком функции у = sinx.

Если задано соответствие p из А в B, будем использовать обозначение p(х) по аналогии с обозначением f(x) для отображений, понимая при этом, что p(х) есть уже не элемент множества В, а его подмножество.

Аналогично графику отображения можно определить график соответствия p из множества А в множество В как множество С_p упорядоченных пар (x,у), таких, что х ∈ А, у ∈ В и элементы х, у связаны соответствием p, т.е. у ∈ p(х). Указанное множество С_p упорядоченных пар есть подмножество декартова произведения А × В.

Обратно, фиксируя на декартовом произведении А × В какое-либо подмножество С, мы тем самым однозначно определяем некоторое соответствие p_C из А в В, а именно p_C(x) = {у: y ∈ B ∧ (x,у) ∈ С}. Нетрудно заметить, что графиком соответствия p_C будет как раз множество С, а соответствием, отвечающим графику С_p, будет p. Поэтому можно отождествить соответствие с его графиком и считать, что соответствие из множества А в множество В есть некоторое подмножество p декартова произведения А × В, т.е. p ⊆ А × В. В частности, при p = ∅ получаем пустое соответствие, а при p, совпадающем со всем указанным декартовым произведением, универсальное соответствие.

При этом будем писать (x, у) ∈ p для упорядоченных пар, связанных соответствием p.

* Используют также термины „частичное мультиотображение", „ча- „частичная многозначная функция".

Пример 1.3. Рассмотрим множество программистов А = {И, П, С} и множество программ В = {n₁, n₂, n₃, n₄, n₅}. Зададим соответствие τ из А в B, связывающее программистов и разрабатываемые ими программы:

τ = {(И, n₁), (И, n₃), (И, n₅), (П, n₂),(П, n₄),(С,n₂),(С,n₅)} ⊆ A × В. #

Область определения соответствия p ⊆ A × В из множества А в множество В — это множество всех первых компонент упорядоченных пар из p: D(τ) = {x:∃y∈B)(x,y)∈τ}.

Область значения соответствия p — это множество всех вторых компонент упорядоченных пар из p:

R(p) = {y:∃x∈A)(x,y)∈p}.

Из определения вытекает, что D(p) ⊆ A, R(p) ⊆ В. Соответствие из А в В называют всюду определенным, если его область определения совпадает с множеством A: D(p) = A.

Сечением соответствия оответствия p ⊆ А × В для фиксированного элемента х ∈ А будем называть множество p(х) = {у: (х, у) ∈ p}. Можно сказать, что сечение соответствия p(х) есть множество всех „образов" элемента х при данном соответствии.

Сечением соответствия p по множеству С ⊆ А будем называть множество p(С) = {у: (x, у) ∈ p, x ∈ С}.

Пример 1.4. Область определения соответствия τ из примера 1.3 есть все множество А, а область значения — все множество В. Сечением соответствия τ по элементу П будет множество τ(П) = {n₂, n₄}. #

Соответствие p ⊆ А × А из множества А в себя, т.е. подмножество множества А², называют бинарным отношением на множестве А.

Пример 1.5. Простейшим примером бинарного отношения является отношение нестрогого неравенства на множестве действительных чисел ℝ. Здесь каждому х ∈ ℝ поставлены в соответствие такие у ∈ ℝ, для которых справедливо х ≤ у. #

Для произвольного бинарного отношения на некотором множестве часто используют запись хpу вместо (ч, у) ∈ p, говоря при этом об элементах, связанных бинарным отношением p. Это согласуется с традиционной формой записи некоторых часто используемых бинарных отношений. Так, пишут х ≤ у, а не (x, у) ∈ ≤. Для таких бинарных отношений употребляют устоявшиеся словосочетания. Например, запись х ≤ у читается так: "х не больше у".

Бинарное отношение на множестве А, состоящее из всех пар (x, x), т.е. пар с совпадающими компонентами, называют диагональю множества* А и обозначают id_A. Нетрудно понять, что диагональ А есть тождественное отображение А на себя.

Для наглядного изображения соответствий из А в В (бинарных отношений, в частности) будем использовать два способа. Первый из этих способов состоит в интерпретации соответствия как подмножества декартова произведения, которое можно изображать примерно так же, как на плоскости можно изображать подмножества декартова квадрата числовых множеств. Второй способ, применяемый для конечных множеств А и B, — построение так называемого графа соответствия. В этом случае элементы множеств А и В изображаются на плоскости кружочками. Если и только если пара (u, v) принадлежит соответствию p, то в графе соответствия из кружочка, обозначающего элемент u ∈ A, проводим стрелку к кружочку, обозначающему элемент v ∈ В. Для бинарного отношения на конечном множестве А часто удобнее использовать граф другого вида. Элементы множества А изображаются кружочками только один раз, а стрелки проводятся по тем же правилам, что и в графе соответствия. Заметим, что при таком построении возможно соединение кружочка стрелкой с самим собой (петля).

* Иногда говорят о диагонали в множестве А, хотя правильнее было бы называть это отношение диагональю декартова квадрата множества А.

Пример 1.6. а. На рис. 1.1, а изображены график и граф бинарного соответствия из примера 1.3.

б. Пусть А = {1,2,3,4}. Бинарное отношение p на А определим как множество всех упорядоченных пар (x, у), таких, что x≥у. Тогда

p={1, 1),(2, 1),(2, 2),(3, 1),(3, 2), (3, 3), (4, 1), (4, 2), (4, 3), (4, 4)}.

Область определения отношения D(p) = {1,2,3,4}, область значений R(p) = {1,2,3,4}. График и два варианта графа отношения p изображены на рис. 1.1, б.

в. Множество точек окружности х² + у² = 1 есть график бинарного отношения на множестве действительных чисел, состоящего из всех таких упорядоченных пар (x, у), что у = ±√(1-х²), или, что равносильно, компоненты пары удовлетворяют уравнению х² + у² = 1. Область определения бинарного отношения есть отрезок [—1,1], область значения — также отрезок [—1,1]. #

Соответствие p ⊆ А × В называют функциональным по второй (первой) компоненте, если для любых двух упорядоченных пар (x, у) ∈ p и (x', у') ∈ p из равенства x = x' следует у = у' (и из у = у' следует x = x'). Функциональность соответствия по второй компоненте означает, что, фиксируя в любой упорядоченной паре, принадлежащей данному соответствию, первую компоненту, мы однозначно определяем и вторую компоненту. Таким образом, мы можем сказать, что соответствие, функциональное по второй компоненте, есть отображение (возможно, частичное).

Поэтому соответствие f ⊆ А × В является отображением из А в В, если и только если оно всюду определено (т.е. D(f) = A) и функционально по второй компоненте. Отметим также, что отображение из А в В является инъекцией тогда и только тогда, когда оно функционально по первой компоненте. В заключение обобщим понятие соответствия, определив отношения произвольной арности.

Определение 1.4. Произвольное подмножество p декартова произведения А₁ × ... × А_n называют (n-арным или n-местным) отношением на множествах А₁ ..., А_n.

В случае если все множества А₁ ..., А_n совпадают, т.е. А₁ = ... = А_n = А, говорят об n-арном отношении на множестве А.

Если p — n-арное отношение на множествах А₁ ..., А_n и (a₁ ..., a_n) ∈ p, то говорят об элементах a₁ ..., a_n, связанных отношением p.

Замечание 1.3. При n = 2 получаем бинарное отношение на множествах А₁, А₂. Это не что иное, как соответствие из А₁ в А₂, где множества А₁ и А₂, вообще говоря, различны.

При А₁ = А₂ = А получаем введенное ранее бинарное отношение на множестве, т.е. подмножество декартова квадрата А.

Таким образом, в общем случае (при произвольном n ≥ 2) следует, строго говоря, различать термины „n-арное отношение" и "n-арное отношение на множестве".

Связь между введенными понятиями отношения, соответствия и отображения проиллюстрирована на рис. 1.2. #

Пусть n-арное отношение p ⊆ А₁ × ... × А_n удовлетворяет условию: для любых двух кортежей (х₁, ..., x_i, ..., х_n) ∈ p и (y₁, ..., y_i, ..., y_n) ∈ p из выполнения равенств х_k = ysub>k для любого k≠i(0≤k≤n) следует, что и x_i = y_i. Тогда отношение p называют функциональным по i-й компоненте (1≤i≤n).

Другими словами, функциональность n-местного отношения по i-й (i≤n) компоненте равносильна условию, что, фиксируя все компоненты, кроме i-й, мы однозначно определяем и i-ю компоненту.

Пример 1.7. а. Представим строку учебного расписания как кортеж вида (преподаватель, группа, дисциплина, аудитория, день, час).

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

б. Рассмотрим на множестве V₃ геометрических векторов в пространстве тернарное (трехместное) отношение p, состоящее из всех упорядоченных троек (х, у, z) компланарных векторов. Это отношение не является функциональным ни по одной компоненте, так как любым двум векторам соответствует бесконечно много векторов, образующих с ними компланарную тройку.