Введение в теорию множеств и комбинаторику

Практическая работа № 8. Отображения. Виды отображений

Вопросы к работе

1. Что такое «отображение множества в множество»?
2. Что такое «образ», что такое «прообраз» при данном отображении?
3. Что такое полный f - образ, что такое полный f - прообраз, при отображении f ?
4. Назовите типы отображений, дайте их определения и приведите примеры.
5. Какие два множества называются эквивалентными? Приведите примеры.
6. Какое множество называется счетным? Приведите примеры.

Образцы решения заданий

Пример 1. Пусть А = {1; 2; 3; 4; 5; 6; 7; 8; 9} N и В ={0; 1} Z Поставим в соответствие каждому числу x A его остаток при делении на 2.

Является ли это соответствие отображением? Какой тип у этого отображения? Какой элемент является образом элемента 6, 7? Найдем полный прообраз элемента 1.

Решение. Изобразим заданное соответствие с помощью графа:

Видим, что:

1) каждый элемент множества А , является точкой исхода;

2) у каждой точки исхода, имеется только по одной точке прибытия. (Значит, указанное соответствие является отображением множества А в множество В);

3) Каждый элемент множества В является точкой прибытия. (Значит, это отображение «на»).

Так как в множестве В есть элемент (например, 0), для которого прообразом является ни один элемент из А , то это отображение не является взаимооднозначным.

Образом числа 6 является число 0 В , образом числа 7 – число 1 В . Полный прообраз числа 1 В есть множество чисел {1; 3; 5; 7; 9} А .

Пример 2. Пусть Х – множество треугольников плоскости, Y = R. Выберем единицу измерения длин и сопоставим каждому треугольнику число – периметр этого треугольника. Будет ли это соответствие отображением? Какой тип у заданного отображения? Каков полный прообраз числа у R ?

Решение. Каждый треугольник на плоскости имеет однозначно определенный периметр. Поэтому каждому треугольнику из множества Х сопоставляется единственное число из R , т. е. это соответствие является отображение Х в R . При этом у двух разных треугольников может быть одинаковый периметр. Другими словами, отображение не является взаимооднозначным. Кроме того, не существует треугольника, периметр которого равен отрицательному числу, т.е. отображение не является отображением «на». Пусть у R . Тогда:

1. у > 0, полный образ – множество всех треугольников плоскости, периметр которых равняется числу у , это множество бесконечное.
2. у ≤ 0, полный образ – пустое множество.

Пример 3. Х = {0; 1; 2; 3; 4} N , Y = Z. Отображение f множества Х в множество Y задано следующим образом:

Определим тип этого отображения и построим его график.

Решение. Для каждого x X найдем образ y Y. Соответствующие результаты запишем в таблицу:

y=f(x)	–2

Множество значений отображения f есть множество

A = {–2; 1; 4; 7; 10} Y и В ≠ Y . У каждого элемента y В в Х имеется только по одному прообразу. Мы имеем, следовательно, отображение взаимооднозначное множества Х в множество Y .

Пары значений (x ; у ) из таблицы образует график данного отображения f: Х→Y . В прямоугольной системе координат этот график имеет вид:

Пример 4. Даны два множества слов: Х = {красный; синий; зеленый; желтый} и Y = {галстук; свет; платок; лист}. Эквивалентны ли эти множества?

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

Например:

Пример 5. Даны множества: А = { x | x = 2 n , n N } и

В = { x | x = , n N }. Эквивалентны ли эти множества?

Решение. Эти множества эквивалентны, т. к. можно подобрать взаимооднозначное отображение множества A на множество В .

Например: f: А В

x = 2 n y = .

Упражнения

1. Между множеством имя Х = {Андрей; Борис; Михаил; Алексей; Константин; Василий; Валентина; Клара; Семен; Мария; Софья; Олег; Трофим4 Юрий; Яков} и множеством Y (букв русского алфавита) установлено соответствие, при котором каждому имени сопоставляется его первая буква. Будет ли это соответствие отображением Х в Y ? Если "да", то какого типа? Найдите образ множества Х . Найдите полные прообразы букв А , Б, К, Л. Постройте граф указанного соответствия.

