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: event: Categories for AI

Topic: Coexponential Objects

Andrew Dudzik (Oct 24 2022 at 14:02):

Starting a separate thread to collect thoughts on Petar's question about coexponential objects in Set.

Andrew Dudzik (Oct 24 2022 at 14:04):

Alberto Meneghello said:

Samuel Gélineau ha scritto:

I have a guess for the coexponential in Set exercise, but I don't like it one bit.

my solution

coexp(B, A) = if A is non-empty, then Void, otherwise B

We need to define a morphism v : B -> coexp(B, A) + A.
Case 1: A is non-empty. Then v : B -> Void + A, so we need to map every element in B to an element in A. Since A is non-empty, it has at least one element a ∈ A, to which we map everything. We pick this a arbitrarily.
Case 2: A is empty. Then v : B -> B + A, so we can simply map the elements of B to themselves.

We also need to produce a unique u : coexp(B, A) -> X for any e : B -> X + A. We proceed by cases.
Case 1: A is non-empty. Then u : Void -> X, so we must choose u : Void -> X to be absurd_Void, the unique morphism out of Void.
Case 2: A is empty. Then u : B -> X, and e : B -> X + Void must map every element of B to an X, so we choose that map for our u.

I don't like it because it is far from being as elegant as the exponential, because it doesn't seem very useful, and because of the arbitrary choice in the definition of v....

My result was quite similar, except for leaving undefined ($\not=$ defined as Void) coexp(B,A) when both A and B are non-empty.

This is my solution for the co-exponential object in Set

Given two sets $X$ and $Y$, we must find a set $X_Y := coexp(Y,X)$ and a function $\eta : X \longrightarrow X_Y \sqcup Y$ such that for every function $e : X \longrightarrow Z \sqcup Y$ there exists a unique function $k : X_Y \longrightarrow Z$ for which $e = (k\sqcup id_Y) \circ \eta$.

The situation is depicted in the following figure: coexp.jpg

0. When $X=\emptyset$ (initial), for every set $Y$ we are forced to consider for $\eta$ the only empty function $\eta : \emptyset \longrightarrow \emptyset_Y \sqcup Y$.
   For every set $Z$, the empty function $e: \emptyset \longrightarrow Z \sqcup Y$ trivially equals $(k\sqcup id_Y) \circ \eta$ , as $\emptyset = k \circ \emptyset$ for any function $k$.
   In order for such a $k: \emptyset_Y \longrightarrow Z$ to exist even in the case $Z=\emptyset$, we must define $\emptyset_Y := \emptyset$ (hence unicity is given by $\emptyset$ initial).

1. When $X\not= \emptyset$:
   Lemma 1.1 $\ \ \ \eta(X) \subseteq \iota_X(X) := \{0\} \times X$
   Suppose $\eta(x) = (1,y)$ for some $x \in X, y \in Y$; then we can consider $e := \iota_X : X \longrightarrow X \sqcup Y : x \longmapsto (0,x)$, for which there is no $k: X_Y \longrightarrow Z$ making the diagram to commute. In fact, $(k \sqcup id_Y) \circ \eta (x) = (k \sqcup id_Y) \circ (1,y) = (1,y) \ \not= \ (0,x) = e(x)$.
   Corollary 1.2 $\ \ \ \eta$ must be injective.
   As we can take $e = \iota_X$ (which is injective); then also the composite $X \stackrel{\eta}{\longrightarrow} Z \sqcup Y \stackrel{k\sqcup id_Y}{\longrightarrow} X \sqcup Y$ and hence $\eta$ must be injective.
   Corollary 1.3 $\ \ \ \eta$ must be surjective on $X_Y$.
   Suppose there is some $(0,w) \in X_Y \sqcup Y \setminus \eta(X)$; then the function $k: X_Y \longrightarrow Z$ making the diagram to commute cannot be unique (provided $|Z| \geq 2$), as every function $k'$ obtained from $k$ by changing the image of $(0,w)$ will fit.
   Lemma 1.4 $\ \ \ Y = \emptyset$
   Otherwise we could define a function $e : X \longrightarrow X_Y \sqcup Y : x \longmapsto (1,y)$ for which there would be no way to make the diagram commutative. In fact, for every $k$ it is: $(k \sqcup id_Y) \circ \eta (x) = (k \sqcup id_Y) \circ (0,x') = (0,k(x')) \ \not= \ (1,y) = e(x)$.

