Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: poset of sub-Q-categories

Mike Stay (Oct 27 2021 at 20:24):

Suppose we have a commutative quantale Q and a Q-enriched category C, i.e.

• a set C0 equipped with

• a function C:C0 x C0 -> Q
  such that

• for all c in C0, 1 ≤ C(c,c) and

• for all c1, c2, c3 in C0, C(c2, c3) ⊗ C(c1, c2) ≤ C(c1, c3).
  (The triangle and pentagon equations are trivial.)

We get a poset P(C) of sub-Q-categories of C, which is itself trivially a Q-category because ⊤ and ⊥ are elements of every quantale. However, it seems to me that there should be a construction something like
$P(C)(S_1, S_2) = \begin{cases} \bot & \text{when } S0_1 \not \subseteq S0_2\\ \bigwedge_{c_1, c_2 \in S_1} S_1(c_1, c_2) \Rightarrow S_2(c_1, c_2) & {\rm otherwise} \end{cases}$
that can assign values between ⊥ and ⊤ to two sub-Q-categories. When Q is the degenerate quantale of truth values, the construction reduces to the plain poset case, but I'm having trouble proving that it works in the general case.

Has anyone seen this construction before? Does the construction work, or is there a way to show that the plain poset is the best you can do?

Mike Shulman (Oct 27 2021 at 20:28):

What is your definition of "sub-Q-category"?

Mike Stay (Oct 27 2021 at 22:04):

Isomorphism class of monic Q-functors. As far as I can tell, a Q-functor is monic when the function between the underlying sets is injective.

Mike Shulman (Oct 27 2021 at 23:43):

Okay. I can't parse the relation $S 0_1 \nsubseteq S 0_2$ either, but I'm guessing it means that not every object of $S_1$ is also an object of $S_2$.

Mike Stay (Oct 27 2021 at 23:44):

Yes, it's saying that the underlying set of $S_1$ is not a subset of the underlying set of $S_2$.

Mike Shulman (Oct 27 2021 at 23:44):

How does $S 0_1$ mean "the underlying set of $S_1$"?

Mike Stay (Oct 27 2021 at 23:46):

Because when I started writing it, I wasn't using latex markup and used C0 to mean the set of elements of C, then was too lazy to fix it when I started using latex. I can go back and edit it if you want.

Mike Shulman (Oct 27 2021 at 23:46):

Ah, I see. No worries.

Mike Shulman (Oct 27 2021 at 23:49):

Anyway it seems easy to me to prove this is a Q-category, but maybe I'm missing something. We have $1 \le P(C)(S,S)$ since $1 \le S(c_1,c_2) \Rightarrow S(c_1,c_2)$ for any $c_1,c_2$. For transitivity, the only nontrivial case is when $\mathrm{ob}(S_1) \subseteq \mathrm{ob}(S_2) \subseteq \mathrm{ob}(S_3)$, in which case we have to prove $P(C)(S_2,S_3) \otimes P(C)(S_1,S_2) \le S_1(c_1,c_2) \Rightarrow S_3(c_1,c_2)$ for any $c_1,c_2$, and this holds since we have $(S_2(c_1,c_2) \Rightarrow S_3(c_1,c_2))\otimes (S_1(c_1,c_2) \Rightarrow S_2(c_1,c_2))$ in the middle.

Mike Stay (Oct 27 2021 at 23:52):

$P(C)(S_2,S_3) \otimes P(C)(S_1,S_2) \le S_1(c_1,c_2) \Rightarrow S_3(c_1,c_2)$

Why this and not $P(C)(S_2,S_3) \otimes P(C)(S_1,S_2) \le P(C)(S_1,S_3)$?

Mike Stay (Oct 27 2021 at 23:59):

$P(C)(S_1, S_2)$ is the "minimum" (really the meet) over all the implications $S_1(c_1, c_2) \Rightarrow S_2(c_1, c_2)$. If the LHS were something as simple as
$\bigwedge_{c_1, c_2} (S_2(c_1,c_2) \Rightarrow S_3(c_1,c_2))\otimes (S_1(c_1,c_2) \Rightarrow S_2(c_1,c_2))$
it would be easy. But it's the product of two meets:
$\bigwedge_{c_1, c_2} (S_2(c_1,c_2) \Rightarrow S_3(c_1,c_2))\otimes \bigwedge_{c_3, c_4} (S_1(c_3,c_4) \Rightarrow S_2(c_3,c_4))$
where I've changed the second set of variables to emphasize that they're from a different binder.

Mike Shulman (Oct 28 2021 at 00:05):

Mike Stay said:

$P(C)(S_2,S_3) \otimes P(C)(S_1,S_2) \le S_1(c_1,c_2) \Rightarrow S_3(c_1,c_2)$

Why this and not $P(C)(S_2,S_3) \otimes P(C)(S_1,S_2) \le P(C)(S_1,S_3)$?