2. Каждой точке М отрезка АВ поставим в соответствие ее проекцию М на данную прямую L . Будет ли это соответствие отображением? Каким? Опишите область определения, область значений этого отображения.

3. Множество Х состоит из всех квадратов на плоскости, а множество Y из всех окружностей на той же плоскости. Поставим в соответствие каждому квадрату вписанную в него окружность. Является ли это соответствие отображением Х на Y ?

4. Можно ли задать отображение следующим образом: множество А из отрезков, на Y – из треугольников; каждому отрезку ставится в соответствие треугольник, для которого этот отрезок является средней линией?

5. Верно ли, что соответствие f: Z Z

X у = –5 х + 2

есть отображение "на"?

6. Пусть Х – множество вещественных чисел. Каждому числу х Х поставим в соответствие его квадрат. Можно ли это соответствие назвать обратимым отображением?

7. Покажите, что следующие множества счетны:

а) множество нечетных натуральных чисел;

б) множество неотрицательных целых чисел;

в) множество квадратов натуральных чисел;

г) множество натуральных чисел, кратных 5;

д) множество кубов натуральных чисел.

8. Даны два множества: A = {Париж; Москва; Варшава; Краков; Лондон; Саранск; Владимир; Марсель} и B = {Франция; Россия; Англия; Польша; Швеция; Австрия}. Зададим соответствие между ними: «город x A находится в стране ». Построим графики этого соответствия. Будет ли это соответствие отображением? Какого типа?

9. Эквивалентны ли множества А изображений населенных пунктов на карте и множество B населенных пунктов местности, изображенной на карте?

Индивидуальное задание

1. Среди указанных соответствий выбрать отображения. Указать их тип, построить график.

2. Изобразите в прямоугольной декартовой системе координат графики следующих отношений в Z . Для каждого отношения выясните, является ли оно отображением Z в Z , отображением Z на Z , взаимооднозначным отображением, наложением:

1) х + у = 3; 7) у < х + 2;

2) х – у ≤ 5; 8) у ≤ х + 2;

3) х + у = 4, x > 0; 9) у = 4;

4) x = y , – 4 ≤ х ≤ 6; 10) ху = 24, –6 ≤ х ≤ 6.

5) = у , – 4 ≤ х ≤ 6;

6) x > у ;

Задания для самоконтроля

Соедините следующие пары множеств знаком «=», если они равны, и знаком «~», если они эквивалентны:

1) А – множество сторон треугольника,

В - множество углов треугольника;

2) А - множество букв в слове «колос»,

В = {о; к; с; л};

3) А – множество колец на пне дерева,

В – множество лет, прожитым деревом;

4) множество материков на Земле и множество государств

Отображение %%f%% называется инъективным ,

если для любых элементов %%x_1, x_2 \in X%%, %%x_1 \neq x_2%%, следует, что %%f(x_1) \neq f(x_2)%%. $$ \forall x_1, x_2 \in X~~x_1 \neq x_2 \rightarrow f(x_1) \neq f(x_2). $$

Другими словами, отображение %%f%% инъективно, если образы различных элементов из %%X%% также различны.

Пример

Функция %%f(x) = x^2%%, определенная на множестве %%\mathbb{R}%%, не является инъективной, так как при %%x_1 = -1, x_2 = 1%% получаем одно и тоже значение функции %%f(x_1) = f(x_2) = 1%%.

Сюръективное отображение

Отображение %%f%% называется сюръективным , если для всякого элемента %%y \in Y%% существует элемент %%x \in X%% с условием, что %%f(x) = y%%. $$ \forall y \in Y~\exists x \in X: f(x) = y. $$

Другими словами, отображение %%f%% сюръективно, если каждый элемент %%y \in Y%% является образом хотя бы одного элемента %%x \in X%%.

Пример

