Question on Galois Connections

205 Views Asked by At

I have been learning about Galois Connections, and came across Steve Roman's book "Lattices and Ordered Sets." Two questions:

  1. There is a theorem which says that if $(\Pi,\Omega)$ is a Galois connection on $(P,Q)$, where we write $p^*=\Pi(p)$ and $q'=\Omega (q)$, then $$p^{*'*}=p^* \text{ and } q^{'*'}=q'.$$ However, then it claims that from this fact it follows that the composite maps $(\;)^{*'}$ and $(\;)^{'*}$ are closure operators on $P$ and $Q$, respectively. Isn't it better to say that they are closure operators on $Q'$ and $P^{*}$, respectively? (hopefully the notation is clear). It seems to me there is no guarantee they are closure operators on all of $P$ or $Q$, right? Or am I missing something form the definition of closure operator?

  2. An exercise in the same section asks to prove that, if $P$ and $Q$ are lattices, then De Morgan's laws hold in Cl$(P)$ and Cl$(Q)$.

I am not sure how to begin with this problem. I don't see how the fact that $P$ and $Q$ have to be lattices is relevant.

I have a feeling that I will have to go back and forth between $P$ and $Q$ in some way, but I do not know how to relate the lattice operations to the maps in the Galois Connection, nor do I know how to reconcile the fact that all you really know is that $p\leq p^{*'}$ (no equality).

Any ideas or hints as to how to get started?

1

There are 1 best solutions below

6
On BEST ANSWER

This asterisk and apostrophe stuff is a little annoying to type, so I'm going to switch to $F:P\to Q$ and $G:Q\to P$.

So, $GF$ is a closure operator on $P$ in the sense that it is nondecreasing ($p\leq GF(p)$) and idempotent $GF(GF(p))=GF(p)$. Something similar applies for $FG$ on $Q$. The idea is that $GF$ extends elements to a "closed" element containing the original element. The equality $FGF=F$ allows you to conclude that $GF$ is an idempotent operator on $P$, and similarly the other equality allows you to conclude that $FG$ is idempotent on $Q$.

Restricting $GF$ to operate only on $G(Q)$ would be boring because all of the elements of $G(Q)$ are "already closed": $GF(G(q))=G(q)$ for all $q\in Q$! So $GF$ doesn't actually expand those elements at all. It's more interesting in cases where $GF(p)>p$, where the nonclosed element $p$ became closed after $GF$ is applied.

For $2)$, DeMorgan's laws are statements about greatest lower bounds and least upper bounds. You need the posets to be lattices so that GLB's and LUB's are defined in the first place. Otherwise you are trying to prove things about things that don't exist :)


Added

When I get to the DeMorgan's Laws part, I have a feeling you might have been meant to work with antitone connections all along. So for this part, let $F$ and $G$ be order reversing. $FG$ and $GF$ still have the idempotence and nondecreasingness they had before. Let $a,b\in F(P)$.

In particular, $FG(a)=a$ and $FG(b)=b$. Actually, $F(P)$ is closed under meets and joins. Here is how to show it for joins: I will leave meets up to you. Since $G\underline{(a\vee b)}\leq \underline{G(a\vee b)}$, it follows that $F(\underline{G(a\vee b)})\leq \underline{a\vee b}$. But this implies $FG(a\vee b)\leq a\vee b$, and the other containment is taken care of by the fact $FG$ is nondecreasing. Thus $FG(a\vee b)=a\vee b$.

One of DeMorgan's Laws on $F(P)$ would now look like this: $G(a\vee b)=G(a)\wedge G(b)$. Let's establish this particular one.

You have that $a,b\leq a\vee b$, which immediately yields $G(a\vee b)\leq G(a), G(b)$. By definition of the greatest lower bound, we have $$G(a\vee b)\leq G(a)\wedge G(b)\leq G(a),G(b).$$ Applying $F$ reverses these: $$a\vee b\geq F(G(a)\wedge G(b))\geq a,b$$

(Notice I used the fact that $FG$ is the identity on $F(P)$ to delete some unnecessary $FG$'s.)

But then by definition of the least upper bound, $a\vee b= F(G(a)\wedge G(b))$. Another application of $G$ on both sides yields that $G(a\vee b)=GF(G(a)\wedge G(b))=G(a)\wedge G(b)$.

I'm going to encourage you to work out $G(a\wedge b)=G(a)\vee G(b)$ on your own. You could reprove everything for $F$ too, but your teacher might rather want to see you appeal to similarity instead of the extra text :)