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

- All Categories 2.2K
- Applied Category Theory Course 355
- Applied Category Theory Seminar 4
- Exercises 149
- Discussion Groups 49
- How to Use MathJax 15
- Chat 480
- Azimuth Code Project 108
- News and Information 145
- Azimuth Blog 149
- Azimuth Forum 29
- Azimuth Project 189
- - Strategy 108
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 711
- - Latest Changes 701
- - - Action 14
- - - Biodiversity 8
- - - Books 2
- - - Carbon 9
- - - Computational methods 38
- - - Climate 53
- - - Earth science 23
- - - Ecology 43
- - - Energy 29
- - - Experiments 30
- - - Geoengineering 0
- - - Mathematical methods 69
- - - Meta 9
- - - Methodology 16
- - - Natural resources 7
- - - Oceans 4
- - - Organizations 34
- - - People 6
- - - Publishing 4
- - - Reports 3
- - - Software 21
- - - Statistical methods 2
- - - Sustainability 4
- - - Things to do 2
- - - Visualisation 1
- General 39

Options

Suppose that if \( f \) is left adjoint to \( g \) . Use Proposition 1.91 to show the following.

- \( p \le ( f .g)(p) \)
- \( ( f .g. f .g)(p) \cong ( f .g)(p) \). To prove this, show inequalities in both directions, \( \le \) and \( \ge \) .

**Proposition 1.91**.
Suppose that \( f : P \rightarrow Q \) and \( g: Q \rightarrow P \) are functions. The following are equivalent

- \( f \) and \( g \) form a Galois connection where \( f \) is left adjoint to \( g \),
- for every \( p \in P \) and \( q \in Q \) we have \( f (g(q)) \le q \) and \( p \le g( f (p)) \) .

**Definition** [Equation].
A Galois connection between preorders P and Q is a pair of monotone maps.
We say that \(f \) is the left adjoint and \(g\) is the right adjoint.

\( f : P \rightarrow Q \) and \( g : Q \rightarrow P \) such that \( f(p) \le q \iff p \le g(q) \).

## Comments

The first point \( p \le (f.g)(p) \) comes directly from Proposition 1.81:1 with a change in notation \( (f.g)(p) = (g \circ f)(p) = g(f(p)) \).

The second point proceeds in two steps, showing inequality in both directions.

First show \( (f.g)(p) \le (f.g.f.g)(p) \).

Let \( r = (f.g)(p) \) .

Then by associativity of composition and substitution \( (f.g.f.g)(p) = (f.g)((f.g)(p)) = (f.g)(r) \).

Taking \( r \le (f.g)(r) \) and substituting shows \( (f.g)(p) \le (f.g.f.g)(p) \).

It remains to be shown that \( (f.g.f.g)(p) \le (f.g)(p) \).

Exercise 83 - Chapter 1 shows that if there exists a right adjoint any other right adjoint will be isomorphic to the first.

`The first point \\( p \le (f.g)(p) \\) comes directly from Proposition 1.81:1 with a change in notation \\( (f.g)(p) = (g \circ f)(p) = g(f(p)) \\). The second point proceeds in two steps, showing inequality in both directions. First show \\( (f.g)(p) \le (f.g.f.g)(p) \\). Let \\( r = (f.g)(p) \\) . Then by associativity of composition and substitution \\( (f.g.f.g)(p) = (f.g)((f.g)(p)) = (f.g)(r) \\). Taking \\( r \le (f.g)(r) \\) and substituting shows \\( (f.g)(p) \le (f.g.f.g)(p) \\). It remains to be shown that \\( (f.g.f.g)(p) \le (f.g)(p) \\). [Exercise 83 - Chapter 1](https://forum.azimuthproject.org/discussion/1923) shows that if there exists a right adjoint any other right adjoint will be isomorphic to the first.`

Fredrick, the \((f.g)(p)≤(f.g.f.g)(p)\) part is indeed easy, however I'm struggling to see how right adjoint isomorphism works out here. I suspect that this is due to the fact that I'm not pretty sure what isomorphism between adjoints means. It should preserve some structure (meets?), but it seems that there is no need for bijection here, right? Because it is easy to find counter-examples for injective left adjoint, which have a number of right adjoints, mapping different \(q \in Q\) to different \(p \in P\), while still being monotone and preserving meets.