Отображение %%f(x) = \sin(x)%%, определенное на множестве %%\mathbb R%%, с множеством %%Y = [-2,2]%% не является сюръективным, т.к. для элемента %%y = 2 \in Y%% нельзя найти прообраз %%x \in X%%.

Биективное отображение

Отображение %%f%% называется биективным , если оно инъективно и сюръективно. Биективное отображение также называется взаимно однозначным или преобразованием .

Обычно, словосочетания «инъективное отображение», «сюрьективное отображение» и «биективно отображение» заменяют на «инъекция», «сюръекция» и «биекция» соответственно.

Обратное отображение

Пусть %%f: X \to Y%% — некоторая биекция и пусть %%y \in Y%%. Обозначим через %%f^{-1}(y)%% единственный элемент %%x \in X%% такой, что %%f(x) = y%%. Тем самым мы определим некоторое новое отображение %%g: Y \to X%%, которое снова является биекцией. Ее называют обратным отображением .

Пример

Пусть %%X, Y = \mathbb R%% — множество действительных чисел. Функция %%f%% задана формулой %%y = 3x + 3%%. Имеет ли данная функция обратную? Если да, то какую?

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

1. Проверим инъекцию. Пусть %%x_1 \neq x_2%%. Проверим, что %%f(x_1) \neq f(x_2)%%, то есть %%3 x_1 + 3 \neq 3 x_2 + 3%%. Предположим противное, %%3 x_1 + 3 = 3 x_2 + 3%%. Тогда получается, что %%x_1 = x_2%%. Получили противоречие, т.к. %%x_1 \neq x_2%%. Следовательно, %%f%% — инъекция.
2. Проверим сюръекцию . Пусть %%y \in Y = \mathbb{R}%%. Найдем элемент %%x \in X = \mathbb{R}%% c условием, что %%f(x) = y%%, то есть %%3x + 3 = y%%. В данном равенстве задан элемент %%y \in \mathbb{R}%% и нужно найти элемент %%x%%. Очевидно, что $$ x = \frac{y-3}{3} \text{ и } x \in \mathbb R $$ Следовательно, отображение %%f%% сюръективно.

Так как %%f%% — инъекция и сюръекция, то %%f%% — биекция. И, соответственно, обратным отображением является %%x = \frac{y-3}{3}%%.

Большую роль в математике имеет установление связей между двумя множествами и , связанное с рассмотрением пар объектов, образованных из элементов первого множества и соответствующих элементов второго множества. Особое значение при этом имеет отображение множеств.

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

Тот факт, что f есть отображение , кратко записывают в виде: .

Применяют также обозначение . Чаще отображения обозначают буквами f , q , F .

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

Если при этом элементу х из Х сопоставлен элемент из Y , то называют образом элементах , а х – прообразом элемента при отображении , что записывается в виде .

Из определения отображения следует, что у каждого элемента из Х образ единственный, однако для элемента прообразов может быть много, а может и вообще не быть. Множество всех прообразов элемента называется его полным прообразом и обозначается через . Таким образом, .

Естественным путем определяются образ подмножества из А и прообраз подмножества из В при отображении :

Например , пусть и - отображение А в А , сопоставляющее каждому элементу а из А остаток от деления а на число 4. Тогда имеем:

В зависимости от свойств, образов и прообразов различают отображения сюръективные, инъективные и биективные.

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

Отображение называется инъективным , если разные элементы множества Х отображаются в разные элементы множества т.е. , или является либо пустым, либо одноэлементным множеством при любом . Инъективные отображения называются также вложениями .

Отображение называется биективным , или взаимно однозначным отображением на , если оно сюръективно и инъективно, т.е. если есть одноэлементное множество при любом . В этом случае можно определить отображения , положив для любого : . Оно называетсяобратным к и обозначается в виде .

Изобразим для наглядности виды отображений.

Сюръективное Инъективное Биективное

Рисунок 12

Отображение множества А в себя называется преобразованием множества А . Биективное преобразование множества А называется подстановкой множества А .

Примером подстановки множества целых чисел может служить отображение , определенное равенством .

