mały|Bronisław Knaster (1893–1980) mały|Alfred Tarski (1901–1983)
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 Słownik teorio-mnogościowy, Katedra Podstaw Informatyki – Wydział Informatyki i Telekomunikacji Politechniki Wrocławskiej (WIT PWr), cs.pwr.edu.pl [dostęp 2025-05-13]..
Udowodnione najpierw przez Bronisława Knastera dla zbiorów potęgowych, później podane w pełnej ogólności przez Alfreda TarskiegoTarski A. A Lattice-Theoretical Fixpoint Theorem and Its Applications. Pacific J. Math. 5, 285-309, 1955.. 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 ).
Przypisy
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]. [dostęp 2024-03-07].
Kategoria:Twierdzenia teorii porządku Kategoria:Twierdzenia o punkcie stałym