Упорядоченные множества. Теорема о неподвижной точке

Множество вместе с заданным на нем отношением порядка называют упорядоченным множеством.

Отношение порядка будем, как правило, обозначать < (или значками ⪯, ⊑ и т.п., похожими на ≤). При этом следует понимать, что даже на некотором множестве S ⊆ ℝ рассматриваться может любое отношение порядка, а не только естественный числовой порядок. Множество М с заданным на нем отношением порядка ≤ будем записывать как пару (М,≤). Записывая х ≤ у, мы будем говорить, что элемент х не больше элемента у.

Каждому отношению порядка ≤ на множестве М можно сопоставить следующие отношения.

1. Отношение, которое будем обозначать <, получается из исходного отношения порядка ≤ выбрасыванием всех элементов диагонали id_M, т.е. х < у для любых х,у∈М тогда и только тогда, когда х ≤ у и х ≤ у. Записывая х < у, мы будем говорить, что элемент х строго меньше элемента у. Из определения следует, что отношение < есть иррефлексивное, антисимметричное и транзитивное бинарное отношение на множестве М, т.е. оно является отношением строгого порядка.

2. Двойственный порядок. Это бинарное отношение на множестве М, называемое также и отношением, двойственным к отношению порядка ≤, определяется как бинарное отношение на множестве М, обратное к отношению ≤. Его обозначают ≥. Тогда для любых x, у условие х ≥ у равносильно тому, что у ≤ х. Можно без труда доказать, что отношение ≥ тоже является отношением порядка.

Записывая х≥у, мы будем говорить, что элемент х не меньше элемента у. Отношение строгого порядка, ассоциированное с ≥, договоримся обозначать >, говоря при этом, что элемент х строго больше элемента у, если х ≥ у и х ≠ у.

3. Отношение доминирования. Для двух элементов х и у, по определению, х ᐊ у тогда и только тогда, когда х строго меньше у и не существует такого элемента z, что х < z < у. Отношение ᐊ называют отношением доминирования (или просто доминированием), ассоциированным с отношением порядка ≤. Если имеет место х ≤ у, то говорят, что элемент у доминирует над элементом х.

Из определения следует, что отношение доминирования рефлексивно, антисимметрично, но не транзитивно. Оно может быть и пусто. Например, легко видеть, что пустым будет отношение доминирования, если исходный порядок является плотным бинарным отношением на соответствующем множе- множестве.

Пример 1.15. а. Рассмотрим множество действительных чисел с естественным числовым порядком. Пусть а < с. Известно, что для любых аи с найдется такое и, что а

По той же причине будет пустым отношение доминирования, ассоциированное с естественным числовым порядком на множестве рациональных чисел. Но на множестве целых чисел (опять-таки с естественным числовым порядком) отношение доминирования не пусто. Так, 1 ᐊ 2, —5 ᐊ —4, но, конечно, неверно, что 1 ᐊ 3, поскольку между единицей и тройкой существует "промежуточный" элемент — двойка.

б. На множестве всех подмножеств трехэлементного множества {а, b, с}, где в качестве отношения порядка взято отношение теоретико-множественного включения С, подмножество {а, b} доминирует над подмножествами {а} и {b}, но не доминирует над пустым множеством. В свою очередь, все множество {а, b, с} доминирует над любым своим двухэлементным подмножеством, но не доминирует над одноэлементным и над пустым.

в. По отношению делимости на множестве натуральных чисел 15 доминирует над 3 и 5, но 20 не доминирует над 5, так как существует япромежуточный" элемент — 10, делитель 20, который делится на 5, но не равен ни 20, ни 5. #

Рассмотрим упорядоченное множество (М, ≤) и его произвольное непустое подмножество В ⊆ М. Упорядоченное множество (B, ≤|_B), где ≤|_B — ограничение отношения ≤ на подмножество В, называют упорядоченным подмножеством упорядоченного множества (М, ≤).

Таким образом, можно переносить отношения порядка на непустые подмножества исходного упорядоченного множества. Как правило, вместо ≤|_B будем писать просто ≤ (если ясно, о каком подмножестве В идет речь). Порядок ≤|_B на подмножестве В называют также порядком, индуцированным исходным порядком ≤ на всем множестве А. Часто прибегают к такому выражению: „рассмотрим подмножество В упорядоченного множества (М, ≤) с индуцированным порядком", понимая под этим порядок ≤|_B.

Элементы х и у упорядоченного множества (М, ≤) называют сравнимыми по отношению порядка ≤, если х ≤ у или у ≤ х. В противном случае элементы х и у называются несравнимыми.

