Материал: Дискретная математика теория и практика

1.5. Прямое произведение множеств

При задании некоторого конечного множества списком его элементов порядок указания элементов этого множества не имеет значения. Например, множества {a, b} и {b, a} совпадают, так как они состоят из одних и тех же элементов, хотя порядок указания элементов в этих записях различен. Кроме этого, каждый элемент входит в множество в точности один раз, то есть среди элементов множества нет повторяющихся. Так, запись {a, a} означает множество, состоящее из единственного элемента a, то есть {a, a} = {a}.

Введем новое исходное понятие – понятие упорядоченной пары (a, b), которая представляет собой набор двух объектов a и b, не обязательно различных, первым элементом которого является a, а вторым – b.

Определение 1.14. Упорядоченные пары (a, b) и (c, d) называются рав-

ными (пишут (a, b) = (c, d)), если a = b и c = d.

В частности, (a, b) = (b, a) a = b (сравните: из равенства {a, b} = {b, a} не следует, что a = b).

Обобщением понятия упорядоченной пары является понятие кортежа (вектора) – упорядоченного набора произвольных, не обязательно различных n объектов. Кортеж, состоящий из элементов x1, x2, …, xn, обозначается

(x1, x2, …, xn) или < x1, x2, …, xn >. Элементы xi (i = 1, 2, …, n) называются коор- динатами или компонентами кортежа. Число координат называется длиной кортежа (размерностью вектора). Кортежи длины 2 называют также упорядоченными парами, кортежи длины 3 – упорядоченными тройками и т.д., кортежи длины n – упорядоченными n-ми («энками»).

12

Определение 1.15. Два кортежа (x1, x2, …, xn) и (y1, y2, …, ym) называются

равными (пишут (x1, x2, …, xn) = (y1, y2, …, ym)), если:

1)n = m;

2)xi = yi (i = 1, 2, …, n).

Введем еще одну операцию над множествами.

Определение 1.16. Прямым (декартовым) произведением

A1 × A2 × … × An n множеств A1, A2,…, An называется множество всех кортежей

длины n (x1, x2, …, xn) таких, что x1 A1, x2 A2, …, xn An. Таким образом, по определению,

A1 × A2 × … × An = {(x1, x2, …, xn) | x1 A1, x2 A2, …, xn An}.

В частности, если n = 2, то A × B = {(x, y) | x A, y B}.

Пример 1.8. Пусть A = {a, b, c} и B ={1, 2}. Тогда

A× B = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}; B × A = {(1, a), (2, a), (1, b), (2, b), (1, c), (2, c)};

A× A = {(a, a), (b, b), (c, c)}; B × B = {(1, 1),(2, 2)}.

Если A1 = A2 = … = An = A, то множество

множества A или n-й степенью множества A и обозначается через An. При этом будем считать, что A1 = A.

Рассмотрим геометрическую интерпретацию прямого произведения двух числовых множеств A и B – множество всех точек координатной плоскости Oxy с координатами (x, y) такими, что x A, а y B. Тогда для двух заданных числовых множеств можно наглядно изображать их прямое произведение и, обратно, по изображению прямого произведения двух множеств определять их элементы.

Пример 1.9. Изобразить на координатной плоскости Oxy A × B, если:

а) A = {3, 5, 7}, B = {2, 4};

б) A = {3, 5, 7}, B = [2; 4]; в) A = [3, 7], B = [2; 4].

Решение.

y y y

Пример 1.10. Определить, прямое произведение каких множеств A и B изображено на рисунках:

13

y

Решение. а – A = {1,2,3,4}, B = {2}; б – A = [1;6], B = (1;3); в – A = [3;5), B = R.

1.6. Метод математической индукции

Метод математической индукции используется для доказательства утверждений, в формулировке которых участвует натуральный параметр n. Он основан на так называемом принципе математической индукции (одна из аксиом формальной теории натуральных чисел): утверждение «для любого n N выполняется P(n)» считается доказанным, если оно доказано для n = 1 и для любого натурального числа k из предположения, что P(n) истинно для n = k , доказана его истинность для n = k + 1.

