Теорема Кнастера — Тарского
теорема в теории решёток Из Википедии, свободной энциклопедии
Теорема Кнастера — Тарского (теорема Тарского) — теорема в теории решёток, впервые сформулированная в частном случае Брониславом Кнастером и обобщенная Альфредом Тарским[1]. Утверждает, что для любого монотонного отображения полной решётки (то есть такого, что ) множество всех неподвижных точек также является полной решёткой.
Результат используется в теоретической информатике, в частности, в работах по семантике языков программирования.
Из теоремы Кнастера — Тарского следует, что монотонное отображение полной решётки на себя имеет хотя бы одну неподвижную точку (так как полная решётка не может быть пустой). Более того, такое отображение имеет наименьшую и наибольшую неподвижные точки[2]. Теорема Клини о неподвижной точке утверждает, что для непрерывных по Скотту отображений (которые, как следствие непрерывности, являются монотонными) существует наименьшая неподвижная точка[англ.]. Кроме того, теорема Клини выполнена также для любых полных частичных порядков.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
