Akhmetova_Vodopyanov_-_Kurs_matana

б) из А В = А вытекает, что А				В;
в) из А В = В вытекает, что А				В.
2.	Доказать:
а) А (В С) = (А В) (А С);
б) А (В С) = (А В) (А С).
3.	Доказать включения:
а) (А С) (В D) (А В)			(С	D);
б) (В – С) – (В – А) А – С;
в) А – С (А – В) (В – С).
4.	Доказать: А В = (А В) – (А			В).
5.	Верны ли утверждения для любых множеств А, В, С: 1) если
А В и В С, то А С; 2) если А			В и В		С, то А С?
6.	При каких	условиях	на	А	и В выполняется	равенство
(А – В)	В = А.
7.	Пусть U =	{a, b, c, d,	e,	f}	– универсум, A =	{a, b, c},

B = {a, c, e, f}, C = {d, e, f}. Найти А – В, В – С, С – В, А – С, АC В,

ВАC, А С, С А.

8.Пусть А В = . Что можно сказать про множества А – В и

В– А.

9. Пусть А ВС = . Что можно сказать про множества А В и

АВ.

10.Доказать равенства:

а) (А – В) – С = (А – С) – (В – С);

б) (А – В) (В – С) (С – А) (А В С) = А В С; в) А – В = А – (А В) = (А В) – В;

г) А – (А – В) = А В;

д) А – (В С) = (А – В) (А – С); е) А – (В С) = (А – В) (А – С); ж) (А В) – С = (А – С) (В – С).

11.	Вытекает ли из А – В = С, что А = В С?
12.	Вытекает ли из А = В С, что А – В = С?
13.	Пусть А – заданное множество, про другое множество Х из-
вестно, что А Х = А. Доказать, что Х = .
14.	Доказать равенства:

а) А (В D) = (А В) D;

11

б) А	(В D) = (А В)	(А	D);
в) А А = ;
г) А	= А.
15.Доказать следующие тождества:
а) (А	В) (С D) = (А	С)	(В С) (А D) (В D);

б) (А В) А = (А В) А = А;

в) А – (В – С) = (А – В) (А С); г) А (В – С) = (А В) – (А С) = (А В) – С;

д) А В = А (В – А);
е) (АС)С = А;
ж) А АС = U;
з) А	АС =		;
и) [АС В] А = А В;
к) А (В-А) =				;
л) А – (В С) = (А – В) – С.
16.Доказать, что
а) (А В) С = А (В С)						А С;
б) А = В			А В =		;
в) А В = А В А = В;
г) (А В) – В = А А В = ;
д) (А – В) В = А В А;
е) (А В) С = А (В С)						С А;
ж) А В			А С В С;
з) А	В		А С В С;
и) А В (С-В) (С-А);
к) А В			ВС	АС;
л) А = В		С	А В= и А В = U.
17.Доказать тождества:
а) А В = А В (А В);
б) А – В = А – (А В);
в) А		= А;
г) А – А =			;
д) A	U = AC;
е) А В = (А В) – (А В);
18. Пусть A				U, B	U. Доказать:
а) A – B = A				BC;

12

б) A B = (A BC) (AC B).
19. Решить систему уравнений
	A	X	B,
а)	A	X	C,

где А, В, С – данные множества и В А С.
	A \ X	B,
б)	X \ A	C,

где А, В, С – данные множества и В				А , А С = .
	A \ X		B,
в)	X	A	C,
где А, В, С – данные множества и В				А С.
20. Определить операции ,				, \ через:
а)	и	;
б)	и	;

в) \ и .
21.	Доказать, что для любых множеств E, F, G, H справедливы
включения:
а) E (F G)			(E	F)	(E G);
б) E		(F – G)	(F	E) – (G		E);
в) (E		F) (G	H)	(E	G)	(F	H);
г) (E		F) – (G	H)	[E	(F – H)]		[(E – G)		(F	H)];
д) E (F G)			(E	F)	(E G);
е) (F E) (G			H)	(G E) (F H).
22.	Справедливо ли равенство
			(А В) (С D) = (А					С)	(В	D)?
23.	Справедливо ли равенство
			(А В) (С D) = (А					С)	(В	D)?

3. Произведение множеств. Бинарные отношения. Отношение эквивалентности

Пусть А и В – множества.

Определение. Произведением множеств А и В называется множество всех упорядоченных пар (а, b), где а А и b В. Произведение обозначается А В.

