2_lektsia

ЛЕКЦИЯ 2

(отображения, инъекция, сюръекция, биекция; композиция отображений, ее свойства; левое и правое обратные отображения, необходимое и достаточное условие существования обратного отображения, свойства обратного отображения)

Отображения

Понятие отображения играет центральную роль во всей математике. Пусть X и Y некоторые множества.

Определение 1. Правило f, по которому каждому элементу a 2 X ставится в соответствие один и только один элемент f(a) 2 Y , называется отображением и обозначается

f : X ! Y: /

В определении отображения важны все три элемента: f, X, Y . Изменение любого из них приводит к другому отображению. Определение отображения и с к л ю ч а е т две ситуации:

1)ситуацию, в которой один элемент x 2 X при отображении f : X ! Y переходит в два разных элемента из Y ;

2)ситуацию, в которой существует хотя бы один элемент x 2 X, который отображение f : X ! Y не перевело ни в один элемент множества Y .

Определение отображения д о п у с к а е т:

1)чтобы двум разным элементам x1; x2 2 X, x1 6= x2 соответствовал один и тот же элемент f(x1) = f(x2) (т.е. отображение может “склеивать”);

2)чтобы множество Y содержало элементы, в которые отображение не переводит ни один элемент из множества X.

Указанные исключения и допуски демонстрируют, что роль множеств X и Y в отображении f : X ! Y не одинакова.

Любая однозначная функция y = f(x); x 2 X; y 2 Y является отображением, если наряду с правилом f указаны множества X и Y . Многозначные функции отображениями не являются.

Равенство отображений f1 : X1 ! Y1 и f2 : X2 ! Y2 означает, что совпадают множества X1 = X2 = X и Y1 = Y2 = Y , кроме того, 8x 2 X выполняется равенство: f1(x) = f2(x):

Тождественное отображение Id X : X ! X любому элементу ставит в соответствие сам этот элемент:

8 a 2 X Id X (a) = a:

(1)

Определение 2. Образом элемента x 2 X при отображении f : X ! Y называется элемент y 2 Y , в который это отображение переводит x, т.е. y = f(x); f(x) 2 Y .

/

1

Из определения отображения следует, что 8 x 2 X образ f(x) 2 Y существует и единственен.

Запись f означает правило, запись f(x) означает образ элемента x при отображении f : X ! Y .

Образ подмножества. Пусть A подмножество множества X (A X), подмножество f(A) множества Y (f(A) Y ) есть образ подмножества A при отображении f : X ! Y :

f(A) = fy 2 Y j 9 x 2 A; f(x) = yg:

Образ отображения f : X ! Y . Подмножество f(X) Y называется образом отображения f : X ! Y и обозначается Im f,

d	(1)
Im f = f(X); f(X) Y:

Инъективные, сюръективные и биективные отображения

Отображения, изображенные на рис. 1–4, качественно различны. Первое “склеивает” и множество Y не содержит элементов, в которые ничего не перешло; второе“склеивает” и множество Y содержит элемент, в который ничего не перешло; третье не “склеивает” и множество Y содержит элементы, в которые ничего не перешло; четвертое не “склеивает” и множество Y не содержит элементов, в которые ничего не перешло.

Определение 3. Отображение f : X ! Y называется инъективным (или инъекцией), если оно не “склеивает”, т.е. если 8 x1; x2 2 X

x1 6= x2

)

f(x1) 6= f(x2):

/

(2)

Пример 1. Отображения на рис. 3, 4 являются инъективными, отображения на рис. 1, 2 не инъективны.

	XXXX				a	XX	XXX:zX y1
a						r			a
b	r	X:-zX		y1	b			r	b	r
c	r		- y2		c	r		ry3	c	r
	r			r		r	:- y2			r
d	r			r	d	r		r	d	r

r

r y1

-r y2

-r y3

-r y4

-r y56y

a	r	H		r	y1
	H		*
c	r	HH
			-r y3
b			HjH y2
	r		-	r y4
d	r
				r

Рис. 1.

Рис. 2.

Рис. 3.

Рис. 4.

Название инъекция произошло от французского слова injection вложение. Для доказательства инъективности отображения надо доказать либо (2), либо

эквивалентное условие: 8 x1; x2 2 X

f(x1) = f(x2)	)		(3)
		x1 = x2:

Определение 4. Отображение f : X ! Y называется сюръективным (или

сюръекцией), если множество Y не содержит элементов, в которые ничего не перешло, т.е. если

Im f = Y:	/	(4)

2

Пример 2. Отображения на рис. 1, 4 являются сюръективными, отображения на рис. 2, 3 не сюръективны.

