Taran_T_A_quot_Osnovy_Diskretnoy_Matematiki_qu

Примеры.

•На множестве N определено отношение α : x < y. Тогда транзитивным замыканием этого отношения для значений 1 < 2 < ... < 6 будет отношение 1 < 6 (см. рис. 2.7).

•Транзитивным замыканием отношения «быть сыном» является отношение «быть прямым потомком».

•Транзитивным замыканием отношения «иметь общую стену» для жильцов одного дома является отношение «жить на одном этаже».

2.3.2. Основные свойства отношений

Будем рассматривать отношения, заданные на множестве X, т.е. xρ y, x, y X.

Определение 2.12. Отношение ρ на множестве X называется рефлексивным, если для любых x X выполняется xρ x. Если для всех x X не выполняется xρ x, то отношение называется

антирефлексивным.

Примеры. Отношение равенства рефлексивно. Отношение x ≥ y, x, y R рефлексивно, так как x ≥ x. Отношение x > y, x, y R антирефлексивно, так как ни для одного числа не выполнимо x > x.

Определение 2.13. Отношение ρ на множестве X называется симметричным, если для любых x X, y X, из xρ y следует yρ x.

Иными словами, отношение симметрично, если всякий раз, как выполняется xρ y, выполняется и yρ x.

Примеры. Из того, что «x родственник y», следует, что «y родственник x»,— отношение симметрично. Отношение «x – сестра y», определенное на множестве всех людей, несимметрично: возможно, что y является братом x. Однако то же отношение, определенное на множестве женщин, является симметричным.

Определение 2.14. Отношение ρ на множестве X называется антисимметричным, если для любых x, y X, из того, что xρ y и yρ x, следует x = y.

Примеры. Отношение x ≤ y антисимметрично: из того, что x ≤ y и y ≤ x, следует, что x = y, т.е. это один и тот же элемент.

Если для любых x, y Х из того, что xρ y, следует, что не выполняется yρ x, то отношение называется асимметричным.

Отношения «x предок у» и «у потомок x» асимметричны, причем второе является обратным к первому. Отношение строгого порядка x < y является асимметричным: если выполняется x < y, то не выполняется y < x.

Определение 2.15. Отношение ρ называется транзитивным, если из того, что xρ y и yρ z, следует xρ z.

Пример. Отношение «x предок y» транзитивно: если «x предок y» и «y предок z», то «x предок z». Отношение x < y, где x, y R, транзитивно: если x < y и y < z, то x < z. Отношение «x любит y», в общем случае нетранзитивно: если «x любит y», а «y любит z», то из этого не следует, что «x любит z».

2.4. Отношение эквивалентности

Определение 2.16. Отношение, которое обладает свойствами рефлексивности, симметричности и транзитивности, называется отношением эквивалентности.

Примеры отношений эквивалентности.

1.Отношение равенства на любом множестве является отношением эквивалентности,причемотношениеравенстваявляетсявнекоторомсмысле минимальным (предельным) случаем отношения эквивалентности.

2.Геометрическое отношение подобия треугольников на плоскости является отношением эквивалентности.

3.Отношения сравнимости по модулю n в Z: x сравнимо с у по модулю n, если разность x – у делится на n (без остатка).

Обозначается: x ≡ у (mod n). Например: 3 ≡ 6 (mod 3), 7 ≡ 13 (mod 3).

4.Отношение параллельности прямых в евклидовом пространстве есть отношение эквивалентности.

5.Утверждения вида sin2x + cos2x = 1, (a + b)(a – b) = a2 – b2, состоящие их формул, соединенных знаком равенства, задают бинарное отношение на множестве формул, описывающих суперпозиции элементарных функций. Это отношение равносильности также является отношением эквивалентности: формулы равносильны, если они задают одну и ту же функцию.

6.Отношение «студенты x и y учатся в одной группе», где x, y {«студенты первого курса»}, есть отношение эквивалентности.

7.Отношение «жить в одном районе», определенное на множестве людей, живущих в г. Киеве, является отношением эквивалентности.

