Материал: Дискретная математика теория и практика

xn = α0(n) ,α1(n) ,α 2(n) ...α m(n) ...

...........................................................

Вравенствах (11) α0(n) (n = 1, 2, ...) – целое число с тем или иным знаком,

аαm(n) (m = 1, 2, ... , n = 1, 2, ...) – одна из цифр 0, 1, 2, ... , 9.

Выберем цифру αn (n = 1, 2, ...) так, чтобы αn ≠ αn(n) и αn ≠ 9. Тогда дробь 0,α1α2...αn... является допустимой. Следовательно, n N: xn = 0,α1α2...αn...

С другой стороны, действительного числа а = 0, α1 α2... αn ... нет среди чисел

xn (n = 1, 2, ...), так как десятичная дробь 0,α1α2... αn... хотя бы одним десятичным знаком отличается от каждой из десятичных дробей (11). Получили противоречие. Следовательно, наше предположение неверно, и множество действительных чисел несчетно.

Мощность множества всех действительных чисел R называют мощностью континуума (от лат. continuum – непрерывное) и обозначают древнееврейской буквой (алеф). Все множества, изоморфные множеству R, имеют мощность континуума. Примерами множеств мощности континуума являются множества точек любого отрезка, луча, прямой.

На множестве кардинальных чисел введем отношение «≤» следующим образом: |X| ≤ |Y| X изоморфно некоторому подмножеству множества Y. Говорят, что мощность множества X меньше мощности множества Y (пишут

|X| < |Y|), если |X| ≤ |Y| и X ≠ Y.

Известно, что мощность 0 счетных множеств меньше мощности

: 0 < .

Есть ли между 0 и другие кардинальные числа – знаменитая проблема (гипотеза) континуума в математике, которая в 1963 г. была решена американским математиком П. Коэном. Он доказал независимость гипотезы континуума от других аксиом теории множеств. Проблема континуума решается аналогично проблеме пятого постулата Евклида в геометрии. Ни утверждение проблемы, ни отрицание ее из аксиоматики теории множеств доказать нельзя. Если в качестве аксиомы взять, что между 0 и есть другие кардинальные числа, то возникает одна ветвь математики, если нет, то другая, совершенно независимая.

Рассмотрим без доказательства несколько теорем, относящиеся к теории бесконечных множеств.

Теорема 3.4. Всякое подмножество счетного множества конечно или счетно.

Теорема 3.5. Объединение счетного числа счетных множеств счетно. Теорема 3.6. Всякое бесконечное множество X содержит счетное под-

множество Y такое, что X \ Y есть бесконечное множество.

Теорема 3.7. Всякое бесконечное множество X содержит подмножество Y X такое, что X \ Y есть бесконечное множество.

47

Теорема 3.8. (Кантора – Бернштейна). Если каждое из двух множеств X

и Y изоморфно подмножеству другого, то множества X и Y изоморфны между собой, то есть |X| ≤ |Y| |Y| ≤ |X| |X| = |Y|.

Замечание 3.5. Сергей Натанович Бернштейн (1880 – 1966) – советский математик.

Теорема 3.9. Для произвольного множества X мощность его булеана P(X) равна 2|X|.

Теорема 3.10. Булеан P(X) произвольного непустого множества X имеет мощность, большую, чем мощность множества X, то есть ( X) |X| < 2|X|.

3.9. Отношение порядка. Диаграммы Хассе

Пусть А – непустое множество.

Определение 3.26. Отношение Р А2 называется предпорядком (квази- порядком), если оно рефлексивно и транзитивно.

сивно, транзитивно и антисимметрично. Таким образом, частичный порядок представляет собой антисимметричный предпорядок. Частичный порядок обозначается символом ≤, а обратное ему отношение ≤ -1 – символом ≤ .

Определение 3.28. Отношение < А2 называется строгим порядком, если оно определяется по следующему правилу: ( x, y A) х < у х ≤ у и х ≠ у.

Отношение строгого порядка не является частичным порядком, так как оно не рефлексивно.

Пример 3.18. Отношение из примера 3.17 не является частичным порядком, а отношение делимости на множестве целых чисел – является.

Определение 3.29. Пусть ≤ А2 и х, у А. Элементы х и у называются несравнимыми, если нельзя сказать, что х ≤ у или у ≤ х.

Пример 3.19. Пусть А = {a, b, c, d}. Отношение включения на булеане P(A) является частичным порядком. Элементы B = {a, c} и C = {b, d} из P(A) являются несравнимыми, так как (B, C) и (C, B) .

Определение 3.30. Частичный порядок ≤ А2 называется линейным по-

рядком, если ( х, у А) х ≤ у или у ≤ х.

Определение 3.31. Пусть А ≠ и ≤ – частичный (линейный) порядок на

А. Упорядоченная пара < А, ≤ > называется частично (линейно) упорядоченным множеством.

48

Другими словами, частично (линейно) упорядоченным множеством является непустое множество А, на котором зафиксирован некоторый частичный (линейный) порядок ≤.

Пример 3.20. Пара < Z, ≤ >, где ≤ – отношение делимости на множестве Z, является частичным, но не линейным порядком. Пары < N, ≤ > , < R, ≤ > с обычными отношениями ≤ образуют линейно упорядоченные множества.

Определение 3.32. Элемент а А частично упорядоченного множества

< А, ≤ > называется максимальным (минимальным), если ( х А) а ≤ х (х ≤ а)

х = а.

Определение 3.33. Элемент а А частично упорядоченного множества

