Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 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). 28 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Определим по индукции операции сложения 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) . 1.4. МОЩНОСТЬ МНОЖЕСТВА 29 Другой эквивалентной формой принципа математической индукции яв- ляется принцип полной индукции: если для всякого 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 ω и т. д. 30 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Эти числа можно рассматривать как имена, обозначающие соответствую- щие мощности. Кардинальным числом конечного множества служит число его элементов. Существование биекции между двумя эквивалентными множествами поз- воляет переносить изучение свойств с одного множества на другое, когда природа элементов не важна. Например, если |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|, 1.4. МОЩНОСТЬ МНОЖЕСТВА 31 где 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}. 32 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Предложение 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), 1.4. МОЩНОСТЬ МНОЖЕСТВА 33 и, следовательно, должно выполняться 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 контину- ально. 34 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ 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 остается показать, что множество |