Множество всех жителей Киева разбивается последним отношением эквивалентности на ряд непересекающихся подмножеств, в данном случае на множества людей, живущих в одном и том же районе. Два жителя считаются эквивалентными по данному отношению, если они живут в одном и том же районе, и в этом смысле они неразличимы, т.е. они обладают одним и тем же свойством: «жить в районе «ХХХ». Это свойство является определяющим свойством (предикатом) множества всех жителей района «ХХХ». С другой стороны, нельзя жить в двух (и более) районах сразу (во всяком случае, согласно прописке), поэтому множества жителей различных районов не пересекаются. Таким образом, отношение

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

Дадим более строгое определение.

Определение 2.17. Пусть на множестве X задано отношение эквивалентности ρ . Тогда подмножество A X называется

классом эквивалентности по отношению ρ , если A состоит из всех тех элементов x X, что для некоторого a X, a A и xρ a.

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

Полученная система классов эквивалентности обладает следующими свойствами.

Теорема 2.1.

1. Пусть ρ есть отношение эквивалентности на X. Тогда множество классов эквивалентности по отношению ρ есть разбиение множества X. Обратно, если есть некоторое разбиение множе-

2. Если отношение эквивалентности ρ определяет разбиение множества X, то отношение эквивалентности, определяемое этим разбиением , совпадает с ρ . Обратно, если некоторое разбиение В множества X определяет некоторое отношение эквивалентности ρ , то разбиение множества X, определяемое этим отношением ρ , совпадает с В.

Доказательство. Доказательство первой части теоремы следует из свойств отношения эквивалентности. Каждый элемент X войдет хотя бы в один класс эквивалентности. Предположим, что некоторый элемент b входит одновременно в два класса эквивалентности Ai è Aj. Тогда существует ai Ai такое, что aiρ b, и существует aj Aj такое, что bρ aj. Но тогда, в силу свойства транзитивности, aiρ aj и, следовательно, классы Ai è Aj есть один и тот же класс.

множество A, что a A, так что ρ рефлексивно. Покажем, что оно транзитивно. Пусть aρ b è bρ c. Тогда в найдется такое A, что a, b A, и такое B, что b, c B. Поскольку b B и b A, то A = B. Следовательно aρ c.

На основании этой теоремы можно дать конструктивное определение отношения эквивалентности: отношение ρ на множестве Х называется эквивалентностью, если существует разбиение Х на подмножества {A1, A2 ,..., An} такое, что отношение xρ у выполняется тогда и только тогда, если x и у принадлежат одному и тому же подмножеству.

Будем обозначать класс эквивалентности, порожденный элементом a X через [a]. Тогда, если aρ b, òî [a] = [b].

Определение 2.18. Множество классов эквивалентности множества X по отношению ρ называется фактор-множеством множества X по отношению ρ и обозначается [X/ρ ].

Примеры.

1.Все классы эквивалентности по отношению равенства состоят из одного элемента. Фактор-множество по отношению равенства состоит из элементов самого множества.

2.Свойство параллельности прямых на плоскости определяет отношение эквивалентности. Фактор-множество этого отношения – множество всех направлений на плоскости. Оно может быть описано, как множество всех углов наклона прямой к оси абсцисс, т.е. интервал [0°, 180°).

3.Пусть х, у Z. Рассмотрим отношение сравнимости по модулю 3: xρ y åñòü x ≡ y(mod 3). Запись x ≡ y(mod 3) означает, что разность õ–ó делится на 3 без остатка. Будем обозначать это так: xρ y åñòü (õ — ó)/3 =

= k Z. Докажем, что x ≡ y (mod 3) – отношение эквивалентности.

3.1.Проверим выполнение свойства рефлексивности: для всякого x xρ x. Действительно, (x – x)/3 = 0/3 = 0; 0 Z, следовательно, отношение рефлексивно.

