Teorema de Knaster-Tarski

La teorema de Knaster-Tarski, que du els noms de Bronisław Knaster i Alfred Tarski, és un teorema matemàtic del àrea de la teoria de retículs.

Enunciat

Siguen $𝒜:=⟨A,\le ⟩$ un retícul complet, $f:A\to A$ una funció monòtona i $P:=\{x\in A\mid f(x)=x\}$ el conjunt dels punts fixos de $f$ en $A$. Llavors $P\ne \mathrm{\varnothing }$ i $𝒫:=⟨P,\le ⟩$ és també un retícul complet.

Esbós de demostració

Sean $\bigcup _{𝒜}$ i $\bigcap _{𝒜}$ les operacions de suprem i ínfim de $𝒜$, respectivament.

Els següents passos mostren que per a subconjunts arbitraris de $P$, $𝒫$ tira un ínfim i un suprem en $P$.

1. $\bigcup _{𝒜}\{x\in A\mid x\le f(x)\}$ és punt fix de $f$, sent ademés major que qualsevol un atre en $A$. Per tant es tracta del suprem $𝒫$ de $P$.
2. Dualmente al pas 1: $\bigcap _{𝒜}\{x\in A\mid f(x)\le x\}$ és punt fix de $f$, sent ademés menor que qualsevol un atre en $A$.
3. Per a subconjunts arbitraris $Y\subseteq P$, es requerix que existixca un suprem $𝒫$. Els casos $Y=P$ i $Y=\mathrm{\varnothing }$ ya es varen considerar en els passos 1 i 2. Ara es consideren els demés casos. Per a això s'aprofita el que $⟨U,\le ⟩$ en $U:=\{x\in A\mid \bigcup _{𝒜}Y\le x\}$ és a la seua volta un retícul complet i que $f{|}_U$ és una funció monòtona $U\to U$, que d'acort al pas 2 té en $U$ al menor dels seus punts fixos. Est és el suprem $𝒫$ de $Y$. En símbols: $\bigcup _{𝒫}Y:=\bigcap _{𝒜}\{x\in A\mid \bigcup _{𝒜}Y\cup f(x)\le x\}$.
4. Dualmente al pas 3 es mostra que per a subconjunts arbitraris de $P$ existix un ínfim $𝒫$.

Referències

• Alfred Tarski(1955).Pacific Journal of Mathematics.5:2

285–309.

• Garrett Birkhoff, 1967. Lattice Theory, 3rd ed. Vol. 25 of AMS Colloquium Publications. American Mathematical Society. ISBN 978-0-8218-1025-5