Запись принципа математической индукции в символической форме вы-

глядит так: [P(1) ( k N ) (P(k ) P(k +1))] ( n N ) P(n).

Для доказательства утверждений методом математической индукции используется схема рассуждений, состоящая из следующих этапов:

1. База индукции. Доказывается истинность утверждения P(n) для

n= 1(обычно это удается сделать непосредственной проверкой).

2.Индуктивное предположение. Допускается, что утверждение P(n) верно для всех 1 ≤ n ≤ k .

3.Индукционный переход. Исходя из индуктивного предположения, доказывается истинность P(n) для n = k + 1.

4.Вывод. На основании первых трех этапов и принципа математической индукции делается вывод о справедливости утверждения для любого

nN .

Замечание 1.6. Если требуется доказать утверждение P(n), где n N0, то база индукции начинается с n = 0.

Замечание 1.7. Иногда бывает нужно доказать справедливость некоторого утверждения P(n) , зависящего от натурального параметра n, для всех n ≥ m ,

где m – фиксированное натуральное число. В этом случае принцип математической индукции можно записать в виде:

[P(m) ( k ≥ m)(P(k ) P(k + 1))] ( n ≥ m) P(n).

Замечание 1.8. С помощью принципа математической индукции можно давать индукционные определения. При этом для определения понятия

14

P(n) (n N), во-первых, задается значение P(1); во-вторых, для любого натурального числа k задается правило получения значения P(k + 1) по числу k и значению P(k).

Пример 1.11. Доказать, что для любого натурального числа n справедли-

Докажем истинность данного равенства методом математической индукции. 1. База индукции. Проверим истинность равенства при n = 1:

для n = 1.

2.Индуктивное предположение. Предположим истинность равенства при n = k :

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

ческой индукции следует, что данное равенство истинно для любого n N.

15

1.7. Соответствия

Определение 1.17. Соответствием между множествами A и B (между элементами множеств A и B) называется подмножество R A B.

Если (a, b) R, то говорят, что элемент b соответствует элементу a при соответствии R.

Проиллюстрировать соответствия между двумя различными множествами можно с помощью диаграмм, которые в дальнейшем будут называться гра- фами соответствий. На них множества изображаются с помощью кругов (или любых других связных фигур) на плоскости, а элементы множеств – точками внутри соответствующих кругов. Каждой упорядоченной паре (a, b) из соответствия R сопоставляется отрезок прямой (или любая другая линия без самопересечений), соединяющий точки a и b и имеющий направление, указываемое стрелкой, от первого элемента упорядоченной пары ко второму.

Пример 1.12. Пусть A = {a, b, c, d, e} и B = {1, 2, 3, 4}. Соответствие R между множествами A и B задано списком его элементов:

R = {(a, 2), (b, 1), (c, 2), (d, 4)}.

На рис. 1.7 представлен граф соответствия R.

Определение 1.18. Множество всех первых элементов упорядоченных пар, входящих в соответствие R, называется его областью определения и обозначается через Dom R. R A B Dom R = {x A | y B: (x; y) R}.

Здесь и далее знак «:» заменяет слова «такой, что».

Определение 1.19. Множество всех вторых элементов упорядоченных пар, входящих в соответствие R, называется его областью значений и обозначается через Im R.

R A B Im R = {y B | a A: (x; y) R}.

Пример 1.13. Найдем область определения и область значений соответ-

ствия R из примера 1.12: Dom R = {a, b, c, d}, Im R = {1, 2, 4}.

Определение 1.20. Если Dom R = A, то соответствие R называется всюду (полностью) определенным. В противном случае соответствие R называется

частичным (частично определенным).

Определение 1.21. Если Im R = B, то соответствие R называется сюръек-

тивным (сюръекцией).

Пример 1.14. На рис. 1.7 изображен граф частичного соответствия R, так как Dom R ≠ A. Соответствие S, граф которого представлен на рис. 1.8, является всюду определенным и сюръективным, так как Dom S = {a, b, c, d, e} = A и

Im S = {1, 2, 3, 4} = B.

16