Федоров В.Н. - Введение в теорию множеств, страница 4

g^–1 = (B, A, G^–1),

где G^–1 (не всегда ).

Геометрически представление обратного соответствия получается из обозначения прямого соответствия заменой направления стрелок. Отсюда следует, что обратное соответствие обратного соответствия будет прямым, т.е.

(g^–1)^–1 = g.

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

Композиция соответствий есть операция с тремя множествами A, B, C, на которых определены два соответствия

g = (A, B, G), ,

p = (B, C, P), ,

причем область значений первого соответствия совпадает с областью определения второго

Пр₂G = Пр₁P.

Первое соответствие определяет для любого некоторый (возможно не один) элемент . В соответствии с определением композиции для этого b надо найти по второму правилу. В результате для найдем .

Композицию соответствий g и p обозначают

g(p) или g p, или просто gp.

График композиций соответствий обозначают G P.

При этом приведенная выше композиция соответствий запишется так

g(p) = (A, C, G P), G P .

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

Композиция ассоциативна h(gp) = (hg)p, но не коммутативна gp pg , даже если рассматриваются соответствия элементов на одном множестве.

Пример 2. Англо–русский словарь устанавливает соответствие между множествами английских и русских слов. Каковы свойства этого соответствия?

• Данное соответствие является:

• не всюду определенным (всегда можно найти английское слово, не содержащееся в словаре);

• не сюръективным (по отношению русских слов, имеющихся в словаре);

• не функциональным (одному английскому слову ставится в соответствие, как правило, несколько русских);

• не взаимно однозначным (в силу предыдущего).

Пример 3. Пусть G – множество всех пар действительных чисел (х, у), удовлетворяющих соотношению (х–3)²+(у – 2)² 1. Графически такое соответствие G представляет собой круг радиуса 1 с центром в точке (3, 2). Таким образом, круг G задает соответствие между R и R (осью абсцисс и осью ординат, рис. 2.2).

Определить, чему равны:

а
) образы и прообразы чисел 2, 3, 4;

б) образы и прообразы отрезков [2, 3], [2, 4].

Рисунок 2.2

Каковы свойства соответствия G?

• а) Образом числа 2 пр₁G (на оси абсцисс) при соответствии G (см. рис. 2.2) является единственное число 2 пр₂G (на оси ординат). Образ числа 3 при соответствии G есть множество всех действительных чисел отрезка [1, 3], а образ числа 4 – число 2.

Прообразом числа 2 пр₂G (на оси ординат) при соответствии G будет множество всех действительных чисел отрезка [2, 4] пр₁G (на оси абсцисс), прообразом числа 3 при соответствии G — число 3, а прообраза числа 4 при соответствии G не существует.

б) Образом множества чисел отрезка [2,3]пр₁G является объединение образов всех чисел отрезка [1, 3] пр₂G. Аналогично образом отрезка [2,4] будет отрезок [1,3] при соответствии G.

Прообраз отрезка [2, 3] при соответствии G – это отрезок [2, 4], а прообраз отрезка [2, 4] – также [2, 4].

Если допустить, что соответствие G установлено на множестве действительных чисел, т.е. , то оно является:

• частично определенным, так как

• не сюръективным, поскольку

• не функциональным, ибо для любого числа отрезка [2,4] = пр₁G (кроме чисел 2, 4) отсутствует единственность образа;

• не взаимно однозначным, так как отсутствуют необходимые условия: G не является всюду определенным на R, не сюръективно, не функционально, а также для любого числа отрезка [1, 3] = пр₂G (кроме чисел 1, 3) отсутствует единственность прообраза.

Если определить соответствие G [2, 4] х [1, 3], то, очевидно, оно будет всюду определенным и сюръективным, однако останется не функциональным и не взаимно однозначным.

Пример 4. Пусть G – множество точек прямой линии, удовлетворяющей соотношению

х – 2 = у

при х, у 0 (рис. 2.3).

Рисунок 2.3

Каковы свойства соответствия G?

• 1. Если соответствие G задано на множестве действительных чисел, т.е. , то G:

• частично определено, так как

пр₁G = [2, ) R;

• не сюръективно, поскольку

пр₂G = R₊ R,

где R₊ = [0, ] – множество всех положительных действительных чисел с нулем;

• функционально, ибо любому х из области определения соответствует единственный; y из области значений, т.е. для соответствия G имеет место единственность образа для любого х пр₁G;

• не взаимно однозначно, так как не выполняются условия – всюду определенности и сюръективности.

