Формула обращения

Теорема. Пусть задано частично упорядоченное множество , тогда для любых функций равносильны следующие свойства:1) ;2) .Доказательство:Пусть матрица А – матрица смежности для . Тогда выполнение равенства (1) равносильно , .Поскольку данная полугруппа является коммутативной слева, то можно умножить на слева.Получим равносильность из (1) в (2). #Мат индукция - один из методов доказательства. Используется, чтобы доказать истинность некоего утверждения для всех натуральных чисел.Справедливость метода математической индукции.

1. Базис по индукции. Пусть P(1) – верно, т.е. верно P(k) для некоторого .
2. Индуктивный шаг. Если (P+k) – верно, то P(n) – верно.

Лемма. Множество является решеткой относительно операций , max, min.Докажем метод математической индукции от противного.Предположим, что для некоторых чисел натурального ряда метод математической индукции неверен.Пусть они образуют множество – решетка min(m,k)=m.

1. Если , то противоречие с первым условием.
2. Если , то (m-1) – не натуральное.

P(m-1+1) – верно, значит, P(m) – верно (противоречие со вторым условием). #