Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
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). 48 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ 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 — вполне упо- ЗАДАЧИ И УПРАЖНЕНИЯ 49 рядоченное множество, 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 (см. с. 17). 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. 50 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ 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. Доказать, что множества точек отрезка и квадрата эквивалентны. ЗАДАЧИ И УПРАЖНЕНИЯ 51 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 лошадей имеют одинаковую масть. В силу принципа математической индукции все лошади имеют одну и ту же масть. ¤ 52 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ 26. Построить бинарное отношение: а) рефлексивное, симметричное, не транзитивное; б) не рефлексивное, антисимметричное, не транзитивное; в) рефлексивное, не симметричное, транзитивное. 27. Пусть L — множество всех прямых на плоскости. Являются ли экви- валентностями следующие отношения: а) отношение параллельности двух прямых; б) отношение перпендикулярности двух прямых? 28. Доказать, что отношение {((x 1 , y 1 ), (x 2 , y 2 )) | x 2 1 + y 2 1 = x 2 2 + y 2 2 } являет- ся отношением эквивалентности на множестве R 2 . Определить классы этой эквивалентности. 29. Доказать, что отношение {(a, b) | (a − b) — рациональное число} явля- ется отношением эквивалентности на множестве вещественных чисел. 30. Пусть на множестве ω определено отношение 6, задаваемое следую- щим правилом: m 6 n ⇔ m делит n. Считая, что 0 делит 0, показать, что 6 — частичный порядок. Для произвольных натуральных чисел m и n найти inf{m, n} и sup{m, n} относительно указанного порядка. 31. Для обычных отношений 6 и < на множестве ω показать, что < ◦ < 6= <, 6 ◦ < = < и 6 ◦ > = ω 2 32. Построить пример ч.у.м. с единственным минимальным элементом, но без наименьшего. 33. Рассмотрим на множестве R 2 отношение Парето Π: (x 1 , y 1 ) Π (x 2 , y 2 ) ⇔ x 1 6 x 2 и y 1 6 y 2 . Для точек A(a 1 , a 2 ) и B(b 1 , b 2 ) найти множество нижних и верхних гра- ней множества {A, B}. Чему равен inf{A, B} и sup{A, B}? 34. Построить линейный порядок на множестве комплексных чисел. 35. Составить матрицу отношения полного порядка, при котором нумера- ция элементов ведется: а) по возрастанию; б) по убыванию. ЗАДАЧИ И УПРАЖНЕНИЯ 53 36. Проверить, являются ли частичными порядками бинарные отношения со следующими матрицами: а) 1 1 1 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 ; б) 1 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 ; в) 1 0 0 0 1 1 1 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 0 1 ; г) 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 0 1 ; д) 1 0 0 0 0 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1 ; е) 1 0 1 1 1 0 1 1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 1 0 1 ; ж) 1 0 1 0 0 1 1 1 0 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 1 ; з) 1 0 0 0 0 1 1 1 1 1 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1 ; и) 1 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 0 1 1 ; к) 1 0 0 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 ; л) 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 ; м) 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 0 1 Построить диаграммы Хассе для заданных порядков. Есть ли в со- ответствующих частично упорядоченных множествах наименьшие или наибольшие элементы? Какие из этих частичных порядков линейные? 37. Построить всевозможные попарно неизоморфные четырехэлементые ч.у.м. hA; 6i. Какие из этих ч.у.м. самодвойственны, т. е. изоморфны hA; >i? Глава 2 АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ § 2.1. Определения и примеры Часто объектом изучения в математике и ее приложениях служит мно- жество вместе с определенной на нем структурой. Читателю уже известны поля, формирующие основу обычной арифметики, линейные пространства, обеспечивающие связь геометрических объектов с операциями над числами, множества с введенными на них бинарными отношениями. Все эти струк- туры образуют алгебраические системы, представляющие собой некоторые миры с определенными в них законами. Перейдем к точному определению алгебраической системы. Рассмотрим непустое множество A. В § 1.2 было введено понятие n-местной операции на множестве A (f : A n → A). Отметим, что, поскольку операция f является функцией, для любого набора (x 1 , . . . , x n ) ∈ A n ре- зультат применения операции f (x 1 , . . . , x n ) однозначно определен. Так как область значений операции f лежит в множестве A, то будем говорить, что операция f замкнута на множестве A. Сигнатурой или языком Σ называется совокупность предикатных и функциональных символов с указанием их местности. При этом множе- ства предикатных и функциональных символов не пересекаются. 0-Местный функциональный символ называется константным символом или просто константой. Если α — функциональный или предикатный символ, то его местность обозначается через µ(α). n-Местные предикатные и функциональ- ные символы часто будем обозначать соответственно через P (n) и f (n) . Если в рассматриваемой сигнатуре используются стандартные символы, такие, например, как + для операции сложения, 6 для отношения порядка, | для 2.1. ОПРЕДЕЛЕНИЯ И ПРИМЕРЫ 55 отношения делимости, 0 для константного символа и другие, то мы просто пишем Σ = {6}, Σ = {6, +, ·, 0}, Σ = {+, −, |, 0, 1} и т. д. Алгебраической системой A = hA; Σi сигнатуры Σ называется непустое множество A, где каждому n-местному предикатному (функциональному) символу из Σ поставлен в соответствие n-местный предикат (соответственно операция), определенный на множестве A. Множество A называется носите- лем или универсумом алгебраической системы hA; Σi. Предикаты и функ- ции, соответствующие символам из Σ, называются их интерпретациями. Обозначать интерпретации будем теми же буквами, что и соответствую- щие символы сигнатуры. Заметим, что интерпретацией любого константного символа является некоторый элемент (константа) из A. Алгебраические системы в дальнейшем будут обозначаться готическими буквами A, B, . . . (возможно, с индексами), а их носители — соответствующи- ми латинскими буквами A, B, . . . (с соответствующими индексами). Иногда мы будем отождествлять носитель с алгебраической системой. Мощностью алгебраической системы A называется мощность ее носите- ля A. В дальнейшем будем часто опускать слово “алгебраическая” и назы- вать A системой или структурой. Непустая сигнатура Σ называется функциональной (предикатной), если она не содержит предикатных (функциональных) символов. Система A на- зывается алгеброй (моделью или реляционной системой), если ее сигнатура функциональна (предикатна). Пример 2.1.1. 1. Набор hω; +, ·i является алгеброй с двумя двухмест- ными операциями. 2. Набор hω; 6, +, ·, 0 , 0, 1i является системой с бинарным отношением 6 (µ(6) = 2), двухместными операциями +, · (µ(+) = µ(·) = 2), одноместной операцией 0 : n 7→ n + 1 (µ( 0 ) = 1) и двумя нуль-местными операциями (константами) 0, 1 (µ(0) = µ(1) = 0). 3. Набор hZ; +, :, √ 2i не образует алгебру, поскольку деление не является операцией на множестве Z (например, 2 : 3 / ∈ Z), а элемент √ 2 не принадле- жит Z. 4. Набор hP(U); ∩, ∪, , 0, 1i с двухместными операциями ∩, ∪, одномест- ной операцией : A 7→ A, константами 0 = ∅ и 1 = U является алгеброй, называемой алгеброй Кантора. 5. Алгеброй является любое кольцо. 6. Пара {f (x) |