Заметим еще, что отображение множества А в В называют также функцией , заданной на множестве А со значениями в множестве В . При этом элемент называют значением функции точке а . Само множество А называют областью определения функции , а множество - областью значений функции .

Функцию зачастую трактуют как переменную величину , принимающую значения из В и так зависящую от переменной величины х , принимающей значения из А , что каждому значению а переменной величины х соответствует вполне определенное значение величины . При этом пишут и вместо «функция » говорят «функция ».

Рассмотрим различные отображения и определим их виды .

1) Пусть Х – множество окружностей на плоскости. Сопоставляя каждой окружности ее центр, получим отображение Х на . Это отображение не является инъективным, поскольку одна и та же точка может быть центром бесконечного множества окружностей. Но оно сюръективно, так как любая точка – центр некоторой окружности. Поэтому обратное соответствие всюду определено, сюръективно, но не функционально.

2) Соответствие является числовой функцией заданной на всем множестве действительных чисел. Множеством значений этой функции является совокупность неотрицательных чисел. Так как , то функция не сюръективна. Она и не инъективна, так как . Поэтому она не имеет обратной функции.

3) Отображение сюръективно и инъективно: для любого есть одно и только одно число такое, что . Этим числом является .

4) Отображение ( - множество неотрицательных чисел) множества в себя всюду определено, инъективно, но не сюръективно. Действительно, для дроби , выполнено .

Поэтому множеством значений этой функции является промежуток . Обратная функция определена на этом промежутке и принимает неотрицательные значения.

5) Отображение , определенное правилом является инъективным отображением. Оно не является биективным, поскольку . Однако, если таким же образом определить отображение в , то получим биективное отображение. . ; из сюръективности следует сюръективность лишь , а из инъективности следует инъективность лишь .

3. Если и - преобразования множества А , то их композиция также является преобразованием множества А .

ОТОБРАЖЕНИЯ МНОЖЕСТВ §1. Основные определения

Определение. Пусть А и В – два множества. Говорят, что задано отображение f множества А в В, если указан закон, по которому любому элементу а из А ставится в соответствие единственный элементb из множества В:

Отображения также называют функциями .

Будем использовать следующие обозначения:

ƒ : А→ В. Отображение f множество А переводит в В;

А f В. Множество А отображается в В при отображении f.

Если элемент а при отображении f переходит в элемент b, то пишут f(a)=b (левая запись) или af=b (правая запись). Элемент b называется образом элемента а при отображении f; элемент а – прообразом b при

этом отображении. Множество { f (a ) | a A } = f (A ) – образ множества А при отображении f. Отметим, что

f (A ) B .

А B

f f(A)

А – область определения отображения f; В – область значений отображения f (иногда –например, в школьной математике – областью значений считается f(A), но мы будем ею считать В).

Отметим, что мы рассматриваем только однозначные отображения.

Из всех отображений особо выделяют следующие виды :

1. Сюръекция (отображение «на») – это отображение f : A → B такое, что f (A ) = B . При сюръекции у каждого элемента из множества В существует хотя бы один прообраз.

2. Инъекция – отображение, при котором разные элементы переходят в разные, т.е. если a , a 1 A и a ≠ a 1 , то f (a ) ≠ f (a 1 ) .

				f(a1 )

3. Биекция, или взаимно однозначное отображение – это отображение, которое одновременно является инъекцией и сюръекцией.

Примеры отображений:.

1. Пусть А – любое множество и В – множество, состоящее из одного элемента, т.е. B={b}.

А . b

Отображение f (a ) = b , a A является сюръекцией, т.к. f(A)=B.

2. Пусть множество А – некоторый отрезок на плоскости, множество В – прямая. Из каждой точки отрезка А опустим перпендикуляр на прямую В и основания этих перпендикуляров поставим в соответствие точкам отрезка А.

А а

φ(а) В

Обозначим это отображение через φ. Очевидно,

ϕ (a ) ≠ ϕ (a 1 ), a , a 1 A , a ≠ a 1 .

