#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Options

# Exercise 1.97-Chapter 1

edited April 2018

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')$$.

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?

• Options
1.
edited April 2018

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$$.

Comment Source: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\$$.
• Options
2.

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

Comment Source:Yes, that makes more sense. I thought there was something weird about that paragraph but could not put my finger on it. Thanks, Thomas.
• Options
3.
edited April 2018

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$$ .

Comment Source:In [comment 1](https://forum.azimuthproject.org/discussion/1892/exercise-1-97-chapter-1#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 \$$ . 
• Options
4.
edited April 2018
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.
Comment Source: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. 
• Options
5.
edited April 2018

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

Comment Source:"This is actually the <s>right</s> **left** adjoint of a Galois connection." The description of \$$Cl(q) \$$ sounds like a right adjoint.