Twierdzenie Knastera-Tarskiego o punkcie stałym

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj]

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

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