Summing up, the quantifications in the universal property compel the function $\eta$ to be bijective (L1.2, L1.3) and to depend solely on X (L1.1); the latter can be accomplished in two cases: when either $X=\emptyset$ (L0) or $Y=\emptyset$ (L1.4). Hence:

Theorem 2 $\ \ \$ Given two sets X, Y, their co-exponential is defined (up to isomorphism) as:
$(X_Y,\eta) \ := \ \begin{cases} (X, \iota_x) & \text{if} \ X=\emptyset \ \text{or} \ Y=\emptyset \\ \text{undefined} \ \ \ \ \ \ & \text{else} \end{cases}$

I agree with this answer. Indeed, since there is no object with the right universal property, it's right to say that the coexponential of $A$ and $B$ doesn't exist when both $A$ and $B$ are nonempty.

Andrew Dudzik (Oct 24 2022 at 14:12):

So what's happening here? We can get some intuition by working in a slightly different category. For a fixed set $S$, consider the category $\mathcal{P}(S)$ of subsets of $S$, where the morphisms are given by subset inclusions.

Exercise: the coexponential $A_B$ in $\mathcal{P}(S)$ is just the set-theoretic difference $A-B$.

So in some sense, the coexponential wants to be a difference of sets. But the difference of sets isn't well-defined in the category $\mathtt{Set}$! For example, suppose $A$ and $B$ are one-element sets. What is $A-B$? It depends on whether $A$ and $B$ are equal, but equality is not a categorical property—only equivalence is!

So we're left with a boring coexponential, which only exists when one of $A$ and $B$ is the empty set. But in other settings (e.g. posets like the above) it can be a sensible thing to think about.

Matteo Capucci (he/him) (Oct 25 2022 at 10:28):

Let me sneak in a little high-brow proof of the non-existence of coexponentials, just to illustrate a powerful general technique. (I don't know if Petar meant coexponentials to be left adjoints to $-+X$ or still right adjoints, so I'll proof both don't exist).
Arguably the most important property of left adjoints is that they preserve [[colimits]], such as [[coproducts]]. So if you had a coexponential right adjoint to $- + X$, it would mean that $-+X$ is left adjoint and thus preserving colimits, so you'd have $(A + B) + X \cong (A+X) + (B+X)$, which is not true in general.
In the same way we see $-+X$ can't be a right adjoint (= it can't have a left adjoint) since in that case it would preserve [[limits]], such as [[cartesian products]], but $(A \times B) + X \cong (A+X) \times (B +X)$ is not true in general.

Alberto Meneghello (Oct 25 2022 at 19:08):

Andrew Dudzik
Thank you Andrew, very interesting your observation!

Effectively every Boolean algebra such as $P(S)$ can be seen as a thin category where:
the exponential (= right adjoint to $\,\underline{ \, \cdot\, }\wedge B$) is implication $A^B := B \rightarrow A \equiv \lnot B \vee A$,
hence taking the opposite (= dual)
the coexponential (= left adjoint to $\,\underline{ \, \cdot\, }\vee B$) amounts to $A_B := \lnot( \lnot B \rightarrow \lnot A ) \equiv \lnot B \wedge A =: A \setminus B$.

Therefore, there seems to be some "contravariance" here: the fewer the morphisms in the category, the fewer the constraints for the universal property to hold, the more likely for the co/limit to exist. Of course it is not always the case (for instance in a discrete category) as certain maps have to exist for co/limits; is there some general criterion or is it specific for every situation?

Andrew Dudzik (Oct 25 2022 at 20:15):

I'm not sure what we can say in general about non-existence of limits. But there is a fact I found on nLab: every category with all exponential and coexponential objects is thin. So in this case, you can have any two of exponentials, coexponentials, and lots of morphisms, but not all three!

Andrew Dudzik (Oct 25 2022 at 20:25):

@Matteo Capucci (he/him)

Let's not forget the third possible definition of coexponential! We don't have $(A\times B)\times X = (A\times X) \times (B\times X)$ in general, so $-\times X$ isn't a right adjoint. Hadn't occurred to me that this was related to picking the correct distributive law.

Matteo Capucci (he/him) (Oct 25 2022 at 21:30):

Andrew Dudzik said:

But there is a fact I found on nLab: every category with all exponential and coexponential objects is thin.

Very cool!