13

А В = {(a, b): a A и b B}.

Произведение двух множеств часто называют прямым или декартовым произведением. Заметим, что произведение n штук одного и того же множества А обозначается через Аn .

Примеры. 1) Если А = {a, b}, B = {0, 1}, C = , то А В = {(a, 0), (a, 1), (b, 0), (b, 1)}, B A = {(0, a) (0, b), (1, a), (1, b)},

A C = C A = .

2)Пусть R – множество действительных чисел. Тогда R2 – мно-

жество, которое обычно изображается в виде плоскости, а элементы из R2 называются точками плоскости.

3)Пусть [a, b], [c, d] – отрезки прямой. Тогда [a, b] [c, d] – прямоугольник на плоскости.

Определение. Бинарным отношением (или просто отношени-

ем) в А В называется любое подмножество множества А В.

Примеры. 1) Пусть А = {1, 2, 3}, B = {1, 2, 3, 4, 5, 6, 7}. Тогда

A B = {(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (2,1), (2,2), (2,3), (2,4), (2,5), (2,6), (2,7), (3,1), (3,2), (3,3), (3,4), (3,5), (3,6), (3,7)}.

Возьмем S = {(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (2,2), (2,4), (2,6), (3,3), (3,6)}. Ясно, что S A B, т.е. S является бинарным отношением в A B. Это отношение может быть охарактеризовано следующей формой

S = {(x, y) A B: x A является делителем y B}.

2) Пусть А некоторое множество, а b(А) множество всех его подмножеств. Множество b(А) называется булеаном. Пусть W отношение в b(А) b(А), задаваемое формой:

W = {(B, C) b(A) b(A): B C}.

Тогда W является отношением включения множеств.

Если S является некоторым отношением и (x, y) S, то мы будем писать xSy и говорить, что x находится в отношении S с y.

Если S является отношением в А А, то говорят, что S является отношением в А.

Пусть S некоторое отношение в А В. Введем два множества:

DS = {a A: b B: (a, b) S},

14

RS = {b B: a A: (a, b) S}.

Множество DS называется областью определения отношения, а множество RS – областью значений. Если DS = A, то такое отношение называют всюду определенным, а если RS = B – сюръективным. Когда отношение одновременно является сюръективным и всюду определенным, то говорят, что S отношение на А В (соответственно на А, если В = А).

Отношение S называется инъективным, если из (a, b) S и (c, b) S следует, что а = с.

Иногда отношения называются соответствием между элементами множества А и В.

Пусть S некоторое отношение в А В. Введем отношение S-1 следующим образом: (у, х) S-1 (х, у) S. Отношение S-1 назовем об-

ратным отношением.

Определение. Отношение S на множестве А называется отношением эквивалентности, если оно удовлетворяет следующим условиям:

1) аSа для а А (рефлексивность);

2)если аSв, то вSа (симметричность);

3)если аSв и вSс, то аSс (транзитивность).

В дальнейшем отношение эквивалентности будем обозначать значком .

Определение. Пусть задано отношение эквивалентности на А. Множество Х А называется классом эквивалентности для этого отношения, если оно удовлетворяет следующим условиям:

1)	для любых х	Х и у	Х выполняется х у;
2)	если х Х , у	А и х	у, то у Х.

Пусть на А задано отношение эквивалентности. Введем следующее обозначение:

[x] = {y A: x y}.

Нетрудно видеть из определений, что [x] является классом экви-

валентности. Его называют классом эквивалентности, порожденным элементом х.

Лемма 1. Для классов эквивалентности [x] и [y] возможны только следующие два случая:

15

1)	[x] = [y];
2)	[x] [y] = .
Доказательство. Предположим, что [x] [y]		и а [x] [y]. То-
гда x	a и y a. Покажем, что в этом случае один класс эквивалент-

ности содержится в другом, а так как они равнозначны, то будет доказано равенство этих классов.

Пусть в	[x]. Тогда х	в, а х, следовательно в	а. Но а y, зна-
чит в y и в	[y], т.е. [x] [y].
Пусть некоторое множество А представимо в виде:
	А =	А, где А А = , если	.

В этом случае говорят, что {A } задает разбиение А. Из доказанной леммы вытекает, что классы эквивалентности задают разбиение на А. Оказывается, верно и обратное.

