Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 13
Текст из файла (страница 13)
Для достижения нашей цели существенно сказать следующее, Возьмем диагонально упорядоченное множество Х Х Х (сль рис. 3.3) и выбросим из него пары, имеющие нетривиальный общий множитель. Это дает метод нумерации элементов Т, однако трудно дать формулу, которая связывала бы элементы Т с элементами Х. Теперь мы должны повторить ваше рассунсдеияе применительно ко всем рациационным числам. Это можно сделать несколькими способами. Выберем для наглядности следующий. Расширяя уже полученное соответствие между Т и ХХХ до оператора моя»ду Я и ХХХ, получаем что дает требуемый результат.
Построение биекции между ЕХХ и ХХХ оставляем в качестве упраж. пения. / Предыдущий пример несколько длинен, однако прп его рассмотрении возникло весколько важных моментов, которые мы сейчас отметим. 1. Если Ю конечно и т: Ю- 5 — инъективное отображение, тогда Х биективно.
Доказательство. Пусть выполнены условия утверждения. Если Я = ~, то треоуемый результат тривиален. Если Я т» б, тогда существует биекцвя ф: Х„- Я для некоторого и ж Х и отображение»р ' ° 11 ° $ инъектпвно: Х вЂ” Х и, следовательно, является биекцией. (Доказательство этого факта оставляем в качестве упражнения.) Основная идея ааключается в переупорядочивании и» объектов и известна под названием «принцип раскладывавия по гнездам».
Даны т гнезд, каждое в своем ящике. Любая схема переселения, при которой в одном ящике может быть не болев одного гнезда, должна использовать все л» ящиков, т. е. ф ' ° 11 ° »р является перестановкой Х (рнс, 3.4). Однако »р — биекция; следовательно, у а»р и у также биекции. (Обратно, если 11: Я- Я не сюръективно, то Ю должно быть бесконечным.) 2. Множества Х бесконечно, так как отображение на Х, определенное как и .
л + 1. ивъективно, но не бнективно (нет злемента, отображающегося в 1). Следовательно, обращая предыдущий результат, получаем, что Х не может быть конечным. Подмножество А из В ограничено сверху (снизу) если существует верхняя (нижняя) граница. А ограниченно, если оно ограничено сверху и снизу. 3. Ограниченное подмножество из Х конечно. Д о к а з а т е л ь с т в о. Каждое подмножество ив Х ограничено снизу нулем. Пусть А ы Х ограничено сверху некоторым ты Х.
Определкм отображение у А- Х Рис. ЗА так, что если Л (а<, ах, ..., а<, ...) и а< <ах(аз<... ...(ш (такой порядок воаможен, так как АжХ), то Х(а<) = ~. Следствием этого является соотношение т(а<)ча<, и у, очевидно, ииъективпо. Оно также должно быть биекцией, т. е. у: А - Х. для некоторого яч.ж. Если вто не так, тогда существует а, ж А такое, что д(аг) ~ <и и, таким образом, а, >~(а,)> т. Однако А ограничено ж; поэтому мы пришли к противоречию, Следовательно, т — бнекция па Х„ и А конечно. 4. Ка<кдое подмнон<естес конечного множества конечно.
Доказательство. Пусть Л <и В и В конечно, Если В З, то А = <в<, и утвержденна доказано. В противном случае В Х для некоторого л«и Х. Тогда существует биеация ~~:  — Х . Применение у к Л дает подмножество из,Х и поэтому т(А) ограничено. Пз случая 3 следует конечность у(А). Поэтому, так как д(Л) бисктпвно с А, то Л конечно, 73 5. Прямым следствием случая 4 является тот факт, что любое мпоя~ество, имеющее бесконечное подмнон~ество, само бесконечно.
Доказывая некоторые неочевидные факты о размерностях множеств Е, О, г(, ?ч'Хг(, ..., разумно задаться вопросом: существуют ли множества, мощность которых больше мощности г(? Ответ на этот вопрос утвердительный. Действительно, из данного произвольного множества мы можем (вспользуя диагональную процедуру Кантора; см. ниже) создать множество, мощность которого строго больше мощности г(.
гйы не будем рассматривать общий случай, а ограни» чимся рассмотрением удивительного примера, который носит фундаментальный характер и соответствует целям нашего изложения. Пример 3.4. Полая~ем, что ! (О, ([ ! ~ 1%1, (О, 7( (х: х ю Н, 0 ~ з ( (). Д о к а з а т е л ь с т в о (А.
Кантор). Каждое число между 0 и 1 может быть записано в виде бесконечной десятичной дроби О.Н ~о'„зЫ„з... Предположим, что зги числа могут быть перенумерованы и что и-е число имеет значение, данное выше, Будем конструировать следующее число: воаьмем и-ю цифру десятичной формы, равную л-му числу. Это дает кам число О.дпдзз4з... Построим новое число: О.бпбззбы..., где каждая цифра б« отличаетсн от соответствующей цифры 4,.
Тогда зто построенное число будет отличаться от каждого числа из первоначального перечня, а именно от л-го числа оно будет отличаться л-й цифрой. Следовательно, мощность (О, Ц строго больше, чем мощность г(, и счетной блекции не существует. Принцип построения числа Обпбыбзз ° ° . в предыдущем доказательстве является наиболее существенным моментом, хотя проницательный читатель может заметить, что существуют задачв, где десятичное представление чисел ве единственно. Это встречается тогда, когда представление заканчивается бесконечной последовательностью 0 или 9.
(Например, 0.3999... и 0.4000...) Чтобы построенное число О.бпбмбзз... отличалось от уже выписанного списка чисел, мы можем оговорить, что б» должны отличаться от О, И» я 9. Соответствующие проблемы возникают и в других подобных конструкциях, однако, чтобы не отвлекать внимание от основных идей, в большинстве случаев мы будем их игнорировать. 78 На самом деле можно показать, что [О, т[- К. Очевидно, что К вЂ” вансное множество, Поэтому его мощность обозначают специальным символом И1 (алеф- один). Рассмотрвм теперь способы, с помощью которых можно объединять множества и отношения между мощностями отдельных множеств и мощностью результирующего множества. Первый из них довольно очевиден. Теорема.
Если А В и С-Р,то (А ХС) (ВХР). Доказательство. Пусть Х: А - В н ф С- Р— биекции. Тогда (а, с) (д(а), д(с)) является биекцией между А Х С н ВХР. в" Теорема. Если 7~ — конечное множество и (Х, У)— разбиение Я, тогда 13! !л!+!У!. Доказательство. Так как 7. конечно, то Я - Х для некоторого лг ж Х и существует биекция у: Я- Х (рнс. 3.6). Более того, так как ХжЯ и УжЯ, то д(Х)жХ н х )((У)иХ . Пусть ф1 является биекцией из )((л) в Х р, для некоторого р1 и! г ~~!ж, где (ф1 ° д) (Х)~ Хгв .
Аналогично пусть $г— ~ бнекция из ,"<(У) в Хр 1 длЯ некотоРого Рг -.д т, ! где (Рг )()( У) - Х, . Тог- Рг ~ да если сч Х- Х опреде- Х ляется как о: х л+ р, ! то о является биекцией между Х„, и Хэ ~.р,~Хе . Следовательно, отобраязение ~р,.)((г), если ген Х, $Ф (сарг )((г), если ген У, является инъекцией и биективно (так как Я конечно) между Я и Хг,+г,. Таким образом, А Хт,+э,. Следовательно, т р1 + рг и !3! ° 1Х1+ 1У!.
Пример 3.5. Чтобы проиллюстрировать применение предыдущей теоремы, рассмотрим случай, когда 2 ° (а, Ь, с, д, в, 1), Х (Ь,е), У (а,с,А,1). 60 Тогда биекция между 7 и № задается следующим образом: д ((а, 5), (Ь, 1), (е, 6), (сК, 3), (е, 4), (1, 2)), и поэтому д(Х) - (1, 4), д (У) - (2, 3, 5, 6). Подходящими отображениями ф, являются ~уФ ((1, 2), (4, 1)), фз ((3, 1), (5, 2), (6, 3), (2, 4)). Поэтому если о определяется как х л + 2, то е(н д(Х) (1, 2), ~уз Х(У) (1, 2, 3, 4), и ° ~уз у(У) (3, 4, 5, 6). Комбинирование ф т и о~фз'д дает нужный результат.
з Предыдущий пример не является характерным в том смысле, что он требует очень тщательных манипуляций с биекциями. Обычно в этом нет необходимости, так как почти всегда можно сослаться на хорошо известные результаты. Закончим обсуждение следующим основным результатом. Если А и  — конечные множества, то А Х В конечно и !А ХВ! 1А! в!В!. Этот результат не только интересен сам по себе, но и дает способ для введения доказательства яо индукции. Доказательство по индукции использует два основных понятия, содержащихся в определении )ч: (1) Существует некоторый начальный элемент (в М это 1), (П) Для заданного утверждения, соответствующего некоторому элементу, существует метод, позволяющий перейти к следующему (в случае Я зто — создание следующего числа за наибольшим до сях пор числом, включенным в г!).
Более конкретно, если для некоторого нею г( (обычно нз 1, но не обязательно) мы можем доказать, что утверждение Р(не) справедливо и для любого я ю М (и ~ яс) справедливость Р(п) влечет справедливость Р(н+ 1) (здесь я+ 1 - следующий за п элемент), то заключаем, что Р(я) справедливо для всех т т яе. Шаг (!) является основанием индукции, шаг (11) — шаеом индукции, В д, ктв, г. веав 8$ Весь процесс, по существу, является прямым доказательством Р(п») ' ...
» Р(т) и, следовательно, осуществляет непосредственную про верку промежуточных результатов. Рассмотрим следующий пример. Пример 3.6. Если А и В конечны, то !А ХВ! !А!» !В!. Доказательство. Поскольку А и В конечны, то А г! с биекцией т: А - 6! и В г), для некоторых т, п»з г!. Будем использовать индукцию по и — размерности В.
Заметим, что от размерности А требуется ковечность, так как мы предполагаем знакомство только о умножением конечных величин. Осноеание индукции. Если В И, то А Х В ° И, и поэтому имеем тривиальное равенство )АХВ! О !А! «О !А!» !В!, Если В (6), то отображение А - А Х В такое, что а (а, 6), очевидно, биективно, и поэтому !А ХВ! * !А! !А(» 1 !А!» !В!. Шае индукции.
Предположим, что !А Х В,! - !А !. !В.!, где В» и В и !В»! й ж 6). Тогда !А !» !В„! т» й»з г( и существует бвекция ф А ХВ„Ь! +». Если й~п, то можно веять подмножество В, которое имеет 1 ° й+ 1 элементов. Пусть В, В»О Ы, где В,— множество из й злемеитов, и пусть отображение у, д: А Х В~- 1ч оп- ределяется следующим образом: )(: (а, к) т(а) + т*й, у: АХЫ- (т» й+1, ..., т ° й+ т), д. '(а, 6) ~р(а, Ь), если Ь ы В».
Очевидно, что д является биекцией на М«,ь»», и т» й+ т т» (й+ 1) т» ~, Позтому !А ХВ,! т»1 !А!» !В~!. Следовательно, тождество справедливо для всех подмножеств В, содер- жащихся в В, и позтомт !А ХВ! !А! ° !В!. г' ез Упражнение ЗЗ. (. Доказать, что отношение мея'ду множествами ((А, В): А — В) является отношением зквивалентности, 2. Построить биекцию между множествами ЕХг< и )ч' Х < !. 3. Доказать, что если А и  — множества и А О В конечно, то !А О В! + !А 0 В! !А ! + !В!. 4.
Доказать (от противного), что произвольная инъекция )ч — <) (<л ю )ч) является бпекцией. 5. Доказать (без использования равенства !Р(А) ! 2<*<), что для любого конечного множества А, такого что 1А! > 2, справедливо соотношение !У(А) ! ) !А!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
