Лекции по СЯП (987656), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

• f (x,y) = sup{x,y}, f : A² A ;

• f (x,y) = inf{x,y}, f : A² A.

Утверждение 5. Суперпозиция монотонных функций есть монотонная функция.

Доказательство. Пусть, например, и A, B и C - какие-либо ч.у.м. и

имеем монотонные функции f : A² B A, g : A B A h : B B. Тогда функция s(x,y) = f(x,g(x,y),h(y)) также монотонна:

(x,y) (x’,y’) x x’, y y’ h(y) h(y’), g(x,y) g(x’,y’)

f (x, g(x,y), h(y)) f (x’, g(x’,y’), h(y’)), т.е.

s(x,y) s(x’,y’).

Ч.т.д.

Определение. Пусть f : A A – отображение множества А в себя. Элемент а А называется неподвижной точкой отображения f , если f (a) = a .

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

Доказательство. Пусть f : A A монотонное отображения. Положим

В = {x A | f (x) x}.

Благодаря тому, что А – полная решетка, это множество имеет инфимум c = inf B. Имеем:

с = inf B ( х B) c x

(монотонность f ) ( х B) f (c) f (x)

( х B) f (c) f (x) x ( х B) f (с) x

f (с) – нижняя грань для B

f(c) inf B, т.е.

f (с) с (1)

(монотонность f ) f (f (с)) f (с)

f (c) B inf B f (c), т.е.

c f (c) . (2)

Из (1) и (2) получаем, что c = inf B – неподвижная точка отображения f : f (c) = c. Покажем, что с – наименьшая неподвижная точка:

x – неподвижная точка f (x) = x x B inf B x

c x.

Двойственным образом, взяв В’ = {x A | f (x) x}, получим, что супремум d = sup B’ является наибольшей неподвижной точкой отображения f.

Ч.т.д.

Определения. Пусть А и В – произвольные полные верхние (нижние) полурешетки. Отображение и f : A B называется непрерывным сверху (снизу) , если для любого множества Х А верно, что f (sup X) = sup f (X) (соответственно, f (inf X) = inf f (X)).

Пусть А и В – произвольные решетки. Отображение и f : A B называется непрерывным, если для любого множества Х А верно, что f (sup X) = sup f (X) и f (inf X) = inf f (X).

Примеры. Пусть А = {x R | 0 x 1} – отрезок вещественной прямой с концами 0 и 1. Пусть в А задано обычное отношение порядка « », означающее «меньше или равно». Ясно, что А является полной решеткой. Тогда:

(1) всякое непрерывное отображение (в обычном смысле, принятом в математическом анализе) является непрерывным в полной решетке А ;

(2) функция f (x) = 0, если 0 х <1, и f (1) = 1 является монотонной, но не является непрерывной. В самом деле, возьмем, например, множество X = {1–¹/_n | n = 1,2,…}. Тогда имеем sup X =1, f (sup X) = 1, sup f (X) = 0 и поэтому f (sup X) sup f (X).

Утверждение 6. Пусть А и В – полные решетки. Тогда любое непрерывное отображение А в В монотонно.

Доказательство. Имеем для непрерывного отображения f :

x y sup{x,y} = y f (sup{x,y}) = f (y) sup{f (x), f (y)} = f (y)

f (x) f (y).

Таким образом, функция f монотонна.

Ч.т.д.

Утверждение 7. Пусть А и В – полные решетки и f : A A – непрерывное отображение. Тогда наименьшей и наибольшей неподвижными точками для f являются:

c = sup{f ⁿ(_┴) | n = 0,1,2,…} и d = inf{f ⁿ(_┴) | n = 0,1,2,…}.

Доказательство. Имеем:

c = sup{f ⁿ(_┴) | n = 0,1,2,…} = sup{{f ⁰(_┴)} {f ⁿ(_┴) | n = 1,2,…}}