3.2.Проверим выполнение свойства симметричности: если xρ y, òî óρ х. Пусть (х – у)/3 = k Z. Тогда (у – х)/3 = –(х – у)/3 = –k Z. Следовательно, условие симметричности выполняется.

3.3.Проверим выполнение свойства транзитивности: из xρ y è óρ z

следует xρ z. Пусть (х – у)/3 = k1 Z, ò.å. õ – ó = 3k1, è (y – z)/3 = k2 Z, ò.å. y – z = 3k2. Решим эту систему уравнений, сложив их:

õ – ó + y – z = 3(k1 + k2), ò.å. x – z = 3(k1 + k2) = k3 Z. Условие транзитивности выполняется.

Следовательно, отношение х ≡ у (mod 3) является отношением эквивалентности. Найдем его фактор-множество [Z/ρ ]. Произвольное число х Z можно записать в виде 3q + r, где q, r Z, 0 ≤ r < 3. В один и тот же класс эквивалентности попадут все числа, дающие при делении на 3 одинаковое число r в остатке. Мы получим три класса эквивалентности: [0] = {0, 3, 6, 9, 12, …}; [1] = {1, 4, 7, 10, 13, …}; [2] = {2, 5, 8, 11, 14, …}. В класс [0] попадают все числа, которые делятся на 3 без остатка, в класс [1] — все числа, при делении на 3 дающие в остатке 1, и в класс [2] — все числа, дающие в остатке 2. Каждый класс можно охарактеризовать одним представителем этого класса, и в данном случае таким представителем удобнее всего выбрать остаток r. Следовательно, фактор-множеством Z по отношению х ≡ у (mod 3) будет [Z/х ≡ у (mod 3)] = {[0], [1], [2]}.

Глава 3. ОТОБРАЖЕНИЯ. ФУНКЦИИ

3.1.Основные понятия

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

порядка. Для отношений, образованных различными множествами, когда ρ E Ч F, говорить о рефлексивности, симметричности и

транзитивности уже не имеет смысла, так как первая и вторая координата ρ могут иметь различную природу. Например, отношение «x родился в году y» является подмножеством декартова произведения множества людей и множества лет (подмножества целых положительных чисел) и ставит в соответствие каждому человеку год его рождения. Для исследования подобных отношений вводятся понятия соответствия, отображения, функции.

Определение 3.1. Говорят, что между множествами E и F определено соответствие Г, если задано некоторое произвольное подмножество декартового произведения E Ч F. Множество E

называется областью определения, F — областью значений

соответствия Г.

Соответствие, обратное Г, обозначим Г–1, где F — область определения, E — область значений Г–1.

Определение 3.2. Отображением множества E на множество F называется такое соответствие, которое каждому элементу x E сопоставляет по крайней мере один элемент y F. Тогда элемент y называется образом элемента x, а x — прообразом элемента y, или переменной, или аргументом. Отображение E в F будем обозначать f: E → F, где f — имя отображения.

Пример. На рис. 3.1 показано соответствие между множествами E и F, на рис. 3.2 — отображение множества E в множество F.

3.1.1. Сюръекция

Определение 3.3. Отображение E на F называется сюръективным, или сюръекцией, или наложением, если каждый элемент y F есть образ по крайней мере одного элемента x E, т.е.y F x E (y = Г(x)).

Условие у F |Г–1(y)| ≥ 1 характеризует сюръекцию. Это означает, что каждый элемент из F имеет не менее одного прообраза в E. На графе соответствия в каждый элемент y входит по крайней мере одна дуга (рис. 3.3) и обратное отображение Г–1(y) не пусто.

Рис. 3.3. Сюръекция.

3.1.2. Инъекция

Определение 3.4. Отображение E в F называется инъективным, или инъекцией,иливложением,есликаждыйэлементу Fестьобразтолько одного элемента x E, либо вообще не имеет прообраза.

В этом случае E инъективно отображается в F. На графе соответствия в каждый элемент y входит самое большее одна дуга, т.е. условие у F |Г–1(y)| ≤ 1 характеризует инъекцию. На рис. 3.4. показана инъекция: в каждый элемент y входит самое большее одна дуга; некоторые элементы y не имеют прообразов в E.

