PROFILPELAJAR.COM

Теорема Кнастера — Тарского (теорема Тарского) — теорема в теории решёток, впервые сформулированная в частном случае Брониславом Кнастером и обобщенная Альфредом Тарским^[1]. Утверждает, что для любого монотонного отображения $f:L\to L$ полной решётки $\langle L,\sqsubseteq \rangle$ (то есть такого, что $l_{1}\sqsubseteq l_{2}\Rightarrow f(l_{1})\sqsubseteq f(l_{2})$ ) множество всех неподвижных точек $\mathrm {Fix} (f)=\{l\in L\mid f(l)=l\}$ также является полной решёткой.

Результат используется в теоретической информатике, в частности, в работах по семантике языков программирования.

Из теоремы Кнастера — Тарского следует, что монотонное отображение полной решётки на себя имеет хотя бы одну неподвижную точку (так как полная решётка не может быть пустой). Более того, такое отображение имеет наименьшую и наибольшую неподвижные точки^[2]. Теорема Клини о неподвижной точке утверждает, что для непрерывных по Скотту отображений (которые, как следствие непрерывности, являются монотонными) существует наименьшая неподвижная точка^[англ.]. Кроме того, теорема Клини выполнена также для любых полных частичных порядков.

Примечания

↑ Tarski, A. A Lattice-Theoretical Fixpoint Theorem and Its Applications // Pacific J. Math.. — 1955. — № 5. — С. 285—309.
↑ Roland Uhl. Tarski's Fixed Point Theorem (англ.) на сайте Wolfram MathWorld.