Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
∀P ³¡ P (0), ∀n(P (n) ⇒ P (n 0 )) ¢ ⇒ ∀nP (n) ´ , а также P (0), ∀n (P (n) ⇒ P (n + 1)) ∀n P (n) или 0 ∈ P, ∀n (n ∈ P ⇒ (n + 1) ∈ P ) P = N . Итак, утверждение “для любого n ∈ N выполняется P (n)” считается до- казанным, если установлены базис индукции (доказано P (0)) и индукцион- ный шаг (доказано, что для любого n ∈ N справедливо P (n + 1) в предпо- ложении, что выполняется P (n)). В этом состоит принцип математической индукции. Принцип математической индукции позволяет также давать индукцион- ные определения, т. е. определения понятий P (n) для всех натуральных чи- сел n, построенные по следующей схеме: 1) задается значение P (0); 2) задается правило получения значения P (n + 1) по числу n и зна- чению P (n). 1.3. НАТУРАЛЬНЫЕ ЧИСЛА. ПРИНЦИП МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ 25 Определим по индукции операции сложения a + b и умножения a · b на натуральных числах. Положим a+0 a (базис индукции). Если известно значение a+n, то a+n 0 (a+n) 0 (индукционный шаг). Аналогично a·0 0. Если задано a · n, то a · n 0 (a · n) + a. Используя операцию сложения, можно ввести отношение 6 на множестве натуральных чисел: a 6 b ⇔ ∃ c(a + c = b). Определим по индукции функцию n! (n-факториал): 0! 1, (n + 1)! n! · (n + 1). Пример 1.3.1. Докажем по индукции неравенство Бернулли: (1 + a) n > 1 + an для всех n ∈ N и a > −1, a ∈ R. При n = 0 неравенство имеет вид (1 + a) 0 > 1 + a · 0 и оно справедливо, т. е. базис индукции выполняется. Установим справедливость индукционного шага. Предположим, что (1 + a) n > 1 + an, (1.1) и покажем, что (1 + a) n+1 > 1 + a(n + 1). (1.2) Умножим обе части неравенства (1.1) на положительное число 1 + a. Тогда (1 + a) n (1 + a) > (1 + an)(1 + a), т. е. (1 + a) n+1 > 1 + a + an + a 2 n. (1.3) Поскольку a 2 > 0, имеем 1 + a + an + a 2 n > 1 + a + an = 1 + a(n + 1). (1.4) Из неравенств (1.3) и (1.4) получаем неравенство (1.2). На основании принципа математической индукции заключаем, что (1 + a) n > 1 + an для всех n ∈ N. ¤ Иногда удается установить только выполнение P (k) для некоторого k > 0 и свойство P (n) ⇒ P (n + 1) для всех n > k. Тогда по принципу математи- ческой индукции свойство P выполняется для всех n > k: P (k), ∀n > k (P (n) ⇒ P (n + 1)) ∀n > k P (n) . 26 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Другой эквивалентной формой принципа математической индукции яв- ляется принцип полной индукции: если для всякого n ∈ N из предположения, что P (k) верно при любом натуральном k < n, следует, что P (k) верно также при k = n, то P (n) верно при любом натуральном n: ∀n ((∀k < n P (k)) ⇒ P (n)) ∀n P (n) . Эта форма используется в том случае, когда для доказательства вы- полнимости P (n + 1) необходимо использовать выполнимость свойства P не только на элементе n, но и на некоторых предыдущих элементах. § 1.4. Мощность множества. Конечные и бесконечные множества Понятие мощности возникает при сравнении множеств по числу элемен- тов. Множества A и B называются эквивалентными (обозначается A ∼ B), если существует биекция f : A ↔ B. Отметим, что для любых множеств A, B, C выполняются следующие свойства: 1) A ∼ A (поскольку id A : A ↔ A); 2) если A ∼ B, то B ∼ A (так как из f : A ↔ B следует f −1 : B ↔ A); 3) если A ∼ B и B ∼ C, то A ∼ C (так как из f : A ↔ B, g: B ↔ C следует f ◦ g: A ↔ C). Мощностью множества A называется класс всех множеств, эквивалент- ных множеству A (обозначается |A|). Эквивалентные множества A и B на- зываются равномощными: |A| = |B|. Если A ∼ n для некоторого n ∈ ω, т. е. A имеет ровно n элементов, то множество A называется конечным. В этом случае пишут |A| = n. Таким образом, мощностью конечного множе- ства является число его элементов. Множество, не являющееся конечным, называется бесконечным. Если A ∼ ω, то множество A называется счетным: |A| = ω. Если A ∼ 2 ω , то мно- жество A называется континуальным или континуумом: |A| = 2 ω На мощность множества A можно смотреть и как на новый объект, на- зываемый кардинальным числом или кардиналом. В качестве примеров кар- диналов можно взять любое натуральное число n, а также ω, 2 ω , 2 2 ω и т. д. 1.4. МОЩНОСТЬ МНОЖЕСТВА 27 Эти числа можно рассматривать как имена, обозначающие соответствую- щие мощности. Кардинальным числом конечного множества служит число его элементов. Существование биекции между двумя эквивалентными множествами поз- воляет переносить изучение свойств с одного множества на другое, когда природа элементов не важна. Например, если |A| = n, то с элементами мно- жества A можно работать как с числами 0, 1, 2, . . . , n − 1, которые являются элементами множества n. Говорят, что мощность множества A не превосходит мощности множе- ства B, и пишут |A| 6 |B|, если A эквивалентно некоторому подмножеству множества B. Мощность множества A меньше мощности множества B (обо- значается |A| < |B|), если |A| 6 |B| и |A| 6= |B|. Теорема 1.4.1 (теорема Кантора—Бернштейна). Если |A| 6 |B| и |B| 6 |A|, то |A| = |B|. Доказательство. Пусть f : A → B, g: B → A — разнозначные отоб- ражения, A 0 = A, A 1 = g(B) и A n+2 = (f ◦ g)(A n ). Индукцией по n легко доказать, что A n+1 ⊆ A n , n ∈ ω. Пусть D = ∩ k∈ω A k и M i = A i \A i+1 . Очевидно, что A k = µ ∪ k6i∈ω M i ¶ ∪ D и M i ∩ M j = ∅ при i 6= j. Так как f ◦ g разнознач- но отображает M i на M i+2 для любого i ∈ ω, то отображение h: A → A, определенное следующим образом: h(a) = a, если a ∈ µ ∪ i∈ω M 2i+1 ¶ ∪ D, (f ◦ g)(a), если a ∈ ∪ i∈ω M 2i , является разнозначным отображением A на A 1 = µ ∪ 16i∈ω M i ¶ ∪ D. Так как |B| = |A 1 |, то |B| = |A|. ¤ Следствие 1.4.2 (теорема о сравнении множеств). Для любых мно- жеств A и B существует одна и только одна из следующих возможно- стей: |A| = |B|, |A| < |B|, |B| < |A|. ¤ Определим на кардинальных числах операции сложения, умножения и возведения в степень. Если |A| = α, |B| = β, то α + β |A ∪ B|, 28 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ где A ∩ B = ∅; α · β |A × B|; α β |A B |. В случаях, когда α, β ∈ ω, вве- денные таким образом операции совпадают с обычными операциями на на- туральных числах. Для конечных кардиналов справедливы следующие три правила, используемые в комбинаторике. Правило суммы. Если |A| = m, |B| = n, то |A ∪ B| = m + n − |A ∩ B|, и |A ∪ B| = m + n в том и только том случае, когда A ∩ B = ∅. Правило произведения. Если |A| = m, |B| = n, то |A × B| = m · n. Правило степени. Если |A| = m, |B| = n, то |A B | = m n Следующее утверждение показывает, что операции на бесконечных кар- диналах могут иметь “необычные” свойства. Предложение 1.4.3. ω 2 ∼ ω. Доказательство. По определению множество ω 2 = ω × ω равно {(m, n) | m, n ∈ ω}. На координатной плоскости изобразим точки с нату- 6 - • • • • • • • • • • @ @ @ @ @ R @ @ @ @ @ R @ @ @ @ @ R @ @ @ @ @ R @ @ @ @ @ R @ @ @ @ @ R @ @ @ @ @ R (0, 0) (0, 1) (0, 2) (0, 3) (1, 0) (2, 0) (3, 0) (1, 1) (1, 2) (2, 1) 0 1 3 6 2 5 9 4 7 8 Рис. 1.7 ральными координатами (m, n) (рис. 1.7). Очевидно, что все эти точки рас- положены в первой четверти. Для доказательства утверждения требу- ется установить биекцию меж- ду множеством натуральных чисел и полученными точками, т. е. пере- нумеровать точки. Нумеруем точки “по диагонали”: 0 7→ (0, 0), 1 7→ (0, 1), 2 7→ (1, 0), 3 7→ (0, 2), 4 7→ (1, 1), 5 7→ (2, 0), 6 7→ (0, 3), 7 7→ (1, 2) и т. д. Так как указанная нумерация разнозначна и каждая пара натуральных чи- сел имеет натуральный номер, то это отображение осуществляет взаимно однозначное соответствие ω ↔ ω 2 . ¤ Упражнение. 1. Используя принцип математической индукции, пока- зать, что ω n ∼ ω для любого n ∈ ω \ {0}. 2. Используя установленный в примере 1.2.10 факт, что Z ∼ ω, доказать эквивалентности ω + ω ∼ ω и Z n ∼ ω, n ∈ ω \ {0}. 1.4. МОЩНОСТЬ МНОЖЕСТВА 29 Предложение 1.4.4. ω ∼ ∪ n∈ω ω n . Доказательство. Так как для любого n ∈ ω существует биекция f n : ω ↔ ω n , то достаточно установить, что найдется биекция ϕ: ω ↔ µ ∪ 16n∈ω {(n, k) | k ∈ ω} ¶ ∪ {∅}, т. е. ϕ: ω ↔ {(n, k) | n, k ∈ ω, n > 1} ∪ {∅}. Биекция ϕ легко строится с помощью биекции ψ: ω ↔ ω 2 из предложения 1.4.3: ϕ(0) = ∅, ϕ(m+1) = (n + 1, k), где ψ(m) = (n, k), m ∈ ω. ¤ Предложение 1.4.5. |Q| = ω. Доказательство. Поскольку множество рациональных чисел Q состо- ит из дробей вида m n , где m ∈ Z, n ∈ ω \ {0}, его можно представить в ви- де множества пар (m, n). Так как множество таких пар содержится в Z 2 , а |Z 2 | = ω, то |Q| 6 ω. С другой стороны, очевидно, множество Q бес- конечно, т. е. |Q| > ω. По теореме Кантора—Бернштейна заключаем, что |Q| = ω. ¤ Теорема 1.4.6. Выполняется |P(U)| = 2 |U | для любого множества U. Доказательство. Очевидно, что любому подмножеству A ⊆ U взаим- но однозначно ставится в соответствие индикаторная функция f ∈ 2 U , для которой f (x) = ( 0, если x / ∈ A, 1, если x ∈ A, т. е. P(U) ∼ 2 U . Осталось заметить, что 2 |U | = |2 U |. ¤ Теорема 1.4.7 (теорема Кантора). Выполняется |U| < 2 |U | для любого множества U. Доказательство. В силу теоремы 1.4.6 достаточно доказать, что |U| < |P(U)|. Так как отображение f : U → P(U), действующее по прави- лу f (x) = {x}, является разнозначным, то |U| 6 |P(U)|. Предположим, что |U| = |P(U)|. Тогда существует биекция ϕ: U ↔ P(U). Рассмотрим множество K = {x ∈ U | x / ∈ ϕ(x)}. Поскольку ϕ — биекция и K ⊆ U, т. е. K ∈ P(U), то существует k ∈ U такое, что ϕ(k) = K. Если k ∈ K, то из определения K получаем k / ∈ ϕ(k) = K. Если же k / ∈ K, то k / ∈ ϕ(k), 30 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ и, следовательно, должно выполняться k ∈ K. Полученное противоречие показывает, что биекции ϕ существовать не может. ¤ Предложение 1.4.8. Если |A| > ω и |B| 6 ω, то |A \ B| = |A|. Доказательство. Так как |B| 6 ω, то |A ∩ B| 6 ω. Рассмотрим мно- жество C со следующими условиями: A ∩ B ⊂ C ⊂ A, |C \ (A ∩ B)| = ω. Такое множество C существует, поскольку по условию имеем |A \ B| > ω. Так как C = (C \ (A ∩ B)) ∪ (A ∩ B), то |C| = ω и существует биекция f : C \ (A ∩ B) ↔ C. Искомая биекция ϕ: A \ B ↔ A строится по следующим правилам: ϕ(x) = x, если x ∈ A \ C, ϕ(x) = f (x), если x ∈ C \ B. ¤ Предложение 1.4.9. 2 ω ∼ 10 ω ∼ ω ω . Доказательство. Поскольку неравенства 2 ω 6 10 ω 6 ω ω очевидны, достаточно доказать неравенство ω ω 6 2 ω , т. е. существование функ- ции ϕ: ω ω 1−1 −−→ 2 ω , которая кодирует всевозможные последовательности натуральных чисел с помощью последовательностей, состоящих из нулей и единиц. Для последовательности f ∈ ω ω определим последовательность ϕ(f ) ∈ 2 ω по следующим правилам: 1, 1, . . . , 1 | {z } f (0) раз , 0, 1, 1, . . . , 1 | {z } f (1) раз , 0, . . . , 1, 1, . . . , 1 | {z } f (n) раз , 0, . . . Очевидно, что если f 1 6= f 2 (f 1 , f 2 ∈ ω ω ), то ϕ(f 1 ) 6= ϕ(f 2 ). ¤ Предложение 1.4.10. R ∼ [0, 1]. Доказательство. Равенство мощностей отрезка I 1 = [0, 1] и интервала I 2 = (0, 1) обеспечивается биекцией ϕ: I 1 ↔ I 2 , задаваемой по следующему правилу: ϕ(x) = x, если x 6= 0, x 6= 1 n , n ∈ ω \ {0}, 1 2 , если x = 0, 1 3 , если x = 1, 1 n+2 , если x = 1 n , n > 1. В свою очередь, биекция ψ(x) = tg (π(x − 1 2 )) (рис. 1.8) определяет экви- валентность интервала I 2 и множества R. Следовательно, R ∼ [0, 1]. ¤ Предложение 1.4.11. Множество вещественных чисел R контину- ально. 1.5. МАТРИЦА БИНАРНОГО ОТНОШЕНИЯ 31 6 - O 1 2 y x 1 Рис. 1.8 Доказательство. В силу предложений 1.4.9 и 1.4.10 достаточно уста- новить, что 10 ω ∼ [0, 1]. Рассмотрим множество X = {f ∈ 10 ω | f (m) 6= 9 для некоторого m ∈ ω и существует k ∈ ω такое, что f (n) = 9 для всех n > k}. Так как множество 10 ω \ X взаимно однозначно соответствует множеству бесконечных десятичных дробей, задающих числа из [0, 1], то по теореме Кантора и предложению 1.4.8 остается показать, что множество X счетно. Нетрудно заметить, что множество X эквивалентно множеству ∪ n∈ω ω n , по- скольку каждая функция f ∈ X однозначно определяется кортежем цифр (f (0), . . . , f (k)), где f (k) 6= 9 и f (n) = 9 для всех n > k. Теперь из предло- жения 1.4.4 получаем X ∼ ∪ n∈ω ω n ∼ ω, т. е. |X| = ω. ¤ § 1.5. Матрица бинарного отношения. Специальные бинарные отношения Рассмотрим два конечных множества A = {a 1 , a 2 , . . ., a m }, B = {b 1 , b 2 , . . . , b n } и бинарное отношение P ⊆ A × B. Определим матрицу [P ] = (p ij ) размера m × n бинарного отношения P по следующему правилу: p ij = ( 1, если (a i , b j ) ∈ P, 0, если (a i , b j ) / ∈ P. 32 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Полученная матрица содержит полную информацию о связях между эле- ментами и позволяет представлять эту информацию на компьютере. Заме- тим, что любая матрица, состоящая из нулей и единиц, является матрицей некоторого бинарного отношения. Пример 1.5.1. Матрица бинарного отношения P ⊆ A 2 , A = {1, 2, 3}, заданного на рис. 1.9, имеет вид [P ] = 1 1 1 0 0 1 1 0 0 . ¤ Отметим основные свойства матриц бинарных отношений. 1. Если P, Q ⊆ A × B, [P ] = (p ij ), [Q] = (q ij ), то [P ∪ Q] = (p ij + q ij ) и [P ∩ Q] = (p ij · q ij ), где сложение осуществля- • • • - ¡ ¡ ¡ ¡ ¡ ¡ ª @ @ @ @ @ @ I@ @ @ @ @ @ R ¹¸ º· ¾ 1 2 3 Рис. 1.9 ется по правилам 0 + 0 0, 1 + 1 1 + 0 0 + 1 1, а умножение — обычным образом. Итак, [P ∪ Q] = [P ] + [Q], а матрица [P ∩ Q] по- лучается перемножением соответствующих эле- ментов из [P ] и [Q]: [P ∩ Q] = [P ] ∗ [Q]. Пример 1.5.2. Пусть [P ] = µ 1 0 1 0 1 1 ¶ , [Q] = µ 0 1 1 0 0 1 ¶ — матрицы отношений P и Q. Тогда [P ∪ Q] = [P ] + [Q] = µ 1 0 1 0 1 1 ¶ + µ 0 1 1 0 0 1 ¶ = µ 1 1 1 0 1 1 ¶ , [P ∩ Q] = [P ] ∗ [Q] = µ 1 0 1 0 1 1 ¶ ∗ µ 0 1 1 0 0 1 ¶ = µ 0 0 1 0 0 1 ¶ . ¤ 2. Если P ⊆ A × B, Q ⊆ B × C, то [P ◦ Q] = [P ] · [Q], где умножение матриц [P ] и [Q] производится по обычному правилу умножения матриц, но произведение и сумма элементов из [P ] и [Q] — по определенным в п. 1 правилам. 1.5. МАТРИЦА БИНАРНОГО ОТНОШЕНИЯ 33 Пример 1.5.3. Если [P ] = µ 0 1 0 1 1 0 ¶ , [Q] = 0 1 1 0 1 1 , то [P ◦ Q] = µ 0 1 0 1 1 0 ¶ · 0 1 1 0 1 1 = µ 1 0 1 1 ¶ . ¤ 3. Матрица обратного отношения P −1 равна транспонированной матрице отношения P : [P −1 ] = [P ] T 4. Если P ⊆ Q, [P ] = (p ij ), [Q] = (q ij ), то p ij 6 q ij 5. Матрица тождественного отношения id A единична: [id A ] = 1 0 · · · 0 0 1 · · · 0 0 0 · · · 1 . Пусть P — бинарное отношение на множестве A: P ⊆ A 2 . Отношение P называется рефлексивным, если (x, x) ∈ P для всех x ∈ A, т. е. id A ⊆ P , [P ] = 1 1 ∗ ∗ 1 . Если P ∩ id A = ∅, то отношение P называется антирефлексивным или ирре- флексивным. Отношение P называется симметричным, если для любых x, y ∈ A из (x, y) ∈ P следует (y, x) ∈ P , т. е. P −1 = P , или [P ] T = [P ]. Если P ∩ P −1 = ∅, то отношение P называется асимметричным. Отношение P называется антисимметричным, если из (x, y) ∈ P и (y, x) ∈ P следует, что x = y, т. е. P ∩ P −1 ⊆ id A . На языке матриц это означает, что в матрице [P ∩ P −1 ] = [P ]∗[P ] T все элементы вне главной диагонали являются нулевы- ми. Отношение P называется транзитивным, если из (x, y) ∈ P и (y, z) ∈ P следует (x, z) ∈ P , т. е. P ◦ P ⊆ P . 34 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Отметим, что антисимметричность не совпадает с несимметрично- стью. Действительно, отношение P = {(1, 2), (2, 3), (3, 2)} на множестве A = {1, 2, 3} не симметрично (так как (1, 2) ∈ P , а (2, 1) / ∈ P ) и не анти- симметрично (поскольку 2 6= 3, но (2, 3) ∈ P и (3, 2) ∈ P ). Тождественное отношение id A является одновременно симметричным и антисимметричным. Пример 1.5.4. Проверим, какими свойствами обла- • • • 6 ¡ ¡ ¡ ¡ ¡ ¡ µ - ±° ²¯ j 2 3 1 Рис. 1.10 дает отношение P ⊆ A 2 , A = {1, 2, 3}, изображенное на рис. 1.10. Составим матрицу отношения P : [P ] = 0 1 1 0 1 1 0 0 0 . Так как в матрице [P ] на главной диагонали имеются ну- левые элементы, отношение P не рефлексивно. Несиммет- ричность матрицы [P ] означает, что отношение P не симметрично. Для проверки антисимметричности вычислим матрицу [P ∩ P −1 ] = [P ] ∗ [P ] T Имеем [P ] ∗ [P ] T = 0 1 1 0 1 1 0 0 0 ∗ 0 0 0 1 1 0 1 1 0 = 0 0 0 0 1 0 0 0 0 . Поскольку в полученной матрице все элементы, стоящие вне главной диа- гонали, нулевые, отношение P антисимметрично. Так как [P ◦ P ] = [P ] (проверьте!), то P ◦ P ⊆ P , т. е. P является транзитивным отношением. ¤ Пример 1.5.5. Отношение < {(x, y) | x, y ∈ Q и x < y} на множестве рациональных чисел Q не рефлексивно, не симметрично, антисимметрично и транзитивно. ¤ Пример 1.5.6. Рассмотрим отношение P = {(x, y) | x, y ∈ Z и x − y < 1} на множестве целых чисел Z. Так как x − x = 0 < 1 для любого x ∈ Z, отношение P рефлексивно. Поскольку (2, 4) ∈ P , а (4, 2) / ∈ P , отношение P не симметрично. Заметим, что если x − y < 1 и y − x < 1, то x = y, так как из x 6= y следует |x − y| > 1. Таким образом, отношение P антисимметрично. Предположим теперь, что (x, y), (y, z) ∈ P , т. е. x − y < 1 и y − z < 1. Имеем x 6 y и y 6 z, тогда x 6 z, значит, x − z < 1, т. е. (x, z) ∈ P . Следовательно, отношение P транзитивно. ¤ 1.6. ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ И РАЗБИЕНИЯ 35 § 1.6. Отношения эквивалентности и разбиения. Фактор-множества Отношение P называется отношением эквивалентности (эквивалентно- стью), если P рефлексивно, симметрично и транзитивно. Эквивалентности часто обозначают символами E и ∼ (тильда): x E y, x ∼ y. Пример 1.6.1. 1. Отношение равенства x = y является эквивалентно- стью на любом множестве A, так как оно рефлексивно (x = x), симметрично (x = y ⇒ y = x) и транзитивно (x = y, y = z ⇒ x = z). 2. Отношение подобия на множестве треугольников есть отношение эк- вивалентности. 3. На любом множестве P(U) отношение равномощности |A| = |B| является отношением эквивалентности (см. § 1.4). 4. Отношение принадлежности к одной студенческой группе на множе- стве студентов НГТУ — отношение эквивалентности. 5. Рассмотрим множество M программ, вычисляющих некоторые функ- ции. Отношение E = {(x, y) | программы x и y вычисляют одну и ту же функцию} является эквивалентностью. ¤ Пусть E — эквивалентность на множестве A. Классом эквивалентно- сти элемента x ∈ A называется множество E(x) {y | x E y}. Клас- сы эквивалентности E будут также называться E-классами. Множество A/E {E(x) | x ∈ A} называется фактор-множеством множества A по от- ношению E. Пример 1.6.2. 1. Для отношения равенства = на множестве A каждый =-класс состоит только из одного элемента: =(x) = {x} для любого x ∈ A. Таким образом, фактор-множество A/= имеет вид {{x} | x ∈ A} и, следова- тельно, биективно множеству A. 2. Для отношения принадлежности к одной студенческой груп- пе классом эквивалентности является множество студентов одной группы. Фактор-множество множества студентов НГТУ по этому отношению экви- валентности представляет собой множество студенческих групп НГТУ. ¤ Предложение 1.6.1. Множество A/E является разбиением множе- ства A. Обратно, если R = {A i } — некоторое разбиение множества A, то можно задать соответствующее ему отношение эквивалентности E по следующему правилу: x E y ⇔ x, y ∈ A i для некоторого i. 36 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Доказательство. Пусть E — отношение эквивалентности на множе- стве A; A/E — фактор-множество множества A по E. Так как в силу ре- флексивности отношения E выполнимо x ∈ E(x) для любого x ∈ A, то каждое множество из A/E непусто и ∪ x∈A E(x) = A. Чтобы установить, что A/E — разбиение множества A, осталось показать, что если E(x)∩E(y) 6= ∅, то E(x) = E(y). Пусть z ∈ E(x) ∩ E(y) и u ∈ E(x), т. е. (x, z), (y, z), (x, u) ∈ E. Так как отношение E симметрично, (z, x) ∈ E. Тогда из транзитивности отношения E следует (y, u) ∈ E, т. е. u ∈ E(y). Таким образом, E(x) ⊆ E(y). Включение E(y) ⊆ E(x) доказывается аналогично. Предположим, что E — отношение на множестве A, соответствующее разбиению R = {A i }. Рефлексивность и симметричность E очевидны. Пусть теперь x E y и y E z. Тогда x, y ∈ A i , y, z ∈ A j , где A i , A j ∈ R. Поскольку y ∈ A i и y ∈ A j , то A i = A j . Следовательно, x, z ∈ A i и x E z. ¤ Таким образом, существует биекция между множеством всех отноше- ний эквивалентности на множестве A и множеством всех разбиений мно- жества A. В любом классе E(x) эквивалентности E каждый элемент y ∈ E(x) свя- зан отношением E с любым элементом z ∈ E(x). Поэтому если E — эк- вивалентность на конечном множестве A, A/E = {E(x 1 ), . . . , E(x n )}, E(x i ) = {b i 1 , . . . , b i m i }, i = 1, . . . , n, и множество A перенумеровано в следу- ющем порядке: b 1 1 , . . . , b 1 m 1 , b 2 1 , . . . , b 2 m 2 , . . . , b n 1 , . . . , b n m n , то матрица [E] имеет блочно-диагональный вид: [E] = m 1 m 2 m n z}|{ z}|{ z}|{ m 1 n m 2 n m n n 1 0 1 0 1 , где блоки 1 состоят из единиц, а остальные элементы равны 0. Если же множество A перенумеровано произвольным образом: A = {a 1 , . . . , a n }, E — отношение эквивалентности на A, то матрица [E] = (e ij ) приводится к блочно-диагональному виду некоторыми одновре- 1.7. ОТНОШЕНИЯ ПОРЯДКА 37 менными перестановками строк и столбцов. Элементы a i и a j эквивалентны по отношению E тогда и только тогда, когда i-я и j-я строки (а также столб- цы) матрицы [E] совпадают. Класс эквивалентности E(a i ) состоит из элемен- тов a j , для которых e ij = 1. Пример 1.6.3. Рассмотрим множество A = {1, 2, 3, 4, 5} с разбиением R = {{1, 3, 5}, {2, 4}}, задающим отношение эквивалентности E с двумя E- классами {1, 3, 5} и {2, 4}. Матрица [E] имеет вид 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 . По этой матрице легко определить, что класс E(3) равен {1, 3, 5}, так как в 3-й строке только e 31 , e 33 и e 35 равны 1. ¤ Пример 1.6.4. Рассмотрим геометрическое векторное пространство E 3 и множество направленных отрезков в нем. Направленные отрезки −−−→ A 1 B 1 и −−−→ A 2 B 2 называются эквивалентными: −−−→ A 1 B 1 ∼ −−−→ A 2 B 2 , если они имеют одина- ковые длину и направление. Отношение ∼ — это отношение эквивалентно- сти. Вектором (геометрическим вектором) − → a в E 3 называется класс экви- валентности направленных отрезков ∼ ( −→ AB) для некоторого −→ AB. Фактор- множество множества направленных отрезков по отношению ∼ образует множество векторов пространства E 3 . ¤ § 1.7. Отношения порядка Отношение эквивалентности является обобщением отношения равенства: эквивалентные элементы считаются “равными”. Обобщением обычного отно- шения 6 служат отношения порядка. Отношение P ⊆ A 2 называется предпорядком или квазипорядком, если P рефлексивно и транзитивно. Пример 1.7.1. Отношение P = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3), (1, 3)} на множестве {1, 2, 3} является предпорядком (рис. 1.11). ¤ 38 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Отметим, что симметричный предпорядок является отношением эквива- лентности. Отношение P ⊆ A 2 называется частичным по- • • • @ @ @ @ R - * ¼ m ¼ m ¸ m K 2 1 3 Рис. 1.11 рядком, если P рефлексивно, транзитивно и анти- симметрично. Таким образом, частичный порядок — это антисимметричный предпорядок. Частичный по- рядок обычно обозначается символом 6, а обратное ему отношение 6 −1 — символом >. Отношение > так- же является частичным порядком и называется двой- ственным порядку 6. Используя отношение 6, определим отношение <, называемое строгим порядком, по следующему правилу: x < y ⇔ x 6 y и x 6= y. Заметим, что отношение строгого порядка не является частичным порядком, так как не выполняется условие рефлексивности (неверно, что x < x). Пример 1.7.2. Частичным порядком является • • • - j j j ¼ ¼ ¼ a b c Рис. 1.12 обычное отношение 6 на множестве N. Действитель- но, это отношение рефлексивно (x 6 x), транзитив- но (x 6 y, y 6 z ⇒ x 6 z) и антисимметрично (x 6 y, y 6 x ⇒ x = y). ¤ Пример 1.7.3. Отношение, изображенное на рис. 1.12, является частичным порядком, а отношение из примера 1.7.1 — нет. ¤ Пример 1.7.4. Отношение включения ⊆ на булеане P(U) образует ча- стичный порядок. ¤ Заметим, что в примерах 1.7.3 и 1.7.4 имеются элементы x и y, про ко- торые нельзя сказать, что x 6 y или y 6 x (например, при a = x, y = c из примера 1.7.3). Такие элементы называются несравнимыми. Частичный порядок 6 ⊆ A 2 называется линейным порядком, если любые два элемен- та x и y из множества A сравнимы, т. е. x 6 y или y 6 x (линейным является частичный порядок из примера 1.7.2). Непустое множество A, на котором зафиксирован некоторый частичный (линейный) порядок, называется частично (линейно) упорядоченным мно- жеством (сокращенно ч.у.м. или л.у.м.). Пример 1.7.5. Пары hω; 6i, h[0, 1]; 6i с обычными отношениями 6 об- разуют линейно упорядоченные множества. ¤ 1.7. ОТНОШЕНИЯ ПОРЯДКА 39 Пусть hA; 6i — частично упорядоченное множество. Определим на мно- жестве A 2 отношение Π условием (a 1 , b 2 ) Π (a 2 , b 2 ) ⇔ a 1 6 a 2 и b 1 6 b 2 . Отношение Π есть отношение частичного порядка. Оно называется отноше- нием Парето. Пара hA 2 ; Πi образует частично, но не линейно упорядоченное множество, если |A| > 1. Элемент a ∈ A частично упорядоченного множества A = hA; 6i называ- ется максимальным (минимальным), если для всех x ∈ A из a 6 x (x 6 a) следует x = a. Элемент a ∈ A называется наибольшим (наименьшим), если x 6 a (a 6 x) для всех x ∈ A. Наибольший (наименьший) элемент ч.у.м. A (если он существует) обозначается через max A (min A). Наибольший эле- мент часто называют единицей, а наименьший — нулем множества A. За- метим, что всякий наибольший элемент является максимальным, а всякий наименьший элемент — минимальным. Обратное утверждение, вообще гово- ря, неверно (см. пример 1.7.6). Всякое конечное ч.у.м. содержит как макси- мальные, так и минимальные элементы. Пример 1.7.6. Частично упорядоченное множе- • • • ³³ ³³ ³³ ³³ 1 PPP PPP PP q i i i ¸ ¸ K 1 3 2 Рис. 1.13 ство h{1, 2, 3}; 6i, изображенное на рис. 1.13, имеет наибольший элемент 2, минимальные элементы 1, 3, но не имеет наименьшего элемента. ¤ Пример 1.7.7. Линейно упорядоченное множе- ство h[0, 1); 6i имеет наименьший элемент 0, но не имеет наибольшего элемента. ¤ Пусть A = hA; 6i — ч.у.м., B — подмножество A. Элемент a ∈ A называ- ется верхней (нижней) гранью множества B и пишут B 6 a (соответственно a 6 B), если b 6 a (a 6 b) для всех b ∈ B. Пример 1.7.8. Рассмотрим ч.у.м. hR; 6i и интервал B = (0, 1]. Тогда любое число x > 1 является верхней гранью B, а любое число x 6 0 — нижней гранью B. ¤ Элемент a ∈ A называется точной верхней гранью (супремумом) мно- жества B (обозначается sup B), если a — наименьшая из верхних граней множества B. Элемент a ∈ A называется точной нижней гранью (инфиму- мом) множества B (обозначается inf B), если a — наибольшая из нижних граней множества B. 40 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ В примере 1.7.8 имеем sup B = 1, inf B = 0. Линейный порядок 6 на множестве A называется полным, если каж- дое непустое подмножество множества A имеет наименьший элемент. Пара hA; 6i, в которой отношение 6 является полным порядком на множестве A, называется вполне упорядоченным множеством (сокращенно в.у.м.). Пример 1.7.9. Пара hω; 6i является в.у.м., а пара h[0, 1]; 6i — нет, поскольку, например, полуоткрытый интервал (1/2, 1], являющийся подмно- жеством [0, 1], не содержит наименьшего элемента. ¤ Определим отношение, на котором основано упорядочение слов в словарях. Рассмотрим непустое множество символов X = {x, y, z, . . .}, называемое алфавитом. Конечные наборы написанных друг за другом символов из X называются словами (например, x, y, xy, yx, zxx, xyyz и т. д.). Элемент x i слова x 1 x 2 . . . x n называется его i-й координатой. Число n называется длиной слова x 1 x 2 . . . x n . Множество слов алфавита X обозначим через W (X). При этом будем считать, что W (X) содержит слово Λ, не имеющее символов и называемое пустым словом. Длина пустого слова Λ по определению равна нулю. Заметим, что каждое слово x 1 x 2 . . . x n из W (X) взаимно однозначно соответствует упорядоченному набору hx 1 , x 2 , . . . , x n i из X n . Следовательно, множество W (X) биективно множеству ∪ n∈ω X n , и, значит, бесконечно. Пусть 6 — отношение порядка на множестве X. Определим на множестве W (X) отношение лексикографического порядка L по следующему правилу: x 1 x 2 . . . x m L y 1 y 2 . . . y n ⇔ (m 6 n и x i = y i для всех 1 6 i 6 m) или (суще- ствует i 6 m такое, что x i < y i , и для всех j < i выполняется x j = y j ). Утверждение 1.7.1. Если hX; 6i — л.у.м., то hW (X); Li — л.у.м. Доказательство. Рефлексивность и транзитивность отношения L очевидны. Для проверки антисимметричности предположим, что x 1 x 2 . . . x m L y 1 y 2 . . . y n и y 1 y 2 . . . y n L x 1 x 2 . . . x m . Так как отношение 6 антисимметрично, не существует i такого, что x i 6= y i и x j = y j для всех j < i. Тогда по определению отношения L получаем m 6 n, n 6 m, т. е. m = n, и x 1 x 2 . . . x m = y 1 y 2 . . . y n . Покажем теперь, что любые два слова ˆ X = x 1 x 2 . . . x m и ˆ Y = y 1 y 2 . . . y n сравнимы. Пусть i — максимальный индекс, такой, что x j = y j для всех j < i. Если x i < y i или i = m + 1 6 n, то ˆ X L ˆ Y . Если y i < x i или i = n + 1 6 m, то ˆ Y L ˆ X. Если же указанные случаи не выполняются, то m = n = i − 1 и ˆ X = ˆ Y . ¤ 1.7. ОТНОШЕНИЯ ПОРЯДКА 41 Как показывает следующий пример, если |X| > 2, система hW (X); Li не является в.у.м. Пример 1.7.10. Рассмотрим в.у.м. hX; 6i, где X = {0, 1}, 6 = {(0, 0), (0, 1), (1, 1)}. Бесконечное множество, состоящее из слов 1, 01, 001, . . . , 00 . . . 01, . . . не имеет наименьшего элемента по отношению L. Следовательно, система hW (X); Li не является в.у.м. ¤ Обозначим через W n (X) множество слов алфавита X, длина которых не превосходит n, через L n — ограничение отношения L на множество W n (X): L n L ∩ (W n (X)) 2 Утверждение 1.7.2. Если hX; 6i — в.у.м., то hW n (X); L n i — в.у.м. для любого n ∈ ω. Доказательство. В силу утверждения 1.7.1 достаточно показать, что любое непустое подмножество Y множества W n (X) имеет наименьший элемент по отношению L n . Если Λ ∈ Y , то Λ является наименьшим эле- ментом. Предположим теперь, что Λ / ∈ Y . Рассмотрим множество Y 1 ⊆ Y , состоящее из слов, у которых первая координата является наименьшей среди первых координат слов из Y . Если Y 1 содержит слово длины 1, то оно будет наименьшим элементом множества Y . В противном случае рассмотрим мно- жество Y 2 ⊆ Y 1 , состоящее из слов, у которых вторая координата является наименьшей среди вторых координат слов из Y 1 . Если Y 2 содержит слово длины 2, то оно будет наименьшим элементом множества Y . В противном случае аналогично определим множество Y 3 и будем продолжать построение множеств Y k до тех пор, пока в Y k не найдется слово длины k, которое будет наименьшим элементом множества Y . По определению множества W n (X) такое слово определится не более чем за n шагов. ¤ Пример 1.7.11. Рассмотрим множество букв русского алфавита, кото- рое обозначим через A. Определим на A полный порядок 6 в соответствии с обычным упорядочением букв по алфавиту. Пусть n — натуральное чис- ло, ограничивающее длину слов, употребляемых в русском языке, например n = 1000. Отношение L n на множестве W n (A) определяет упорядочение слов, по которому составляются словари. ¤ 42 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Рассмотрим частично упорядоченное множество hA; 6i. Говорят, что эле- мент y покрывает элемент x (обозначается x ≺ y), если x 6 y и не су- ществует такого элемента z, что x < z < y. Если множество A конечно, частично упорядоченное множество hA; 6i можно представить в виде схе- мы, в которой каждый элемент изображается точкой на плоскости, и если y покрывает x, то точки x и y соединяют отрезком, причем точку, соответ- ствующую x, располагают ниже y. Такие схемы называются диаграммами Хассе. На рис. 1.14 показаны две диаграммы Хассе. Вторая диаграмма со- ответствует линейно упорядоченному множеству. Пример 1.7.12. 1. Рассмотрим частично упорядо- • • • • • • ¡ ¡ ¡ @ @ @ ¡ ¡ ¡ @ @ @ • • • • • а б Рис. 1.14 ченное множество hP(A); ⊆i, где A = {1, 2, 3}. Множе- ство P(A) содержит восемь элементов: {0, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. На рис. 1.15a изображена диаграмма Хассе, соответствующая hP(A); ⊆i. 2. Пусть A = {1, 2, 3, 5, 6, 10, 15, 30}. Рассмотрим отношение частичного порядка 6 на множестве A, зада- ваемое по правилу: x 6 y ⇔ y делится на x. Диаграмма Хассе для ч.у.м. hA; 6i изображена на рис. 1.15б. 3. На рис. 1.15в изображена диаграмма Хассе линейно упорядоченного множества h{0, 1, 2, 3, 4, 5, 6, 7}; 6i c обычным отношением порядка на мно- жестве натуральных чисел, не превосходящих семи. ¤ • • • • • • • • ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ @ @ @ @ @ @ @ @ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ @ @ @ @ @ @ @ @ ∅ {1} {2} {3} {1,2} {2,3} {1,3} {1,2,3} • • • • • • • • ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ @ @ @ @ @ @ @ @ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ @ @ @ @ @ @ @ @ 1 2 3 5 6 10 15 30 • • • • • • • • 0 1 2 3 4 5 6 7 а б в Рис. 1.15 1.7. ОТНОШЕНИЯ ПОРЯДКА 43 Заметим, что диаграммы Хассе, изображенные на рис. 1.15а и б, сов- падают. Это означает, что эти частично упорядоченные множества имеют одинаковую структуру, причем отличную от структуры третьего ч.у.м., хотя оно тоже содержит восемь элементов. Формально такая общность структуры определяется понятием изоморфизма. Пусть A = hA; 6 A i, B = hB, 6 B i — частично упорядоченные множества. Отображение f : A → B называется изоморфизмом частично упорядоченных множеств A и B, если выполняются следующие условия: 1) f — биекция между множествами A и B; 2) для любых a 1 , a 2 ∈ A, a 1 6 A a 2 тогда и только тогда, когда f (a 1 ) 6 B f (a 2 ). Если существует изоморфизм между A и B, то частично упорядоченные множества A и B называются изоморфными и этот факт обозначается через A ' B. Теорема 1.7.3. Всякое частично упорядоченное множество A = hA; 6i изоморфно некоторой системе подмножеств множества A, частично упорядоченной отношением включения. Доказательство. Для каждого элемента a ∈ A рассмотрим множество S a = {x ∈ A | x 6 a}. Тогда S a ⊆ A и Y = {S a | a ∈ A} — совокупность всех таких подмножеств. Докажем, что ч.у.м. A изоморфно ч.у.м. hY ; ⊆i. Рассмотрим отображение ϕ: A → Y такое, что ϕ(a) = S a . Отображение ϕ инъективно. Действительно, если S a = S b , то a ∈ S b и b ∈ S a , значит, a 6 b и b 6 a, откуда по антисимметричности отношения 6 получаем a = b. Отоб- ражение ϕ сюръективно, так как у любого подмножества S a есть прообраз a. Докажем, что ϕ сохраняет отношение частичного порядка. Предположим, что a 6 b. Тогда из x 6 a в силу транзитивности отношения 6 следует x 6 b, и, значит, S a ⊆ S b . Напротив, если S a ⊆ S b , то, поскольку a ∈ S a , имеем a ∈ S b , откуда a 6 b. ¤ Пусть A = hA; 6i — ч.у.м., a — элемент множества A. Открытым (замкнутым) начальным сегментом множества A называется множество O(a, A) {x ∈ A | x < a} (соответственно O[a, A] {x ∈ A | x 6 a}), в ко- тором определено отношение 6 0 , являющееся ограничением отношения 6 из A: b 1 6 0 b 2 тогда и только тогда, когда b 1 6 b 2 в A. Теорема 1.7.4. Если A и B — в.у.м., то A изоморфно некоторому на- чальному сегменту множества B или B изоморфно некоторому началь- ному сегменту множества A. ¤ 44 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ § 1.8. Аксиомы теории множеств Сейчас у нас имеются все средства, чтобы сформулировать систему ак- сиом теории множеств ZFC, в рамках которой можно изложить все обще- принятые в современной математике способы рассуждений и не проходит ни один из известных теоретико-множественных парадоксов. Эта система поз- воляет строить все математические объекты исходя из пустого множества. Представим систему аксиом Цермело—Френкеля (ZF). 1. Аксиома существования пустого множества: Существует пустое множество ∅. 2. Аксиома существования пары: Если существуют множества a и b, то существует множество {a, b}. 3. Аксиома суммы: Если существует множество X, то существует множество ∪X {a | a ∈ b для некоторого b ∈ X}. 4. Аксиома бесконечности: Существует множество ω {0, 1, . . . , n, . . .}, где 0 ∅, n+1 n∪{n}. 5. Аксиома множества всех подмножеств: Если существует множество A, то существует множество P(A) {B | B ⊆ A}. 6. Аксиома замены: Если P (x, y) — некоторое условие на множества x, y, такое, что для любо- го множества x существует не более одного множества y, удовлетворяющего P (x, y), то для любого множества a существует множество {b | P (c, b) для некоторого c ∈ a}. 7. Аксиома экстенсиональности: Два множества, имеющие одинаковые элементы, равны, т. е. любое мно- жество определяется своими элементами: A = B ⇔ ∀x (x ∈ A ⇔ x ∈ B). 1.8. АКСИОМЫ ТЕОРИИ МНОЖЕСТВ 45 8. Аксиома регулярности: Всякое непустое множество x имеет элемент a ∈ x, для которого a∩x = ∅. Из аксиомы регулярности следует, что каждое множество получается на некотором шаге “регулярного процесса” образования множества всех под- множеств, начинающегося с ∅ и подобного построению натуральных чисел из пустого множества по аксиоме бесконечности. Это означает, что любой элемент любого множества является множеством, сконструированным из пу- стого множества. Покажем, как аксиоматика ZF позволяет определять теоретико-множес- твенные операции. Пример 1.8.1. 1. Определим множество A ∪ B исходя из множеств A и B. По аксиоме существования пары образуется множество {A, B}. С помо- щью аксиомы суммы получаем множество ∪{A, B}, которое по определению совпадает с множеством A ∪ B. 2. Пересечение A ∩ B множеств A и B определяется по аксиоме замены с помощью следующего свойства P (x, y): x = y и x ∈ A. Имеем множество {b | P (c, b) и c ∈ B} = {b | c = b, c ∈ A и c ∈ B} = {c | c ∈ A и c ∈ B} = A∩B. 3. Покажем, что из аксиом 5 и 6 следует существование множества A 2 = {(a, b) | a, b ∈ A} для любого множества A. Так как (a, b) = {{a}, {a, b}}, то A 2 ⊆ P(P(A)). Пусть свойство P (x, y) означает, что существуют такие a, b ∈ A, что x = {{a}, {a, b}} и y = x. Тогда множество A 2 равно {b | P (c, b), c ∈ P(P(A))} и по аксиоме 6 оно существует. ¤ Система аксиом ZFC образуется из ZF добавлением одной из следующих двух эквивалентных аксиом, которые, с одной стороны, являются наименее “очевидными”, а с другой — наиболее содержательными. 1. Аксиома выбора: Для любого непустого множества A существует такое отображение ϕ: P(A) \ {∅} → A, что ϕ(X) ∈ X для любого непустого множества X ⊆ A. 2. Принцип полного упорядочения: Для любого непустого множества A существует бинарное отношение 6 на A, для которого hA; 6i — в.у.м. В системе ZFC справедлив принцип трансфинитной индукции, являю- щийся обобщением принципа полной индукции: если hA; 6i — вполне упо- 46 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ рядоченное множество, P (x) — некоторое свойство, то справедливость свой- ства P (x) на всех элементах x ∈ A следует из того, что для любого z ∈ A выполнимость свойства P на элементах y, где y < z, влечет выполни- мость P (z): ∀z ³¡ (∀y < z) P (y) ¢ ⇒ P (z) ´ ∀x P (x) . Задачи и упражнения 1. Доказать, что {∅} 6= ∅. 2. Доказать, что {{0, 1}, {0, 2}} 6= {0, 1, 2}. 3. Доказать, что существует лишь одно множество, не имеющее элементов. 4. Существуют ли множества A, B и C, для которых A ∩ B 6= ∅, A ∩ C = ∅, (A ∩ B) \ C = ∅? 5. Доказать, что (A ∪ B) = A ∩ B. 6. Доказать основные теоретико-множественные тождества 1–8 (см. с. 14). 7. Решить систему уравнений: а) ( A ∩ X = B, A ∪ X = C, где A, B и C — данные множества и B ⊆ A ⊆ C; б) ( A \ X = B, X \ A = C, где A, B и C — данные множества и B ⊆ A, A ∩ C = ∅; в) ( A \ X = B, A ∪ X = C, где A, B и C — данные множества и B ⊆ A ⊆ C; г) ( A ∪ X = B ∩ X, A ∩ X = C ∪ X; д) ( A \ X = X \ B, X \ A = C \ X; е) ( A ∩ X = B \ X, C ∪ X = X \ A. ЗАДАЧИ И УПРАЖНЕНИЯ 47 8. Построить пример множеств A и B таких, что A × B 6= B × A. 9. Пусть [0, 1], [0, 2] — отрезки на числовой прямой. Дать геометрическую интерпретацию множеств [0, 1] × [0, 2], [0, 1] 2 , [0, 2] 3 10. Изобразить отношения P = {(a, 1), (a, 2), (b, 2), (b, 3), (c, 1), (c, 4)} и Q = {(1, α), (2, β), (3, α)}. Найти δ Q , ρ Q , P ◦ Q, [P ], [Q], [P ◦ Q]. 11. Для отношений P = {(x, y) ∈ R 2 | x = y 2 } и Q = {(x, y) ∈ R 2 | x · y > 0} найти P ◦ Q, Q ◦ P , P ◦ P и P −1 12. Пусть A и B — конечные множества мощности m и n соответственно. Найти: а) число бинарных отношений между элементами множеств A и B; б) число функций из A в B; в) число инъекций из A в B; г) число биекций из A в B. 13. Доказать следующие эквивалентности: а) A × B ∼ B × A; б) (A × B) C ∼ A C × B C 14. Доказать, что: а) если A — конечное множество, B — подмножество множества A, то множество B конечно; б) если A 1 , . . . , A n — конечные множества, то множества A 1 ∪ . . . ∪ A n и A 1 × . . . × A n конечны. 15. Доказать, что если A — счетное множество, B — конечное множество, то множество A \ B счетно. 16. Доказать, что если множества A i , i ∈ ω, счетны, то множество ∪ i∈ω A i счетно. 17. Доказать, что если A — счетное множество, то множество ∪ n∈ω A n всех конечных последовательностей, составленных из элементов множества A, счетно. 18. Доказать, что множество всех многочленов от одной переменной с ра- циональными коэффициентами счетно. 19. Доказать, что множества точек отрезка и квадрата эквивалентны. 48 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ 20. Доказать, что n 3 − n делится на 3 для любого n ∈ ω. 21. Доказать, что имеют место следующие равенства: а) 1 + 3 + 5 + . . . + (2n − 1) = n 2 ; б) 1 + 4 + 7 + . . . + (3n − 2) = 3n 2 − n 2 ; в) 1 + a + a 2 + . . . + a n−1 = 1 − a n 1 − a , a ∈ R \ {1}. 22. Доказать, что имеют место следующие неравенства: а) n 2 > 2n + 1, n ∈ ω, n > 3; б) 2 n > n 2 , n ∈ ω, n > 5; в) n! > n 3 , n ∈ ω, n > 6; г) 4 n n + 1 < (2n)! (n!) 2 , n ∈ ω, n > 2. 23. Найти множество всех натуральных чисел, для которых истинно нера- венство n! < 2 n 24. Доказать, что каждое натуральное число n > 8 может быть представ- лено в виде n = 3k + 5l, k, l ∈ ω. 25. Найти ошибку в доказательстве того, что все лошади имеют одинако- вую масть. Доказательство. Покажем с помощью математической индукции, что любые n лошадей имеют одну и ту же масть. При n = 1 имеет- ся лишь одна лошадь, и поэтому она имеет ту же масть, как она сама. Рассмотрим теперь индукционное предположение, состоящее в том что любые n лошадей имеют одинаковую масть, и установим, что имеют одну и ту же масть любые n + 1 лошадей. Предположим, что в загон помещена (n+1)-я лошадь. Выведем из загона одну лошадь. Поскольку теперь в загоне n лошадей, по индукционному предположению все они имеют одинаковую масть. Вернем выведенную лошадь в загон и выве- дем другую лошадь. Снова в загоне n лошадей, и все они имеют од- ну масть. Следовательно, все рассматриваемые лошади имеют ту же масть, что и те лошади, которые были выведены. Поэтому все n + 1 лошадей имеют одинаковую масть. В силу принципа математической индукции все лошади имеют одну и ту же масть. ¤ ЗАДАЧИ И УПРАЖНЕНИЯ 49 26. Построить бинарное отношение: а) рефлексивное, симметричное, не транзитивное; б) не рефлексивное, антисимметричное, не транзитивное; в) рефлексивное, не симметричное, транзитивное. 27. Пусть L — множество всех прямых на плоскости. Являются ли экви- валентностями следующие отношения: а) отношение параллельности двух прямых; |