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

Нехай D — ${\displaystyle \omega }$-область, ${\displaystyle \varphi :D\to D}$ — неперервне відображення задане на цій області. Тоді існує найменша нерухома точка ${\displaystyle \varphi }$, яка позначається ${\displaystyle lfp\ \varphi }$, для якої справедлива формула:

${\displaystyle lfp\ \varphi =\bigsqcup _{i\in \omega }\varphi ^{(i)}(\perp )}$,

де ${\displaystyle \varphi ^{(0)}(\perp )=\perp \ \varphi ^{(i+1)}(\perp )=\varphi (\varphi ^{(i)}(\perp )),\,i\in \omega }$

Альфред Тарський сформулював теорему в її найзагальнішій формі^[1]

Доведення

Доведення складається з трьох частин:

• Доведення факту, що множина ${\displaystyle \{\varphi ^{(i)}(\perp )\}i\in \omega }$ — ланцюг (тому її супремум ${\displaystyle \bigsqcup _{i\in \omega }\varphi ^{(i)}(\perp )}$ існує).
• Доведення того, що ${\displaystyle \bigsqcup _{i\in \omega }\varphi ^{(i)}(\perp )}$ є нерухомою точкою ${\displaystyle \varphi }$.
• Доведення, що ${\displaystyle \bigsqcup _{i\in \omega }\varphi ^{(i)}(\perp )}$ є найменшою з нерухомих точок ${\displaystyle \varphi }$.

Використані терміни

Омега-область

Множина D — ${\displaystyle \omega }$-область (також вживається термін індуктивна множина, ${\displaystyle \omega }$-домен), якщо

• на D введено частковий порядок ${\displaystyle \leq }$
• в D існує найменший елемент ${\displaystyle \perp }$
• D є повною частково впорядкованою множиною

Зноски

1. Tarski, Alfred (1 червня 1955). A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics. 5 (2): 285—309. doi:http://dx.doi.org/10.2140/pjm.1955.5.285. {{cite journal}}: Перевірте значення |doi= (довідка)

Посилання

• Нікітченко, М.С. (2010). ТЕОРІЯ ПРОГРАМУВАННЯ. Ніжин: Видавництво НДУ імені Миколи Гоголя.
• Weisstein, Eric W. Tarski's Fixed Point Theorem. mathworld.wolfram.com (англ.). Процитовано 31 березня 2024.