![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Соответствие G между множествами A и B: G Í A ´ B. Если (a, b)Î G, то говорят, что “ b соответствует a при соответствии G ”.
Область определения соответствия G – множество пр1 G ={ a: (a, b)Î G }. Область значений соответствия G – множество пр2 G ={ b: (a, b)Î G }.
Свойства соответствий G Í A ´ B:
· Всюду (полностью) определенное соответствие – если пр1 G = A. Частично определенное соответствие – в противном случае.
· Сюръективное соответствие – если пр2 G = B.
Образом элемента a в множество B при соответствии G называется множество всех b Î B, соответствующих элементу a Î A. Прообразом элемента b в множество A при соответствии G называется множество всех a Î A, которым соответствует b Î B.
Образом множества C Íпр1 G называется объединение образов всех элементов a Î C. Прообразом множества D Íпр2 G называется объеди-нение прообразов всех элементов b Î D.
· Функциональное (однозначное) соответствие – если образом любого элемента a из области определения пр1 G является единственный элемент b из области значений пр2 G.
· Взаимно однозначное соответствие – если оно: а) всюду опреде-лено; б) сюръективно; в) функционально; г) прообразом любого элемента b из области значений пр2 G является единственный элемент a из области определения пр1 G.
· Если между множествами A и B существует взаимно однозначное соответствие, то мощности этих множеств равны, т.е. | A |=| B |. В таком случае говорят, что множества A и B равномощны.
Множества, равномощные множеству натуральных чисел N, назы-ваются счетными. Множества, равномощные множеству вещественных чисел R, называются континуальными.
Замечание. Разница между понятиями соответствия и отношения следующая: соответствие имеет направление от области определения (отправления) к области значений (прибытия); если (a, b)Î G, то первой компоненте пары а соответствует вторая компонента пары b; элементы а и b не равноправны.
Отношения характеризуют свойства пар из M 2; если а j b, то элементы а и b при этом равноправны, просто пара (а, b) обладает свойством j.
Бинарное отношение на множестве является частным случаем соответствия.
Пример 1. Пусть G – множество всех пар действительных чисел (x, y), удовлетворяющих соотношению (x –3)2+(y –2)2£1. Графически такое соответствие G представляет собой круг радиуса 1 с центром в точке (3, 2). Таким образом, круг G задает соответствие между R и R (осью абсцисс и осью ординат, рис 3.1).
Определить, чему равны:
а) образы и прообразы чисел 2, 3, 4;
б) образы и прообразы отрезков [2, 3], [2, 4].
Каковы свойства соответствия G?
а) Образом числа 2Îпр1 G (на оси абсцисс) при соответствии G (см. рис. 3.1) является единственное число 2Îпр2 G (на оси ординат). Образ числа 3 при соответствии G есть множество всех действительных чисел отрезка [1, 3], а образ числа 4 – число 3.
Прообразом числа 2Îпр2 G (на оси ординат) при соответствии G будет множество всех действительных чисел отрезка [2, 4]Íпр1 G (на оси абсцисс), прообразом числа 3 при соответствии G – число 3, а прообраза числа 4 при соответствии G не существует.
б) Образом множества чисел отрезка [2, 3]Í пр1 G является объедине-ние образов всех чисел отрезка, т.е. отрезок [1, 3]Íпр2 G. Аналогично образом отрезка [2, 4] будет отрезок [1, 3] при соответствии G.
Прообраз отрезка [2, 3] при соответствии G – это отрезок [2, 4], а прообраз отрезка [2, 4] – также [2, 4].
Если допустить, что соответствие G установлено на множестве действительных чисел, т.е. G Í R ´ R, то оно является:
· частично определенным, так как пр1 G ¹ R (пр1 G Ì R);
· не сюръективным, поскольку пр2 G ¹ R (пр2 G Ì R);
· не функциональным, ибо для любого числа отрезка [2, 4]=пр1 G (кроме чисел 2, 4) отсутствует единственность образа;
· не взаимно однозначным, так как отсутствуют необходимые условия: G не является всюду определенным на R, не сюръективно, не функционально, а также для любого числа отрезка [1, 3]=пр2 G (кроме чисел 1, 3) отсутствует единственность прообраза.
Если определить соответствие G Í[2, 4]´[1, 3], то, очевидно, оно будет всюду определенным и сюръективным, однако останется не функциональным и не взаимно однозначным.
Пример 2. Пусть множества b(U), где U ={ a, b, c }, и B 3 определены следующим образом:
b(U) – множество всех подмножеств (булеан) множества U ={ a, b, c };
B 3 – множество всех двоичных векторов длины 3, т.е. B 3= A ´ A ´ A, где A ={0, 1}.
Показать, что между множествами b(U) и B 3, где U ={ a, b, c }, имеет место взаимно однозначное соответствие.
b(U)={Æ, { a }, { b }, { c }, { a, b }, { a, c }, { b, c }, { a, b, c }}; |b(U)|=8.
B 3={(000), (001), (010), (011), (100), (101), (110), (111)}; | B 3|=8.
(для упрощения обозначений запятые между компонентами векторов опущены).
Установим следующее соответствие G между множествами из b(U) и векторами из B 3:
· если в множестве из b(U) присутствует элемент а, то в соответ-ствующем ему векторе из B 3 первая компонента равна 1, а если отсутствует – то 0;
· если в множестве из b(U) присутствует элемент b, то в соответ-ствующем ему векторе из B 3 вторая компонента равна 1, а если отсутствует – то 0;
· аналогичное соответствие установим между элементом с в мно-жестве из b(U) и значением третьей компоненты вектора из B 3.
Например, множеству { b } из b(U) соответствует вектор (010) из B 3, множеству { 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 2 n степеней двойки:
G ={(n, 2 n –1): n Î N, 2 n –1Î M 2 n }Í N ´ M 2 n?
Соответствие G взаимно однозначно:
· всюду определено, так как пр1 G = N;
· сюръективно, поскольку пр2 G = M 2 n;
· функционально, так как любому n ÎN соответствует единствен-ный образ 2 n –1Î M 2 n;
· характеризуется единственностью прообраза, ибо для любого 2 n –1Î M 2 n существует единственное n Î N;
Пример 4. Используя определение равномощности множеств, показать, что множество M 2 n натуральных чисел, являющихся степенями двойки, счетно.
Для доказательства следует установить взаимно однозначное соответствие между множествами M 2 n и N. Если каждому натуральному n Î N поставить в соответствие число 2 n –1Î M 2 n, то установленное таким образом соответствие G Í N ´ M 2 n, очевидно, является взаимно однозначным (удовлетворяет всем требованиям для взаимно однозначного соответствия, см. пример 3) и представляет множество всех векторов G ={(n, 2 n –1): n Î N }. А так как мощность множества N счетна, то из установленной взаимной однозначности между множествами N и M 2 n, согласно определению равномощности бесконечных множеств, следует, что множество M 2 n также счетно.
Вопросы для самопроверки и упражнения:
1. Каковы свойства соответствия G между множеством N натураль-ных чисел и множеством M 2 n натуральных четных чисел:
G Í N ´ M 2 n; G ={(n, 2 n): n Î N, 2 n Î M 2 n }.
2. Используя определение равномощности множеств, показать, что множество M 2 n натуральных четных чисел счетно.
Дата публикования: 2015-03-29; Прочитано: 2393 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!