Лемма 2. Если {A } – некоторое разбиение множества А, то отношение S, определяемое следующим условием: аSв : а Аи в А , является отношением эквивалентности.

Доказательство. По существу, в доказательстве нуждается лишь третье свойство эквивалентности. Пусть аSв и вSс. Тогда из за-

дания отношения S вытекает следующее:				: а	А	и в А , а также
: в	А и с А	. Тогда в А	А и из свойств разбиения следует,
что А	= А или	= , следовательно, а А		и с	А	. Это доказывает,

что аSс и отношение S является отношением эквивалентности. Теорема. Пусть S – некоторое отношение эквивалентности на А.

Пусть {А } – разбиение множества А, порожденное этим отношением (лемма 1). Пусть Т – отношение эквивалентности, порожденное разбиением {А } (лемма 2). Тогда S = T.

Доказательство. Для доказательства напомним, что S и T являются подмножеством А А и их равенство понимается как равенство множеств. Пусть (а,в) S, т.е. аSв. Тогда а и в из одного класса эквивалентности, т.е. : а А и в А . Это означает, что (а,в) T и S T. Аналогично показывается обратное включение.

Задачи.

1. Доказать, что существуют А, В и С такие, что а) А В В А; б) А (В С) (А В) С.

2. Доказать, что если А, В, С и D не пусты, то

16

а) А В и С D А С В D;

б) А = В и С = D A C = B D.

3. Доказать, что

а)(А В)	(С	D) = (А	С)	(В	D);
б)(А В)	(C	D) (A	C)	(B	D);

в)(А В) С = (А С) (В С); г)А (В С) = (А В) (А С);

д)(А В) (C D) = (A C) (B C) (A D) (B D);

е)(А–В) С = (А С) – (В С); ж)А (В–С) = (А В) – (А С);

з)А В = (A D)	(C B), где А С и B D.
4. Найти область определения и область значений для отноше-
ний:
а) R={(x, y): x, y	N и x делит y};
б) R={(x, y): x, y	N и y делит x};
в) R={(x, y): x, y	R и x + y 0};
г) R={(x, y): x, y	R и 2x > 3y}.

5. Пусть S отношение в А В, а R – в В С. Через SoR (суперпозиция отношений) обозначается отношение в А С, опреде-

ляемое равенством SoR = {(x, y) A C: z B: (x, z) S и (z, y) R}.

Пусть R, S, T – некоторые отношения. Проверить справедливость равенств:

а) Ro(SoT) = (RoS)oT; б) (R-1)-1 = R;

в) (RoS)-1 = S-1oR-1.

6. Пусть на множестве А заданы отношения R1 и R2. Доказать:

а) если отношения R1 и R2 рефлексивны, то рефлексивны отно-

шения R1 R2, R1 R2, R1-1, R1oR2;

б) если отношения R1 и R2 иррефлексивны (т.е. для х А не выполняется хRх), то иррефлексивны R1 R2, R1 R2, R1-1, суперпозиция R1оR2 может быть иррефлексивной;

в) если отношения R1 и R2 симметричны, то симметричны отно-

шения R1 R2, R1 R2, R1-1, R1oR2-1;

г) отношение R1oR2, где R1 и R2 симметричны, симметрично тогда и только тогда, когда R1oR2 = R2oR1;

17

д) если отношения R1 и R2 антисимметричны, то антисимметричны R1 R2, R1-1.

7. Пусть А ‒ конечное множество, n – число его элементов. Доказать, что число подмножеств множества А, состоящих из m элементов, где 0 m n, равно

	m	n!
	Cn			.
		m!(n m)!

8. Пусть r – отношение, обладающее свойством рефлексивности и транзитивности в множестве А. Определим для а, b А отношение R, полагая аRb, если аrb и brа.

а) Доказать, что R есть отношение эквивалентности на А. в) Доказать, что если аRа', bRb' и аrb, то а'rb'.

9. Во множестве Z+ Z+ положим по определению (а, b)r(с, d), если а+d=b+с. Доказать, что r является отношением эквивалентности на данном множестве.

«Понятие функции такое же основное, как и понятие множества» Хаусдорф

4. Функция

Пусть Х и У два множества и F отношение в Х У. Определение. Отношение F называется функцией из Х в У, если

оно удовлетворяет свойству:

из xFy и xFz следует, что y = z.

В дальнейшем мы будем применять также обозначение y = F(x) вместо xFy, если F является функцией. Множества DF и RF , введенные в предыдущем пункте для функции F носят соответственно на-

