# Tarski's Fixed Point but with an Order Reversing Function

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.

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$$).

• Thank you so much Gerd! I also kind of want to know what exactly does the non-transposing condition implies. Thank you again! Commented Feb 3, 2022 at 3:26