2. если соответствие G задано на множестве R₊ с нулем, т.е. , то соответствие G:

• частично определено, так как пp₁ G = [2, ) и пр₁G R₊;

• сюръективно, поскольку пр₂G = R₊;

• функционально;

• не взаимно однозначно, так как не выполняется условие – всюду определенности.

3. При G [2, ) х R₊ соответствие G:

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

• сюръективно;

• функционально;

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

Пример 5. Пусть множества , где U = {а, b, с}, и В₃ определены следующим образом:

– множество всех подмножеств (булеан) множества U= {а, b, с);

В₃ – множество всех двоичных векторов длины 3, т.е. B₃ = AxAxA, где A={0,1}.

Показать, что между множествами и В₃, где U= {a, b, с}, имеет место взаимно однозначное соответствие.

• = { , {а}, {b}, {с}, {а, b}, {а, с}, {b, с}, {а, b, с}};

В = {(000), (001), (010), (011), (100), (101), (110), (111)};

(для упрощения обозначений запятые между компонентами двоичных векторов опущены).

Установим следующее соответствие G между множествами из и векторами из В₃:

• если в множестве из присутствует элемент а, то в соответствующем ему векторе из В₃ первая компонента равна 1, а если отсутствует – то 0;

• если в множестве из присутствует элемент b, то в соответствующем ему векторе из В₃ вторая компонента равна 1, а если отсутствует – то 0;

• аналогичное соответствие установим между элементом с в множестве из и значением третьей компоненты вектора из В₃

Например, множеству {b} из соответствует вектор (010) из В₃, множеству {а, с} – вектор (101) и т.д.:

Очевидно, что установленное таким образом соответствие G является взаимно однозначным, так как выполняются все условия для взаимно однозначного соответствия.

Пример 6. Каковы свойства соответствия между множеством N натуральных чисел и множеством степеней двойки:

• Соответствие G взаимно однозначно:

• всюду определено, так как пр₁G = N;

• сюръективно, поскольку пр₂G = ;

• функционально, так как любому n N соответствует единственный образ

• характеризуется единственностью прообраза, ибо для любого существует единственное n N.

2.2. Функции

Функцией f называется однозначное соответствие, т.е. такое соответствие, при котором для пар (a₁, b₁) f и (a₂, b₂) f из a₁ = a₂ следует b₂ = b₁.

Если функция f устанавливает соответствие между множествами А и В, то говорят, что функция имеет тип А→В (обозначается f: А→В).

Каждому элементу а из области определения функция f ставит в соответствие элемент b из области значений. Это обозначается f(а) = b. Элемент а – аргумент функции, элемент b — значение функции на а.

Функции f и g равны, если:

• их области определения – одно и то же множество А,

• для любого а A f(a) = g(a).

Функция типа называется п–местной. В этом случае принято считать, что функция имеет п аргументов: f(a₁, ..., а_п) = b, где а₁ А₁,..., а_п А_п, b В.

Поскольку функция – это соответствие, то для неё справедливы понятия обратной функции и композиции функций.

Если соответствие, обратное к функции f: А→В, является функциональным (однозначным), то оно называется функцией, обратной к f (обозначается ). Таким образом, для функции f: А→В обратная функция существует тогда и только тогда, когда f является взаимно однозначным соответствием между своими областями определения и значений.

Пусть даны функции f: А → В и g: В → С. Функция h: A→C называется композицией функций f и g (обозначается f○g), если имеет место равенство

h(x) = g(f(x)),

где х А.

В этом случае говорят также, что функция h получена подстановкой f в g.

Для многоместных функций

f : А^т → В, и g : Вⁿ → С

возможны различные варианты подстановки f в g, дающие функции различных типов. Например, при т = 3 и п = 4 функция

h = g (х₁, f(y_l ,y₂, y₃), x₃ ,x₄)

имеет шесть аргументов и тип B х A³ х В² → С.

Функция, полученная из функций f₁, ..., f_n некоторой подстановкой их друг в друга и переименованием аргументов, называется суперпозицией f₁, ..., f_n. Выражение, описывающее эту суперпозицию и содержащее функциональные знаки и символы аргументов и скобки, называется формулой.

Формально функцию можно записать так

Здесь f – обозначает множество пар (a, b), f(a) – обозначает b, соответствующее данному a.

Такое определение функции позволяет установить формы задания функций:

• Перечислением пар a, b;

• Формулой b = f(a);

• Графиком в виде точек на плоскости с координатами a и b;

• рекурсивной вычислительной процедурой.

Например, функция