Exercise 1.97-Chapter 1

Aqilah Rasat

Let \(S=\{1,2,3\}\).

1. Come up with any preorder relation \(\leq\) on \(S\), and let \(L\subseteq S\times S\) be the set \(\{(s_1,s_2)|s_1\leq s_2\}\), i.e. \(L\) is the image of \(\leq\) under the inclusion \(\mathbf{Pos}(S)\rightarrow\mathbf{Rel}(S)\).
2. Come up with two binary relations \(Q\subseteq S\times S\) and \(Q'\subseteq S\times S\) such that \(L\leq Q\) but \(L\nleq Q'\).
3. Show that \( \leq\trianglelefteq \text{Cl}(Q) \).
4. Show that \( \leq\ntrianglelefteq \text{Cl}(Q')\).

The following is my answer:

1. \( L=\{(1,1),(1,2),(2,2),(3,3)\}\)
2. \( Q=\{(1,1),(1,2),(2,2),(3,3),(2,3)\} \) and \( Q'=\{(1,1),(1,2),(2,3),(3,3)\} \)

For question 2, I interpreted \( \leq L \) to mean 'subset of \( L \)'. While \( Q'\) contains some elements of \( L\), one of its elements is not in \( L\), i.e. (2,3), which means \( L\) is not a subset of \( Q'\). We can check that \( \text{Cl}(Q) =\text{Cl}(Q')\) and \( L\) is a subset of both \(\text{Cl}(Q)\) and \(\text{Cl}(Q')\). Thus,

1. \(\leq\trianglelefteq\text{Cl}(Q)\)
2. \(\leq\trianglelefteq\text{Cl}(Q')\) which contradicts what question 4 is asking.

The statement of question 4 seems to imply some general statement on relationship between the sets containing \( L \) and the order of their closures. So, am I misinterpreting some definition in section 1.5.5? Or have I missed out some other details?

ThomasRead

I think this is a typo in the book - I submitted it to the mistakes list a couple days ago.

The preceding paragraph should say "[The inclusion \(\mathbf{Pos}(S)\rightarrow\mathbf{Rel}(S)\)] is actually the right adjoint of a Galois connection. Its left adjoint is a monotone map \(\text{Cl}:\mathbf{Rel}(S)\rightarrow\mathbf{Pos}(S)\)."

and the exercise should ask you to pick \(Q\leq L\) and \(Q'\nleq L\), and then show that \(\text{Cl}(Q)\trianglelefteq\leq\) and \(\text{Cl}(Q')\ntrianglelefteq\leq\).

Aqilah Rasat

Yes, that makes more sense. I thought there was something weird about that paragraph but could not put my finger on it. Thanks, Thomas.

Fredrick Eisele

In comment 1 Aqilah proposes a solution:

1. \( L=\{(1,1),(1,2),(2,2),(3,3)\}\)

I want to point out to the casual reader that the \( \le \) relation here defined is not its conventional meaning over \( \mathbb{N} \), it can be defined as any set of pairs from \( S \times S \). That conventional meaning would define the \( \le \) relation as \( \{(1,1),(1,2),(2,2),(2,3),(3,3)\} \) [incidentally chosen to be \( Q \)]. This is essential to the exercise, to see that there are many ways which the preorder relation may be defined and that they form a preorder structure \( \trianglelefteq \) .

Fredrick Eisele

1. \( L=\{(1,2),(3,3)\} \)
2. \( Q=\{(1,2),(2,3),(3,3)\} \) and \( Q'=\{(1,1),(2,3),(3,3)\} \)
3. Show \( \le \trianglelefteq Cl(Q) \)
4. Show \( \le \ntrianglelefteq Cl(Q') \)

We show this by recognizing inclusion. We find \(Cl(q)\) by adding to \(q\) the reflective (adding \((s,s)\) for every \(s\) ) and transitive (adding \((s,u)\) when \((s,t)\) and \((t,u)\) ) closures.

• \( L=\{(1,2),(3,3)\} \)
• \( Cl(Q) = \{(1,2),(2,3),(3,3)\} \cup \{(1,1),(2,2)\} \cup \{ (1,3) \} = \{(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)\} \)
• \( Cl(Q') = \{(1,1),(2,3),(3,3)\} \cup \{(2,2)\} \cup \{ \} = \{(1,1),(2,2),(2,3),(3,3)\} \)

Thus we can see

• \( \{(1,2),(3,3)\} \subseteq \{(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)\} \)
• \( \{(1,2),(3,3)\} \nsubseteq \{(1,1),(2,2),(2,3),(3,3)\} \)

That this must be true takes a bit more work.

• \( L \subseteq Q \subseteq Cl(Q) \) is true by the transitive property of subsets.
• It I had chosen a \( Q'' = \{(1,2),(2,3)\} \) then \( Cl(Q'') = \{(1,2),(2,3)\} \cup \{(1,1),(2,2),(3,3)\} \cup \{ (1,3) \} = \{(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)\} \) and the condition would not have been met.

Fredrick Eisele

"This is actually the right left adjoint of a Galois connection." The description of \( Cl(q) \) sounds like a right adjoint.