Рис. 3.4. Инъекция.

3.1.3. Биекция

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

Âэтом случае каждый элемент F является образом некоторого,

èпритом единственного, элемента из E. На графе соответствия на рис. 3.5 показана биекция: в каждый элемент y входит одна и только

одна дуга, т.е. при биекции каждый образ имеет только один прообраз: у F |Г–1(y)| = 1.

Рис. 3.5. Биекция.

3.1.4. Функциональные отображения

Определение 3.6. Соответствие, при котором каждому x E сопоставляется один и только один элемент у F, называется

функциональным соответствием, или функцией.

Для функционального отображения выполняется условие:x E |Г(x)| = 1. Иными словами, функция — это соответствие или отображение, при котором два различных элемента не имеют одинаковых первых координат, т.е. если <x, y>, <x, z> Г, то y = z. Если функциональное соответствие не является отображением, т.е. в E существуют элементы, не имеющие образа в F, то оно называется

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

В дальнейшем мы будем рассматривать только функциональные отображения и обозначать их функциональными символами ƒ, ϕ и т.п. Функция может быть биективной, сюръективной и инъективной, как показано на рис. 3.6, 3.7, 3.8.

Функциональная биекция E → F устанавливает такое отображение, при котором каждый элемент из E имеет единственный образ в F, а каждый элемент из F имеет единственный прообраз в E, поэтому функциональная биекция называется взаимно однознач- ным соответствием. Функциональное отображение E → F, которое является сюръекцией, возможно только в том случае, если количе- ство элементов в E не меньше количества элементов в F, т.е. |E| ≥ |F|. Для функциональной инъекции, наоборот, должно выполняться соотношение |E| ≤ |F|.

Рис. 3.8. Функциональная сюръекция.

Определение 3.7. Отображение множества E в E, определенное равенством ƒ(x) = x, называется тождественным отображением (оператором).

Определение 3.8. Отображение множества в его фактор-множе- ство называется канонической сюръекцией.

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

1. Пусть задано соответствие ƒ: R → R, такое, что ƒ(x) = x2. Это соответствие является отображением, так как для каждого x R существует образ ƒ(x) = x2. Область определения этого отображения — множество всех действительных чисел R; область значений — Im(R) = [0, ∞). Отображение ƒ функционально, так как каждое значение x R имеет только один образ в R. Отображение ƒ: R → [0, ∞) является функциональной сюръекцией, так как для каждого ƒ(x) [0, ∞) существует по крайней мере один прообраз x R.

2. Если E – множество ограниченных кривых на плоскости, то функция вычисления длины кривой есть сюръекция ƒ: E → R+.

3.Отображение ƒ: R → R, такое, что ƒ(x) = 2x+3, т.е. прямая, есть биекция.

4.Отображение g: N → R, такое, что g(x) = ±√x, является биекцией, но не является функциональным отображением.

5.Соответствие ƒ: R → R, такое, что ƒ(x) = x/sin x, является частич- но определенной функцией: для sin x = 0 значение функции не определено.

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

3.2. Кардинальная степень множеств

Если E и F — два множества, то можно говорить о некотором новом множестве — множестве функциональных отображений E в F.

Пример. На рис. 3.9 показано множество всех функциональных отображений из E = {0, 1} в F = {a, b}. Это же множество задано в таблице – это множество всех одноместных функций, определенных на E со значениями в F.

Рис. 3.9. Множество отображений E = {0, 1} в F = {a, b}.

Из таблицы видно, что множество всех функций из E = {0, 1} в

F= {a, b} можно биективно отобразить на декартово произведение

FЧ F, так как каждой функции можно поставить в соответствие упорядоченную пару из F Ч F. В данном примере такой биекцией

будет: f1 ó <a, a>, f2 ó <a, b>, f3 ó <b, a>, f4 у <b, b>. Если E состоит из n элементов x1, x2, ..., xn, то множество