`[Fredrick](https://forum.azimuthproject.org/profile/2031/Fredrick%20Eisele), the \\((f.g)(p)≤(f.g.f.g)(p)\\) part is indeed easy, however I'm struggling to see how right adjoint isomorphism works out here. I suspect that this is due to the fact that I'm not pretty sure what isomorphism between adjoints means. It should preserve some structure (meets?), but it seems that there is no need for bijection here, right? Because it is easy to find counter-examples for injective left adjoint, which have a number of right adjoints, mapping different \\(q \in Q\\) to different \\(p \in P\\), while still being monotone and preserving meets.`

Igor, the isomorphism is between the two right adjoint, not between right and left adjoints. But two right adjoints can be isomorphic (and not identical) only in a preorder (\( g(r) \le g'(r) \) and \( g(r) \ge g'(r) \) but \( g(r) \neq g'(r) \) ), in a poset RA are unique (when they exist). In other words, two monotone functions on a poset are isomorphic iff they are equal. (as Fredrick said, see Ex 83 - Ch 1)

`Igor, the isomorphism is between the two right adjoint, not between right and left adjoints. But two right adjoints can be isomorphic (and not identical) only in a preorder (\\( g(r) \le g'(r) \\) and \\( g(r) \ge g'(r) \\) but \\( g(r) \neq g'(r) \\) ), in a poset RA are unique (when they exist). In other words, two monotone functions on a poset are isomorphic iff they are equal. (as Fredrick said, see [Ex 83 - Ch 1](https://forum.azimuthproject.org/discussion/1923/exercise-83-chapter-1))`

Thank you Matias, of course I mean isomorphism between right adjoints, I apologize if something in my question pointed you to this sad conclusion :) Yes, indeed now I notice that in question we are talking about preorders, and indeed for posets there is no such notion, this was the source of my confusion - I couldn't imagine how these different functions may be isomorphic, and indeed they can't.

`Thank you [Matias](https://forum.azimuthproject.org/profile/1662/Matias%20Bossa), of course I mean isomorphism between right adjoints, I apologize if something in my question pointed you to this sad conclusion :) Yes, indeed now I notice that in question we are talking about preorders, and indeed for posets there is no such notion, this was the source of my confusion - I couldn't imagine how these different functions may be isomorphic, and indeed they can't.`

It is very interesting how allowing cycles in the graph (preorder) gives rise to this generation of right adjoints. Effectively, if one collapses the cycle to a single node, transforming the preorder to poset, all nodes belonged to the cycle (and giving rise to all these isomorphic right adjoints) become the same, collapsing right adjoints too into a unique one.

`It is very interesting how allowing cycles in the graph (preorder) gives rise to this generation of right adjoints. Effectively, if one collapses the cycle to a single node, transforming the preorder to poset, all nodes belonged to the cycle (and giving rise to all these isomorphic right adjoints) become the same, collapsing right adjoints too into a unique one.`

Okay, still I feel like my understanding of the closure operator is not complete :) If anybody would be able to shed some light on the following, I would really appreciate. So I introduced two linear posets P and Q, P consisting of 3 elements, Q of 2, and I also defined left adjoint \(f\) (blue) and right adjoint \(g\) (orange) as below:

So \(f.g\) maps {1, 2} to {1}, and {3} is mapped to {2}. However, \(f.g.f.g\) maps {3} to {1}, while {1, 2} are still mapped to {1}. And for me these two operators, \(f.g\) and \(f.g.f.g\) look quite different, because they produce different mappings, and therefore they cannot be isomorphic to each other.

`Okay, still I feel like my understanding of the closure operator is not complete :) If anybody would be able to shed some light on the following, I would really appreciate. So I introduced two linear posets P and Q, P consisting of 3 elements, Q of 2, and I also defined left adjoint \\(f\\) (blue) and right adjoint \\(g\\) (orange) as below: ![PQPQ](https://raw.githubusercontent.com/ikshv/categories/master/PQPQ.svg?sanitize=true) So \\(f.g\\) maps {1, 2} to {1}, and {3} is mapped to {2}. However, \\(f.g.f.g\\) maps {3} to {1}, while {1, 2} are still mapped to {1}. And for me these two operators, \\(f.g\\) and \\(f.g.f.g\\) look quite different, because they produce different mappings, and therefore they cannot be isomorphic to each other.`

