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,⩽)$ oraz funkcji monotonicznej $f:P\to P$ określonej na tej kracie, istnieje najmniejszy punkt stały funkcji $f,$ tzn.

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

oraz

${\mathrm{\forall }}_{y\in P}f(y)=y⟹x⩽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],⩽)$ oraz indykator zbioru $[0;1/2]$).

Linki zewnętrzne

• Szablon:Otwarty dostęp 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].
• Szablon:MathWorld [dostęp 2024-03-07].