(одноместных) функций из E в F можно биективно отобразить на F n, так как каждое такое отображение эквивалентно заданию кортежа <y1, y2, ... , yn> F n образов элементов x1, x2, ..., xn при этом отображении. Поэтому количество функциональных отображений определяется количеством элементов в декартовом произведении F n, где n – количество элементов множества E. В нашем примере для f: {0, 1} → {a, b} количество функций |f| = 22 = 4. Åñëè |E| = 3, |F| = 2, òî |f| = 23. В общем случае |f| = |F| |E|.

Это дает основание обозначать множество всех функциональных отображений {ƒ: E → F} в виде степени FE. Таким образом, мы определили еще одну операцию над множествами — это возведение множества в степень другого множества: FE. Результатом ее является множество всех функциональных отображений E → F, т.е. множество всех одноместных функций, определенных на E со значениями в F. В отличие от декартовой степени множества, степень множества F E как множество всех функциональных отображений E → F называют кардинальной степенью.

Определение 3.9. Множество всех функциональных отображений {ƒ: E → F} называется (кардинальной) степенью множеств

и обозначается F E.

Отображение множества En â F, ãäå n N, En — декартова степень множества E, образует функцию от n переменных. Множество всех n-местных функций есть множество всех (функциональных)

Как видно из таблицы, каждая функция есть множество пар {<<x1, x2>, y>}, например, f4 = {{<<0, 0>, a>, <<0, 1>, a>, <<1, 0>, b>, <<1, 1>, b>}.

3.3. Свойства функциональных отображений

Пусть ƒ — функциональное отображение E в F и A — подмножество E. Обозначим через ƒ(A) подмножество F, образованное из

отображение сохраняет операции , ∩ , , \ в следующем смысле. (В доказательствах символ означает «влечет», «следовательно», символ — «равносильно», «равнозначно».)

Утверждение 3.3. f(A\B) = f(A)\f(B).

f(x) f(A)\f(B) f(x) f(A) è f(x) f(B) x A è x B

x A\B f(x) f(A\B) f(A)\f(B) f(A\B). (2) Èç (1) è (2) ƒ(A\B) = ƒ(A)\ƒ(B).

Однако, операции ∩ , при этом отображении не сохраняются, имеет место лишь включение.

Утверждение 3.4. ƒ(A ∩ B) ƒ(A) ∩ ƒ(B).

Доказательство.

f(x) f(A ∩ B) x A ∩ B x A è x B f(x) f(A) è f(x) f(B) f(x) f(A) ∩ f(B)

но при этом возможно, что f(A) ∩ f(B) ≠ , и тогда

ƒ(A) ∩ ƒ(B) ƒ(A ∩ B), потому мы ограничимся результатом (1).

Пусть теперь B является некоторым подмножеством множества F. Будем обозначать через ƒ–1(B) подмножество E, образованное из всех таких элементов x, что ƒ(x) B. Подмножество ƒ–1(B) называется прообразом множества B при отображении ƒ. Это определение вовсе не предполагает биективности ƒ. Если y F, то можно говорить о ƒ–1({y}), но это — некоторое подмножество E, а не элемент E. Оно может содержать более одного элемента, если ƒ не является инъективным, и может оказаться пустым, если ƒ не сюръективно. Если ƒ биективно, то ƒ–1({y}) = {ƒ–1(y)}. Очевидно, что ƒ–1( ) = .

Мы связали с отображением ƒ отображение B → ƒ–1(B) множества (F) во множество (E). Это отображение сохраняет операции , , ∩ , \, ′ в следующем смысле.

Доказательство.

x ƒ–1(A ∩ B) ƒ(x) A ∩ B ƒ(x) A è ƒ(x) B

x ƒ–1(A) è x ƒ–1(B) x ƒ–1(A) ∩ ƒ–1(B)

x ƒ–1(A) ∩ ƒ–1(B) x ƒ–1(A) è x ƒ–1(B) ƒ(x) A è

ƒ(x) B ƒ(x) A ∩ B x ƒ–1(A ∩ B)

Доказать самостоятельно.

Утверждение 3.9. ƒ–1(A\B) = ƒ–1(A)\f–1(B). Доказать самостоятельно.

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

Определение 3.10. Пусть даны три множества E, F и G, и заданы отображения ƒ: E → F, g: F → G. Тогда композицией отображений goƒ: E → G называется отображение E в G, которое определяется формулой goƒ = g(ƒ(x)).

Иными словами, если существует множество пар <x, y> ƒ и <y, z> g, то множество пар <x, z> goƒ образует композицию отображений goƒ. Запись goƒ производится в порядке, обратном тому, в котором производятся операции ƒ: E → F, g: F → G. Таким образом, в математике принято правило, согласно которому композицию отображений goƒ надо начинать с выполнения операции ƒ, которая расположена справа.

(y) mod2. Тогда gof: R → {0, 1} есть ([x]) mod2 – остаток от деления целой части числа x на 2.

Теорема 3.1. Композиция отображений ассоциативна, т.е., если ƒ, g, h — отображения E в F, F в G и G в H соответственно, то (hog)oƒ = ho(goƒ), что записывается в виде: hogoƒ.

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

Доказательство. Пусть <x, u> ho(goƒ), <x, z> goƒ, <z, u> h. Поскольку <x, z> goƒ, то существует такое y, что <x, y> ƒ, и <y, z> g, а поскольку существует <z, u> h, то существует и <y, u> hog. Следовательно, если <x, y> ƒ и <y, u> hog, то существует и <x, u> (hog)of (см. рис. 3.10).

Теорема 3.2. Композиция отображений не коммутативна.

Доказательство этой теоремы очевидно, оно основано на самом определении композиции.

Для примера рассмотрим два отображения ƒ: y = sin x и g: y = x2, где x, y R. Композиция goƒ: y = sin2x, а композиция ƒog: y = sin x2. Очевидно, это различные функции.

Определение 3.11. Отображение множества E в E, при котором каждый элемент переходит в себя, называется тождественным отображением и обозначается IE. Для тождественных отображений справедливы равенства1:

foIE = IFof = f.

Теорема 3.3. Отображение f: E → F имеет обратное тогда и только тогда, когда f — биекция.

Доказательство.

Достаточность. Если f — инъекция и сюръекция, то необходимо доказать, что существует ƒ–1: F → E.

Так как ƒ(x) — сюръекция, то каждый элемент из F имеет хотя бы один прообраз в E: x E (ƒ(x) = y), т.е. соответствие ƒ–1: F → E всюду определено на F и, следовательно, является отображением.

1 Если все рассматриваемые отображения есть биекции, то для каждого отображения существует обратное, и множество всех отображений из E в F образует группу, в которой тождественные отображения IE, IF являются левой и правой единицей.

A так как ƒ(x) — инъекция, т.е. для x1 ≠ x2 ƒ(x1) ≠ ƒ(x2), то каждый элемент y имеет только один прообраз, следовательно, отображение ƒ–1: F → E функционально.

Необходимость. Пусть f–1: F → E — функциональное отображение. Докажем, что ƒ — биекция.

Поскольку ƒ–1 — отображение, то каждый элемент y из F имеет прообраз в E, т.е. отображение ƒ сюръективно. Поскольку отображение ƒ–1 функционально, то каждому образу ƒ(x) соответствует единственный прообраз x, т.е. ƒ — инъекция. Следовательно, ƒ — биекция.

Теорема 3.4. Если ƒ и g — функциональные отображения, либо сюръекции, либо инъекции, либо биекции, то можно доказать ряд утверждений о свойствах композиции этих отображений. Эти свойства отображены в табл. 3.1, где символами обозначены: О — отображение, С — сюръекция, И — инъекция, Б — биекция.

Доказательство этих 16 утверждений предоставляется читателю.

Таблица 3.1.

Пример. Докажем утверждение: композиция инъекции и сюръекции есть отображение.

Доказательство. Пусть g — сюръекция, f — инъекция, goƒ — их композиция, и пусть <x, y> f, <y, z> g, <x, z> goƒ (см. рис. 3.11).

Рис. 3.11. Композиция инъекции и сюръекции.

Åëè y1 есть образ элемента x E, то z1 есть образ элемента x в G, т.е. существует пара, <x, z1> goƒ. Элемент y2 может не иметь прообраза в E, и, следовательно, не каждый элемент z имеет прообраз в E, откуда следует, что goƒ не сюръекция.

3.5. Замена переменной и замена функции

Определение 3.12. Пусть ƒ — функция, определенная на E со значениями в F. Если u является отображением некоторого множества E1 во множество E, то можно построить новую функцию ƒ1 = ƒou, определенную на E1 со значениями в F (рис. 3.12). Говорят, что в этом случае произведена замена переменной, или замена исходного множества E на E1, è ÷òî ƒ1 является прообразом ƒ при этой замене переменных. Произведя в выражении

ƒ(x) подстановку x = u(x1), получают выражение ƒ1(x1). Иногда это обозначают как ƒ*(x1) = ƒ(u(x1)).

Рис. 3.12. Замена переменной.

Определение 3.13. Пусть v является некоторым отображением F в множество F1. Тогда можно определить новую функцию ƒ* = voƒ, определенную на E со значениями в F1 (рис. 3.13). В этом случае говорят, что произведена замена функции или замена множества значений F на множество F1 и что ƒ* является образом ƒ при этой замене. Замену функции называют еще аппликацией функций. Иногда это обозначают как ƒ*(x) = v(ƒ(x)).

Пример. Пусть исходная функция E → F: ƒ(x) = x2. Заданы

Рис. 3.13. Замена функции.

функции в функции ƒ(x): v(ƒ(x)) = 2x2. Таким образом, при замене переменной мы получаем новую функцию, зависящую от новой переменной, а при замене функции — новую функцию, зависящую от той же самой переменной.

Можно произвести одновременно и замену переменной и замену функции: ƒ3 = voƒou. Здесь ƒ3 является образом ƒ при замене переменной u и замене функции v. Например, для определенных выше функций: ƒ3 = voƒou = v(ƒ(u(x1))) = 2(x1 + 1)2.

Глава 4. МОЩНОСТЬ МНОЖЕСТВ

4.1. Определение мощности

Понятие мощности множеств связано с оценкой числа элементов в нем. В конечном множестве количество элементов можно пересчитать. Число элементов в множестве Х обозначается обычно как |Х|. Например, если X = {a, b, c}, то |X| = 3. Если два множества имеют одинаковое число элементов, то между ними можно установить взаимно однозначное соответствие. Тогда все конечные множества, имеющие одинаковое количество элементов, будут эквивалентны по числу элементов в них и образуютодинклассэквивалентности.Этотклассэквивалентности может быть обозначен целым натуральным числом, определяющим количество элементов в множествах. Все одноэлементные множества образуют один класс эквивалентности, двухэлементные — другой, и так далее. Каждому натуральному числу соответствует класс эквивалентности, объединяющийвсеконечныемножествасчисломэлементов,равнымданномучислу.

Мощность объединения нескольких конечных множеств можно найти по формулам:

(Читателю предлагается доказать эти равенства самостоятельно и найти общее выражение.)

Рассмотрим теперь бесконечные множества. Для некоторых бесконечных множеств тоже можно установить взаимно однозначное соответствие элементов. Например, для множества четных натуральных чисел, которое можно представить в виде списка: {2, 4, 6, …}, последовательность (1, 2, 3, …) будет нумерацией этого списка, т.е. существует отображение ƒ(n) = 2n,длякаждогоn NмножестванатуральныхчиселNвмножество всех четных положительных целых чисел, которое является биекцией. Следовательно, множество всех четных натуральных чисел эквивалентно множеству всех натуральных чисел, т.е. четных чисел ровно столько же, скольковсехнатуральныхчисел.Но,сдругойстороны,множествонатуральных чисел можно разбить на два подмножества четных и нечетных чисел, т.е. четных чисел ровно половина из всех натуральных чисел! Получаем, что в некотором смысле часть равна целому1. И это действительно так.

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

Можнопоказать,чтосуществуетбиекцияизмножестванатуральныхчисел на любое его бесконечное подмножество. Действительно, пусть P N. ВыберемвPнаименьшийэлементиобозначимегоx1;вычтемэтотэлемент из P инаименьшийэлементизвсехоставшихсяобозначимx2. Продолжая этот процесс, мы присвоим номер каждому элементу изP. Эта нумерация есть биекция N → P: n → xn, ãäå xn есть (n + 1)-й в порядке возрастания элемент P. Таким образом, множество нечетных чисел, множество квадратовнатуральныхчиселимножестволюбыхлинейныхкомбинаций, например, ax + b, где a, b N, будут эквивалентны между собой и войдут в один класс эквивалентности.

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

Мощность множества X обозначается card X. Число элементов конечного множества также называется мощностью, тогда card X = |X|. Для равномощных множеств часто используется обозначение E F.

4.2. Кардинальные числа

Сравнение бесконечных множеств возможно благодаря свойствам функциональных отображений. Из определения инъекции следует, что инъекция из множества E в множество F возможна только в том случае, если количество элементов в E не больше, чем количество элементов в F: |E| ≤ |F| (для конечных множеств), причем, если не существует инъекции из F в E, то это неравенство превращается в строгое неравенство |E| < |F| (см. рис.4.1). Если же существует инъекция из F в E, причем не обязательно совпадающая с обратным отображением для инъекции E → F, то это возможно лишь тогда, когда количество элементов в них совпадает, т.е. |E| = |F|, а в этом случае можно найти и взаимно однозначное соответствие между E и F, т.е. биекцию.

Аналогично, если существует сюръекция из E на F, такая, что один образ в F имеет несколько прообразов в E, то количество элементов в E строго больше количества элементов в F, т.е. |E| > |F|.

Рис. 4.1. Инъекция E → F.

Эти свойства обобщаются для случая бесконечных множеств следующей теоремой.

Теорема 4.1 (Кантора — Бернштейна1).

Пусть Е и F — два произвольных бесконечных множества. Тогда:

а) либо существует инъекция из E в F, либо существует инъекция из F в E (одно не исключает другого);

