Options

Exercise 1.97-Chapter 1

edited April 2018 in Exercises

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?

Comments

  • 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\\).
  • 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.
  • 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 \\) .
  • 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.
  • 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.
Sign In or Register to comment.