Processing math: 0%

Friday, November 11, 2022

The adjoint definition of monotonicity

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