Упорядоченное множество, все элементы которого попарно сравнимы, называют линейно упорядоченным, а соответствующее отношение — отношением линейного порядка (или просто линейным порядком). Если индуцированный порядок на подмножестве упорядоченного множества является линейным, то это линейно упорядоченное подмножество называют цепью. Любое подмножество попарно не сравнимых элементов данного упорядоченного множества называют антицепью.

Замечание 1.5. Обратим внимание на то, что термину „упорядоченное множество" (в смысле приведенного определения) в [I] отвечает термин „частично упорядоченное множе- множество", а то, что мы называем линейно упорядоченным мно- множеством, в [I] называется просто упорядоченным множеством. Терминология этого вьшуска более принята в алгебраической литературе и литературе по дискретной математике. Употребление в [I] термина „частично упорядоченное множество" мотивировало желанием подчеркнуть, что в общем случае в упорядоченном множестве существуют не сравнимые элементы.

Пример 1.16. а. Отношение естественного числового порядка на множестве ℝ действительных чисел является отношением линейного порядка, поскольку для любых двух чисел а, b имеет место или неравенство а ≤ b, или неравенство b≤а.

б. Отношение делимости (см. пример 1.13.г) на множестве ℝ и отношение включения ⊆ на В (А) (см. пример 1.13.д) не являются линейными порядками, за исключением случая, когда А — одноэлементное множество. #

Пусть (А, ≤) — упорядоченное множество. Элемент а ∈ А называют наибольшим элементом множества А, если для всех х ∈ А выполняется неравенство х ≤ а.

Элемент b называют максимальным элементом множества А, если для всякого х ∈ А имеет место одно из двух: или х ≤ b, или х и b не сравнимы.

Аналогично определяются наименьший и минимальный элементы упорядоченного множества, а именно: наименьший элемент упорядоченного множества А — это такой его элемент а, что а≤х для каждого х ∈ А, а минимальный элемент — это такой элемент b ∈ А, что для любого х ∈ А элементы b и х не сравнимы или b ≤ х.

Покажем, что наибольший (наименьший) элемент множества, если он существует, является единственным. Действительно, полагая, что а и а' — наибольшие элементы А по отношению порядка ≤, получаем, что для всякого х ∈ А выполняется х ≤ а и х ≤ а'. В частности, а' ≤ a и а ≤ а', откуда ввиду антисимметричности любого отношения порядка следует, что a = а'. Аналогично доказывается единственность наименьшего элемента.

Замечание 1.6. Поскольку на одном и том же множестве могут быть определены разные отношения порядка (например, на множестве натуральных чисел — естественный числовой порядок и отношение делимости), то, когда это необходимо, мы будем говорить о наибольших, наименьших (соответственно максимальных и минимальных) элементах по данному отношению порядка, уточняя тем самым, о каком отношении порядка идет речь. #

Следующие примеры показывают, что максимальных (минимальных) элементов может быть сколько угодно*.

Пример 1.17. Рассмотрим множество точек плоскости с некоторой фиксированной прямоугольной декартовой системой координат. Координаты каждой точки плоскости задаются упорядоченной парой (x, у) действительных чисел. Отношение порядка на множестве точек плоскости определим следующим образом: (а, b) < (c,d), если и только если а ≤ с и b ≤ d. Рассмотрим множество точек треугольника ОАВ (рис. 1.11, а). Точка с координатами (0,0) является наименьшим элементом этого множества. Максимальными элементами являются все точки, лежащие на стороне АВ. Наибольшего элемента нет. #

Пусть (А, ≤) — упорядоченное множество и В ⊆ А. Элемент а ∈ А называется верхней (соответственно нижней) гранью множества B, если для всех элементов х ∈ В имеет место (х ≤ а) (соответственно (х ≥ а)).

*Но заметим, что если у множества есть наибольший (соответственно наименьший) элемент, то он является единственным максимальным (соответственно минимальным) элементом данного множества.

Наименьший элемент множества всех верхних граней (соответственно наибольший элемент множества всех нижних граней) множества В называют точной верхней гранью В (соответственно точной нижней гранью В) и обозначают supB (infB).

Множество всех верхних (нижних) граней множества В называют верхним (нижним) конусом В и обозначают B^▽ (соответственно В^Δ).

В отличие от наибольшего и наименьшего элементов множества В элементы supВ и infВ не обязаны принадлежать множеству В. Точная верхняя (нижняя) грань множества существует не всегда.

