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^[1]. Ma ono szereg ważnych zastosowań w semantyce języków programowania.

Twierdzenie

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

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

oraz

${\displaystyle \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 ${\displaystyle 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 ${\displaystyle ([0;1],\leqslant )}$ oraz indykator zbioru ${\displaystyle [0;1/2]}$).

Przypisy

1. Tarski A. A Lattice-Theoretical Fixpoint Theorem and Its Applications. Pacific J. Math. 5, 285-309, 1955.

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].