I have read the Tarski's fixed point theorem for powersets. It requires an order-preserving/monotonic function. I wonder if there are results (with strengthened conditions) for order-reversing functions.
Let $U$ be a set, then its power set $P(U)$ with inclusion $\subseteq$ forms a partial order. A function $\phi:P(U) \to P(U)$ is monotonic if
$$S \subset S' \implies \phi(S) \subset \phi(S')$$
for all $S,S'\in P(U)$.
A function $\psi:P(U) \to P(U)$ is order-reversing if
$$S \subset S' \implies \psi(S') \subset \phi(S)$$
for all $S,S'\in P(U)$.
The Tarski's Theorem for minimum fixed points states
Let $P(U)$ be a power set and $\phi:P(U) \to P(U)$ be a monotonic function. Define
$$m = \bigcap \{S\subseteq U | \phi(S) \subseteq S\},$$
then $m$ is a fixed point of $\phi$.
I think that if we want to extend this result to order-reversing functions, we need additional conditions such as "continuity". I tried to draw the analogy between the fixed point argument for functions that maps from $[0,1]$ to $[0,1]$, but had no luck. We can easily construct counter example for decreasing function without a fixed point on $[0,1]$ through a discontinuity. But I don't know how to define continuity over powersets. I would really appreciate if someone can point me to something.
Best Answer
I know the following result due to J. Björner, Algebra Universalis 12 (1981), 402-403:
Let $L$ be a complete lattice and let $f:L \to L$ be order-reversing. Now, $f$ is called non-transposing if there is no $x \in L$ with $f^2(x)=x < f(x)$. In this case $f$ has a unique fixed point.
Proof: Let $B$ be the set of all $x \in L$ with $f^2(x) \le x$ and set $b:= \inf B$.
We prove that $b$ is the unique fixed point of $f$. Since $f^2$ is order-preserving $f^2(b) \le f^2(x) \le x$ $(x \in B)$. Hence $f^2(b) \le b$. Thus $f^2(b) \in B$, so $b \le f^2(b)$ and therefore $f^2(b)=b$. (Up to this point this is Tarski's proof for the order-preserving mapping $f^2$.) Next $f^2(b \wedge f(b)) \le f^2(b)=b$ and $f^2(b \wedge f(b)) \le f^2(f(b))=f(b)$. Thus $f^2(b \wedge f(b)) \le b \wedge f(b)$, that is $b \wedge f(b) \in B$. Hence $b \le b \wedge f(b)$ which is the same as $b \le f(b)$. Now, if $b$ is not a fixed point of $f$ then $f^2(b)=b < f(b)$, a contradiction. Moreocer if $c \in L$ is another fixed point of $f$, then $c \in B$, hence $b \le c$ which implies $c=f(c) \le f(b)=b$, so $b=c$.
In fact, I am not sure how sustainable the concept of non-transposing mappings is. Maybe someone finds an interesting example.
Edit: I chew a bit over this condition. Tarski says that an oder-preserving mapping on a complete lattice has a smallest and a greatest fixed point. If $x_l$ and $x_u$ are the smallest and the greatest fixed point of $f^2$, respectively, then $f(x_l)=x_u$ and $f(x_u)=x_l$ (since $f$ is order-reversing). Now, if $x_l < x_u$ then $f^2(x_l)=x_l < x_u = f(x_l)$ which is forbidden if $f$ is non-transposing. Thus "non-transposing" just forces that the smallest and the greatest fixed point of $f^2$ are the same (and not different and transposed by $f$).