Пример 1.18. а. Рассмотрим множество D точек прямоугольника ОАВС (рис. 1.11, б) с заданным в примере 1.17 отношением порядка. Точка О является точной нижней гранью, а точка В — точной верхней гранью этого множества. Обе точки принадлежат множеству.

Если рассмотреть множество F (рис. 1.11, б) с тем же отношением порядка, то увидим, что точная нижняя грань (точка О) и точная верхняя грань (точка Е) множества F существуют, но не принадлежат множеству.

б. На числовой прямой с „выколотой" точкой b для полуинтервала [а, b) множество верхних граней есть (b, +∞), но точной верхней грани нет. #

Упорядоченное множество (М, ≤) называют вполне упорядоченным, если его любое непустое подмножество имеет наименьший элемент.

Множество натуральных чисел с отношением естественного числового порядка вполне упорядоченное. Множество целых чисел не вполне упорядоченное, поскольку оно не имеет наименьшего элемента. Аналогично множества рациональных и действительных чисел не являются вполне упорядоченными. Можно показать, что справедлив принцип двойственности для упорядоченных множеств. Пусть (М, ≤) — произвольное упорядоченное множество. Тогда любое утверждение, доказанное для порядка ≤, останется справедливым для двойственного порядка ≤, если в нем:

1. порядок ≤ заменить на порядок ≥ и наоборот
2. наименьший (минимальный) элемент заменить наибольшим (максимальным) элементом и наоборот;
3. inf заменить на sup и наоборот.

Например, если для некоторого a ∈ М и для В ⊆ М мы доказали, что a = supВ при заданном отношении порядка, то для двойственного порядка a = infВ.

Говорят также и о взаимно двойственных определениях: если в любом определении, связанном с упорядоченным множеством, произвести взаимные замены согласно принципу двойственности, то получится новое определение, называемое двойственным к исходному. Так, определение наибольшего (максимального) элемента множества двойственно к определению наименьшего (минимального) элемента, и наоборот. Часто употребляют оборот речи: „двойственным образом..." (или „двойственно..."), понимая под этим переход к утверждению или определению, которое двойственно к исходному.

Рассмотрим теперь некоторые способы наглядного представления упорядоченных множеств.

Конечное упорядоченное множество можно графически изобразить в виде так называемой диаграммы Хассе. На этой Диаграмме элементы множества изображаются кружочками.

При этом если элемент b доминирует над элементом а, то кружочек, изображающий элемент b, располагается выше кружочка, изображающего элемент а, и соединяется с ним прямой линией. Иногда для большей наглядности из а в b ведут стрелку. На рис. 1.12 изображены диаграммы Хассе для упорядоченных множеств делителей чисел 2, 6, 30 и 36 по рассмотренному выше отношению делимости (см. пример 1.13.г).

На рис. 1.13 приведена диаграмма Хассе для упорядоченного множества всех подмножеств трехэлементного множества {a,b,c} по отношению включения (см. пример 1.13.д). Последовательность {x_i}_i∈ℕ элементов упорядоченного множества называют неубывающей, если для каждого i∈ℕ справедливо неравенство x_i≤x_i+1.

Элемент а упорядоченного множества (М, ≤) называют точной верхней гранью последовательности {x_i}_i∈ℕ если он есть точная верхняя грань множества всех членов последовательности*.

* Другими словами, точная верхняя грань последовательности есть точная верхняя грань области ее значений как функции натурального аргумента.

Двойственно определяется точная нижняя грань дователъности.

Упорядоченное множество (М, ≤) называют индуктивным, если:

1. оно содержит наименьший элемент;
2. всякая неубывающая последовательность элементов этого множества имеет точную верхнюю грань.

Например, множество всех подмножеств некоторого множества по отношению включения будет индуктивным. Наименьший элемент — пустое множество, а точной верхней гранью произвольной неубывающей последовательности множеств будет объединение всех членов этой последовательности (наименьшее по включению множество, содержащее в качестве подмножества любой член последовательности).

Определение 1.5. Пусть (M₁, ≤) и (М₂, ⪯) — индуктивные упорядоченные множества. Отображение f: M₁ → М₂ одного индуктивного упорядоченного множества в другое называют непрерывным, если для любой неубывающей последовательности а₁, ..., а_n, ... элементов множества M₁ образ ее точной верхней грани равен точной верхней грани последовательности образов f(а₁), ..., f(а_n), ..., т.е. справедливо равенство f(supa_n) =supf(_n).

