Соответствия и их свойства. Основные определения

Соответствие G между множествами A и B: G Í A ´ B. Если (a, b)Î G, то говорят, что “ b соответствует a при соответствии G ”.

Область определения соответствия G – множество пр₁ G ={ a: (a, b)Î G }. Область значений соответствия G – множество пр₂ G ={ b: (a, b)Î G }.

Свойства соответствий G Í A ´ B:

· Всюду (полностью) определенное соответствие – если пр₁ G = A. Частично определенное соответствие – в противном случае.

· Сюръективное соответствие – если пр₂ G = B.

Образом элемента a в множество B при соответствии G называется множество всех b Î B, соответствующих элементу a Î A. Прообразом элемента b в множество A при соответствии G называется множество всех a Î A, которым соответствует b Î B.

Образом множества C Íпр₁ G называется объединение образов всех элементов a Î C. Прообразом множества D Íпр₂ G называется объеди-нение прообразов всех элементов b Î D.

· Функциональное (однозначное) соответствие – если образом любого элемента a из области определения пр₁ G является единственный элемент b из области значений пр₂ G.

· Взаимно однозначное соответствие – если оно: а) всюду опреде-лено; б) сюръективно; в) функционально; г) прообразом любого элемента b из области значений пр₂ G является единственный элемент a из области определения пр₁ G.

· Если между множествами A и B существует взаимно однозначное соответствие, то мощности этих множеств равны, т.е. | A |=| B |. В таком случае говорят, что множества A и B равномощны.

Множества, равномощные множеству натуральных чисел N, назы-ваются счетными. Множества, равномощные множеству вещественных чисел R, называются континуальными.

Замечание. Разница между понятиями соответствия и отношения следующая: соответствие имеет направление от области определения (отправления) к области значений (прибытия); если (a, b)Î G, то первой компоненте пары а соответствует вторая компонента пары b; элементы а и b не равноправны.

Отношения характеризуют свойства пар из M ²; если а j b, то элементы а и b при этом равноправны, просто пара (а, b) обладает свойством j.

Бинарное отношение на множестве является частным случаем соответствия.

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

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

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

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

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

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

Прообразом числа 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 установлено на множестве действительных чисел, т.е. G Í R ´ R, то оно является:

· частично определенным, так как пр₁ G ¹ R (пр₁ G Ì R);

· не сюръективным, поскольку пр₂ G ¹ R (пр₂ G Ì R);

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

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

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

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

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

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

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

b(U)={Æ, { a }, { b }, { c }, { a, b }, { a, c }, { b, c }, { a, b, c }}; |b(U)|=8.

B ₃={(000), (001), (010), (011), (100), (101), (110), (111)}; | B ₃|=8.

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

Установим следующее соответствие G между множествами из b(U) и векторами из B ₃:

· если в множестве из b(U) присутствует элемент а, то в соответ-ствующем ему векторе из B ₃ первая компонента равна 1, а если отсутствует – то 0;

· если в множестве из b(U) присутствует элемент b, то в соответ-ствующем ему векторе из B ₃ вторая компонента равна 1, а если отсутствует – то 0;

· аналогичное соответствие установим между элементом с в мно-жестве из b(U) и значением третьей компоненты вектора из B ₃.

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

G: Æ®(000), { a }®(100), { b }®(010), { c }®(001), { a, b }®(110), { a, c }®(101), { b, c }®(011), { a, b, c }®(111).

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

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

G ={(n, 2 ^{n –1}): n Î N, 2 ^{n –1}Î M ₂ n }Í N ´ M ₂ n?

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

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

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

· функционально, так как любому n ÎN соответствует единствен-ный образ 2 ^{n –1}Î M ₂ n;

· характеризуется единственностью прообраза, ибо для любого 2 ^{n –1}Î M ₂ n существует единственное n Î N;

Пример 4. Используя определение равномощности множеств, показать, что множество M ₂ n натуральных чисел, являющихся степенями двойки, счетно.

Для доказательства следует установить взаимно однозначное соответствие между множествами M ₂ n и N. Если каждому натуральному n Î N поставить в соответствие число 2 ^{n –1}Î M ₂ n, то установленное таким образом соответствие G Í N ´ M ₂ n, очевидно, является взаимно однозначным (удовлетворяет всем требованиям для взаимно однозначного соответствия, см. пример 3) и представляет множество всех векторов G ={(n, 2 ^{n –1}): n Î N }. А так как мощность множества N счетна, то из установленной взаимной однозначности между множествами N и M ₂ n, согласно определению равномощности бесконечных множеств, следует, что множество M ₂ n также счетно.

Вопросы для самопроверки и упражнения:

1. Каковы свойства соответствия G между множеством N натураль-ных чисел и множеством M ₂ n натуральных четных чисел:

G Í N ´ M ₂ n; G ={(n, 2 n): n Î N, 2 n Î M ₂ n }.

2. Используя определение равномощности множеств, показать, что множество M ₂ n натуральных четных чисел счетно.