Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
{ √ 2 + i √ 2}, X 22 = {z 1 , z 2 } (z 1 , z 2 ∈ Z), X 23 = Z, X 24 = Z ∪ { . ı}, X 25 = R∪ { . ı}; B 1 = hω; +i, B 2 = hZ; +i, B 3 = hZ; +, −i, B 4 = hZ; ·i, B 5 = hQ; +i, B 6 = hQ; ·i, B 7 = hQ \ {0}; ·, :i, B 8 = hR; 3 √ i, B 9 = hC; +i, B 10 = hC; ·i, B 11 = hC; ·, 2i, B 12 = hC; +, ·i. Для множеств X i ⊆ B j построить подсистемы B j (X i ), i = 1, . . . , 25, j = 1 . . . , 12. 10. Рассмотрим алгебру A = h{a, b, c, d, e}; ·i, определенную следующей таблицей Кэли: · a b c d e a c d a b e b d c b b e c a a b a c d b a a b d e a b e e c Какое из следующих разбиений образует конгруэнцию на алгебре A: а) {{a, b, c}, {d, e}}; б) {{a, b}, {c, d}, {e}}? Построить фактор-алгебру алгебры A по найденной конгруэнции. 11. Доказать, что любое л.у.м. является решеткой. 12. Доказать, что в решетке максимальный элемент является наибольшим, а минимальный — наименьшим. 13. Построить пример решетки с наибольшим элементом, но без наименьшего. 14. Построить булеву алгебру подмножеств трехэлементного (четырехэлемент- ного) множества. 15. Для терма x ∨ (y ∧ z) булевой алгебры найти соответствующий терм в буле- вом кольце. Глава 3 ЧИСЛОВЫЕ СИСТЕМЫ § 3.1. Бесконечные числовые системы 1. Системы Дедекинда—Пеано Как отмечалось в § 1.3, множество натуральных чисел можно определять двояко: 1) исходя из ∅ последовательно выражать натуральные числа как мно- жества, состоящие из предыдущих натуральных чисел; 2) задавать алгебраическую систему N = hN; 0, 0 i, удовлетворяющую си- стеме аксиом Дедекинда—Пеано. В дальнейшем мы будем рассматривать второй подход и называть такие системы системами Дедекинда—Пеано. Теорема 3.1.1 (теорема Дедекинда—Пеано). Любые две системы Деде- кинда—Пеано изоморфны. ¤ В § 1.3 показано, что по индукции в системе N однозначно определимы двухместные операции сложения и умножения. В дальнейшем через N будем обозначать систему Дедекинда—Пеано с этими операциями: hN; 0, 0 , +, ·i. 2. Кольцо целых чисел Определим с помощью системы N кольцо целых чисел Z = hZ; +, ·i. Рассмотрим множество N 2 = {(a, b) | a, b ∈ N} и зададим отношение ∼ по следующему правилу: (a, b) ∼ (c, d) ⇔ a + d = b + c. 3.1. БЕСКОНЕЧНЫЕ ЧИСЛОВЫЕ СИСТЕМЫ 77 Положим (a, b) + (c, d) (a + c, b + d), (a, b) · (c, d) (a · c + b · d, a · d + b · c). Лемма 3.1.2. Отношение ∼ является конгруэнцией на алгебре hN 2 ; +, ·i. Доказательство. Покажем сначала, что ∼ является отношением экви- валентности. Действительно, ∼ рефлексивно, так как из a+b = b+a следует (a, b) ∼ (a, b). Из симметричности отношения равенства и (a, b) ∼ (c, d) сле- дует (c, d) ∼ (a, b), т. е. отношение ∼ симметрично. Установим теперь, что отношение ∼ транзитивно. Предположим, что (a 1 , b 1 ) ∼ (a 2 , b 2 ) и (a 2 , b 2 ) ∼ (a 3 , b 3 ). Тогда по опреде- лению выполняются равенства a 1 + b 2 = a 2 + b 1 и a 2 + b 3 = a 3 + b 2 . Складывая равенства, имеем a 1 + b 2 + a 2 + b 3 = a 2 + b 1 + a 3 + b 2 , отсюда a 1 + b 3 = a 3 + b 1 , т. е. (a 1 , b 1 ) ∼ (a 3 , b 3 ). Таким образом, ∼ — отношение эквивалентности. Докажем, что отношение ∼ согласовано с операциями + и ·. Предполо- жим (a 1 , b 1 ) ∼ (a 2 , b 2 ) и (c 1 , d 1 ) ∼ (c 2 , d 2 ). Необходимо доказать: 1) (a 1 , b 1 ) + (c 1 , d 1 ) ∼ (a 2 , b 2 ) + (c 2 , d 2 ); 2) (a 1 , b 1 ) · (c 1 , d 1 ) ∼ (a 2 , b 2 ) · (c 2 , d 2 ). Для доказательства свойства 1 нужно установить, что (a 1 + c 1 , b 1 + d 1 ) ∼ (a 2 + c 2 , b 2 + d 2 ). т. е. (a 1 + c 1 ) + (b 2 + d 2 ) = (a 2 + c 2 ) + (b 1 + d 1 ). По условию имеем a 1 + b 2 = a 2 + b 1 и c 1 + d 2 = c 2 + d 1 . (3.1) Тогда (a 1 + b 2 ) + (c 1 + d 2 ) = (a 2 + b 1 ) + (c 2 + d 1 ), откуда получаем искомое равенство. Для доказательства свойства 2 покажем, что (a 1 c 1 + b 1 d 1 , a 1 d 1 + b 1 c 1 ) ∼ (a 2 c 2 + b 2 d 2 , a 2 d 2 + b 2 c 2 ), 78 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ т. е. (a 1 c 1 + b 1 d 1 ) + (a 2 d 2 + b 2 c 2 ) = (a 2 c 2 + b 2 d 2 ) + (a 1 d 1 + b 1 c 1 ). Умножая поочередно первое равенство из (3.1) на c 1 , d 1 , c 2 , d 2 , получаем a 1 c 1 + b 2 c 1 = a 2 c 1 + b 1 c 1 , b 1 d 1 + a 2 d 1 = a 1 d 1 + b 2 d 1 , a 1 c 2 + b 2 c 2 = a 2 c 2 + b 1 c 2 , b 1 d 2 + a 2 d 2 = a 1 d 2 + b 2 d 2 . Аналогично, умножая поочередно второе равенство из (3.1) на a 1 , b 1 , a 2 , b 2 , имеем a 1 c 1 + a 1 d 2 = a 1 c 2 + a 1 d 1 , b 1 c 1 + b 1 d 2 = b 1 c 2 + b 1 d 1 , a 2 c 1 + a 2 d 2 = a 2 c 2 + a 2 d 1 , b 2 c 1 + b 2 d 2 = b 2 c 2 + b 2 d 1 . Складывая эти четыре равенства, после приведения подобных и деления пополам получаем искомое равенство. ¤ В дальнейшем носитель алгебры N будет также обозначаться через N. Определим фактор-алгебру A = hN 2 / ∼; +, ·i. Лемма 3.1.3. Алгебра A является коммутативным ассоциативным кольцом с единицей. Доказательство. Проверка законов ассоциативности, коммутативно- сти и дистрибутивности для операций сложения и умножения осуществля- ется непосредственно. Нулевым элементом в A является класс ∼ (0, 0), еди- ничным элементом — ∼ (1, 0). Для произвольного элемента α = ∼ (a, b) про- тивоположный элемент −α равен ∼ (b, a). ¤ Множество N 2 / ∼ разобьем на три части: 1) {∼ (a, b) | a > b}, 2) {∼ (a, b) | a = b}, 3) {∼ (a, b) | a < b}. В первом случае класс ∼ (a, b) содер- жит пару (k, 0), где a = b + k. Такие классы можно интерпретировать как положительные натуральные числа k = ∼ (k, 0). Второе множество содер- жит всего один класс, который играет роль нуля в A: 0 = ∼ (0, 0). Каждый класс ∼ (a, b) из третьего множества содержит пару (0, k), где b = a + k. Эти классы интерпретируются как отрицательные числа: −k ∼ (0, k). Введен- ные обозначения позволяют рассматривать алгебру A как кольцо целых чи- сел h{. . . , −n, . . . , −2, −1, 0, 1, 2, . . . , n, . . .}; +, ·i, которое в дальнейшем будем обозначать через hZ; +, ·i или просто Z. При этом ∼-классы будем называть целыми числами. 3.1. БЕСКОНЕЧНЫЕ ЧИСЛОВЫЕ СИСТЕМЫ 79 3. Поле рациональных чисел Рассмотрим множество Z × (N \ {0}). Пару (m, n) из этого множества можно представить в виде дроби m n . Если рассматривать дроби как раци- ональные числа, то некоторые из них считаются равными, например 1 2 и 2 4 , хотя записываются они по-разному. Чтобы отождествить эти записи, определим отношение эквивалентности ∼ следующим образом: (m 1 , n 1 ) ∼ (m 2 , n 2 ) ⇔ m 1 · n 2 = m 2 · n 1 . Классы эквивалентности по отношению ∼ называются рациональными числами, а множество всех классов эквивалентности образует множество рациональных чисел Q = ¡ Z × (N \ {0}) ¢ / ∼. Рассмотрим алгебру B = hZ × (N \ {0}); +, ·i, в которой операции сложе- ния и умножения определены так: (m 1 , n 1 ) + (m 2 , n 2 ) (m 1 · n 2 + m 2 · n 1 , n 1 · n 2 ), (m 1 , n 1 ) · (m 2 , n 2 ) (m 1 · m 2 , n 1 · n 2 ) для любых (m 1 , n 1 ), (m 2 , n 2 ) ∈ Z × (N \ {0}). Эти операции можно представ- лять и виде сложения и умножения дробей. Проверим, что отношение ∼ согласовано с операциями алгебры B. Лемма 3.1.4. Отношение ∼ является конгруэнцией на алгебре B. Доказательство. Пусть (m 1 , n 1 ), (m 2 , n 2 ), (m 0 1 , n 0 1 ), (m 0 2 , n 0 2 ) — пары из Z × (N \ {0}) с условиями (m 1 , n 1 ) ∼ (m 0 1 , n 0 1 ) и (m 2 , n 2 ) ∼ (m 0 2 , n 0 2 ). (3.2) Требуется доказать, что: 1) ((m 1 , n 1 ) + (m 2 , n 2 )) ∼ ((m 0 1 , n 0 1 ) + (m 0 2 , n 0 2 )); 2) ((m 1 , n 1 ) · (m 2 , n 2 )) ∼ ((m 0 1 , n 0 1 ) · (m 0 2 , n 0 2 )). Для проверки свойства 1 имеем (m 1 , n 1 ) + (m 2 , n 2 ) = (m 1 · n 2 + m 2 · n 1 , n 1 · n 2 ), (m 0 1 , n 0 1 ) + (m 0 2 , n 0 2 ) = (m 0 1 · n 0 2 + m 0 2 · n 0 1 , n 0 1 · n 0 2 ). 80 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ Нужно установить, что (m 1 · n 2 + m 2 · n 1 ) · (n 0 1 · n 0 2 ) = (m 0 1 · n 0 2 + m 0 2 · n 0 1 ) · (n 1 · n 2 ). (3.3) Зная из (3.2), что m 1 · n 0 1 = m 0 1 · n 1 и m 2 · n 0 2 = m 0 2 · n 2 , (3.4) имеем (m 1 · n 2 + m 2 · n 1 ) · (n 0 1 · n 0 2 ) = (m 1 · n 2 ) · (n 0 1 · n 0 2 ) + (m 2 · n 1 ) · (n 0 1 · n 0 2 ) = = (m 1 · n 0 1 ) · (n 2 · n 0 2 ) + (m 2 · n 0 2 ) · (n 1 · n 0 1 ) = {в силу (3.4)} = = (m 0 1 · n 1 ) · (n 2 · n 0 2 ) + (m 0 2 · n 2 ) · (n 1 · n 0 1 ) = = (m 0 1 · n 0 2 ) · (n 1 · n 2 ) + (m 0 2 · n 0 1 ) · (n 1 · n 2 ) = ((m 0 1 · n 0 2 ) + (m 0 2 · n 0 1 )) · (n 1 · n 2 ), и тем самым равенство (3.3) установлено. Проверка свойства 2 проводится аналогично и оставляется читателю в ка- честве упражнения. ¤ Таким образом, отношение ∼ — конгруэнция, и фактор-алгебра B/ ∼ образует множество рациональных чисел Q с обычными операциями сложе- ния и умножения: B/ ∼ = hQ; +, ·i. В полученной алгебре выполняются все аксиомы поля. Нулевым рациональным числом является класс ∼ (0, 1), еди- ницей — класс ∼ (1, 1), числом, противоположным числу ∼ (m, n), является число −(∼ (m, n)) ∼ (−m, n), обратным ненулевому числу ∼ (m, n) — чис- ло (∼ (m, n)) −1 ∼ (±n, ±m), где знак плюс берется при m > 0 и минус — при m < 0. 4. Поле действительных чисел Последовательность (x n ) n∈ω рациональных чисел называется фундамен- тальной, если для любого рационального числа ε > 0 существует такое n 0 , что |x p −x q | < ε для всех p и q, больших n 0 . Фундаментальные последователь- ности (x n ) n∈ω и (y n ) n∈ω называются эквивалентными: (x n ) ∼ (y n ), если для любого рационального числа ε > 0 существует такое n 0 , что |x p − y q | < ε для всех p и q, больших n 0 . Классы эквивалентности фундаментальных после- довательностей ∼ (x n ) называются действительными или вещественными 3.1. БЕСКОНЕЧНЫЕ ЧИСЛОВЫЕ СИСТЕМЫ 81 числами. Таким образом, множество R действительных чисел является фактор-множеством X/ ∼, где X = {(x n ) | (x n ) — фундаментальная последовательность}. На множестве R определим основные арифметические операции. Для этого рассмотрим алгебру X = hX; +, ·i со следующими операциями: (x n ) + (y n ) (x n + y n ), (x n ) · (y n ) ( |