Доказательство

Дополнение

К курсу «Дискретная математика для программистов»

Наименьшая неподвижная точка функции

Изложение построено в форме дополнений к учебнику «Дискретная математика для программистов 3-е издание». Места дополнений указаны с помощью номеров параграфов учебника.

1.6.3.

…

Пусть задана функция f : M ® M, а функции F, F^–1 : 2^M®2^M обозначают функции перехода к образам и прообразам соответственно. Тогда нетрудно показать, что

"X, Y Ì M (F(XÇY) Ì F(X) Ç F(Y)) и "X, Y Ì M (F(XÈY) Ì F(X) È F(Y)).

Обычно по определению полагают, что F(Æ) = F^–1(Æ) = Æ.

1.6.4.

…

Поскольку функция является отношением, можно ввести степень функции относительно суперпозиции. Степенью n функции f (обозначение f ⁿ) называется n-кратная суперпозиция функции f. Соответственно, f ⁰(x) = x, f ¹(x) = f(x), и вообще f ⁿ = f ° f ^n–1.

ЗАМЕЧАНИЕ. В математическом анализе часто используют такое же обозначение для степени значения функции относительно умножения. Например, sin²(x)=sin(x) × sin(x). Следует различать по контексту, в каком смысле используется степень функции. В частности, в контексте данной книги sin²(x) = sin(sin(x)).

1.8.1.

…

ЗАМЕЧАНИЕ …

"a, b (a < b Þ Ø(b < a)) º "a, b (Ø(a < b) Ú Ø(b < a)) º "a, b Ø (a < b & b < a).

…

ТЕОРЕМА 1 Если – отношение частичного порядка, то обратное отношение также является отношением частичного порядка.

Доказательство

[антисимметричность] "a, b ((a b) & (b a) Þ a = b) Û
"a, b ((b a) & (a b) Þ a = b) Û "a, b ((a b) & (b a) Þ a = b)

[транзитивность] "a, b, c ((a b) & (b c) Þ a c) Û
"a, b, c ((b a) & (c b) Þ c a) Û "a, b, c ((c b) & (b a) Þ c a). 

СЛЕДСТВИЕ. Если – отношение частичного порядка, то отношения и являются отношениями строгого частичного порядка.