Название сюръекция произошло от французского слова surjection.

Любое отображения легко сделать сюръективным, достаточно заменить множество Y на множество f(X), а именно, отображение на образ f : X ! f(X) всегда сюръективно.

Определение 5. Отображение f : X ! Y называется биективным (или биекцией), если оно инъективно и сюръективно одновременно. /

Биективное отображение называют также взаимно однозначным. Название биективное произошло от французского слова bijective.

Пример 3. Из всех отображений на рис. 1–4 только отображение на рис. 4 является биективным.

Определение 6. Прообразом f 1(y) элемента y 2 Y при отображении f : X ! Y называется подмножество множества X, состоящее из всех элементов множества X, перешедших при этом отображении в элемент y. /

Прообраз f 1(y) может, в зависимости от типа отображения, содержать либо один элемент из X, либо совокупность элементов из X, либо быть пустым множеством.

Пример 4. Для отображения на рис. 1 прообразом элемента y1 являются элементы a; b; c 2 X, т.е. f 1(y1) = fa; b; cg; прообразом элемента y2 является элемент d, т.е. f 1(y2) = fdg. Прообразом элемента y3 для отображения на рис. 2 является пустое множество, т.е. f 1(y3) = . /

Определения инъективных, сюръективных и биективных отображений можно дать в терминах прообразов элементов, а именно:

1.Отображение f : X ! Y инъективно, если прообраз любого элемента y 2 Y

содержит не более одного элемента.

2.Отображение f : X ! Y сюръективно, если прообраз любого элемента y 2 Y

содержит не менее одного элемента.

3.Отображение f : X ! Y биективно, если прообраз любого элемента y 2 Y

состоит из одного элемента.

Замечание 1. Инъекция на образ всегда биекция. Действительно, отображение на образ всегда сюръективно, если к тому же это инъекция, то отображение биективно. Например, из инъективного отображения (рис. 3) можно сделать биективное, заменив Y = fy1; y2; y3; y4; y5; y6g множеством f(X) = fy2; y3; y4; y5g.

Композиция отображений

Определение 7. Композицией отображений f : X ! Y и g : Y ! Z называ-

ется отображение
h : X ! Z h = g f; 8 x 2 X h(x) = (g f)(x) = g(f(x));	(5)
здесь ( ) знак композиции отображений f : X ! Y и g : Y ! Z. /
Часто для облегчения текста используется запись: (g f)(x) = g f(x).

3

Композиция определена не для любых отображений; только если множество Y отображения f : X ! Y совпадает со множество U отображения g : U ! Z, можно определить их композицию отображение h : X ! Z, h = g f. В случае f : X ! X, g : X ! X композиция определена всегда. На языке функций композиция отображений является сложной функцией.

Свойства композиции отображений

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

Пусть отображения заданы следующим образом:

f : R ! R 8 x 2 R f(x) = x+a; a 2 R; g : R ! R 8 x 2 R g(x) =

x

; b 6= 0; b 2 R:

b

Найдем композиции g f и f g:

8 x 2 R g f(x) = g(f(x)) = g(x + a) =

x + a

x

a

=

+

;

b

b

b

x

x

8 x 2 R f g(x) = f(g(x)) = f

=

+ a:

) g f 6= f g:

b

b

Ассоциативность композиции отображений проверяется непосредственно в со-

ответствии с опр. 7:		h (x) = (f		g)(h(x)) = f	g(h(x))	:
(f (g)
	f g h) (x) = f (g h)(x) = f g(h(x)) ;

Утверждение 1. Композиция инъекций является инъекцией.

Доказательство. Пусть оба отображения f : X ! Y и g : Y ! Z инъективны. Для доказательства инъективности их композиции h : X ! Z, h = g f достаточно доказать выполнение условия (3).

Пусть 8 x1; x2 2 X h(x1) = h(x2) ) g(f(x1)) = g(f(x2)) ) (так как отображение g : Y ! Z инъективно) ) f(x1) = f(x2) ) (так как отображение f : X ! Y инъективно) ) x1 = x2: /

Утверждение 2. Композиция сюръекций является сюръекцией.

Доказательство. Пусть оба отображения f : X ! Y и g : Y ! Z сюръективны. Докажем сюръективность композиции h : X ! Z h = g f. Так как f : X ! Y сюръекция, f(X) = Y ; так как g : Y ! Z сюръекция, g(Y ) = Z. Из этих равенств следует:

h(X) = g(f(X)) = g(Y ) = Z;

что доказывает сюръективность композиции h = g f. /

Утверждение 3. Композиция биекций является биекцией.

