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

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

$lfp\phi =\underset{i\in \omega }{⨆}{\phi }^{(i)}(\perp )$,

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

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

Доведення

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

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

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

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

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

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

Посилання

• Шаблон:Cite book
• Шаблон:Cite web