Because $P(C)(S_1,S_3)$ is a meet, so to be less than it, it suffices to be less than all the conjuncts.

Mike Shulman (Oct 28 2021 at 00:06):

Mike Stay said:

$P(C)(S_1, S_2)$ is the "minimum" (really the meet) over all the implications $S_1(c_1, c_2) \Rightarrow S_2(c_1, c_2)$. If the LHS were something as simple as
$\bigwedge_{c_1, c_2} (S_2(c_1,c_2) \Rightarrow S_3(c_1,c_2))\otimes (S_1(c_1,c_2) \Rightarrow S_2(c_1,c_2))$
it would be easy. But it's the product of two meets:
$\bigwedge_{c_1, c_2} (S_2(c_1,c_2) \Rightarrow S_3(c_1,c_2))\otimes \bigwedge_{c_3, c_4} (S_1(c_3,c_4) \Rightarrow S_2(c_3,c_4))$
where I've changed the second set of variables to emphasize that they're from a different binder.

But you still have the relevant projection from each meet. In general, you have $\bigwedge_i p_i \le p_{i_0}$ and $\bigwedge_j q_j \le q_{j_0}$, and hence $(\bigwedge_i p_i) \otimes (\bigwedge_j q_j) \le p_{i_0} \otimes q_{i_0}$ by functoriality of $\otimes$.

Mike Shulman (Oct 28 2021 at 00:15):

Note that this is really just a sub-Q-category of $Q^{\mathrm{ob}(C) \times \mathrm{ob}(C)}$.

Mike Stay (Oct 28 2021 at 15:53):

Ah! That was the insight I was missing. Thanks!

Simon Willerton (Oct 31 2021 at 07:35):

Thinking about the metric space case, this feels like an odd definition (or maybe I don't properly understand it). Your definition of a sub-$\R_+$-category of a metric space $X$ is a subset equipped with a metric which dominates the original metric. (In other words, a metric space with an injective short map to $X$.) The distance from $A$ to $B$ is then $\infty$ if $A$ is not contained in $B$ but is otherwise the maximum of how bigger a distance is in $B$ than in $A$. (Is that right?)

The main reason that I say it feels odd is that I've not seen anything like that, I don't think.

Simon Willerton (Oct 31 2021 at 07:45):

What I have seen before for sub-metric spaces of a metric space is the Hausdorff metric. In this case you consider a submetric space to be a subset with the induced metric and the (generalized) distance between two subsets $A$ and $B$ is $\sup_{a\in A} \inf_{b\in B} d(a,b)$, so the furthest you would have to travel to get from somewhere in $A$ to $B$. (The traditional Hausdorff distance where is the symmetrized version of this and you need to consider compact subsets in order to get $d(A,B)=0$ if and only if $A=B$, but I'm thinking of $\R_+$-categories so don't need to worry about that.)

Simon Willerton (Oct 31 2021 at 07:48):

If you look at the underlying poset of this then you get something close to the inclusion poset on $P(X)$ except, I think $A\le B$ if $A$ is contained in the closure of $B$.

Simon Willerton (Oct 31 2021 at 07:57):

Anyway, this is generalized to $Q$-categories by Andrei Akhvlediani, Maria Manuel Clementino, Walter Tholen in On the categorical meaning of Hausdorff and Gromov distances, I (see also Andrei's Masters thesis).

For $C$ a $Q$-category, they define a $Q$-category structure on the powerset $P(CO)$ by

$P(C0)(S_1,S_2) =\bigwedge_{c_1\in S_1} \bigvee_{c_2\in S_2} C(c_1, c_2).$

I don't know if this is helpful for you!

John Baez (Oct 31 2021 at 18:02):

Hi, Simon!

James Deikun (Nov 01 2021 at 02:50):

Mike Stay said:

$P(C)(S_1, S_2) = \begin{cases} \bot & \text{when } S0_1 \not \subseteq S0_2\\ \bigwedge_{c_1, c_2 \in S_1} S_1(c_1, c_2) \Rightarrow S_2(c_1, c_2) & {\rm otherwise} \end{cases}$

Has anyone seen this construction before? Does the construction work, or is there a way to show that the plain poset is the best you can do?

If you interpret this outside of the quantale case, it probably looks like:

$P(C)(S_1,S_2) = \begin{cases} \bot & \text{when } {\rm Obj}(S_1) \not \subseteq {\rm Obj}(S_2)\\ {\rm Nat}(S_1(-,=),S_2(-,=)) & \text{otherwise} \end{cases}$

where in the second case $S_2$ is restricted to the objects of $S_1$. These are also natural transformations of semifunctors on the entirety of ${\rm Obj}(S)$ which makes me think it's more natural to define this construction on sub-Q-semicategories where points can have nonzero distance from themselves ...