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

Нехай 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 є повною частково впорядкованою множиною