= sup{{_┴} {f ⁿ(_┴) | n =1,2,…} = sup{f ⁿ(_┴) | n = 1,2,…};

f (c) = f (sup{f ⁿ(_┴) | n = 0,1,2,…})

= (благодаря непрерывности f) sup f ({f ⁿ(_┴) | n = 0,1,2,…})

= sup{f ⁿ⁺¹(_┴) | n = 0,1,2,…} = sup{f ⁿ(_┴) | n = 1,2,…} = c.

Следовательно, f (c) = c, т.е. с – неподвижная точка отображения f.

Если х – какая-либо неподвижная точка, то благодаря монотонности f имеем:

_┴ х f (_┴) f (x) = x f (_┴) x f (f (_┴)) = f ²(_┴) f (x) = x

f ²(_┴) x f ³(_┴) x …

Отсюда c = sup{f ⁿ(_┴) | n = 0,1,2,…} x. Следовательно, с - наименьшая неподвижная точка.

Двойственным образом доказывается, что d – наибольшая неподвижная точка.

Ч.т.д.

Рассматривая еще раз доказательство утверждения 11, можно заметить, что фактически здесь операция супремума применялась к частному виду множеств, а именно, к так называемым цепям.

Цепью в ч.у.м. А называется представленное последовательностью множество Х = {x_n | n = 0,1,2,…} такое, что либо

x₀ х₁ х₂ … х_{n –1} х_n … ,

либо

x₀ х₁ х₂ … х_{n –1} х_n … .

В первом случае говорят, что цепь является неубывающей, во втором случае – невозрастающей.

Ясно, что множество {f ⁿ(_┴) | n = 0,1,2,…} является неубывающей цепью, так как по монотонности f из _┴ f(_┴) получаем f (_┴) f ²(_┴) и, значит, имеем _┴ f(_┴) f ²(_┴) f ³(_┴) … f ^n-1(_┴) f ⁿ(_┴) … . Двойственным образом, множество {f ⁿ(T) | n = 0,1,2,…} является невозрастающей цепью.

Определение. Ч.у.м. называется полным по неубывающим (по невозрастающим) цепям, если в нем всякая неубывающая (соответственно, невозрастающая) цепь имеет супремум (соответственно, инфимум). Коротко такие ч.у.м. будем называть -полными (соответственно, -полными).

Определение. Пусть А – -полное ( -полное) ч.у.м. Отображение f : A A называется непрерывным снизу (соответственно, сверху), если для любой невозрастающей (соответственно, неубывающей) цепи Х А имеет место соотношение f (sup X) = sup f (X) (соответственно, соотношение f (inf X) = inf f (X) ).

Свойство ч.у.м быть -полным или -полным сохраняется при декартовых произведениях и при образовании множеств функций.

Утверждение 8. Если А и В – -полные ( -полные) ч.у.м. Тогда декартово произведение А В является -полным (соответственно, -полным).

Доказательство. Пусть X – неубывающая цепь в А В. Очевидно, что проекции X₁ = {x A | ( y) (x,y) X} и X₂ = {у A | ( х) (x,y) X} являются неубывающими цепями и, значит, имеют супремумы a =sup X₁ и b =sup X₂ . Тогда ясно, что sup X = (a,b).

Ч.т.д.

Теорема Клини. Пусть А – -полное ( -полное) ч.у.м., содержащее наименьший элемент _┴ (соответственно, наибольший элемент T) и f : A A – непрерывное снизу (соответственно, сверху) отображение. Тогда отображение f имеет наименьшую неподвижную точку c = sup{f ⁿ(_┴) | n = 0,1,2,…} и наибольшую неподвижную точку d = inf{f ⁿ(T) | n = 0,1,2,…}.

Доказательство. Множество {f ⁿ(_┴) | n = 0,1,2,…}, как мы видели, является неубывающей цепью. Двойственным образом, множество {f ⁿ(T) | n = 0,1,2,…}, Поэтому доказательство утверждения 13 устанавливает справедливость теоремы Клини. Ч.т.д.

3. МНОЖЕСТВА ФУНКЦИЙ

3.1. Функции со значениями в ч.у.м.

Для произвольных множеств А и В обозначим через Fun(A,B) множество всех функций, заданных на А и принимающих значения в В. Если В – ч.у.м., то порядок в В следующим образом индуцирует порядок в Fun(A,B):

f g _df ( x A) f (x) g(x).

Легко видеть, что Fun(A,B) будет решеткой, если В – решетка. Операции и в Fun(A,B) определяются так :

(f g)(x) = f(x) g(x) и (f g)(x) = f(x) g(x) для всех х А.

В том случае, когда оба А и В – ч.у.м., мы можем рассматривать монотонные функции. Через Fun*(A,B) обозначим множество всех монотонных функций из А в В. Так как Fun*(A,B) Fun(A,B), то в множестве всех монотонных функций определено отношение порядка. Таким образом, множество Fun*(A,B) является ч.у.м.

Ясно, если f и g – монотонные функции, то монотонными также будут и функции f g и f g:

х у f(x) f(у), g(x) g(у)

f(x) g(x) f(у) g(у), f(x) g(x) f(у) g(у)

(f g)(x) (f g)(x), (f g)(x) (f g)(x).

Следовательно, если В – решетка и А – ч.у.м., то Fun*(A,B) также решетка .

Утверждение 9. Если А – произвольное множество, а В является полной решеткой, то Fun(A,B) также является полной решеткой.

Доказательство. Пусть Х – произвольное множество функций, Х Fun(A,B). Покажем, что Х имеет супремум. Для каждого х А рассмотрим множество {f(х) | f X}. Это множество, как подмножество полной решетки В имеет супремум sup{f(х) | f X}. Положим g(x) = sup{f(х) | f X}.

Докажем, что функция g(x) является супремумом множества Х : g = sup X. Если h – произвольная верхняя грань для Х, то

( f X) f h ( f X) ( x A) f (x) h(x)

( x A) ( f X) f (x) h(x)

( x A) sup{f (x) | f X } h(x)

( x A) g (x) h(x) g h

Таким образом, если h – верхняя грань для Х , то g h. C другой стороны, g является верхней гранью для Х, так из определения функции g следует, что f(х) g(x) для всех f Х и всех х А. Значит, h есть наименьшая верхняя грань для Х .

Двойственным образом получаем, что функция h(x) = inf{f(х) | f X} является инфимумом для Х : h = inf X.

Ч.т.д.

Утверждение 10. Если А - ч.у.м. и В является полной решеткой, то Fun*(A,B) также является полной решеткой.

Доказательство. Пусть Х – произвольное множество монотонных функций, Х Fun*(A,B). Как подмножество решетки Fun(A,B), множество Х имеет супремум и инфимум. В утверждении 7 мы определили супремум как функцию g(x) = sup{f (x) | f X}. Функция f на самом деле является монотонной:

x y ( f X) f (x) f (y) sup{f (x) | f X} sup{ f (y) | f X}

g(x) g(y) .

Ч.т.д.

Характеристики

Список файлов лекций