Igor, I don’t believe \(g\) is the correct right adjoint to \(f\). Let’s label the elements of \(Q\) by \(1.5\) and \(2.5\) to correspond with your picture. Consider the set \(\{a \in P : f(a) \le 1.5\}\), which is \(\{1, 2\}\). We require that \(g(1.5)\) be a least upper bound of this set, so \(g(1.5) = 2\), not \(1\) as in your diagram.

`Igor, I don’t believe \\(g\\) is the correct right adjoint to \\(f\\). Let’s label the elements of \\(Q\\) by \\(1.5\\) and \\(2.5\\) to correspond with your picture. Consider the set \\(\\{a \in P : f(a) \le 1.5\\}\\), which is \\(\\{1, 2\\}\\). We require that \\(g(1.5)\\) be a least upper bound of this set, so \\(g(1.5) = 2\\), not \\(1\\) as in your diagram.`

Thanks @Jonathan, this is a nice catch! To make up this example I followed some assertion that function arrows shouldn't intersect to form adjoints, clearly this condition is not sufficient, and the example is indeed not a Galois connection.

`Thanks @Jonathan, this is a nice catch! To make up this example I followed some assertion that function arrows shouldn't intersect to form adjoints, clearly this condition is not sufficient, and the example is indeed not a Galois connection.`

@Igor I think the arrows of g are going to the wrong elements of P if g is a right adjoint. The bottom should point to 3 I think. And the set P needs an order which is not clear in your diagram (up or down?)

Also I think it’d be interesting to try an injective function too.

`@Igor I think the arrows of g are going to the wrong elements of P if g is a right adjoint. The bottom should point to 3 I think. And the set P needs an order which is not clear in your diagram (up or down?) Also I think it’d be interesting to try an injective function too.`

(btw, this has become exercise 1.96 in the latest draft - dated 20 April 2018)

I still can't see how to exploit the isomorphism of right adjoints here, but I found the Wikipedia page on Galois connections quite useful. Here's what I got:

1) Putting \(g(q)\) in the place of \(p\) in \(p \leq g(f(p))\) we get \(g(q) \leq g(f(g(q)))\).

2) Applying the monotone function \(g\) to \(f(g(q))\leq q\) we get \(g(f(g(q)))\leq g(q)\).

The above must hold for all \(q \in Y\).

So, if we are working with posets, anti-symmetry of \(\leq\) would then give us \(g \circ f \circ g = g \). Apart from being interesting in its own right, this also gives the idempotence of \(g \circ f \) and \( f \circ g \) - just apply \(f\) on the right to get \(g \circ f \circ g \circ f= g \circ f\) and apply it on the left to get \(f \circ g \circ f \circ g = f \circ g\).

If we do the same when we are working with preorders (and thus cannot rely on anti-symmetry), we don't quite get idempotence, but only isomorphisms: \(g \circ f \circ g \circ f \cong g \circ f\) and \(f \circ g \circ f \circ g \cong f \circ g\).

`(btw, this has become exercise 1.96 in the latest draft - dated 20 April 2018) I still can't see how to exploit the isomorphism of right adjoints here, but I found the Wikipedia page on [Galois connections](https://en.wikipedia.org/wiki/Galois_connection) quite useful. Here's what I got: 1) Putting \\(g(q)\\) in the place of \\(p\\) in \\(p \leq g(f(p))\\) we get \\(g(q) \leq g(f(g(q)))\\). 2) Applying the monotone function \\(g\\) to \\(f(g(q))\leq q\\) we get \\(g(f(g(q)))\leq g(q)\\). The above must hold for all \\(q \in Y\\). So, if we are working with posets, anti-symmetry of \\(\leq\\) would then give us \\(g \circ f \circ g = g \\). Apart from being interesting in its own right, this also gives the idempotence of \\(g \circ f \\) and \\( f \circ g \\) - just apply \\(f\\) on the right to get \\(g \circ f \circ g \circ f= g \circ f\\) and apply it on the left to get \\(f \circ g \circ f \circ g = f \circ g\\). If we do the same when we are working with preorders (and thus cannot rely on anti-symmetry), we don't quite get idempotence, but only isomorphisms: \\(g \circ f \circ g \circ f \cong g \circ f\\) and \\(f \circ g \circ f \circ g \cong f \circ g\\).`