звания: DF – область определения и RF – область значений функции

F. Очень часто область определения и область значений заранее не задаются, а возникают, исходя из задания функции.

Примеры.

1){(1,2), (2,2), (Рузвельт, Черчилль)};

2){(1,2), (1,3), (2,2)};

3){(x, x2 + x + 1)|x R};

18

4) {(x2, x)|x R}.

Из приведенных примеров 1 и 3 определяют функцию, а 2 и 4 не являются функцией, так как не выполнено определение функции.

Для функции применяются также другие названия: преобразование, отображение, соответствие. Если y = F(x), то x называют аргу-

ментом функции, а y образом.

Две функции F и G считаются равными, если выполнены равенства соответствующих множеств. Последнее эквивалентно следующим двум равенствам:

DF = DG и F(x) = G(x) для x DF.

Следующие определения переносятся с отношений:

1) В случае, когда DF = Х функцию называют всюду определен-

ной.

2)Функция F из Х в У называется сюръекцией (или отображе-

нием на), если RF = У.

3)Функция F из Х в У называется инъекцией (или однозначным

отображением), если из х1 х2 следует, что F(х1) F(х2).

Всюду определенная функция F из Х в У называется биекцией, если она одновременно является сюръекцией и инъекцией.

Примеры: 1) функция у = еx – биекция из R в R+ ;

2) у = х2 – сюръекция из [-1, 1] на [0, 1], не являющаяся инъекци-

ей.

Определение. Пусть F – функция из X в Y, а G – из Y в Z. Суперпозицией функций F и G называется такая функция H из X в Z, что z = H(x) (т.е. (x, z) H X Z) тогда и только тогда, когда y = F(x) и z = G(y). Суперпозиция обозначается GoF.

Определение. Для функции F из Х в У функция G из У в Х на-

зывается правой обратной (соответственно, левой обратной), если справедливо равенство FoG=IУ (соответственно, GoF=IХ), где через IХ (IУ) обозначено тождественное отображение на Х (соответственно на У), т.е. IХ(x) = x (IУ(y) = y).

	Функция у = х2, из рассмотренного выше примера не имеет ле-
вой	обратной, но имеет правую обратную (ею является функция
х =
		y	). Однако если сузить область определения функции у = х2 до

отрезка [0,1] (или [-1,0]), оставив без изменений область значений, то

19

эта функция будет иметь уже и левую обратную: х = y (соответственно, х = - y ).

Лемма 1. Если функция F имеет левую обратную, то F является инъекцией.

Доказательство. Действительно, если бы F не являлась инъекцией, то существовали бы х1 х2 такие, что y = F(x1) = F(x2). Пусть G – левая обратная к F, то x1 = GoF(x1) = G(y) = GoF(x2) = x2, что противоречит предположению.

Лемма 2. Если функция F имеет правую обратную, то F является сюръекцией.

Доказательство. Утверждение легко вытекает из определения правой обратной функции G: для любого у У FoG(у) = у.

Лемма 3. Если у функции F из Х в У существуют левая и правая обратная функции, то они совпадают.

Доказательство. Пусть G и H – обозначают соответственно левую и правую обратную функции к F. Тогда DG = RF = DH = У. Остается проверить равенство G(y) = H(y) для любого y У. Но

G(y) = G(IУ(y)) = G(F(H(y))) = IХ(H(y)) = H(y).

Определение. Функция из У в Х, которая является правой и левой обратной к функции F, называется обратной функцией к F и обозначается через F -1.

Теорема. Пусть F является функцией из Х в У. Для существования обратной функции F-1 из У в Х необходимо и достаточно, чтобы F была биекцией.

Необходимость легко вытекает из лемм 1 и 2.

Достаточность. Пусть y У. Так как F является сюръекцией, то существует х Х такое, что F(x) = y. При этом такое х одно, так как F также и инъекция. Определим функцию G(x) = y. Легко проверить, что таким образом определенная функция является обратной к F.

Следствие. Если F является биекцией, то и F-1 также является биекцией.

Задачи.

1. Установить, что следующие отношения являются функцией:

а) в У, R = X	{в}	X У (постоянное отображение);
б) R = {(x, x): x	X}	X	X (тождественное отображение IX);
в) R = {((x, y), x)} (X			Y) X (проекция на Х);

20