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

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

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

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

Доказательство. Пусть Х ={f_n | n = 0,1,2,…} – произвольная неубывающая цепь. Тогда для любого x А в ч.у.м. В имеем неубывающую цепь {f_n (х) | n=0,1,2,…}, которая в силу -полноты В имеет супремум sup{f_n (х) | n=0,1,2,…}= g(x). Таким образом, имеем функцию g: A A, которая является супремумом цепи Х ={f_n | n=0,1,2,…}.

В самом деле, g f_n для всех n и

( n) f_n h ( n)( х) f_n(x) h(х) ( x)( n) f_n(x) h(х)

( x) sup{f_n(x) | n =0,1,2,…} h(х) ( x) g(x) h(х)

g h.

Часть утверждения 11, касающаяся -полноты, следует из соображений двойственности.

Ч.т.д.

Утверждение 12. Если В – -полное ( -полное) ч.у.м. и А - произвольное ч.у.м., то множество Fun*(A,B) всех монотонных функций является -полным (соответственно, -полным) ч.у.м.

Доказательство. В доказательстве предыдущего утверждения функция g на самом деле монотонна, если f_n – монотонные функции. В самом деле,

x y f_n (x) f_n (y) для всех n N

f_n (x) sup{ f_k (y) | k N} для всех n N

sup{ f_k (x) | k N} sup{ f_k (y) | k N} g(x) g(y).

Ч.т.д.

3.2. Частичные функции

Многоместная частичная функция f (x₁,x₂,…,x_n) – это не всюду определенное отображение f : A₁ A₂ … A_n B, где A_j – область значений переменной x_j , а В – область значений функции.

Если к В добавить символ _┴ неопределенности и обозначить В⁺=В {_┴}, то функцию f можно считать обычным (всюду определенным) отображением f : A₁ A₂ … A_n B⁺.

В множестве В⁺ введем порядок: _┴ х для всех х В, а любые два различные элементы В будем считать несравнимыми. Например, если B ={a,b,c,d}, то ч.у.м. В⁺ имеет диаграмму Хассе, показанную на рис.

a b c d

_┴

Рис. 6

Утверждение 13. В⁺ является -полным ч.у.м. с наименьшим элементом _┴.

Доказательство тривиально.

Утверждение 14. Fun(A,B⁺) является -полным ч.у.м. с наименьшим элементом.

Доказательство. Это следствие утверждений 13 и 15.

Поскольку приходится делать суперпозицию функций, к области определения функций следует также присоединять символ неопределенности _┴.

Естественное продолжение функций

Пусть f : A₁ A₂ … A_n B – произвольная функция. Продолжим эту функцию на A₁⁺ A₂⁺ … A_n⁺ следующим образом:

f(x₁,x₂,…,x_n) = _┴, если x_j = _┴ хотя бы для одного 1 j n.

Таким образом, мы получаем функцию A₁⁺ A₂⁺ … A_n⁺ В⁺, которая называется естественным продолжением функции f.

Замечание. В дальнейшем мы воспользуемся следующими сокращениями:

А = A₁ A₂ … A_n , А⁺ = A₁⁺ A₂⁺ … A_n⁺, х = (х₁, х₂,…, х_n).

Утверждение 15. Если В – ч.у.м., то естественное продолжение любой функции f : A B является монотонной функцией A⁺ В⁺.

Доказательство. Предположим, что это не так. Тогда найдутся два значения a =(a₁,a₂,…,a_n) и b =(b₁,b₂,…,b_n) такие, что a<b , но не верно, что f*(a) f*(b), где f* – естественное продолжение функции f. Из a<b следует, что для некоторого k имеет место a_k = _┴ и a_{k ┴}. Но тогда должно быть f*(a) = _┴ и, значит, f*(a) f*(b). Мы получили противоречие.

Ч.т.д.

Утверждение 16. Одноместная функция f (x), f : A⁺ В⁺ монотонна тогда и только тогда, когда либо f – постоянная (т.е. f (x) = c для всех х А⁺), либо f (_┴) =_┴ , а значения f (х), х А, могут быть произвольными.

Доказательство. Ясно, что соотношение х у имеет место тогда и только тогда, когда либо х =_┴ и у произвольно, либо х = у. Пусть f – монотонная функция. Тогда, если х =_┴ , то f (_┴) = _┴ f (y), причем значение f (y) может быть произвольным элементом из В⁺. Если f (_┴) = с _┴ , то для всех х А имеем с f (х) (так как _┴ х), и следовательно, f (х) = с для всех х А⁺.

Наоборот, пусть f – произвольная функция A⁺ В⁺, но такая, что f (_┴) =_┴. Тогда f монотонна. В самом деле,

х у х =_┴ или х = у f (х) = f (_┴) = _┴ f (у) или f (х) = f (y).

Ч.т.д.

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

Утверждение 17. Если многоместная функция f(x₁,х₂,…,х_n), f : A⁺ В⁺ (n 2) монотонна, то либо f – постоянная функция, либо f (_┴ , _┴ ,…, _┴) =_┴ , а остальные значения функции могут быть произвольными.

Доказательство этого утверждения аналогично первой части доказательства утверждения 18.