We can call property 1 "inflation" and property 2 "idempotence", in analogy with closure operators (which is what \(g \circ f\) would be for posets). Proposition 1.81 gives us inflation for free, so all we must show is that \(g(f(g(f(x)))) \cong g(f(x))\).

Recall that \(g(f(x))\) is a least upper bound of \(\{z \mid f(z) \le f(x)\}\). Notably, so is \(x\). Therefore, \(f(g(f(x))) \cong f(x)\); by monotonicity, \(g(f(g(f(x)))) \cong g(f(x))\). Thus, \(g \circ f\) is idempotent.

I am... not entirely certain of this argument. I find it very hard sometimes to keep these sets and the adjoints straight in my head.

`We can call property 1 "inflation" and property 2 "idempotence", in analogy with closure operators (which is what \\(g \circ f\\) would be for posets). Proposition 1.81 gives us inflation for free, so all we must show is that \\(g(f(g(f(x)))) \cong g(f(x))\\). Recall that \\(g(f(x))\\) is a least upper bound of \\(\\{z \mid f(z) \le f(x)\\}\\). Notably, so is \\(x\\). Therefore, \\(f(g(f(x))) \cong f(x)\\); by monotonicity, \\(g(f(g(f(x)))) \cong g(f(x))\\). Thus, \\(g \circ f\\) is idempotent. I am... not entirely certain of this argument. I find it very hard sometimes to keep these sets and the adjoints straight in my head.`

Igor wrote:

Right, that condition is not sufficient.

It's very helpful to compute left and right adjoints of monotone mappings using just the definition: \( f : P \rightarrow Q \) is the left adjoint of \( g : Q \rightarrow P \) and \(g\) is the right adjoint of \(f\) iff

$$ f(p) \le q \iff p \le g(q) $$ for all \(p \in P, q \in Q\). If it seems hard to use this definition to compute adjoints, then it's good to practice! Eventually it becomes easy.

`Igor wrote: > To make up this example I followed some assertion that function arrows shouldn't intersect to form adjoints, clearly this condition is not sufficient, and the example is indeed not a Galois connection. Right, that condition is not sufficient. It's very helpful to compute left and right adjoints of monotone mappings using just the definition: \\( f : P \rightarrow Q \\) is the left adjoint of \\( g : Q \rightarrow P \\) and \\(g\\) is the right adjoint of \\(f\\) iff $$ f(p) \le q \iff p \le g(q) $$ for all \\(p \in P, q \in Q\\). If it seems hard to use this definition to compute adjoints, then it's good to practice! Eventually it becomes easy.`

@JonathanCastello: you wrote

I think the "Thus" is not justified: "\(g \circ f\) is idempotent" means \(g(f(g(f(x)))) = g(f(x))\) with "=", not just "\( \cong \)". The two are the same in a poset, but not in a preorder.

`@JonathanCastello: you wrote > > \\(g(f(g(f(x)))) \cong g(f(x))\\). Thus, \\(g \circ f\\) is idempotent I think the "Thus" is not justified: "\\(g \circ f\\) is idempotent" means \\(g(f(g(f(x)))) = g(f(x))\\) with "=", not just "\\( \cong \\)". The two are the same in a poset, but not in a preorder.`

Valter, that's why I prefaced with this:

I merely wanted to call it something other than "property 2".

`Valter, that's why I prefaced with this: > We can call property 1 "inflation" and property 2 "idempotence", in analogy with closure operators (which is what g∘f would be for posets). I merely wanted to call it something other than "property 2".`

@JonathanCastello : oh, I see! Sorry, I had not understood what the 1 and 2 referred to.

Anyway, since idempotence already has a generally accepted definition (\(f \circ f = f\)), why don’t we call it, say, “isopotence”?

`@JonathanCastello : oh, I see! Sorry, I had not understood what the 1 and 2 referred to. Anyway, since idempotence already has a generally accepted definition (\\(f \circ f = f\\)), why don’t we call it, say, “isopotence”?`