XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 14
Текст из файла (страница 14)
Этот элемент и будет наименьшей неподвижной точкой отображения ~. Отметим, что доказательство теоремы о неподвижной точке конструктивное: оно дает метод получения неподвижной точки. Для ее нахождения надо построить последовательность вида (1.7) и найти ее точную верхнюю грань. Пример 1.20. Приведем простой пример вычисления наименьшей неподвижной точки. В качестве индуктивного упорядоченного множества М возьмем отрезок (О, 1] с естественным 88 1. МНОЖЕСТВА И ОТНОШЕНИЯ числовым порядком <. Согласно примеру 1.19, это индуктивное упорядоченное множество.
1 1 Рассмотрим на этом множестве уравнение х = -х+ —. Мож- 2 4 но показать, что для индуктивного упорядоченного множества М любая монотоннал функция /: [О, Ц -+ [О, Ц, непрерывная в смысле определения из курса математического анализа, непрерывна и в смысле данного выше определения. Действительно, для любой неубывающей последовательности (х„) на множестве [О, Ц справедливо равенство зир(х„1 = 1пп х„ [1]. В сия-ни лу непрерывности функции У в смысле определения из курса математического анализа имеем /[ Бш х„) = 1пп /(х„). Так и-+оо я~оо как функция / монотонна, то Щх„))„>е — неубывающая последовательность и Иш /(х„) = зир/(х„).
В итоге получаем /(вверх„) = /[ 1пп х„) = Вш /(х„) = вар/(х„). Следовательно, правая часть данного уравнения непрерывна. Заметим, что если бы в правой части стояла линейная функция с отрицательным коэффициентом при х, то условие непрерывности функции в смысле приведенного вьппе определения было бы уже нарушено, поскольку такая функция не является монотонной в смысле определения 1.6. Наименьшим элементом рассматриваемого множества является число О.
Вычисляем: УО(0) /~(0) = 1/4, / (0) = (1/2) (1/4) + 1/4 = 3/8, У~(0) = (1/2) ' (3/8) + 1/4 = 7/16, получая последовательность приближений к наименьшей неподвижной точке. Можно проверить (например, с помощью метода матема2п тической индукции), что /"(0) = — „,, и Е М. Предел этой 89 последовательности равен 1/2.
Таким образом, наименьшая неподвижная точка отображения у, определяемого правой частью уравнения, равна 1~2. Это единственная в данном случае неподвижная точка отображения у, что, конечно, очевидно и без теоремы 1.7 о неподвижной точке. Но здесь мы нарочно рассмотрели простой пример, показав, как можно решать подобные уравнения, основываясь на доказательстве теоремы. Мы не будем пока приводить более сложные примеры, так как интересные приложения теоремы о неподвижной точке имеются в теории графов и теории автоматов, и вернемся к этой теореме при решении задачи о путях в ориентированных графах. 1.9.
Мощность множества Некоторые сведения о мощности множества приведены в [Ц. Здесь мы рассмотрим это понятие более подробно. Множество А равномощно множеству В, если существует биекиил у: А~В. Из того, что существует биекция у: А -+ В, следует, что соответствие у 1 есть биекция В на А (см. 1.4).
Поэтому если А равномощно В, то и В равномощно А, и мы можем говорить, что множества А и В равномоеаны. Факт равномощности множеств А и В будем записывать так: А В. Иэ определения равномощности и свойств биекции также следует, что для любого множества А имеет место А А (тождественное отображение есть биекция множества А на себя); а для любых множеств А, В, С вз А ° В и В ° С следует А С (компоэииил биекций есть биекция). Таким образом, отношение равномощности множеств есть отношение эквивалентносшй, заданное на „множестве всех 'Зачастую в литературе по теории множеств равномопщые множества и называют „зквиваиентными множествами". Однако следует различать общее понлтие отношение зквнвалентности и его частный случай — эквивалентность, или равномощность, множеств.
90 Ь МНОЖЕСТВА И ОТНОШЕНИЯ множеств" (на самом деле на множестве всех подмножеств некоторого универсальноео множесшва). Если мы обозначим через ~А~ класс эквивавеншносши множества А по отношению, то утверждение о равномощности множеств А и В можно записать так: ~А~ = ~В~. Этот класс эквивалентности ~А~ называют мощностью мноисвсепва А. Конечные множества А = (а1, ..., а„) и В = (Ь1 " бш) равномощны тогда и только тогда, когда множества А и В состоят из одного и того же числа элементов, т.е. п = ш. Отсюда, в частности, следует, что конечное множество не является рзлномощным никакому своему собственному подмножеству. Это свойство конечных множеств можно сформулировать так. Теорема 1.8. Если А — конечное множество и у: А -~ -+ А — инъекция, то она является сюръекцией и, следовательно, биекцией. ф В силу приведенных выше соображений мощностью конечного множества А = (ап..., а„) можно считать натуральное число п, так как, задавая такое число, мы задаем и класс всех (попарно равномощных) множеств вида (ам..., а„).
Обратно, каждый такой класс однозначно определяет натуральное число п как число элементов в каждом множестве данного класса. Естественно считается, что мощность пустого множества равна нулю. Перейдем теперь к исследованию мощности бесконечных множеств. Таковы хорошо известные нам числовые множества М, Е, Щ К и О. Любое множество, равномощное множеству всех натуральных чисел, называют счешным. Мощность счетного множества обозначают Ие (читается „алеФ нуль" ). Любую биекцию ьс г1 -+ М называют нумерацией счетного множества М; если элемент М есть и(п) для некоторого п Е М, то этот элемент М обозначаем через а„, называя на- 91. 1.9.
Мицвость мвожества туральное число и номером элемента а„ относительно данной нумерации и. Таким образом, элементы счетного множества можно перенумеровать, записав их в виде последовашельиосши ам ..., а„, ... или (а„)„еи. Другими словами, счетное множество есть область значений некоторой функции натурального аргумента. Пример 1.21. а. Множество всех нечетных натуральных чисел счетно. Нумерацию и можно задать так: и(п) = 2п — 1, п Е М. б. Множество всех натуральных чисел, делящихся на заданное число л > 2, счетно. Нумерацию и можно задать так: и(п) = лп, и е Я. В частности, при й = 2 получаем, что множество всех четных чисел счетно.
Этот и предыдущий примеры показывают, что бесконечное (счетное) множество может иметь собственное равномощное ему подмножество. в. Множество Е всех целых чисел счетно. Нумерацию можно установить так: и(п) = з — 1, и = 2л (четко); — и = 2Й вЂ” 1 (не четно). ф в+1 Рассмотрим свойства счетных множеств. Теорема 1.9.
Любое бесконечное множество содержит счетное подмножество. ч Пусть Мз — бесконечное множество. Значит, оно не пусто и существует элемент а~ Е Мо. Положим М~ = Мо 1(ад~. Множество М~ не пусто, так как в противном случае имело бы место равенство Ме = (а~), что противоречит предположению о бесконечности Ме. Выберем элемент аз Е М~ и положим Мз = Мд ~(аг) = Мо~1ад, аз).
Множество Мз также не пусто, поскольку иначе мы бы имели Мо = (ад, аз1 и множество Мз было бы конечным. 1. МНОЖЕОТВА И ОТНОШЕНИЯ Методом математической индукции можно показать, что для любого и > 1 множество М„= Ме ~(ам...,а,Д, где а1 6 Е Ме, ..., а„Е М„м не пусто. Тогда существует элемент а„+1 Е М„и а„+1 ф М„+1 = М„~ ~аз+1).
Таким образом, все элементы а„, и Е М, попарно различны и множество (аьс и Е г1) счетно, а его нумерация может быть задана так: и(п) = а„. > Теорема 1.10. В любом бесконечном множестве можно выделить два не пересекающихся между собой счетных подмножества. ~ Разобьем множество натуральных чисел на два подмножества: М1 = (и: и = 2я — 1, к Е г1) (множество нечетных чисел), и Мз = (гк п = 2Й, я Е Щ (множество четных чисел). Оба эти множества счетны (см. пример 1.21). Согласно теореме 1.9, бесконечное множество содержит некоторое счетное подмножество А.
Пусть установлена некоторая его нумерация. Разобьем это подмножество на два подмножества: всех элементов с четными и всех элементов с нечетными номерами. По построению эти подмножества не пересекаются и являются счетными, поскольку счетны множества четных и нечетных чисел. ° Теорема 1.11.
Любое подмножество счетного множества конечно или счетно. < Пустое подмножество конечно по определению. Пусть М— счетное множество, а  — его некоторое непустое подмножество. Поскольку множество М счетно, можно считать, что задана некоторая его нумерация. Следовательно, каждый элемент подмножества В имеет свой номер. Запишем номера элементов множества В в порядке возрастания: 1м ..., 1„, ... Если среди них есть наибольший номер 1р, то подмножество В конечно. В противном случае получим счетное подмножество 1а;„а;„..., а;„,...), нумерация которого установлена так: и(п) =а;„.
и 93 КО. Мохцаость мяоиества Теорема 1.12. Объединение любого не более чем счетного семейства счетных множеств счетно. ч Пусть (А;)сег — конечное или счетное семейство счетных множеств. Рассмотрим сначала случай, когда множества А; попарно не пересекаются. В этом случае нумерация объединения конечного семейства счетных множеств может быть проведена по схеме, изображенной на рис. 1.14, а нумерация объединения счетного семейства счетных множеств — по схеме, приведенной на рис. 1.15. ао-~ аи аи-~аи " аи ад~ аи -~ " а,„-~ г~ га а„аи "а,".
аи аи" Ф~ аи "и " аэ а„, а,а ам а„а„„... аа аа "' оъ Рис. 1.14 Рис. 1.1$ Пусть теперь (Аа)аеи — произвольное счетное семейство счетных множеств, т.е. множества А; могут пересекаться. В этом случае, применяя указанные на рис. 1.14 и 1.15 схемы нумерации к конечному или счетному объединению счетных множеств, следует пропускать каждый раз элементы, которые уже получили номера. В Полезно отметить также и следующий факт. Теорема 1.13. Объединение конечного и счетного множеств счетно. ф Если множество конечно или счетно, его называют не более чем счетиным. Семебстпво (А;)сег множеств называют ие более чем счетным, если множество (индексов) 1 не более чем счетно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