Определение 1.6. Отображение f: M₁ → М₂ упорядоченных множеств (M₁, ≤) и (М₂, ⪯) называют монотонным, если для любых a, b ∈ M₁ из a ≤ b следует f(а) ⪯ f(b.

Теорема 1.6. Всякое непрерывное отображение одного индуктивного упорядоченного множества в другое монотонно.

◀ Пусть f — непрерывное отображение индуктивного упорядоченного множества (M₁, ≤) в индуктивное упорядоченное множество (М₂, ⪯). Пусть a, b ∈ M₁ и а ≤ b. Образуем последовательность {x_n}_n∈ℕ где х₁ = а, а х_n = b, n ≥ 2. Эта последовательность неубывающая. Для нее supx_n = sup {a, b} = b. В силу непрерывности отображения f

f(b) = f(supx_n) = f(sup{a, b}) = sup{f(a), f(b))},

откуда следует, что f(a) ⪯ f(b). >

Заметим, что функция f: ℝ → ℝ, непрерывная в смысле определений математического анализа, не обязана быть монотонным отображением упорядоченных множеств ℝ с естественным числовым порядком, т.е. приведенное выше определение 1.5 непрерывности не вполне аналогично определению непрерывности в анализе [I]. Например, рассмотрим непрерывное в смысле определений математического анализа отображение у = —х числовой прямой с естественным числовым порядком на себя. Это отображение не является монотонным в смысле данного выше определения 1.6, поскольку, например, 0≤1, однако неравенство f(0)=0≤f(1)=—1 не выполняется.

В общем случае монотонное в смысле определения 1.6 отображение не является непрерывным в смысле определения 1.5. Приведем пример, показывающий, что утверждение, обратное теореме 1.6, неверно.

Пример 1.19. Рассмотрим множество всех точек отрезка [0,1] числовой прямой с порядком, индуцированным естественным числовым порядком. Это множество индуктивно: его наименьший элемент — 0, а любая неубывающая последователь- последовательность элементов ограничена сверху и по признаку Вейерштрасса [I] имеет предел, который и будет ее точной верхней гранью. Любая кусочно непрерывная (но не непрерывная!) и монотонная в смысле обычных определений из курса математического анализа функция [I], отображающая этот отрезок на любой отрезок с порядком, индуцированным естественным числовым порядком, дает пример монотонного в смысле определения 1.6, но не непрерывного в смысле определения 1.5 отображения между индуктивными частично упорядоченными множествами. Например, пусть функция f имеет вид

Это отображение монотонно. Для последовательности точная верхняя грань равна 0,5. Точная верхняя грань последовательности {f(x_n)} равна 0,25, a f(supx_n) = f(0,5) = 0,75. Следовательно, отображение не является непрерывным в смысле определения 1.5. #

Не следует путать отображение, монотонное в смысле определения 1.6, с монотонными функциями из курса математического анализа. Функция f: ℝ → ℝ будет монотонной в смысле определения 1.6 тогда и только тогда, когда она является неубывающей [I].

Для приложений особенно важны непрерывные отображения индуктивного упорядоченного множества в себя.

Определение 1.7. Элемент а множества А называют неподвижной точкой отображения f: ℝ → ℝ, если f(а) = а.

Элемент а упорядоченного множества М называют наименьшей неподвижной точкой отображения f: ℝ → ℝ, если он является наименьшим элементом множества всех неподвижных точек отображения f.

Теорема 1.7 (теорема о неподвижной точке). Любое непрерывное отображение f индуктивного упорядоченного множества (М, ≤) в себя имеет наименьшую неподвижную точку.

<4 Обозначим через O наименьший элемент множества М. Полагаем f⁰(x) = x и fⁿ(x) = f(f^n-1(x)) для любого n > 0, т.е. fⁿ(x) означает результат n-кратного применения f к х. Рассмотрим последовательность элементов М