< А, ≤ > называется наибольшим (наименьшим), если ( х А) х ≤ а (а ≤ х).

Наибольший (наименьший) элемент частично упорядоченного множества < А, ≤ > (если он существует) обозначается через max A (min А). Наибольший элемент часто называют единицей, а наименьший – нулем множества < А, ≤ >.

Теорема 3.11. Пусть < А, ≤ > является частично упорядоченным множеством, где А – непустое и конечное множество. Тогда < А, ≤ > содержит хотя бы один минимальный элемент, и если он является единственным, то он также является и наименьшим. Аналогично, < А, ≤ > содержит хотя бы один максимальный элемент, и если он является единственным, то он также является наибольшим.

Пример 3.21. Частично упорядоченное множество < А, ≤ >, где

А = {a, b, c, d}, а граф отношения ≤ изображен на рис. 3.7, имеет единственный минимальный и он же наименьший элемент a, максимальные элементы c и d, но не имеет наибольшего элемента.

Пример 3.22. Частично упорядоченное множество < B, ≤ >, где

B = {1, 2, 3, 4}, а граф отношения ≤ изображен на рис. 3.8, имеет минимальные элементы 1 и 2, единственный максимальный и он же наибольший элемент 4, но не имеет наименьшего элемента.

мальным. Обратное утверждение, вообще говоря, неверно (см. примеры 3.21 и 3.22).

49

Определение 3.34. Пусть < А, ≤ > – частично упорядоченное множество и

ВА. Элемент а А называется верхней (нижней) гранью подмножества В,

если ( b В) b ≤ a (a ≤ b).

Пример 3.23. Рассмотрим частично упорядоченное множество < R, ≤ > и

В= [0;1). Тогда любое число х ≥ 1 является верхней гранью В, а любое число

х ≤ 0 – нижней гранью В. Определение 3.35. Пусть < А, ≤ > – частично упорядоченное множество и

В А. Точной верхней (нижней) гранью подмножества В называется наимень-

шая верхняя (наибольшая нижняя) грань множества В.

Точная верхняя грань подмножества В обозначается через sup B (супремум), а точная нижняя грань – через inf B (инфимум).

Пример 3.24. В условиях примера 3.21 имеем, что sup В = 1, inf B = 0. Определение 3.36. Линейный порядок ≤ на множестве А называется пол-

ным, если каждое непустое подмножество множества А имеет наименьший элемент.

Определение 3.37. Пусть ≤ – полный порядок на непустом множестве А.

Упорядоченная пара < А, ≤ > называется вполне упорядоченным множеством.

Пример 3.25. Упорядоченная пара < N, ≤ > является вполне упорядоченным множеством, а < [−1;1], ≤ > не является, так как, например, полуинтервал (0;1], являющийся подмножеством [-1;1], не содержит наименьшего элемента. Пусть < А, ≤ > – частично упорядоченное множество и x, y А. Говорят, что элемент у покрывает элемент х, если х ≤ у и не существует такого элемента

z А, что х < z < y. Если А – любое конечное множество, то частично упорядоченное множество < А, ≤ > можно представить в виде схемы, в которой каждый элемент изображается точкой на плоскости, и если элемент у покрывает элемент х, то точки, изображающие элементы х и y, соединяют отрезком, причем точку, соответствующую элементу х, располагают ниже точки, соответствующей элементу у. Такие схемы называются диаграммами Хассе.

Пример 3.27. а) Рассмотрим частично упорядоченное множество

<Р(А), >, где А = {a, b, c, d} и Р(А) = { , {a}, {b}, {c},{a, b},{b, c},{a, c},

{a, b, c}}. На рис. 3.11 изображена диаграмма Хассе, соответствующая

<Р(А), >. б) Пусть B = {1, 2, 3, 4, 5 , 6, 8} и ≤ – обычное отношение порядка на множестве натуральных чисел, не превосходящих восьми. Диаграмма Хассе,

50

Определение 3.38. Соответствие ƒ A B называется функцией из множества A в множество B, если ƒ функциональное и полностью определенное. Соответствие ƒ называется частичной функцией, если ƒ функциональное и частично определенное.

Таким образом, соответствие ƒ A B является функцией из A в B, если для любого x A существует единственный элемент y B такой, что (x, y) ƒ. При этом элемент y обозначается через ƒ(x) и называется значением функции ƒ для аргумента x. Функция f из A в B обозначается через ƒ: A → B или A →f B. Если (x, y) ƒ, то используется общепринятая запись y = ƒ(x), а также запись ƒ: x a y (означает, что функция ƒ ставит в соответствие элементу x элемент y).

Область определения и область значений функции, равные функции определяются так же, как и для соответствий.

Пример 3.28. Какие из соответствий, графы которых изображены на рис. 3.13, являются функциями? Найдите для каждой функции ее область определения и область значений.

Рис. 3.13

Решение. Соответствия f2, f3 и f4 являются функциями, а f1 – не является,

так как f1(b) = {1, 3}. Далее имеем: Dom f2 = {1, 2, 3} = B, Im f2 = {a, b, c} A; Dom f3 = {a, b, c} = A, Im f3 = {1, 2, 3} = B; Dom f4 = {a, b, c, d} = A,

Im f4 = {1, 2, 3} = B.

Аргументами функции могут являться элементы произвольной природы, в частности, кортежи длины n (x1, x2, …, xn). Функцию ƒ: A n → B называют n-местной функцией из A в B. Тогда пишут y = ƒ(x1, x2, …, xn) и говорят, что y есть значение функции ƒ при значении аргументов x1, x2, …, xn.

51