Теорема Кнастера — Тарского

Теорема Кнастера — Тарского (теорема Тарского) — теорема в теории решёток, впервые сформулированная в частном случае Брониславом Кнастером и обобщенная Альфредом Тарским^[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.

Литература

S. Abramsky, Dov M. Gabbay, T. S. E. Maibaum, Handbook of Logic in Computer Science: Volume 1: Background: Mathematical Structures

Похожие исследовательские статьи

В этом глоссарии приведены определения основных терминов, используемых в общей топологии. Курсивом выделены ссылки внутри глоссария.

Крива́я или ли́ния — геометрическое понятие, определяемое в разных разделах математики различно.

Теорема Бо́рсука — У́лама — классическая теорема алгебраической топологии, утверждающая, что всякая непрерывная функция, отображающая $\text{[math]}$ -мерную сферу в $\text{[math]}$ -мерное евклидово пространство для некоторой пары диаметрально противоположных точек имеет общее значение. Неформально утверждение известно как «теорема о температуре и давлении»: в любой момент времени на поверхности Земли найдутся антиподальные точки с равной температурой и равным давлением; одномерный случай обычно иллюстрируют двумя диаметрально противоположными точками экватора с равной температурой.

Теорема о неявной функции — общее название для теорем, гарантирующих локальное существование и описывающих свойства неявной функции, то есть функции

\text{[math]}

\text{[math]}

Теорема Брауэра о неподвижной точке — важная теорема о неподвижной точке, применимая к непрерывным отображениям в конечномерных пространствах, являющаяся основной для некоторых более общих теорем.

Оператор замыкания — обобщение интуитивной концепции замыкания. Именно: если $\text{[math]}$ — частично упорядоченное множество, оператор $\text{[math]}$ будет называться оператором замыкания, если выполнены три условия:

$\text{[math]}$ (экстенсивность),
$\text{[math]}$ (монотонность)
$\text{[math]}$ (идемпотентность)

Теорема о причёсывании ежа утверждает, что на сфере невозможно выбрать касательное направление в каждой точке, которое определено во всех точках сферы и непрерывно зависит от точки. Неформально говоря, невозможно причесать свернувшегося клубком ежа так, чтобы у него не торчала ни одна иголка — отсюда и упоминание ежа в названии теоремы.

Теоре́ма о сво́йстве Дарбу́ (Д-сво́йстве) для непреры́вной фу́нкции в математическом анализе утверждает, что непрерывный образ отрезка есть отрезок.

Языки Арнольда — в теории динамических систем, области рациональности числа вращения в двупараметрическом семействе гомеоморфизмов окружности, начинающемся с чистых поворотов.

Неподвижная точка в математике — точка, которую заданное отображение переводит в неё же, иными словами, решение уравнения $\text{[math]}$ . Иногда такую точку называют инвариантной [по названию соответствующего у неё свойства].

Кошмар Фубини — название кажущегося нарушения теоремы Фубини в не-абсолютно непрерывных слоениях с гладкими слоями. Состоит в том, что множество в расслоенном пространстве, пересекающее все слои по множеству меры ноль, может, тем не менее, иметь положительную меру в объемлющем пространстве. Такой эффект, на самом деле, теореме Фубини не противоречит, поскольку выпрямляющее отображение слоения не является абсолютно непрерывным.

Теорема Сарда — теорема математического анализа с приложениями в дифференциальной геометрии и топологии, теории катастроф и теории динамических систем.

Непрерывность по Скотту — свойство функций над частично упорядоченными множествами, выражающееся в сохранении точной верхней грани относительно отношения частичного порядка.

Универсальная алгебра — раздел математики, изучающий общие свойства алгебраических систем, использующий сходства между различными алгебраическими структурами — группами, кольцами, модулями, решётками, вводящий присущие им всем понятия и устанавливающий общие для всех них утверждения. Занимает промежуточное положение между математической логикой и общей алгеброй, как реализующий аппарат математической логики в применении к общеалгебраическим структурам.

Теорема Клини о неподвижной точке — утверждение о существовании наименьшей неподвижной точки у всякого непрерывного по Скотту отображения полного частично упорядоченного множества на себя. Результат относят к Стивену Клини; используется в теории областей, теории решёток, теории графов, теории автоматов.

Теорема об упаковке кругов описывает возможные варианты касания окружностей, не имеющих общих внутренних точек. Граф пересечений упаковки кругов — это граф, вершины которого соответствуют кругам, а рёбра — точкам касания. Если упаковка кругов осуществляется на плоскости, то их граф пересечений называется графом монет. Графы монет всегда связны, просты и планарны. Теорема упаковки кругов утверждает, что обратное также верно:

Теорема Адамара — Картана — утверждение о том, что универсальное накрытие риманова многообразия с неположительной кривизной диффеоморфно евклидову пространству.

Принцип равномерной ограниченности или Теорема Банаха — Штейнгауза — фундаментальный результат функционального анализа. Теорема утверждает, что поточечная и равномерная ограниченности эквивалентны для семейств непрерывных линейных операторов, заданных на Банаховом пространстве.

Максимальная компактная подгруппа K топологической группы G — это компактное пространство с индуцированной топологией, максимальное среди всех подгрупп. Максимальные компактные подгруппы играют важную роль в классификации групп Ли и, особенно, в классификации полупростых групп Ли. Максимальные компактные подгруппы групп Ли в общем случае не единственны, но единственны с точностью до сопряжённости — они являются существенно сопряжёнными.

Арифметическая группа — это группа, получаемая как целые точки алгебраической группы, например, $\text{[math]}$ Арифметические группы возникают естественным образом при изучении арифметических свойств квадратичных форм и других классических областей теории чисел. Они также являются источником для очень интересных примеров римановых многообразий, а потому представляют интерес для дифференциальной геометрии и топологии. Наконец, эти две области объединяются в теорию автоморфных форм, которая является фундаментальной в современной теории чисел.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.