Twierdzenie Knastera-Tarskiego o punkcie stałym

Twierdzenie Knastera-Tarskiego o punkcie stałym – twierdzenie mówiące, że każda funkcja monotoniczna określona na kracie zupełnej ma punkt stały; udowodnione najpierw przez Bronisława Knastera dla zbiorów potęgowych, później podane w pełnej ogólności przez Alfreda Tarskiego. Ma ono szereg ważnych zastosowań w semantyce języków programowania.

Twierdzenie

Dla kraty zupełnej $(P,\leqslant )$ oraz funkcji monotonicznej $f\colon P\to P$ określonej na tej kracie, istnieje najmniejszy punkt stały funkcji $f,$ tzn.

$\exists _{x\in P}\;f(x)=x$

oraz

$\forall _{y\in P}\;f(y)=y\implies x\leqslant y.$

Ostatni warunek oznacza, że zbiór wszystkich punktów stałych jest również kratą zupełną.

Należy podkreślić, że funkcja $f$ musi być funkcją monotoniczną na porządku zupełnym, a nie w znaczeniu analizy matematycznej. W szczególności twierdzenie nie jest prawdziwe dla funkcji antymonotonicznych (np. krata $([0;1],\leqslant )$ oraz indykator zbioru $[0;1/2]$).

Linki zewnętrzne

• Marek Zaionc, Jakub Kozik, Marcin Kozik, Logika i teoria mnogości, Wykład 6. 7. Twierdzenie Knastra-Tarskiego, wazniak.mimuw.edu.pl, 19 października 2021 [dostęp 2021-08-12].
• Eric W.E.W. Weisstein Eric W.E.W., Tarski's Fixed Point Theorem, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2024-03-07].