Следовательно, отображение φ – инъекция (но не является сюръекцией).

3. Пусть множество А – гипотенуза прямоугольного треугольника, а В – его катет. Любой точке гипотенузы поставим в соответствие её проекцию на катет. Получим взаимно однозначное отображение А на В:

т.е. f – биекция.

Отметим, что именно так в математике доказывается, что «количество» точек на гипотенузе и катете одинаково (точнее, эти множества имеют одинаковую мощность).

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

4. Если f – любая функция действительного переменного, то f – отображение R в R.

§2. Умножение отображений

Пусть А, В, С – три множества и заданы два отображения f : A → B и ϕ : B → C .

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

ϕ f

Возможны два варианта записи.

1. Левая запись.
ƒ (a)=b, ϕ (b)=c.		обозначить ϕ f :
Тогда произведение f и φ будет	переводить а в с, его следует
(ϕ f ) (a ) = ϕ (f (a ) ) = ϕ (b ) = c , ϕ f : A → C (см. выше рисунок).
По определению (ϕ f ) (a ) = ϕ (f (a ) ) ,	т.е. произведение отображений –	это сложная функция,
заданная на А.

2. Правая запись.

aƒ =b, bϕ =c. Тогда a (f ϕ ) = (af ) ϕ = b ϕ = c ,

f ϕ : A → C.

Мы будем пользоваться левой записью (отметим, что в книге используется правая). Произведение отображений ниже мы будем обозначать через f ϕ .

Замечание 1 . Из определения умножения отображений следует, что перемножать можно не любые отображения, а только те, у которых «средние» множества одинаковые. Например, если f : A → B ,ϕ : D → C , то при В=D можно перемножать отображения f и φ, а при В≠D нельзя.

Свойства умножения отображений

Определение 2 . Отображения f и g называются равными , если у них совпадают области определения и области значений, т.е. f : A → B , g : A → B и выполняется условие: a A справедливо

равенство f (a ) = g (a ) .

1. Умножение отображений некоммутативно. Другими словами, если fφ и φf существуют, то они не обязательно равны.

Пусть, например, множества A=B=C=R, f (x ) = sin x ,ϕ (x ) Рассмотрим произведения:

(ϕ f ) (x ) = ϕ (f (x )) = ϕ (sin x ) = e sin x ,

(f ϕ ) (x ) = f (ϕ (x )) = f (e x ) = sin(e x ).

Следовательно, функции fφ и φf различны.

2. Умножение отображений ассоциативно.

Пусть f : A → B , ϕ : B → C , ψ : C → D . Докажем, что (ψϕ ) f

E x , f : R → R, ϕ : R → R .

и ψ (ϕ f ) существуют и равны,т.е.(ψϕ ) f =

ψ (ϕ f ) . (1)

Очевидно, что (ψϕ ) f : A → D ,ψ (ϕ f ) : A → D .

Для доказательства равенства (1) в силу определения равенства отображений требуется проверить, чтоa A : ((ψϕ ) f ) (a ) = (ψ (ϕ f )) (a ) (2). Пользуясь определением умножения отображений (в левой записи)

((ψϕ )f )(a ) = (ψϕ )(f (a ) )= ψ (ϕ (f (a ) )),

(ψ (ϕ f ))(a ) = ψ ((ϕ f )(a ) )= ψ (ϕ (f (a ) )). (4)

Т.к. в равенствах (3) и (4) равны правые части, то равны и левые, т.е. справедливо равенство (2), а тогда выполняется и (1).

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

несколько прообразов в А, либо вообще не быть прообразов. Однако для биективного отображения f обратное определить можно.

Пусть f : A → B – биекция, f (a ) = b , a A , b B . Тогда для любого элемента b B по определению биекции существует единственный прообраз при отображении f – это элемент а. Теперь можно определить f − 1 : B → A , полагая f − 1 (b ) = a (b B ) . Нетрудно видеть, что f − 1 – биекция.

Итак, у всякого биективного отображения имеется обратное.

