The Proof of Knaster-Tarski Theorem

Definition[Monotone Function]

  A function \mathcal{F}:\mathcal{P(U)}\rightarrow\mathcal{P(U)} from some universal set \mathcal{U} is monotone if X\subseteq Y\implies \mathcal{F}(X)\subseteq\mathcal{F}(Y)

Definition[Fixed Point]

  1. Set X is \mathcal{F}-closed if \mathcal{F}(X)\subseteq X
  2. Set X is \mathcal{F}-consistent if X\subseteq\mathcal{F}(X)
  3. Set X is a fixed point of \mathcal{F} if it's both \mathcal{F}-closed and \mathcal{F}-consistent, i.e., \mathcal{F}(X)=X, the greatest fixed point of \mathcal{F} is denoted by \mathcal{\nu F}, and the least fixed point of \mathcal{F} is denoted by \mathcal{\mu F}

Theorem[Knaster-Tarski (Specialized on Sets)]

  1. The intersection of all \mathcal{F}-closed set is the least fixed point of \mathcal{F}
  2. The union of all \mathcal{F}-consistent set is the greatest fixed point of \mathcal{F}

Proof

Part 1

  Let X be the set of all \mathcal{F}-closed sets, i.e., X=\lbrace C|\mathcal{F}(C)\subseteq C \rbrace. Let P be the intersection of X, i.e., P=\bigcap_X, we need to prove: 1. \mathcal{F}(P)\subseteq P 2. P\subseteq\mathcal{F}(P).
  For the first, noticed that P\subseteq C for all C\in X, from the monotonicity of \mathcal{F} we get \mathcal{F}(P)\subseteq\mathcal{F}(C) for all C\in X, from the definition of X we can further conclude that \mathcal{F}(P)\subseteq C for all C\in X, since P is the intersection of all C, if an element x is in all C, then x must in P, and since \forall C\in X.\mathcal{F}(P)\subseteq C, then x\in\mathcal{F}(P)\implies\forall C\in X. x\in C, which follows the definition of set intersection and further proves that \forall x\in\mathcal{F}(P).x\in P, i.e., \mathcal{F}(P)\sube P.
  For the second, since we've proved that \mathcal{F}(P)\sube P, from the definition of \mathcal{F} we have \mathcal{F}(\mathcal{F}(P))\sube \mathcal{F}(P), which, from the definition of X, we know that \mathcal{F}(P)\in X, moreover, we know that P is the intersection of X. This means, P\sube C for all C\in X, and since \mathcal{F}(P)\in X, it is clear that P\sube \mathcal{F}(P) must hold.

Part 2

  Let X be the set of all \mathcal{F}-consistent sets, i.e., X=\lbrace C|C\sube \mathcal{F}(C) \rbrace. Let P be the union of X, i.e. P=\bigcup_{X}, we need to prove: 1. P\sube\mathcal{F}(P) 2. P\sube\mathcal{F}(P).
  For the first, noticed that C\sube P for all C\in X, from the monotonicity of \mathcal{F} and the definition C we get C\sube\mathcal{F}(C)\sube \mathcal{F}(P) for all C\in X, since P=\bigcup_{X}, we have P=\bigcup_{X}\sube \mathcal{F}(P).
  For the second, since we've proved P\sube\mathcal{F}(P), from the monotonicity of \mathcal{F} it is obvious that \mathcal{F}(\mathcal{F}(P))\sube \mathcal{F}(P), moreover, from the definition of X, we know \mathcal{F}(P)\in X,and since P is the union of X, \mathcal{F}(P)\sube P must hold. ∎


We Choose to Go to the Moon