{fⁿ(O)_n≥0 = {O, f(O),..., fⁿ (O),...}. (1.7)

Докажем, что последовательность (1.7) неубывающая. Используем метод математической индукции. Для элемента О, как наименьшего элемента множества М, имеем О = f⁰(О) ≤ f⁰. Пусть для некоторого натурального n верно соотношение f^n-1(O)≤fⁿ(O). Согласно теореме 1.6, отображение f монотонно, и поэтому fⁿ(O) = f(f^n-1(O))≤f(fⁿ(O))=fⁿ⁺¹(O), т.е. соотношение верно и для номера n + 1. Согласно методу математической индукции, fⁿ(O)≤fⁿ⁺¹(O) для любого n ∈ ℕ₀, т.е. последовательность (1.7) неубывающая. Следовательно, по определению индуктивного упорядоченного множества, она имеет точную верхнюю грань. Обозначим ее через а:

Докажем теперь, что если у неубывающей последовательности отбросить любое конечное число начальных членов, то ее точная верхняя грань не изменится.

Действительно, если а есть точная верхняя грань неубывающей последовательности {x_n}_n≥0 то а ≥ x_n для всякого n ≥ 0. В частности, фиксируя произвольно k > 0, для любого n ≥ k имеем а ≥ x_n, т.е. а будет верхней гранью подпоследовательности {x_n}_n≥k>0

Докажем, что а является точной верхней гранью этой подпоследовательности. Пусть b — какая-то ее верхняя грань, т.е. b≥x_n для любого n ≥ k. Так как последовательность {x_n}_n≥0 неубывающая, то х_p≤х_k для каждого р = 0,k—1. Поскольку х_k ≤ b, то в силу транзитивности отношения порядка х_p ≤ b и тем самым b ≥ х_n для любого n ≥ 0, т.е. b есть верхняя грань

Таким образом, доказано, что а является неподвижной точкой отображения f.

Покажем теперь, что найденная неподвижная точка является наименьшей. Пусть для некоторого у ∈ M f(у) = у. Так как О ≤ у, а отображение f, будучи непрерывным, монотонно, то f(О) ≤ f(y) = у, f(f(О)) ≤ f(f(у)) = у и т.д. Следовательно, для любого n ≥ О fⁿ(О) ≤ у, т.е. элемент у есть верхняя грань последовательности {fⁿ(O)}n≥0. Поскольку элемент a (как точная верхняя грань) есть наименьший элемент на множестве всех верхних граней этой последовательности, то у ≥ а. Таким образом, мы доказали, что произвольная неподвижная точка отображения f не меньше элемента а, т.е. а — наименьшая неподвижная точка отображения f. >

Поиск неподвижной точки отображения f: M → M можно рассматривать как задачу решения уравнения

x = f(x).     (1.9)

Теорему о неподвижной точке можно трактовать таким образом: для непрерывного отображения f индуктивного упорядоченного множества в себя уравнение х = f(x) имеет решение, т.е. существует такой x₀ ∈ М, что выполняется равенство x₀ = f(x₀), причем множество всех решений этого уравнения имеет наименьший элемент. Этот элемент и будет наименьшей неподвижной точкой отображения f.

Отметим, что доказательство теоремы о неподвижной точке конструктивное: оно дает метод получения неподвижной точки. Для ее нахождения надо построить последовательность вида (1.7) и найти ее точную верхнюю грань.

Пример 1.20. Приведем простой пример вычисления наименьшей неподвижной точки. В качестве индуктивного упорядоченного множества М возьмем отрезок [0,1] с естественным числовым порядком ≤. Согласно примеру 1.19, это индуктивное упорядоченное множество.

Рассмотрим на этом множестве уравнение х = 1/2х + 1/4. Можно показать, что для индуктивного упорядоченного множества М любая монотонная функция f: [0,1] → [0,1], непрерывная в смысле определения из курса математического анализа, непрерывна и в смысле данного выше определения. Действительно, для любой неубывающей последовательности {х_n} на множестве [0,1] справедливо равенство

Следовательно, правая часть данного уравнения непрерывна.

Заметим, что если бы в правой части стояла линейная функция с отрицательным коэффициентом при х, то условие непрерывности функции в смысле приведенного выше определения было бы уже нарушено, поскольку такая функция не является монотонной в смысле определения 1.6.

Наименьшим элементом рассматриваемого множества является число 0. Вычисляем:

f⁰(0) = 0,

f¹(0) = 1/4,

f²(0) = (1/2)⋅(1/4)+1/4 = 3/8

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

получая последовательность приближений к наименьшей неподвижной точке.

Можно проверить (например, с помощью метода математической индукции), что f⁰(0) =   2ⁿ-1  2ⁿ⁺¹       , n ∈ ℕ. Предел этой последовательности равен 1/2. Таким образом, наименьшая неподвижная точка отображения f, определяемого правой частью уравнения, равна 1/2. Это единственная в данном случае неподвижная точка отображения f, что, конечно, очевидно и без теоремы 1.7 о неподвижной точке. Но здесь мы нарочно рассмотрели простой пример, показав, как можно решать подобные уравнения, основываясь на доказательстве теоремы. Мы не будем пока приводить более сложные примеры, так как интересные приложения теоремы о неподвижной точке имеются в теории графов и теории автоматов, и вернемся к этой теореме при решении задачи о путях в ориентированных графах.