Galois connections generalize closure conditions like those provided by the adjoint pairs of image/inverse image functions. In the special case of lattices, it can be shown that these closed pairs have certain special properties.
Definition. let $F: A \to B$ and $G: B \to A$ be a monotone Galois connection. Then we say that $(A,B)$ is a closed pair if it satisfies one of the equivalent conditions $F(A) \subseteq B$ or $A \subseteq G(B)$.
The point of Galois connections is that these closed pairs can be described by any one of two equivalent conditions. In the case of elementary set theory, these conditions are provided by the image and inverse image functions between sets.
Definition. let $F: A \to B$ and $G: B \to A$ be a monotone Galois connection. Let $A \times B$ be the product ordering on $A$ and $B$ defined in the natural way by the category of preorders. Define the partial order on the set of all closed pairs $C(F,G)$ to be the one induced on it by $A \times B$.
The special case of lattices warrants further examination. If there is a Galois connection between two lattices $A$ and $B$ then the product ordering $A \times B$ is itself a lattice, and so $C(F,G)$ is a suborder of a lattice. As we shall see, it is actually the most desirable type of suborder of a lattice.
Theorem. let $F: A \to B$ and $G: B \to A$ be a monotone Galois connection of lattices. Then $C(F,G)$ is a sublattice of $A \times B$.
Proof. let $(a,b)$ and $(c,d)$ be closed pairs. Then $F(a) \subseteq b$ and $G(c) \subseteq d$. Consider $(a \vee c, b \vee d)$. Then since $F(a) \subseteq b \subseteq b \vee d$ and $F(c) \subseteq d \subseteq b \vee d$ so both $F(a)$ and $F(c)$ are less then $b \vee d$. Then since $F(a) \vee F(c)$ is the least upper bound of $F(a)$ and $F(c)$ we have $F(a) \vee F(c) \subseteq b \vee d$. Then since $F$ preserves suprema we have $F(a \vee c) = F(a) \vee F(c)$ so that $F(a \vee c) \subseteq b \vee d$ which implies that $(a \vee c, b \vee d)$ is a closed pair. This demonstrates join-closedness. Meet-closedness follows by the dualizing. $\square$
Every sublattice $S$ of a lattice $L$ is associated to a closure operator and an interior operator. The closure of $x \in L$ is the meet of all of its successors in $S$ and its interior is the join of all of its predecessors. In the case of a monotone Galois connection, the computation of closure and interior operators on closed pairs are rather easier.
Definition. let $(a,b)$ be a pair in the product lattice $A \times B$ of a monotone Galois connection $(F,G)$ between lattices. Then the closure of $(a,b)$ is $(a,b \vee F(a))$ and the interior of $(a,b)$ is $(a \wedge G(b),b)$.
The most important Galois connections are actually between lattices, so this gets closer to what monotone Galois connections are actually about. In the special case of the image/inverse image functor, this demonstrates that the closed pairs of a $F: A \to B$ are a sublattice of $\wp(A) \times \wp(B)$. This lattice $\wp(A) \times \wp(B)$ is a distributive lattice, so this means that closed pairs form a distributive lattice, in fact they are the distributive lattice of subobjects of a $F: A \to B$ in the topos $Sets^{\to}$.
Example. let $f : A \to B$ be a multi-valued function in $Rel$, then $f$ induces a single-valued function $f: A \to \wp(B)$ in the topos $Sets$. Then for closed pairs $(a,b)$ we define a lower adjoint of $a$ to be $\{b : \exists c \in a : b \in f(c)\}$ and we define the upper adjoint of $b$ to be $\{d : r(d) \subseteq b \}$. Then closed pairs $(a,b)$ form a lattice: the lattice of subalgebras of a multi-valued function $Sub(f)$.
This basic concept is how we can define specialized subalgebras for hyperstructures, by generalizing the concept of subalgebras from classical algebra. Let $f: X^2 \to X$ be a hypersemigroup. Then a hypersubsemigroup of $f$ will simply be a pair $(S^2,S)$ that forms a closed pair with respect to $f$ which is induced by a subset $S \subseteq X$, and so on. In either case, the fundamental objects of lattice theory like lattices of subobjects come from adjoints.
References:
Galois connection
No comments:
Post a Comment