Доказательство следует из определения биективного отображения и утв. 1, 2.

4

		Обратное отображение
Начнем с	примера. Рассмотрим два отображения: f								:	R ! R	f(x) = 2x и
		x
g : R ! R g(x) =		2 . Найдем композиции g f и f g.
8 x 2 R g f(x) = g(f(x)) = g(2x) =					2x		= x		) g f = Id R;
					2
		x					x
8 x 2 R f g(x) = f(g(x)) = f				= 2				= x	) f g = Id R:
			2				2

Равенство обеих композиций тождественному отображению позволяет, как будет показано ниже, утверждать, что g является обратным отображением к отображению f и отображение f является обратным к g.

Некоторая трудность заключается в том, что композиция отображений не коммутативна и возможны такие ситуации:

g f = Id ;	f g 6= Id ;
либо	g f 6= Id :
f g = Id ;

Поэтому вводятся понятия левого обратного отображения, правого обратного отображения и просто обратного отображения.

Определим эти понятия и найдем необходимые и достаточные условия существования этих обратных отображений.

Определение 8. Отображение g : Y ! X называется левым обратным к

отображению f : X ! Y , если g f = Id X , т.е. 8 x 2 X g(f(x)) = x. /

Определение 9. Отображение g : Y ! X называется правым обратным к

отображению f : X ! Y , если f g = Id Y , т.е. 8 y 2 Y f(g(y)) = y. /

Утверждение 4. Для существования левого обратного отображения g : Y ! X к отображению f : X ! Y необходимо и достаточно, чтобы отображение f : X ! Y было инъекцией.

				9 левое обратное
f : X	!	Y
			()	g : Y	!	X
инъекция
				g f = Id X :

Доказательство. Пусть отображение f : X ! Y инъекция. Существование левого обратного отображения докажем конструктивно. Из определения инъективного отображения следует, что 8 y 2 f(X) существует и единственен элемент x 2 X такой, что y = f(x). Это позволяет 8 y 2 f(X) определить отображение g : f(X) ! X из условия: g(y) = x, т.е. g(f(x)) = x ) g f = Id X . Для остальных элементов y 2 (Y nf(X)) левое обратное отображение можно определить, например, так

8 y 2 (Y n f(X)) g(y) = x ; x 2 X;

выбор элемента x из множества X произволен. Построенное таким образом отображение g : Y ! X будет левым обратным к f : X ! Y , так как 8 x 2 X g f : X ! X

5

g f = Id X . Ясно, что левое обратное отображение не единственно, так как для разных элементов x будут получаться разные отображения, при том, что все они будут левыми обратными к исходному.

Пусть дано существование отображения: g f = Id X , g : Y ! X. Для доказательства инъективности f : X ! Y покажем, что из равенства f(x1) = f(x2) следует равенство x1 = x2.

8 x1; x2 2 X	f(x1) = f(x2) ) g(f(x1)) = g(f(x2)) ) g f(x1) = g f(x2) )
Id X (x1) = Id X (x2) ! x1 = x2: /
Пример	5. Пусть f : N ! N, f(x) = x + 1. Это отображение (называемое

отображением “следования”) инъективно, но не сюръективно, так как в число 1 2 N ни одно число из N не отображается. f(N) = N n f1g. Для y 2 f(N) определим обратное отображение g : f(N) ! N так, чтобы g(f(x)) = x, т.е. положим 8 y 2 f(N) g(y) = y 1. При таком выборе 8 x 2 N g f(x) = g(f(x)) = g(x + 1) = x + 1 1 = x, т.е. g f = Id X .

Для элемента y = 1, в который не перешел ни один элемент x 2 N, определим левое обратное отображение, например, так

g(1) = 5:

Число 5 здесь выбрано произвольно, на его месте может быть любое натуральное число. Отображение g : N ! N задано, так как 8 y 2 N указано правило, по которому ему ставится в соответствие элемент x 2 N. Как отмечалось, 8 x 2 N g f(x) = x, т.е. g f = Id X ) g : N ! N левое обратное отображение. Оно, очевидно, не единственно, поскольку элемент y = 1 можно отобразить любым образом на множество N и это не нарушит равенства: g f(x) = x 8 x 2 N. /

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

Утверждение 5. Для существования правого обратного отображения g : Y ! X к отображению f : X ! Y необходимо и достаточно, чтобы отображение f : X ! Y было сюръекцией.

f : X ! Y

9 правое обратное

сюръекция

() g : Y ! X f g = Id Y :

