Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 30
Текст из файла (страница 30)
Определим ф: (1,2,3,...) — А 0 В следующим образом: ф(9) = фд(й) для 1 < и < и и ф()с) = фз(9 — п) для 9 > п. Функция ф устанавливает взаимно однозначное соответствие между множествами (1,2,3,...) и А О В. Доказательство следующей теоремы предоставляется читателю. ТЕОРЕМА 4.69. Множество неотрицательных целых чисел и множество целых чисел являются счетно бесконечными. Дальнейшие свойства мощности будут рассмотрены в следующем разделе. Будет показано, что существуют множества, которые не являются счетными, и что имеется бесконечно много различных бесконечных мощностей.
° УПРАЖНЕНИЯ 1. Используя определение, найдите мощности следующих множеств: а) (а,Ь,с,д,е,/,д); 6) (3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33); в) (5,10,15,20,25,30,...). 2. Покажите, что множество неотрицательных целых чисел счетно бесконечно. 3. Покажите, что множество отрицательных целых чисел счетно бесконечно. 4. Покажите, что множество целых чисел счетно бесконечно. 5. Покажите, что множество ( — 10, — 9, — 8,..., — 2, — 1, О, 1, 2, 3,...) счетно бесконечно. 4.5.
МОЩНОСТЬ (ПРОДОЛЖЕНИЕ) Исследуем теперь понятие мощности множества более основательно. Прежде всего, покажем, что подмножество счетного множества счетно. Отсюда будет следовать, что всякое множество, для которого существует взаимно однозначное соответствие с подмножеством счетного множества, счетно.
ТЕОРЕМА 4.80. Подмножество счетного множества счетно. РЯЗЛЕЛ 4.5. Мощность (продолменое) 179 ДОКАЗАТЕЛЬСТВО. Покажем, что если  — счетное множество и А С В, то множество А также счетно. Предположим, что  — конечное множество. Покажем, что в таком случае А тоже конечно. Поскольку В конечно, для некоторого положительного целого числа п существует взаимно однозначное соответствие ф между (1,2,3,...,и) и В. Следовательно, В можно представить в виде (ЬыЬг,Ьз,...,Ь„), где 6, = ф(1). Теперь построим взаимно однозначное соответствие ф между (1,2,3,...,т) и А, где т < п. Начинаем с Ьг и находим первое Ь,, скажем, 6 „в последовательности Ьы 6г, Ьз, ..., 6„такое, что Ь, е А.
Пусть ф(1) = Ь,. Просматривая последовательность, находим в ней следующее Ь;, скажем, Ь„такое, что 6, Е А. Пусть 4(2) = Ь„. Продолжаем процесс, пока не достигнем Ь„. Пусть т — наибольшее целое число, которое ф отображает в элемент А. Поскольку г < а, для всех г, то т < и и поэтому, несомненно, ф отображает (1,2,3,...,т) в А. Теперь предположим, что  — счетно бесконечное множество. Если А— конечное, то оно счетное, поэтому предположим, что оно не является конечным.
Поскольку  — счетно бесконечное, существует взаимно однозначное соответствие ф между (1,2,3,...) и В. Следовательно, В можно представить в виде (Ьы6г,Ьз, .), где Ь, = ф(1). Используя принцип вполне упорядочения, находим наименьшее 1 такое, что 6, Е А. Пусть ф(1) = Ь, и В~ =  — (Ьг). Очевидно, что 1 < г.
Предположим, что мы определили ф(1),ф(2),ф(3),...,ф(к) Е А, Вь =  — (ф(1), ф(2), ф(3),...,ф()с)), ф(() < Ь для всех 1 < г < й и всех Ь Е Вю и если ф(й) = Ь„, то )с < т. Выберем наименьшее у такое, что Ь, Е А О Вь. Пусть 4(й) = Ь, и Вьег = Вь — (Ь)). Очевидным образом получаем последовательность ф(1), ф(2), ф(3),..., ф(Ь), ф()с+1) и А, Вь.ьг — —  — (ф(1), ф(2), ф(3),..., фЯ, ф(Ь+ 1)), ф(1) < Ь для всех 1 < 1 < й + 1 и всех 6 Е Вь+„и если ф()с+ 1) = 6„, то Ь + 1 < т. Итак, функция ф определена по индукции, при этом очевидно, что ф(1) Е А для всех 1 и ф(1) ф ф0), если г ф ).
Остается только показать, что отображение ф сюръективно. Пусть а Е А, тогда а = Ь„для некоторого п. Следовательно, для некоторого т < п имеем ф(т) = Ь„. ТЕОРЕМА 4.61. Пусть Я вЂ” счетно бесконечное множество, тогда множество Я х Я также счетно бесконечно. ДОКАЗАТЕЛЬСТВО. Сначала покажем, что если Аг — множество положительных целых чисел, то Х х )У счетно. Рассмотрим следующий рисунок: Рис. 4.) Двигаясь по диагональным стрелкам, начиная с верхней, мы определяем отображение ф следующим образом: ф(1) = (1,1), 4(2) = (1,2), ф(3) = (2,1), 180 ГПАВА 4. Функции и матрицы Ф(4) = (1,3, ), ф(5) = (2,3) и т.д. Функция ф устанавливает искомое взаимно однозначное соответствие. Упорядоченная пара (т,п) лежит на т + п — 1-ой по порядку диагонали и является т-ым элементом вдоль этой диагональной линии.
Следовательно, множество, изображенное на рис. 4.1, счетно. Таким образом, множество 11г х Ж счетно. Поскольку Я вЂ” счетно бесконечное множество, то существует взаимно однозначное соответствие 0; 1к' — Я. Определим соответствие 0 х 0: Х х Х вЂ” 5 х В следующим образом; В х В(а, 6) = (0(а), В(6)). Легко показать, что функция 0 х 0 устанавливает взаимно однозначное соответствие между множествами Ж х 1у и Я х Я. ТЕОРЕМА 4.62.
Множество Я+ положительных рациональных чисел является счетно бесконечным. ДОКАЗАТЕЛЬСТВО. Рассмотрим подмножество М множества Ж х)к' вида ((а, 6): (а, 6) 6 11Г х 11, при этом целые числа а и 6 — взаимно простые). Очевидно, функция ф: Я+ — М, определенная соотношением ф(а/6) = (а,6), — это и есть искомое взаимно однозначное соответствие. Поскольку множество Аг х Х вЂ” счетно бесконечное, множество М также является счетно бесконечным. Следовательно, Я4 — счетно бесконечное множество.
ТЕОРЕМА 4.63. Если А и  — счетные множества, то множество А О В также счетно. ДОКАЗАТЕЛЬСТВО. Множество А — В счетно, как подмножество счетного множества А. Но множества А — В и В не пересекаются, поэтому по теореме 4.58 (в) множество (А — В) О В = А О В является счетным. Приведенные выше теоремы могут навести на мысль, что все множества счетны.
Однако, как показывает следующая теорема, существуют бесконечные, но несчетные множества. ТЕОРЕМА 4.64. Пусть  — множество действительных чисел. Множество 1 вида 1 = (х: х е В и 0 < х ( 1) не является счетным. ДОКАЗАТЕЛЬСТВО. Применим метод сведения к абсурду. Предположим, что множество 1 счетно. Тогда 1 можно представить в виде (а1,аз,аз,а4,аз,...), где а, — образ 1 при взаимно однозначном соответствии между 1к' и 1.
Пусть .а,1агаа,за,4ам... — это запись в виде десятичной дроби числа а,. Тогда мы имеем таблицу а1 = .а11а12агза14а15 а2 = а21а22а23а24а25 аз — .а31а32аззазка35 ° а4 — — .а41а42а4за44а45 аз = .а51аззазза54а55 Определим элемент 6 6 1, где 6 = .61626з6465..., следующим образом: 6; = 5, если ац -,4 5, и 6, = 8, если аи = 5. Рассмотрим конкретный пример; а, = .5135897623 , РАЗДЕЛ 45.
Мощность (прооолженое) 161 аз = 1425958273 аз = 2837462982 а4 = .1985723986.. аз = .2309847621.. ИмеЯ аы = 5, ааа = 4, азз — 3, а44 = 5, азз = 8 и т д., полУчаем 61 = 8, Ьз = 5, Ьз = 5, Ь4 — — 8, Ьз = 5 и т.д. Таким образом, Ь = .85585., Число Ь не пРинадлежит множествУ (ам аз,аз,а4,аз,...), т.к.
длЯ каждого т число Ь не может совпадать с а . В самом деле, Ь ф а, поэтому Ь и а не совпадают в гп-ой цифре. Но это противоречит предположению о том, что 1 = (аы аг, аз, аю аз,...), так как Ь Е 1, но 6 ф (аы аг, аз, аз, аю...). Следовательно, предположение о счетности 1 является ложным, и множество 1 — несчетное. ° ТЕОРЕМА 4.66. Множество действительных чисел В несчетно. ДОКАЗАТЕЛЬСТВО.
Если бы 17 было счетным, то множество 1, как подмножество В, было бы счетным, однако, 1 — несчетно. Следовательно, множество Л— несчетное. В дальнейшем мы опишем метод построения бесконечного числа бесконечных множеств, никакие два из которых нельзя связать взаимно однозначным соответствием.
ТЕОРЕМА 4.66. Не существует взаимно однозначного соответствия между множеством Я и его булеаном 'Р(Я). ДОКАЗАТЕЛЬСТВО. Очевидно, не существует взаимно однозначного соответствия между пустым множеством о и его булеаном (о), содержащим один элемент — а. Снова воспользуемся методом сведения к абсурду. Предположим, что взаимна однозначное соответствие ф между Я и его булеаном существует. Это значит, что функция ф биективно отображает элементы множества Я на подмножества множества Я. Например, пусть Я вЂ” множество положительных целых чисел, и пусть ф(1) = (2,5,7,9,10), ф(2) = (2, 4, 6, 8,...), ф(3) = Я, ф(4) = (1,2,3,4,5,6,...), ф(5) = (1,2), В некоторых случаях 1 Е ф(1).
В нашем примере 2 Е ф(2) и 4 Е ф(4). Однако, 1 ф ф(1), 3 ф ф(3) и 5 ф ф(5). Понятно, что любой элемент г, который функция ф 182 Г7ГД6Д 4. Функции и матрицы отображает в пустое множество, будет обладать свойством 1 ф ф(г), а всякий элемент 1, который функция ф отображает в 5, будет обладать свойством у 6 фО). Пусть Иг = (х: х 6 о и х ф ф(х)). Поскольку отображение ф сюръективно, то существует элемент а 6 о такой, что ф(а) = Иг. Принадлежит ли а множеству Иг? Если а 6 И', то а принадлежит множеству тех элементов о, которые ф не отображает на множества, их содержащие.
Следовательно, а ф ф(а) = Иг. Таким образом, мы приходим к противоречию. Если же а ф Иг, то а ф ф(а) = И'. Поэтому а удовлетворяет условию принадлежности множеству И', т.е. а 6 Иг. Снова получаем противоречие. Итак, в любом случае мы приходим к противоречию. Следовательно, утверждение о существовании взаимно однозначного соответствия ф между Я и его булеаном неверно. ПРИМЕР 4.67.
Пусть о = (1,2,3,4) и ф(1) = (2, 4), ф(2) = (1,2,3,4), ф(3) = (1, 3), ф(4) = И. Тогда И' = (1,4) — множество из доказательства теоремы, и в него не отображается никакой элемент. П Примером рассуждения, очень похожего на доказательство предыдущей теоремы, является парадокс Рассела.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
