XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 13
Текст из файла (страница 13)
1.12 При этом если элемент Ь доминирует над элементом а, то кружочек, изображающий элемент Ь, располагается вьппе кружочка, изображающего элемент а, и соединяется с ним прямой линией. Иногда для большей наглядности из а в Ь ведут стрелку. На рис. 1.12 изображены диаграммы Хассе для упорядоченных множеств делителей чисел 2, б, ЗО и 36 по рассмотренному выше отношению делимости (см. пример 1.13.г). На рис. 1.13 приведена диаграм(о,Ь,с» ма Хассе для упорядоченного множества всех подмножеств трехэлемент(о„с ного множества (а, Ь, с) по отношению включения (см. пример 1.13.д).
Последовательность (хе)еен зле (а» (Ь» ментов упорядоченного множества называют неубыеоюецеб, если для 9 каждого 6 Е г( справедливо первее~- ство х; < х,+1. Элемент а упорядоченного множества (М, <) называют тпочной верхней гранью носледоваетьельнос1тьм (х;)1ен, если он есть точная верхняя грань множества всех членов последовательности". (а,Ь» (с» *Другвмн слоаамв, точнее верхвлл грань воследовательноств есть точнал верхнлл грань области ее эначевнй как фувкцнн натурального аргумента. 1.В. Уворюдочоввме мвохеотва 83 Двойственно определяется шочнал мижнл,в грань последовагпеаьносгпи.
Упорядоченное множество (М, <) называют имдуипзивмым, если: 1) оно содержит наименьший элемент; 2) всякал неубывающая последовательность элементов этого множества имеет точную верхнюю грань. Например, множество всех подмножеств некоторого множества по отношению включения будет индуктивным. Наименьший элемент — пустое множество, а точной верхней гранью произвольной неубывающей последовательности множеств будет объединение всех членов этой последовательности (наименьшее по включению множество, содержащее в качестве подмножества любой член последовательности). Определение 1.5. Пусть (Мм <) и (Мо, 4) — индуктивные упорядоченные множества.
Отображение у: М~ -~ Мо одного индуктивного упорядоченного множества в другое называют меирерывмььм, если для любой неубывающей последовательности ам ..., ао, ... элементов множества М~ образ ее точной верхней грани равен точной верхней грани последовательности образов ~(а~), ..., у(ао), ..., т.е. справедливо равенство у(яирао) = яира(а„). Определение 1.6.
Отображение у: М~ ~ Мо упорядоченных множеств (Мм ~<) и (Мз, 4) называют монотонным, если для любых а, Ьб М~ из а < Ь следует Яа) 4 ДЬ). Теорема 1.6. Всякое непрерывное отображение одного индуктивного упорядоченного множества в другое монотонно. ° Пусть у — непрерывное отображение индуктивного упорядоченного множества (Мм <) в индуктивное упорядоченное множество (Мо, 4). Пусть а,Ь Е М~ и а < Ь.
Образуем последовательность (хо1оеи, где х~ = а, а хо = Ь, и > 2. Эта послеДовательность неубывающая. Для нее япряо = яир(а, Ь) = Ь. В силу 84 1. МНОЖЕСТВА И ОТНОШЕНИЯ непрерывности отображения у 1(Ь) = У(зпрх„) = У(вир(а, Ь)) =вирЦ(а),1(Ь)), откуда следует, что у(а) 4 У(Ь). ~ Заметим, что функция у: й -+ К, непрерывная в смысле определений математического анализа, не обязана быть монотонным отображением упорядоченных множеств И с естественным числовым порядком, т.е. приведенное выше определение 1.5 непрерывности не вполне аналогично определению непрерывности в анализе [1].
Например, рассмотрим непрерывное в смысле определений математического анализа отображение у = — х числовой прямой с естественным числовым порядком на себя. Это отображение не является монотонным в смысле данного выше определения 1.6, поскольку, например, 0 < 1, однако неравенство у(0) = 0 < Д1) = -1 не выполняется. В общем случае монотонное в смысле определения 1.6 отображение не является непрерывным в смысле определения 1.5. Приведем пример, показывающий, что утверждение, обратное теореме 1.6, неверно. Пример 1.19. Рассмотрим множество всех точек отрезка [О, 1) числовой прямой с порядком, индуцированным естественным числовым порядком.
Это множество индуктивно: его наименьший элемент — О, а любая неубывающая последовательность элементов ограничена сверху и по признаку Вейерштрасса Щ имеет предел, который и будет ее точной верхней гранью. Любая кусочно непрерывная (но не непрерывная!) и монотонная в смысле обычных определений из курса математического анализа функция [Ц, отображающая этот отрезок на любой отрезок с порядком, индуцированным естественным числовым порядком, дает пример монотонного в смысле определения 1.6, но не непрерывного в смысле определения 1.5 отображения между индуктивными частично упорядоченными множества- 85 КВ. улорядочеввше множества ми. Например, пусть функция У имеет вид У= 05х, 0<х<05; 0,5+ О,бх, 0,5 ( (х < 1.
Это отображение монотонно. Для последовательности (х„) = 1, и Е Я, точная верхняя грань равна 0,5. Точная верх~ 2н+1 2 ' нял грань последовательности (У(х„)) равна 0,25, а У(впрх„) = = У(0,5) = 0,75. Следовательно, отображение не является непрерывным в смысле определения 1.5. Не следует путать отображение, монотонное в смысле опре. деления 1.6, с монотонными функциями из курса математического анализа.
Функция У: К -+ й будет монотонной в смысле определения 1.6 тогда и только тогда, когда она является неубывающей 11]. Для приложений особенно важны непрерывные отображения индуктивного упорядоченного множества в себя. Определение 1.7. Элемент а множества А называют неподвижной точкой отображения У: А ~ А, если У(а) = а. Элемент а упорядоченного множества М называют наименьшей неподвижной точко>Ъ отображения У: М -~ М, если он является наименьшим элементом множества всех неподвижных точек отображения У.
Теорема 1.7 (теорема о неподвижной точке). Любое непрерывное отображение У индуктивного упорядоченного множества (М, <) в себя имеет наименьшую неподвижную точку. Обозначим через О наименьший элемент множества М. Полагаем Уо(х) = х и У"(х) = У(У" '(х)) для любого и > О, т.е. У" (х) означает результат п-кратного применения У к х. Рассмотрим последовательность элементов М (У" (ОЦн>о = СО, У(О) > ", У" (О) > " 1 (1 7) 86 Е МНОЖЕСТВА Н ОТНОШЕНИЯ Докажем, что последовательность (1.7) неубывающая.
Используем метод математической индукции. Для элемента О, как наименьшего элемента множества М, имеем О = Уе(О) < < у (О). Пусть для некоторого натурального и верно соотношение ~" 1(О) < ~" (О). Согласно теореме 1.6, отображение ~ монотонно, и поэтому ~"'(О) = Щ" 1(О)) < У(1" (О)) = ~"+1(О), т.е. соотношение верно и для номера и+1. Согласно методу математической индукции, ~" (О) < ~"+~(О) для любого и Н М0, т.е.
последовательность (1.7) неубывающая. Следовательно, по определению индуктивного упорядоченного множества, она имеет точную верхнюю грань. Обозначим ее через ш 0 П Р ~ а ( (1.8) п>0 Докажем теперь, что если у неубывающей последовательности отбросить любое конечное число начальных членов, то ее точная верхняя грань не измените. Действительно, если а есть точная верхняя грань неубывающей последовательности (х„)„>0, то а ) х„для всякого и ) О. В частности, фиксируя произвольно й ) О, для любого и ) й имеем а ) х„, т.е.
а будет верхней гранью подпоследовательности (Яз)п)/с>0. Докажем, что а является точной верхней гранью этой подпоследовательности. Пусть 6 — какая-то ее верхняя грань, т.е. 6 ) я„для любого и ) й. Так как последовательность (х,Д„>0 неубывающая, то хр < хь для каждого р = О, й-1. Поскольку яь < 6, то в силу транзитнвности отношения порядка тр (~ 6 и тем самьпа Ь ) х„для любого и ) О, т.е. Ь есть верхняя грань всей последовательности (я„)„>0. Поскольку а = япрх„, то а < Ь п>0 и а = вар х„.
Следовательно, а — точная верхняя грань пода>0>0 последовательности (х„)„>ь. В силу непрерывности ~ получаем 87 1.8. Уяорвдочеввые ижасества Но И""(О) = р(У'(О) У'(О) " 1 = И"(О) = . а)0 з)1 Таким образом, доказано, что а является неподвижной точкой отображения У. Покажем теперь, что найденная неподвижная точка является наименьшей. Пусть для некоторого 9 е М у(у) = у. Так как О < р,а отображение ~, будучи непрерывным, монотонно, то ДО) < Ду) = 9, ~ЩО)) < ~(У(у)) = 9 и т.д. Следователь но, для любого и > 0 ~"(О) < у, т.е. элемент 9 есть верхняя грань последовательности 1Ц"(О))„>е.
Поскольку элемент а (как точная верхняя грань) есть наименьший элемент на множестве всех верхних граней этой последовательности, то р ) а. Таким образом, мы доказали, что произвольнал неподвижная точка отображения ~ не меньше элемента а, т.е. а — наименьшая неподвижная точка отображения ~. ~ Поиск неподвижной точки отображения 1: М -ь М можно рассматривать как задачу решения уравнения х = Дз). (1.9) Теорему о неподвижной точке можно трактовать таким образом: для непрерывного отображения ~ индуктивного упорядоченного множества в себя уравнение х = ~(я) имеет решение, т.е. существует такой хе Е М, что выполняется равенство зе = ~(зе), причем множество всех решений этого уравнения имеет наименьший элемент.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