Доказательство. Пусть f : X ! Y сюръекция. Существование правого обратного отображения докажем конструктивно. Из сюръективности отображение f : X ! Y следует, что прообраз любого y 2 Y не пустое множество. Выберем любой элемент x 2 f 1(y) из прообраза f 1(y) элемента y 2 Y и положим:

g(y) = x :

Проделаем это для каждого элемента y 2 Y . Построенное таким образом отображение будет правым обратным к f : X ! Y , так как

8 y 2 Y f g(y) = f(g(y)) = f(x ) = y ) f g = Id Y :

6

Единственности правого обратного отображения может не быть, так как прообраз y 2 Y может содержать более одного элемента, в качестве x в указанном построении можно выбрать любой элемент прообраза y.

Пусть существует правое обратное отображение g : Y ! X, f g = Id Y . Докажем, что тогда отображение f : X ! Y сюръекция.

8 y 2 Y y = Id Y (y) = f g(y) = f(g(y)):

По определению отображения g : Y ! X g(y) = x; x 2 X. Это позволяет записать:

8 y 2 Y y = f g(y) = f(g(y)) = f(x); x 2 X:

Таким образом, доказано, что 8 y 2 Y 9 x 2 X такой, что y = f(x), т.е. отображение f : X ! Y сюръективно. /

Замечание 3. Из приведенного доказательства следует, что правое обратное отображение, если оно существует, может быть не единственно.

Определение 10. Отображение g : Y ! X называется обратным к отображению f : X ! Y , если оно является одновременно и левым и правым обратным к отображению f : X ! Y , т.е.

g f = Id X и f g = Id Y

()

g обратное к f:

/

Утверждение 6. Для существования обратного отображения g : Y ! X к отображению f : X ! Y необходимо и достаточно, чтобы отображение f : X ! Y было биекцией.

Доказательство непосредственно следует из определений биекции, обратного отображения и утверждений 5 и 4.

Замечание 4. Из утв. 6 следует, что для доказательства биективности отображения достаточно построить обратное к нему отображение.

Утверждение 7. Обратное отображение единственно.

Докажем утверждение от противного. Пусть для отображения f : X ! Y существуют два обратных отображения: g : Y ! X и g^ : Y ! X, т.е. для g : Y ! X выполняются равенства:

g f = Id X ; f g = Id Y ;

и для g^ : Y ! X выполняются равенства:

g^ f = Id X ; f g^ = Id Y :

Из определений композиции отображений и тождественных отображений Id X ; Id Y следует: Id X g = g; g^ Id Y = g:^ Ассоциативность композиции отображений и эти равенства позволяют доказать единственность обратного отображения:

g = Id X g = (^g f) g = g^ (f g) = g^ Id Y = g:^ /

7

Пример 6. Построим обратные отображения для отображений, изображенных на рис. 1 4. Отображение на рис. 1 сюръективно, но не инъективно, следовательно (утв. 5), для него существует правое обратное отображение. Например, его можно задать следующим образом:

g1(y1) = b; g1(y2) = d:

Отображение g1 : Y ! X удовлетворяет условию: 8 y 2 Y f g1 = Id Y , так как f(g1(y1)) = f(b) = y1, f(g1(y2)) = f(d) = y2. Единственности правого обратного отображения нет, так как, очевидно, его можно задать и другим образом:

g~1(y1) = a; g~1(y2) = d:

Для отображения на рис. 2 не существует ни левого обратного (так как оно не инъективно), ни правого обратного (так как оно не сюръективно), не существует, соответственно, никакого обратного отображения.

Для отображения на рис. 3, так как оно инъективно, существует и не единственно левое обратное отображение. Например, его можно задать следующим образом:

g3(y1) = a; g3(y2) = a; g3(y3) = b; g3(y4) = c; g3(y5) = d; g3(y6) = a:

При этом

g3(f(a)) = g3(y2) = a; g3(f(b)) = g3(y3) = b; g3(f(c)) = g3(y4) = c; g3(f(d)) = g3(y5) = d;

т.е. 8 x 2 X g3(f(x)) = x ) g3 f = Id X .

При этом в качестве значений g3(y1) и g3(y6) могут быть выбраны любые элементы множества X.

Отображение на рис. 4 биективно (взаимно однозначно), по утверждениям 6 и 7 для него существует и единственно обратное отображение g4 : Y ! X, которое задается следующим образом:

g4(y1) = b; g4(y2) = a; g4(y3) = c; g4(y4) = d;

при этом выполняются равенства: g4 f = Id X и f g4 = Id Y .

Утверждение 8. Если g : Y ! X обратное отображение к f : X ! Y , то f : X ! Y обратное к g : Y ! X.

