DM_Mnozhestva (1)

Пример решение задания 2.2.

Для данного графика P 1,1 , 1,2 , 2,3 , 2,2 найти:

P 1, P P, P 1 P , пр 2 Р 1 Р пр1 P P .

Решение. По определению инверсии, 2,1 Р 1 , так как 1,2 Р . Рассуждая подобным обра-

зом, получим: P 1 1,1 , 2,1 , 3, 2 , 2 , 2, .

По определению композиции,			1, 3 P P , так как существует 2 такой, что				1, 2 P и
2, 3 P . Продолжая строить композицию, приходим: P P 1,1 , 1, 2 , 1,3 , 2,3 , 2, 2 .
Аналогично получаем
		P 1 P 1,1 , 2, 2 , 1, 2 , 2,1 , 2, 3 , 3, 2 , 3, 3
Вспоминая определение проекции множества векторов на ось, получим: пр				2	Р 1	Р 1, 2,3 ,
аналогично найдём другую проекцию: пр1 Р Р 1, 2 и, наконец, можем написать:
пр	2	Р 1 Р пр P P 1,1 , 1, 2 , 2,1 , 2, 2 , 3,1 , 3, 2
			1

21

Задание 2.3. Для данных графиков P и T решить относительно графика X уравнение

X P T при условии, что		X		6 ,	пр1X пр2 X 1, 2,3, 4,5, 6 . Для каждого найденного X ука-
зать P X .

Пример решения задания 2.3.

Для графиков P 5,3 , 1,3 , 4,4 , 2,1 , 3,6 и T 1, 4 , 2,1 , 6,3 , 5, 6 , 3,3 решить

относительно

графика

X

уравнение

X P T

при

условии,

что

X 6 ,

пр1X пр2 X 1, 2,3, 4,5, 6 . Для каждого найденного Х указать P X .

Решение. Для каждой пары a,b T	ищем пару x, b P . Если такая пара существует, то
a, x может принадлежать графику X .

22

Запишем множество A , составленное из пар вида a, x , отвечающих парам a,b T :

A 1, 4 , 2, 2 , 6,1 , 6, 5 , 5, 3 , 3,1 , 3, 5 .

Так как по условию задачи 4 пр1X , то пара 4, x X . Однако в графике T нет пары, начинающейся на 4. Поскольку в графике P нет пары, начинающейся на 6, то x 6 , т.е. для пары4, 6 X не найдется подходящей (для композиции) пары из графика P.

Составим X , добавляя к паре 4, 6 пары из графика A , так чтобы выполнилось условие задачи. Получим два варианта решения:

X1 1, 4 , 2, 2 , 6,1 , 5,3 , 3,5 , 4, 6 ,

X 2 1, 4 , 2, 2 , 6,5 , 5,3 , 3,1 , 4, 6 .

Проверкой убеждаемся в том, что X1 и		X 2 являются решениями исходного уравнения. Со-
гласно определению композиции, выпишем Р Х1 и			Р Х 2 :
Р Х1 1, 5 , 2, 4 , 3,1 , 4, 6 , 5, 5 ,			P X 2 1,1 , 2, 4 , 3, 5 , 5,1 , 4, 6 .
Ответ: X1 1, 4 , 2, 2	, 6,1 , 5,3 , 3,5 , 4, 6 , X 2 1, 4 , 2, 2 , 6,5 , 5,3 , 3,1 , 4, 6 ;
Р Х1 1, 5 ,	2, 4 , 3,1 , 4, 6 , 5, 5 ,	P X 2 1,1 , 2, 4 , 3, 5 , 5,1 , 4, 6 .

Задание 2.4. Для графиков P и T из соотношения P X T найти график X наименьшей возможной мощности.

23

Пример решения задания 2.4.

Для графиков P b, a , c, a , c, b и T b, b , b, c , b, a , c, b , c, c , c, a из соот-

