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

Теорема. Пусть задано частично упорядоченное множество , тогда для любых функций равносильны следующие свойства:

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) – верно (противоречие со вторым условием). #

Найти похожие вопросы