[1] "xÎX (ax), следовательно, a – нижняя граница X. Пусть b – любая нижняя граница X, тогда ba, так как aÎX. Следовательно, a – наибольшая нижняя граница.
[2] "xÎX (ax), поскольку a – нижняя граница X, и значит это наименьший элемент, поскольку aÎX.
СЛЕДСТВИЕПусть М – частично упорядоченное множество, а Х – любое его подмножество. Тогда:
Если существует наибольший элемент a = max X, то a = sup X;
Если существует супремум a = sup X и aÎX, то a = max X.
Говорят, что частично упорядоченное множество линейно полно, если любое его линейно упорядоченное подмножество имеет супремум.
ПримерЕсли множество X конечно, то – линейно полно относительно .
1.8.5. Монотонные и непрерывные функции
…
Примеры
…
4. Пусть f : M ® M – некоторая функция. Тогда функция перехода к образам (см. 1.6.3.) F : 2M® 2M является монотонно возрастающей по включению.
ТЕОРЕМА 1Суперпозиция одинаково монотонных функции монотонна в том же смысле.
ДоказательствоПусть ab и g монотонно возрастает, тогда g(a) g(b). Но f также монотонно возрастает и значит f(g(a)) f(g(b)).
Функция f : M ® M, где M – частично упорядоченное множество, называется непрерывной, если для любой возрастающей последовательности a1 … an …, для которой существует супремум, выполнено равенство
f(sup{ai}) = sup{f(ai)}.
ЗАМЕЧАНИЕ Учитывая теоремы подраздела 1.8.1 и последнее замечание подраздела 1.8.2, непрерывность можно определить через строго убывающие и имеющие инфимум последовательности.
ТЕОРЕМА 2. Непрерывная функция монотонно возрастает.
Доказательство Пусть ab. Тогда sup{a, b} = b. Имеем f(b) = f(sup{a, b}) = sup{f(a), f(b)}. Следовательно, f(a) f(b).
ТЕОРЕМА 3Суперпозиция непрерывных функций непрерывна.
Рассмотрим функцию f : M ® M. Элемент xÎM называется неподвижной точкой функции f, если f(x) = x.
ЗАМЕЧАНИЕ Неподвижная точка функции f – это то же, что и корень уравнения f(x) = x.
Пример Пусть f : X ® X. Рассмотрим функцию перехода к образам F : 2X ® 2X. Тогда множество A = Ç {YÌX | F(Y)ÌY} (т. е. пересечение всех таких подмножеств Y множества X, образы которых являются подмножествами аргументов) является неподвижной точкой функции F. Покажем, что F(A) Ì A. Действительно, F(A) = F(Ç {YÌX | F(Y)ÌY}) Ì Ç F(Y) = A. Отсюда по монотонности F имеем F(F(A)) Ì F(A), то есть F(A) удовлетворяет условию для множеств Y и значит A Ì F(A). Имеем A = F(A) и значит A – неподвижная точка функции перехода к образам F.
Замечание Если A= Ç {YÌX | F(Y)ÌY} = Æ, то F(Æ) = Æ и пустое множество является неподвижной точкой функции перехода к образам по определению.
Вообще говоря, функция f : X ® X может не иметь неподвижных точек, иметь одну неподвижную точку или иметь их несколько, может быть даже бесконечно много. Если множество X упорядочено, и функция f : X ® X имеет неподвижные точки, то среди них можно выделить наименьшую неподвижную точку. Однако даже если функция имеет неподвижные точки, среди них может не быть наименьшей, просто потому, что не всякое, даже конечное частично упорядоченное множество имеет наименьший элемент.
Пример Наименьшей неподвижной точкой для функции перехода к образам F : 2X ® 2X является множество A = Ç {YÌX | F(Y)ÌY}, введенное в предыдущем примере. Действительно, пусть $BÌX(F(B)=B & AËB). Тогда F(B)ÌB, и значит, множество B является одним из множеств Y.Получается, что пересечение не является подмножеством одного их пересекаемых множеств – противоречие.
ТЕОРЕМА [о наименьшей неподвижной точке]. Если множество Х частично упорядочено, линейно полно, имеет наименьший элемент 0 = min X, и функция f : X ® X непрерывна и тотальна,dom f = X, то a = sup{f n(0) | n³0} является наименьшей неподвижной точкой функции f.
Доказательство Поскольку функция f тотальна, элементы f n(0) определены для любого n³0. Рассмотрим подмножество Y := {f n(0) | n³0}. Имеем: f 0(0)= 0f 1(0), поскольку 0 – наименьший элемент. Поскольку функция f непрерывна, она и монотонна, а значит f 1(0)= f(f 0(0)) f 2(0) = f(f 1(0)), f 2(0)= f(f 1(0)) f 3(0) = f(f 2(0)) и вообще f n(0) f n+1(0) для любого n³0. Таким образом, подмножество Y линейно упорядочено, а значит элемент a = sup{f n(0) | n³0} определен по условию теоремы.
Покажем теперь, что элемент a действительно является неподвижной точкой функции f, то есть f(a) = a. Имеем:
Покажем теперь, что a – наименьшая неподвижная точка. Пусть b – любая неподвижная точка. Поскольку f(b)=b, имеем "n³0 (f n(b) =b). Но 0b и функция f монотонна, следовательно "n³0 (f n(0) b), то есть b – верхняя граница множества {f n(0) | n³0}, а значит ab.
ЗАМЕЧАНИЕ Требование непрерывности в формулировке теоремы нужно только для того, чтобы гарантировать существование супремумов. Вообще говоря, если супремумы заведомо существуют, то от функции требуется только монотонность.
ОТСТУПЛЕНИЕ Фактически, приведенная теорема о наименьшей неподвижной точке служит обоснованием одного из случаев, когда для решения уравнения x=f(x) правомерно применять метод итераций: xi+1:=f(xi).