Примеры. 1) Функция деления x/y из R R в R (где R – множество всех вещественных чисел) становится монотонной при естественном продолжении, т.е. если положить x/_┴ = _┴/x = _┴.

2) На множестве А⁺ А⁺, где А – любое множество, можно задать два отношения равенства:

(а) слабое равенство, обозначаемое «=», – это естественное продолжение равенства, заданного на А. Другими словами, «=» рассматривается как функция из А⁺ А⁺ в {true,false}⁺ ={true,false, _┴}:

/ true, если х, у А и х совпадает с у

(x = y) = false, если х, у А и х не совпадает с у

\ _┴, если х=_┴ или у=_┴

Как естественное продолжение, функция слабого равенства монотонна.

(б) сильное равенство, обозначаемое , определяется как функция из А⁺ А⁺ в {true,false}:

(х у) = true x и у совпадают как элементы А⁺ .

Сильное равенство не монотонно: если взять х =_┴ и x’= a и у = а, то будем иметь (x,y) (x’,y), но значения x y и x’ y не сравнимы, так как они есть (соответственно) false и true.

1. Определяющая функция def отображает А⁺ в {true,false}.

/ true, если x A

def(x) = |

\ false, если x =_┴

Функция def не монотонна: _┴ а А, def(_┴) = false, def(a) = true.

Функция if-then-else

В общем случае функция if-then-else отображает множество {true, false, _┴} A⁺ B⁺ в множество A⁺ B⁺. Если эту функцию считать естественно продолженной, то ее определение таково:

/ y, если х= true, z _┴

if x then y else z = z, если х= false, y _┴

\ _┴ , если х=_┴ или х=_┴ или х=_┴

Как и всякая естественно продолженная функция, так определенная функция if-then-else монотонна. Но существует другое определение if-then-else, при котором также получается монотонная функция:

/ y, если х= true

if x then y else z = z, если х= false

\ _┴ , если х=_┴

В самом деле, (x,y,z) (x’,y’,z’) означает, что x x’, y y’ и z z’. Ясно, что x x’ тогда и только тогда, когда x=_┴ или x=x’. В первом случае if x then y else z = и поэтому

if x then y else z if x’ then y’ else z’

Во втором случае, если x=x’= true, то

if true then y else z = y y’ = if true then y’ else z’ ;

если же x=x’= false, то

if false then y else z = z z’ = if false then y’ else z’ .

Утверждение 18. Для произвольной функции f (заданной на множестве A⁺ B⁺) всегда

if x then f (y) else f (z) f (if x then y else z)

Если же f (_┴) = _┴ , то

if x then f (y) else f (z) = f (if x then y else z).

Доказательство. Если х = true, то

f (if x then y else z) = f (if true then y else z) = f (y)

= if true then f (y) else f (z) = if x then f (y) else f (z).

Если x = false, то

f (if x then y else z) = f (if false then y else z) = f (z)

= if false then f (y) else f (z) = if x then f (y) else f(z).

Если x =_┴ , то

f (if x then y else z) = f (if _┴ then y else z) = f (_┴) _┴

= if _┴ then f (y) else f (z) = if x then f (y) else f(z).

Если f (_┴) = _┴ , то в последней цепочке соотношений неравенство следует заменить на равенство.

Ч.т.д.

Суперпозиция монотонных функций

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

Доказательство. Справедливость этого утверждения ясна из следующего рассуждения в частном случае.

Пусть даны монотонные функции f : A B C, g: C A и, h: C C. Тогда суперпозиция h(f (g(x), y)) является функцией, заданной на C B и принимающей значения в С. Покажем, что эта функция монотонна:

x x’, y y’ g(x) g(x’ ) f (g(x), y) f (g(x’ ), y’ )

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

Ч.т.д.

4. НЕПРЕРЫВНЫЕ ОПЕРАТОРЫ

Под оператором понимается отображение τ множества функций Fun(A,B) в себя: τ: Fun(A,B) Fun(A,B). Если B – - полное ч.у.м , то, как мы видели, множество функций Fun(A,B) также является -полным ч.у.м. Поэтому можно рассматривать непрерывные операторы. Оператор τ непрерывен, если

τ[sup{f_n | n N} = sup{τ[f_n] | n N}

для любой цепи f₁ f₂ … f_n … .

Примеры .

1) Пусть h(x) – произвольная функция из Fun(A,B). Оператор τ, переводящий произвольную функцию f в функцию h, непрерывен:

sup{τ[f_n] | n N} = sup{h | n N} = h = τ[sup{f_n] | n N}].

2) Тождественный оператор τ, τ[f] = f, непрерывен:

sup{τ[f_n] | n N} = sup{f_n | n N}] = τ[sup{f_n] | n N}].

3) Зададим оператор τ следующим образом:

τ[F](x,y) = F(y,x).

Таким образом, если обозначить f^ (x,y) =_df f (y,x), то оператор τ можно описать как такой, который преобразует функцию f в функцию f^ : τ[f] = f^ . Этот оператор непрерывен. В самом деле, пусть g = sup{f_n | | n N}, где f₀ f₁ f₂ … f_n … – произвольная цепь. Тогда ясно, что g^ = sup{f_n ^ | n N}. Поэтому

τ[sup{f_n | n N}] = τ[g] = g^ = sup{f_n ^ | n N}.

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

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