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

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

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

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

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

Доведення

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

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

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

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

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

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

Посилання

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