б) если существуют инъекции E → F è F → E, то существует биекция из E в F.

Иными словами, если множество E равномощно некоторому подмножеству множества F, а множество F равномощно некоторому подмножеству множества E, то E и F равномощны.

Доказательство. Пусть E равномощно некоторому подмножеству F1 множества F, а F равномощно некоторому подмножеству E1 множества E (см. рис. 4.2, a). При взаимно однозначном соответствии между E1 и F подмножество F1 F переходит в некоторое подмножество E2 E1. При этом все три множества E, E1 è E2 равномощны, и нужно доказать, что они равномощны множеству F, или, что то же самое, множеству E1. Теперь мы можем забыть про множество F и его подмножества и доказывать такой факт:

åñëè E2 E1 E0, (ãäå E0 — обозначение для E) и E2 равномощно E0, то все три множества равномощны.

Пусть f — функция, которая осуществляет взаимно однозначное

соответствие E0 → E2, так, что элемент x E0 соответствует элементу f(x) E2. Когда E0 переходит в E2, меньшее множество E1 переходит в какое-то множество E3 E2 (см. рис. 4.2, б). Аналогично, само E2 переходит в какое-то множество E4 E2. Ïðè ýòîì E4 E3, òàê êàê E2 E1.

Рис. 4. 2. К доказательству теоремы Кантора — Бернштейна.

1 Кантор сформулировал эту теорему без доказательства в 1883 году, пообещав вернуться к ней позже, однако, не выполнил этого обещания. Первые доказательства теоремы были даны Шр¸дером (1896) и Бернштейном (1897).