Теорема. Пусть задано частично упорядоченное множество , тогда для любых функций равносильны следующие свойства:
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) – верно (противоречие со вторым условием). #