Теорема. Пусть задано частично упорядоченное множество 
, тогда для любых функций 
равносильны следующие свойства:
1) 
;
2) 
.
Доказательство:
Пусть матрица А – матрица смежности для 
. Тогда выполнение равенства (1) равносильно 
, 
.
Поскольку данная полугруппа является коммутативной слева, то можно умножить на 
слева.
Получим равносильность из (1) в (2). #
Мат индукция - один из методов доказательства. Используется, чтобы доказать истинность некоего утверждения для всех натуральных чисел.
Справедливость метода математической индукции.
- Базис по индукции. Пусть P(1) – верно, т.е. верно P(k) для некоторого
. - Индуктивный шаг. Если (P+k) – верно, то
P(n) – верно.
Лемма. Множество 
является решеткой относительно операций 
, max, min.
Докажем метод математической индукции от противного.
Предположим, что для некоторых чисел натурального ряда метод математической индукции неверен.
Пусть они образуют множество 
– решетка 
min(m,k)=m.
- Если
, то противоречие с первым условием. - Если
, то (m-1) – не натуральное.
P(m-1+1) – верно, значит, P(m) – верно (противоречие со вторым условием). #