Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
⊆ на булеане 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 об- разуют линейно упорядоченные множества. ¤ 42 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Пусть 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. 1.7. ОТНОШЕНИЯ ПОРЯДКА 43 В примере 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 . ¤ 44 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Как показывает следующий пример, если |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) определяет упорядочение слов, по которому составляются словари. ¤ 1.7. ОТНОШЕНИЯ ПОРЯДКА 45 Рассмотрим частично упорядоченное множество 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 46 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Заметим, что диаграммы Хассе, изображенные на рис. 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. ¤ 1.8. АКСИОМЫ ТЕОРИИ МНОЖЕСТВ 47 § 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. Аксиома множества всех подмножеств: Если существует множество |