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

- All Categories 2.4K
- Chat 505
- Study Groups 21
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 2
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- Baez ACT 2019: Online Course 339
- Baez ACT 2019: Lectures 79
- Baez ACT 2019: Exercises 149
- Baez ACT 2019: Chat 50
- UCR ACT Seminar 4
- General 75
- Azimuth Code Project 111
- Statistical methods 4
- Drafts 10
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 148
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 719

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”?`