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 oraz funkcji monotonicznej określonej na tej kracie, istnieje najmniejszy punkt stały funkcji tzn.
oraz
Ostatni warunek oznacza, że zbiór wszystkich punktów stałych jest również kratą zupełną.
Należy podkreślić, że funkcja 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 oraz indykator zbioru ).
![{\displaystyle ([0;1],\leqslant )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/24a1ab8e94e079776ec4034bc37c142c393fdebc)
![{\displaystyle [0;1/2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99cfdac29b03c89c4f79997ae297122fde7a74f6)
Przypisy
- ↑ 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. Weisstein, Tarski’s Fixed Point Theorem, [w:] MathWorld, Wolfram Research (ang.). [dostęp 2024-03-07].