ношения P X T найти график X наименьшей возможной мощности. Решение. Найдём инверсию графика P : P 1 a, b , a, c , b, c .

24

Пусть X график наименьшей мощности, являющийся решением уравнения Р Х T . Из определения композиции графиков и минимальности X следует, что пр2 P пр1X a,b .

Найдём композицию графика P 1 с левой и правой частями равенства Р Х T . Получим:

a, b , a, c , b, c b, a , c, a , c, b X P 1 T , или

a, a , b,b , a,b , b, a X P 1 T , откуда а, a , b,b X a,b , b, a X P 1 T .

Из равенства пр2 P пр1X a,b и определение композиции графиков следует, что
a, a , b,b X Х .
Значит, верно равенство X a,b , b, a X P 1 T .
Итак, график P 1 T кроме пар графика X может содержать	также пары графика
a,b , b, a X , не попавшие в X . Выпишем все пары, попавшие в график	P 1 T .

P 1 T a, b , a, c , b , c b, b , b, c , b, a , c, b , c, c , c, aa,b , a,c , a, a , b,b , b,c , b, a .

Выберем из этого графика пары, образующие X .

Для этого изобразим таблицу, в заголовках столбцов выписав пары графика P 1 T , а в заголовках строк – пары графика Т (таблица 2). Для каждой пары u, v P 1 T (для каждого столбца)

звёздочкой отметим

пары типа

, v из Т

(строки этого

столбца),

попавшие в

композицию

u, , v , здесь u, P 1 . Например, для пары (столбца)

a,b звёздочкой отмечены строки пар

b,b , c,b T , так как a,b b,b a,b , a, c c,b a,b .

Таблица 2

P 1 T

ab

ac

aa

bb

bc

ba

Т

bb

*

bc

*

ba

*

cb

*

*

cc

*

*

ca

*

*

Далее, выберем наименьшее число столбцов таблицы так, чтобы для любой строки в выбранном наборе нашёлся столбец, имеющий символ «*» в данной строке.

25

В нашем примере видно, что такой набор образуют столбцы, помеченные комбинациями
ab, ac, aa, следовательно, X ab, ac, aa .
Ответ: X ab, ac, aa .
3. Соответствия
Соответствием между множествами	X и Y будем называть тройку объектов: Г X ,Y, G ,
где X – область отправления соответствия,	Y – область прибытия соответствия, G – график соот-
ветствия, т.е. G X Y .

Областью определения соответствия будем называть пр1 G . Областью значений соответствия будем называть пр2 G .

Соответствие называется всюду определённым, если пр1 G Х .

Соответствие называется сюръективным, если пр2 G Y

Соответствие будем называть функциональным, или функцией, если его график не содержит пар с одинаковыми первыми и различными вторыми координатами, т.е. пар типа a,b , a, c

Соответствие называется инъективным, если его график не содержит пар с одинаковыми вторыми и различными первыми координатами, т.е. пар типа a,b , d,b

Соответствие называется отображением X в Y , если оно всюду определено и функциональ-

но.

Соответствие называется отображением X на Y , если оно всюду определено, функционально и сюръективно.

Соответствие называется взаимно однозначным, если оно функционально и инъективно.

Соответствие называется биекцией, если оно всюду определено, сюръективно, функционально и инъективно.

	Образом элемента x пр1 G				при соответствии					Г X ,Y, G	называется такой элемент
y пр 2 G , что х, у G , т.е.			Г x у		y пр2 G и х, у G .
	Прообразом элемента		y пр 2 G при соответствии							Г X ,Y, G	называется такой элемент
x пр	1	G , что х, у G , т.е. Г 1 y x					x пр	1	G и x, y G .

Образом множества А при соответствии Г X ,Y, G называется множество

Г A у х, у G и x A .

Прообразом множества B при соответствии Г X ,Y, G называется множество

Г 1 B x x, y G и y B .

26