Доказательство. Из того, что g обратное отображение к f следует: g f = Id X и f g = Id Y ) f левое обратное и правое обратное отображение к g ) f обратное отображение к g. /

Замечание 5. Далее для отображения, обратного к f, используется обозначение f 1. Из контекста обычно ясно, о чем идет речь, об обратном отображении или о прообразе элемента y 2 Y , поэтому использование (в силу традиций) одного обозначения не должно привести к двусмысленности. /

8

Утв. 8 в терминах этого обозначения формулируется следующим образом: отображение f является обратным к отображению f 1, т.е.

(f 1) 1 = f:

Утверждение 9. Отображение f 1 : Y ! X, обратное к биективному отображению f : X ! Y , биективно.

Доказательство. Из утв. 8 следует, что для f 1 существует обратное отображение: f, из утв. 6 следует, что отображение, имеющее обратное, является биекцией, следовательно, отображение f 1 биекция.

Утверждение 10. Пусть h : X ! Y и f : Y ! Z биективные отображения, для которых определена композиция, тогда

(f h) 1 = h 1 f 1:

Доказательство. По утв. 3 композиция биекций есть биекция, следовательно для отображения f h : X ! Z существует и единственно обратное отображение, удовлетворяющее равенствам:

(f h) 1 (f h) = Id X ;

(f h) (f h) 1 = Id Z :

Проверим, что эти равенства выполняются, если в качестве обратного отображения (f h) 1 взять отображение h 1 f 1.

Ассоциативность композиции отображений и определение тождественного отображения позволяют записать равенства:

(h 1 f 1) (f h) = h 1(f 1 f) h = h 1 h = Id X ; (f h) (h 1 f 1) = f (h h 1) f 1 = f f 1 = Id Z ;

из которых следует, что h 1 f 1 является обратным отображением. В силу единственности, другого обратного отображения для отображния f h : X ! Z не существует. /

Утверждение 11. Прообразы элементов y 2 Y при отображении f : X ! Y образуют разбиение множества X.

Доказательство. Надо доказать, что подмножества f 1(yi) (yi 2 Y ) попарно не пересекаются и что их объединение равно множеству X. Первое докажем от противного:

пусть для yi 6= yj (yi; yj 2 Y ) 9 x 2 (f 1(yi)) \ (f 1(yj)) ) f(x ) = yi и f(x ) = yj:

Выполнение этих равенств при yi 6= yj противоречит определению отображения f : X ! Y , поскольку нарушается единственность образа элемента x . Следовательно, прообразы не пересекаются.

y	Y		X =	f 1	(y)		f : X Y
				S		. Определения отображения	!	и прообраза
Докажем, что				y2Y
элемента 2
		(опр. 6) позволяют записать:
						[
8 x 2 X () x 2 f 1(y ); y 2 Y () x 2 f 1(y):								/

y2Y

9

В лекции 1 (опр. 7) было введено понятие фактор-множества и доказано, что любое разбиение множества задает на нем отношение эквивалентности (утв. 6). В утв. 11 настоящей лекции доказано, что прообразы элементов y 2 Y при отображении f : X ! Y образуют разбиение множества X. Обозначим X= фактор-множество множества X по отношению эквивалентности, определенному следующим образом:

8x1; x2 2 X x1 x2 () y = f(x1); x1; x2 2 f 1(y):

Класс эквивалентности Kx при этом является прообразом f 1(y) элемента y 2 Y; равного: y = f(x).

Отображение g : X ! X= 8x 2 X g(x) = Kx называется канонической проекцией X на фактор-множество X= . Это отображение сюръективно, так как классы эквивалентности Kx покрывают всё множество X и, следовательно, g(X) = X= .

Введем отображение

h : X= ! Y 8 Kx 2 X= h(Kx) = f(x);

которое каждому классу эквивалентности Kx 2 X= ставит в соответствие элемент y = f(x) y 2 Y , являющийся образом элемента x, задающего класс эквивалентности

Kx.

Отображение h : X= ! Y инъективно, так как для него очевидно выполнение условия инъективности (3): h(Kx1 ) = h(Kx2 ) ) f(x1) = f(x2) ) Kx1 = Kx2 :

Утверждение 12. Любое отображение f : X ! Y может быть разложено в композицию f = h g сюръективного отображения g : X ! X= 8x 2 X g(x) = Kx и инъективного отображения h : X= ! Y 8 Kx 2 X= h(Kx) = f(x):

Доказательство следует из определений отображений g и h, которые позволяют записать:

8x 2 X h g(x) = h(g(x)) = h(Kx) = f(x) ) h g = f: /

10