A recent interest of mine is the ubiquity of adjoint relationships in mathematics, and the analysis of which categories are founded on adjoint relationships. The category $Ord$ of preorders and monotone maps is one example. We start by generalizing functions from taking values in points to taking values in preorders.
- Preorder image: let $f: A \to B$ be a function and let $\subseteq_R$ be a preorder on $A$ then define a preorder on $B$ by the preorder closure of $\{(f(x),f(y)): x \subseteq_R y\}$.
- Preorder inverse image: let $f: A \to B$ be a function and let $\subseteq_S$ be a preorder on $B$ then define a preorder on $A$ by $\{(a_1, a_2) : f(a_1) \subseteq_S f(a_2) \}$.
Then the interesting thing is that for any function $f: A \to B$ the definition of a monotonicity of $f$ with respect to two preorders can be defined by a monotone Galois connection expressed in terms of preorders on $A$ and $B$. In particular, for preorders $P$ on $A$ and $Q$ on $B$.
\[ f(P) \subseteq Q \Leftrightarrow P \subseteq f^{-1}(Q) \Leftrightarrow \text{f is monotone} \]
Every function $f: A \to B$ induces a dual pair of monotone maps $F: Ord(A) \to Ord(B)$ and $F^{-1} : Ord(B) \to Ord(A)$ from the lattices of preorders on $A$ to the lattice of preorders on $B$ which together form adjoint functors. The key realisation here is that preorders can be defined by the adjoint relationship between images/inverse images.
The preorder inverse image construction is particularly useful, because it induces an input preorder from an function to a preordered set. Consider the example of a set-valued function $f: A \to \mathcal{P}(B)$ then the preorder inverse image produces the familiar induced preorder on $A$. Similarly, for a ranking function $f: A \to \mathbb{N}$ this produces a preorder on $A$ by the size of its output numbers, and so on. So preorder images/inverse images are an important constructions in order theory, which can be described by adjoints.
References:
Galois connection
Adjoint functor
No comments:
Post a Comment