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 jeżeli P jest kratą zupełną oraz funkcja jest monotoniczna, to ma ona punkt stały, co więcej zbiór wszystkich punktów stałych jest również kratą zupełną. Twierdzenie 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

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.