Множества называются равномощными (эквивалентными), если между ними можно установить биекцию.

Множество называется счётным, если оно равномощно множеству натуральных чисел.

Множество называется континуальным, если оно равномощно множеству действительных чисел отрезка 0; 1 .

Задание 3.1. Дано соответствие Г X ,Y, G .

1.Изобразить соответствие в виде графа.

2.Выяснить, какими из 4 основных свойств (всюду определённость, сюръективность, функциональность, инъективность) обладает Г .

3.Найти образ множества А и прообраз множества В при данном соответствии.

4.Построить соответствие между бесконечными множествами, обладающее тем же набором свойств, что и Г .

5.Построить соответствие между конечными множествами, обладающее набором свойств, противоположным набору свойств соответствия Г .

Замечание. Для данного и построенных соответствий отметить случаи отображений, указать их тип, отметить случаи биекций.

27

Пример решения заданий 3.1.
Решим задание 3.1 для соответствия Г X ,Y , G ,
если X a, b, c, d , Y 1, 2, 3, 4, 5 ,	G a, 2 , b,1 , b, 5 , d, 4 ,	A a, b ,	B 3, 4 .
	28

Решение.
1. Изобразим соответствие в виде графа (рис. 5).
Х	Y
а	1
b	2
	3
c	4
d	5

Рис. 5 2. Выясним, какими из свойств обладает данное соответствие.

а) Соответствие не всюду определено, так как пр1 G a,b, d X .

б) Соответствие не является сюръективным, так как пр2 G 1, 2, 4, 5 Y .

в) Соответствие не является функциональным, так как его график содержит две пары b,1 иb, 5 с одинаковыми первыми и различными вторыми координатами.

г) Соответствие инъективно, так как его график G не содержит пар с одинаковыми вторыми и различными первыми координатами.

3. Найдём образ Г А и прообраз Г 1 В .

ГА 1, 2, 5 , так как A a, b и a, 2 , b,1 , b, 5 G .

Г1 B d , так как B 3, 4 и только d, 4 G .

4.Построим соответствие между бесконечными множествами, обладающее тем же набором свойств, что и данное соответствие.

Пусть X 0;2 , Y , , G x, y		x2 y2	1 и x 0 .
Покажем, что это соответствие (рис. 6) обладает			у
тем же набором свойств, что и данное.
а) Построенное соответствие не всюду опреде-
лено, так как пр1 G 0;1 Х .			0	1	2

б) Построенное соответствие не сюръективно,		х
так как пр2 G 1;1 Y .
в) Построенное соответствие не функционально,
т.к., например, 0,1 G и	0, 1 G .	Рис. 6

29

г) Соответствие инъективно, так как его график не содержит пар с различными первыми и одинаковыми вторыми координатами.

5. Построим соответствие между		X
конечными множествами, чтобы оно было
всюду определено, сюръективно, функцио-	u	Y
нально и не инъективно, изобразим его в
виде графа (рис. 7) и аналитически:		w
u, v , w , u, w , v, w	v
Покажем, что это соответствие об-
ладает набором свойств, противоположным		Рис. 7
набору свойств соответствия Г .

а) Действительно, это соответствие всюду определено, так как пр1 G Х u, v .

б) Соответствие сюръективно, так как пр2 G w Y .

в) Соответствие функционально, так как в его графике нет пар с одинаковыми первыми и различными вторыми координатами.

г) Соответствие не инъективно, так как его график состоит из двух пар u, w и v, w с различными первыми и одинаковыми вторыми координатами.

Так как построенное соответствие всюду определено, сюръективно и функционально, оно является отображением Х на Y .

Задание 3.2. Для соответствия Г X ,Y , G

1.Определить набор свойств, которыми обладает данное соответствие.

2.Построить соответствие между конечными множествами с набором свойств, противоположным данному, изобразив соответствие аналитически и в виде графа.

Замечание. Отметить случаи отображений и биекций.

30