Соответствия
Решение задачСоответствием g между множествами X и Y будем называть тройку объектов: Г = (Х, K,G), где X — область отправления соответствия, Y — область прибытия соответствия, G — график соответствия, причём G ⊆ X × Y.
Областью определения соответствия будем называть пр1G.
Областью значений соответствия будем называть пр2G.
Соответствие называется всюду определённым, если пр1 G = X.
Соответствие называется сюръективным, если np2G = Y.
Соответствие будем называть функциональным, или функцией, если его график не содержит пар с одинаковыми первыми и различными вторыми координатами.
Соответствие называется инъективным, если его график не содержит пар с одинаковыми вторыми и различными первыми координатами.
Соответствие называется отображением X в Y, если оно всюду определено и функционально.
Соответствие называется отображением X на Y, если оно всюду определено, функционально и сюръективно.
Соответствие называется взаимно однозначным, если оно функционально и инъективно.
Соответствие называется биекцией, если оно всюду определено, сюръективно, функционально и инъективно.
Образом множества А при данном соответствии называется множество Г(В) = {у|(х,у)∈ G и х∈ А].
Прообразом множecmвa В при данном соответствии называется множество Г-1 (В) = {х|(х,у)∈ G и у∈ В}.
Множества называются равномощными, если между ними можно установить биекцию.
Множество называется счётным, если оно равномощно множеству натуральных чисел.
Множество называется континуальным, если оно равномощно множеству действительных чисел отрезка [0,1].
Задание 1.3.1
- Изобразить соответствие в виде графа.
- Выяснить, какими из 4 основных свойств (всюду определённость, сюръективность, функциональность, инъективность) обладает Г.
- Найти образ множества А и прообраз множества В при данном соответствии.
- Построить соответствие между бесконечными множествами, обладающее тем же набором свойств, что и Г.
- Построить соответствие между конечными множествами, обладающее набором свойств, противоположным данному. Замечание. Для данного и построенных соответствий отметить случаи отображений, указать их тип, отметить случаи биекций.
Замечание. Для данного и постоенных соответствий отметить случаи отображений, указать их тип, отметить случаи биекций.
Таблица 1.3.1
| № | X | Y | G | A | B |
| 1 | a,b,с,d,e | 1,2,3 | (a,2),(b,3),(c,l),(d,2),(e,l) | e,c | 2,3 |
| 2 | a,b,с,d | 1,2,3,4 | (a,4),(b,3),(c,2),(d,1) | a,b | 1,3 |
| 3 | a,b,с,d | 1,2,3,4,5 | (a,3),(b,5),(c,4),(d,1) | a,c | 1,4 |
| 4 | a,b,с,d,e | 1,2,3,4 | (d,1),(b,2),(e,4),(a,3) | b,c | 1,2 |
| 5 | a,b,с,d,e | 1,2,3 | (b,2),(c,1),(e,3),(a,3) | e,c | 3,1 |
| 6 | a,b,с,d | 1,2,3,4 | (a,2),(b,3),(c,1),(a,4) | a,b | 1,2 |
| 7 | a,b,с,d,e | 1,2,3,4,5 | (a,5),(b,3),(d,1),(e,2) | d,e | 1,3 |
| 8 | a,b,с,d | 1,2,3,4 | (a,3),(b,4),(c,3),(d,1) | a,c | 1,3 |
| 9 | a,b,с | 1,2,3,4,5 | (a,2),(b,1),(c,5),(a,3) | a,b | 3,4 |
| 10 | a,b,с | 1,2,3 | (a,1),(a,3),(b,2),(c,3) | a,c | 2,3 |
| 11 | a,b,с,d | 1,2,3,4,5 | (a,2),(c,1),(d,5),(c,3) | b,c | 1,2 |
| 12 | a,b,с,d,e | 1,2,3,4 | (b,1),(c,3),(d,2),(c,1) | a,c | 1,2 |
| 13 | a,b,с,d | 1,2,3 | (a,1),(b,1),(c,3),(b,2) | b,d | 1,3 |
| 14 | a,b,с,d | 1,2,3,4 | (a,4),(b,3),(b,2),(c,3),(d,4) | a,b | 3,4 |
| 15 | a,b,с,d | 1,2,3,4 | (a,4),(c,4),(b,2),(a,3) | a,b | 2,4 |
| 16 | a,b,с,d,e | 1,2,3 | (a,2),(b,1),(d,3),(e,1) | a,b | 1,2 |
| 17 | a,b,с,d | 1,2,3,4 | (b,3),(a,2),(c,2),(d,1) | a,c | 1,4 |
| 18 | a,b,с,d | 1,2,3,4 | (a,3),(c,2),(d,1),(c,4) | c,d | 2,3 |
| 19 | a,b,с | 1,2,3,4,5 | (a,2),(b,5),(c,4),(b,3) | a,b | 2,5 |
| 20 | a,b,с,d | 1,2,3,4 | (a,1),(b,3),(a,2),(c,4) | a,b | 2,3 |
| 21 | a,b,с,d | 1,2,3,4 | (a,1),(b,3),(a,2),(c,4) | a,b | 2,3 |
| 22 | a,b,с,d | 1,2,3 | (a,1),(b,3),(c,2),(a,2) | a,b | 2,3 |
| 23 | a,b,с,d | 1,2,3,4 | (a,3),(b,4),(c,1),(d,2) | a,b | 1,4 |
| 24 | a,b,с | 1,2,3,4 | (a,3),(b,1),(c,2),(c,1) | a,c | 4,2 |
| 25 | a,b,с,d,e | 1,2,3 | (c,2),(d,1),(a,3),(b,3) | a,d | 3,1 |
| 26 | a,b,с,d | 1,2,3,4 | (b,2),(c,3),(d,1),(b,4) | b,c | 1,2 |
| 27 | a,b,с,d,e | 1,2,3,4,5 | (b,5),(c,3),(e,1),(a,2) | a,e | 1,3 |
| 28 | a,b,с,d | 1,2,3,4 | (b,3),(c,4),(d,3),(a,1) | b,d | 3,1 |
| 29 | a,b,с | 1,2,3,4,5 | (b,3),(c,4),(d,3),(a,1) | b,d | 3,1 |
| 30 | a,b,с | 1,2,3 | (b,1),(b,3),(c,2),(a,3) | a,b | 2,3 |
Пример решения заданя 1.3.1 Решим задание 1.3.1 для соответствия Г = (X,Y,G), если X - {a,b,c,d}, Y = {1,2,3,4,5} G = {(a,2),(b,l),(b,5),(d,4)}, А = {а,Ь), В = {3,4}. |
Рис 1.3.1,а
|
- Изобразим соответствие в виде графа (рис. 1.3.1, а).
- Выясним, какими из свойств обладает данное соответствие. α) Соответствие не всюду определено, так как npjG -{a,byd} Ф X. β) Соответствие не сюръективно, так как np2G = {1,2,4,5} Ф Y. γ) Соответствие не функционально, так как его график содержит две пары (Ь,1)и (Ь,5) с одинаковыми первыми и различными вторыми координатами. δ) Соответствие инъективно, так как его график G не содержит пар с одинаковыми вторыми и различными первыми координатами.
- Найдём образ Г(А)и прообраз Г-1(В). Г(А) = {1,2,5}, так как А = {a,b} и {(а,2),(b,1),(b,5)} ⊆ G Г-1(B) = {d}, так как В = {3,4} и только (d,4) ⊆ G.
- Построим соответствие между бесконечными множествами, обладающее тем же набором свойств, что и данное соответствие. Пусть Х=[0,2], У = (-оо,+оо), G = {(x,y)\x2 +у2=1 и х>0}. Покажем, что это соответст- вие (рис. 1.3.1, б) обладает тем же набором свойств, что и данное.
α) Построенное соответствие не всюду определено, так как nptG = [0,l]*X. β) Построенное соответствие не сюръективно, так как np2G = [-l,l]*K.
γ) Построенное соответствие не функционально, т. к., например, (ОД)еС и (0,-1)eG.
δ) Соответствие инъективно, так как его график не содержит пар с различными первыми и одинаковыми вторыми координатами. |
Рис. 1.3.1, б
|
Построим соответствие между конечными множествами, чтобы оно было всюду определено, сюръективно, функционально и не инъективно, изобразим его в виде графа (рис. 1.3.1, в) и аналитически: Г = ({u,v},{w},{(u,w),(v,w)}). Покажем, что это соответствие обладает требуемым набором свойств, что и данное. |
Рис. 1.3.1, б
|
α) Действительно, это соответствие всюду определено, так как np1G = X = {u,v}.
β) Соответствие сюръективно, так как np2G = {w} = Y.
γ) Соответствие функционально, так как в его графике нет пар с одинаковыми первыми и различными вторыми координатами.
δ) Соответствие не инъективно, так как его график состоит из двух пар (u,w)и , (v,w) с различными первыми и одинаковыми вторыми координатами.
Так как построенное соответствие всюду определено, сюръективно и функционально, оно является отображением X на Y.
Задание 1.3.2
Для соответствия Г =(X,Y,G)
- Определить набор свойств, которыми обладает данное соответствие.
- Построить соответствие между конечными множествами с набором свойств, противоположным данному, изобразив соответствие аналитически и в виде графа.
Замечание. Отметить случаи отображений и биекций.
Таблица 1.3.2
| № | X | Y | G |
| 1 | многочлены 2 степени от одной переменной с действительными коэффичентами | R | (многочлен, его корень) |
| 2 | множество кугов на плоскости | множество точек плоскости | (круг, его центр) |
| 3 | (0, + ∞) | [-1,1] | (x,y)|x2 |
| 4 | N | R | (x, ± 1n x) |
| 5 | R | непрерывные на [a,b] функции |
|
| 6 | вузы вашего города | жители вышего города | (вуз; человек, окончивший этот вуз) |
| 7 | (0, + ∞) | отрезки на прямой | (x, отрезок длины x) |
| 8 | фамилии студентов вашей группы | {1,2,...,100} | (фамилия, число букв в фамилии) |
| 9 | окружности на плоскости | Z | (окружность, ее длина) |
| 10 | функции, определенные на [0,1] | R | (функция, ордината ее точки максимума) |
| 11 | R2 | N |
|
| 12 | Имена студентов вашей группы | буквы русского алфавита | (имя, буква из имени) |
| 13 | N | студенты вашего вуза | (n, человек с годом рождения n) |
| 14 | [0,1] | {0,1} |
(x,f(x)), где
|
| 15 | R | R10 | (maxai,(at,a2,..,a10))1≤i≤10 |
| 16 | окружности на плоскости | прямые на плоскости | (окружность, касательная к этой оружности) |
| 17 | [P(U)]3 | P(U) | ((A,B,C),A⌒B⌒C) |
| 18 | [0,1] | R2 | (x,(x,y)|x2+ y2 = 1) |
| 19 | R | функции, непрерывные на [0,1] |
|
| 20 | P(U) | [P(U)]3 |
|
| 21 | {0,1,2} | N | (x,y)|x - остаток от деления y на 3 |
| 22 | [1,3] | R+ | (x,y)|(x-2)2 + (y-2)2≤1 |
| 23 | пары окружностей на плоскости | R2 | (пара окружностей, координаты точки пересечения этих окружностей) |
| 24 | множество книг в библиотеке вашего вуза | Z | (книга, число страниц в этой книге) |
| 25 | (-4,4) | [1,6] | (x,y)|y=|x-2|+1 |
| 26 | мужчины вашего города | женщины вашего города | (x,y)|x и y состоят или когда-либо состояли друг с другом в законном браке |
| 27 | [P(U)]2 | P(U) | ((A,B),A\B) |
| 28 | политические партии вашего города | жители вашего города | ((партия), (человек, состоящий в этой партии) |
| 29 | P(U), где U ={1,2,...,40} | N | (A,|A|), где A∈ P(U) |
| 30 | пары прямых на плоскости | R | (пара прямых, абцисса точки пересечения прямых) |
Пример решения задания 1.3.2
Решим задание 1.3.2 для соответствия Г = (X,Y,G), если
X = N, Y — множество непрерывных на [а,Ь] функций, а график G задан так: G =
.
1. Определим набор свойств, которым обладает данное соответствие.
α) Для любого натурального числа п можно рассмотреть непрерывную функцию f(x) =
Тогда, вычисляя определённый интеграл,
будем иметь:
Итак, доказано, что данное соответствие является всюду определённым.
β) Так как для некоторых непрерывных функций на [а,b] определённый интеграл не выражается натуральным числом, то данное соответствие не является сюръективным.
γ) Покажем, что две различные функции могут иметь на рассматриваемом промежутке одинаковое значение определённого интеграла. Для этого можно рассмотреть функции
Для f(x) определённый интеграл не отрезке [а,b], как мы уже выяснили, равен n. Найдём соответствующий интеграл для g(x):
Итак, доказано, что соответствие, описанное в условии задания, не является функциональным.
δ) Так как для каждой функции её определённый интеграл на данном промежутке находится однозначно, данное соответствие является инъективным.
2. Построим соответствие между конечными множествами, чтобы оно было не всюду определено, сюръективно, функционально и не инъективно.
Пусть Г = ({a,d,c},{1},{(а,1),(b,1)} (рис. 1.3.2). Покажем, что построенное соответствие обладает требуемым набором свойств. |
Рис. 1.3.2
|
α) Соответствие Г не всюду определено, так как элемент с, входящий в область отправления, не имеет образа при данном соответствии.
β) Соответствие Г сюръективно, так как его область прибытия {1} совпадает с областью значений.
γ) Соответствие Г функционально, так как его график не содержит пар с равными первыми и различными вторыми координатами.
δ) Соответствие Г не инъективно. так как в его графике пары (а,1) и (b,1) имеют различные первые и одинаковые вторые координаты.
Задание 1.3.3
Установить биекцию между множествами
Таблица 1.3.3
| № | Множества |
| 1 |
{(x,y)|x2+y2≤1}и{(x,y)|x2+y2<1} |
| 2 |
[0,1] и R |
| 3 |
[0,+∞)и[0,1] |
| 4 |
N и множество многочленов 3й степени с натуральными коэффицентами |
| 5 |
R и [0,+∞] |
| 6 |
{(x,y)|x2+y2=1} и [0.1) |
| 7 |
все окружности на плоскости и R×R×(0,+∞) |
| 8 |
{(x,y)|-π2 < x < π2 ,0 < y < π} и R2 |
| 9 |
Q⌒[0,1] и Q2⌒[0,1]2 |
| 10 |
(0,1) и [e,π] |
| 11 |
[0,+∞) и (a,b) |
| 12 |
все интервалы на прямой и полуплоскость, расположенная ниже линии y=x |
| 13 |
{(x,y)|x2+y2≤1} и {(x,y)|x2+y2<100} |
| 14 |
Q и Q⌒[0+∞) |
| 15 |
[0,1] и (2,5) |
| 16 |
полуокружность без концевых точек и луч (0,+∞) |
| 17 |
(-∞,0) и R |
| 18 |
N и Q2 |
| 19 |
Q и множество всех многочленов с рациональными коэффицентами |
| 20 |
(0,1) и R |
| 21 |
Q и Q2 |
| 22 |
сфера с выколотой точкой и вся плоскость |
| 23 |
{(x,y)|x2+y2≤4} и {(x,y)|x2+y2≥4} |
| 24 |
Q и Q⌒[0,1] |
| 25 |
R и [1,+∞)∪{-10} |
| 26 |
N и N2 |
| 27 |
все последовательности натуральных чисел и все возрастающие последовательности натуральных чисел |
| 28 |
N и множество всех многочленов с натуральными коффицентами |
| 29 |
R и R\Q |
| 30 |
Q и N2 |
Пример решения задания 1.3.3
Установить биекцию между множествами [0,1] и (0,1).
Будем считать, что Х=[0,1], К = (0,1).Пусть A={ 1/2 , 1/3 ,..., 1/n ,...}, B={ 0,1, 1/2 , 1/3 ,..., 1/n ,...}=A∪{0,1} Очевидно, что X\B=Y\A, X=X\B∪B, Y=Y\A∪A.
Установим биекцию между множествами Х\В и У\А, как тождественное соответствие f(x) = х.
Биекцию между множествами А и В зададим так:
f(0)=1/2 , f(1)=1/3 , f(1/2) = 1/4 , f(1/3) = 1/5 ,...,f(1/n)= 1/n+2 ,...
Таким образом, между X и К установлена биекция:
Изобразим график этой биекции в декартовой системе координат (рис. 1.3.3).
Рис. 1.3.3
Задание выполнено
Задание 1.3.4
Доказать, что множество:
Таблица 1.3.4
| № |
Условие |
| 1 |
всех многочленов от х с рациональными коэффициентами счетно |
| 2 |
всех пар рациональных чисел счётно |
| 3 |
всех многочленов от дг с целыми коэффициентами счётно |
| 4 |
всех кругов на плоскости, радиусы которых и координаты центра являются рациональными числами — счётно |
| 5 |
попарно непересекающихся замкнутых кругов на плоскости не более чем счётно |
| 6 |
всех многочленов n-й степени от х с рациональными коэффициентами счётно |
| 7 |
всех многочленов п -и степени от х с целыми коэффициентами счётно |
| 8 |
попарно непересекающихся прямоугольников на плоскости не более чем счётно |
| 9 |
всех окружностей на плоскости, радиусы которых и координаты центра являются целыми числами — счётно |
| 10 |
полученное объединением счётного числа конечных множеств — не более, чем счётно |
| 11 |
полученное объединением счётного числа счётных множеств — счётно |
| 12 |
рациональных чисел интервала (0,1) — счётно |
| 13 |
непересекающихся окружностей на плоскости может быть континуально |
| 14 |
всех действительных чисел интервала (0,1), в десятичном разложении которых на четвёртом месте стоит цифра 7 — континуально |
| 15 |
точек разрыва монотонно убывающей на [а,Ь] функции — не более чем счётно |
| 16 |
точек плоскости, расстояние между любыми элементами которого больше 3, не более чем счётно |
| 17 |
попарно непересекающихся открытых интервалов на прямой не более чем счётно |
| 18 |
полученное объединением счётного числа непустых попарно непересекающихся конечных множеств, счётно |
| 19 |
всех конечных последовательностей натуральных чисел — счётно |
| 20 |
всех конечных подмножеств счётного множества — счётно |
| 21 |
попарно непересекающихся букв Г на плоскости может быть континуально |
| 22 |
попарно непересекающихся букв L на плоскости может быть континуально |
| 23 |
попарно непересекающихся букв Т на плоскости не более чем счётно |
| 24 |
А1×А2×...×Аn— счётно, если каждое из множеств А1,А2,...,Аn — счётно |
| 25 |
чисел вида 2n .3m —счётно, если не N и m∈ N |
| 26 |
иррациональных чисел интервала (0,1) — несчётно |
| 27 |
всех бесконечных последовательностей, составленных из нулей и единиц — континуально |
| 28 |
всех корней многочленов третьей степени с натуральными коэффициентами — счётно |
| 29 |
функций вида f:E"->E, где E = {0,1}, п = 1,2,3,... — счётно |
| 30 |
полученное объединением конечного числа счётных множеств — счётно |
Пример решения задания 1.3.4
Доказать, что множество всех конечных последовательнос- тей, составленных из элементов некоторого счётного мно- жества, счётно.
Пусть множество А счётно, А = {а1,а2,...,an,...}. Обозначим через Вк множество конечных последовательностей длины к, составленных из элементов множества A, k∈N. Покажем для любого к, что множество Вк —счётно.
Пусть
Таким образом, любая конечная последовательность длины k, составленная из элементов счётного множества, получит свой номер.
Выпишем элементы множеств Вk в виде бесконечной таблицы, где k∈N.
Таблица 1.3.4
|
Будем обходить таблицу по маршруту, помеченному стрелками. По мере продвижения по этому маршруту будем навешивать номера: b11 -1, b12- 2, b22 -3, b21 -4 и т.д. |
Имеем, что для любых индексов i,p последовательность bpi получит когда-нибудь единственный номер.
Таким образом, установлена биекция между множеством, составленным из элементов bpi, и множеством индексов N, то есть доказана счётность множества всех конечных последовательностей, составленных из элементов некоторого счётного множества А.