§3. Преобразования множеств

Всякое отображение f : A → A называется преобразованием множества А. В частности, любая

функция действительной переменной является преобразованием множества R.

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

Так как преобразования – это частный случай отображений, то для них справедливо всё сказанное выше об отображениях. Но умножение преобразований множества А имеет и специфические свойства:

1. для любых преобразований f и φ множества А произведения fφ и φf существуют;

2. существует тождественное преобразование множества А ε : ε (a ) = a , a A .

Нетрудно видеть, что для любого преобразования f этого множества f ε = ε f = f , так как, например, (f ε ) (a ) = f (ε (a ) ) = f (a ) . Значит, преобразование ε играет роль единичного элемента при умножении преобразований.

равенства легко проверяются. Тем самым обратное преобразование играет роль обратного элемента при умножении преобразований.

Пусть $X$ и $Y$ - два произвольных множества.

Определение. Соответствие, при котором каждому из элементов множества $X$ сопоставялется единственный элемент из множества $Y$, называется отображением .

Обозначение отображения из множества $X$ в множество $Y$: $X \stackrel{f}{\longrightarrow} Y$.

Множество $X$ называется областью определения отображения и обозначается $X=D(f)$.

$E(f)$ называется множеством значений отображения, и $E(f) = \{ y \in Y \; | \; \exists x \in X, y = f(x) \}$.

Множество $\Gamma(f)$ называется графиком отображения. $\Gamma(f)=\{(x,y) \in X \times Y, y=f(x), \forall x \in X, y \in Y \}$.

Пусть $f$ - некоторое отображение из множества $X$ в множество $Y$. Если $x$ при этом отображении сопоставляется $y$, то $y=f(x)$. При этом $y$ называется образом $x$, или значением отображения $f$ в точке $x$. А $x$, соответственно, прообразом элемента $y$.

Исходя из определения отображения, видно, что не требуется, чтобы все элементы в множестве $Y$ являлись образами какого-либо $x$ и при том единственного.

Пример.

Даны два множества $X=\{ с, е, н, т, я, б, р, ь \}$ и $Y=\{ 1, 2, 3, 4, 5, 9, 10, 11 \}$

Отображение из множества $X$ в множество $Y$ имеет следующий вид:

$\begin{matrix} \{ с, & е, & н, & т, & я, & б, & р, & ь \} \\ \;\; \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow \;\; \\ \{ 1, & 2, & 3, & 4, & 5, & 9, & 10, & 11 \} \end{matrix}$

Определение. Совокупность всех элементов из множества $X$, образом которых является $y$ из $Y$, назвается полным прообразом $y$ из $X$. Обозначается: $f^{-1}(y)$.

Определение. Пусть $A \subset X$. Совокупность всех элементов $f(a)$, $a \in A$, называется полным образом множества $A$ при отображении $f$.

Определение. Пусть $B \subset Y$. Множество всех элементов из $X$, образы которых принадлежат множеству $B$, называется полным прообразом множества $B$.

Пример.

$X=Y=R$, $y=x^2$.

$A=[-1; 1] \subset X$

Полный образ $f(A)=$

$B= \subset Y$

Полный прообраз $f^{-1}(B)=[-1; 1]$

Определение. Отображение $f$ называется инъективным отображением, если $\forall \; y \in Y$ $y=f(x)$ является образом единственного $x$.

Определение. Отображение $f$ называется сюръективным отображением, если все элементы в множестве $Y$ являются образами какого-либо $x$. (Это отображение множества $X$ на множество $Y$).

Определение. Отображение $f$ называется биективным , если оно инъективно и сюръективно, в противном случае такое отображение назвается взаимно однозначным соответствием.

Определение. Множества $X$ и $Y$ называются эквивалентными (равномощными), если они находятся во взаимно однозначном соответствии. Обозначается: $X Y$ (множество $X$ эквивалентно множеству $Y$ или множество $X$ равномощно множеству $Y$).

1. Граф соответствия. Отображение. Инъективное, не сюръективное.