User michal r. przybylek - MathOverflow

Internal Day convolution

2013-04-21T18:10:53Z

Let me recall that any small category $\mathbb{A}$ enriched in a complete and cocomplete symmetric monoidal closed category $\mathbb{V}$ admits embedding (the Yoneda embedding): $$y_\mathbb{A} \colon \mathbb{A} \rightarrow \mathbb{V}^{\mathbb{A}^{op}}$$ into a complete and cocomplete $\mathbb{V}$-enriched category. And:

this embedding preserves any monoidal structure $\langle \otimes_\mathbb{A}, I_\mathbb{A} \rangle$ defined on $\mathbb{A}$; the induced structure $\mathbb{V}^{\mathbb{A}^{op}} \otimes \mathbb{V}^{\mathbb{A}^{op}} \rightarrow \mathbb{V}^{\mathbb{A}^{op}}$ is given by the Day convolution: $$\langle F, G \rangle \mapsto \int^{B \in \mathbb{A}, C \in \mathbb{A}} F(B) \otimes G(C) \otimes \hom(-, B \otimes_\mathbb{A} C)$$
the induced structure on $\mathbb{V}^{\mathbb{A}^{op}}$ is always monoidal (bi)closed
more generally, any promonoidal structure (i.e. a weak monoidal object in the bi-category of $\mathbb{V}$-enriched distributors) defined on $\mathbb{A}$ induces a (bi)closed monoidal structure on $\mathbb{V}^{\mathbb{A}^{op}}$; moreover there is a bijective correspondence between (bi)closed monoidal structures defined on $\mathbb{V}^{\mathbb{A}^{op}}$ and promonoidal structures defined on $\mathbb{A}$

It seems (though I have not checked details) that all of the above carry to the context of categories internal to any finitely cocomplete locally cartesian closed category $\mathbb{C}$. For any $\mathbb{C}$-internal category $\mathbb{A}$ there exists a fibred fully faithful embedding: $$y_\mathbb{A} \colon \mathbb{A} \rightarrow \mathbb{C}^{\rightarrow^{\mathbb{A}^{op}}}$$ where $\mathbb{C}^{\rightarrow^{\mathbb{A}^{op}}}$ is the (complete and cocomplete cartesian closed) fibration of $\mathbb{A}^{op}$-indexed diagrams in the fundamental (i.e. codomain) fibration on $\mathbb{C}$.

This observation is so blatantly obvious that it must have been made (and written somewhere) before. What are the references?

Much of the work has been done in "Cosmoi of Internal Categories" by Ross Street. However, I have not found any statement about transporting monoidal structures from $\mathbb{A}$ to $\mathbb{C}^{\rightarrow^{\mathbb{A}^{op}}}$ in the paper.

Answer by Michal R. Przybylek for Internal Day convolution

2013-05-07T19:40:56Z

After some research, I think it has not been observed until now. However, all of the bricks needed to make the argument are almost ready.

In paper "Monoidal bicategories and Hopf algebroids" Brain Day and Ross Street defined a notion of convolution in the context of Gray monoids. For a reason that shall become clear later, I am willing to call it "virtual convolution". Here is the definition. Let $\langle A, \delta \colon A \rightarrow A \otimes A, \epsilon \colon A \rightarrow I \rangle$ be a weak comonoid, and $\langle B, \mu \colon B \otimes B \rightarrow B, \eta \colon I \rightarrow B \rangle$ be a weak monoid in a monoidal bi-category with tensor $\otimes$ and unit $I$, then $\langle \hom(A, B), \star, i \rangle$ is a monoidal category by: \begin{array}{ccc} f\star g &=& \mu \circ (f \otimes g) \circ \delta \newline i &=& \eta \circ \epsilon \end{array} So the "convolution structure" exists only virtually --- on $\hom$-categories. If the monoidal bi-category admits all right Kan liftings, then such induced monoidal category $\langle \hom(I, B), \star, i \rangle$ for trivial comonoid on $I$ is monoidal (bi)closed by: $$f \overset{L}\multimap h = \mathit{Rift}_{\mu \circ (f \otimes \mathit{id})}(h)$$

$$f \overset{R}\multimap h = \mathit{Rift}_{\mu \circ (\mathit{id} \otimes f)}(h)$$ Taking for the monoidal bi-category the bi-category of profunctors, we obtain the well-known formula for convolution. However, in the general setting, such induced structure is far weaker than one would wish to have --- for example in the category of profunctors enriched over a monoidal category $\mathbb{V}$ the induced convolution instead of giving a monoidal structure on the category of enriched presheaves: $$\mathbb{V}^{B^{op}}$$ merely gives a monoidal structure on the underlying category: $$\hom(I, \mathbb{V}^{B^{op}})$$ Actually, there is a work-around for this issue in the context of enriched categories, as suggested in the paper, but the general weakness of "virtual convolution" is obvious.

The solution is to find a way to "materialize" the convolution. I shall sketch the idea for internal categories. I think all of the following works for split fibrations and split structures, so let me replace the codomain fibration $\mathbb{C}^\rightarrow \rightarrow \mathbb{C}$ from the question by its split version corresponding to the internal "family functor": $$\mathit{fam}(\mathbb{C}) \colon \mathbb{C}^{op} \rightarrow \mathbf{Cat}$$ Likewise, for a category $A$ internal to $\mathbb{C}$ I shall write: $$\mathit{fam}(A) \colon \mathbb{C}^{op} \rightarrow \mathbf{Cat}$$ for the functor corresponding to the externalisation of $A$. We want to show that given a promonoidal structure $$\langle A, \mu \colon A \times A \nrightarrow A, \eta \colon 1 \nrightarrow A \rangle$$ there is a corresponding monoidal closed structure on: $$\mathit{fam}(\mathbb{C})^{\mathit{fam}(A)^{op}}$$ which just means, that each fibre of $\mathit{fam}(\mathbb{C})^{\mathit{fam}(A)^{op}}$ is a monoidal closed category and reindexing functors preserve these monoidal structures. By fibred Yoneda lemma, for $K \in \mathbb{C}$: $$\mathit{fam}(\mathbb{C})^{\mathit{fam}(A)^{op}}(K) = \mathit{Prof}(K, A)$$ where $K$ is interpreted as a discrete internal category. There is a correspondence: $$\mathit{Prof}(K, A) \approx \mathit{Prof}(1, K^{op} \times A) = \mathit{Prof}(1, K \times A)$$ where the last equality holds because $K^{op} = K$ for any discrete category $K$. Since $K$ has a trivial promonoidal structure: $$K \times K \overset{\Delta^*}\nrightarrow K$$ we obtain a "product" promonoidal structure on $K \times A$:

\begin{array}{rcc} K \times A \times K \times A &\overset{\Delta^* \times \mu}\nrightarrow& K \times A \newline 1 &\overset{\langle !^*, \eta \rangle}\nrightarrow& K \times A \end{array} In more details, since $\mathbb{C}$ is cartesian, every object $K \in \mathbb{C}$ carries a unique comonoid structure:

\begin{array}{l} K \overset{\Delta}\rightarrow K \times K \newline K \overset{!}\rightarrow 1 \end{array}

which has a promonoidal right adjoint structure $\langle \Delta^*, !^* \rangle$ in the (bi)category of internal profunctors. The product of the above two promonoidal structures is given by the usual cartesian product of internal categories (note, it is not a product in the bicategory of internal profunctors) followed by the internal product functor $\mathit{fam}(\mathbb{C}) \times \mathit{fam}(\mathbb{C}) \overset{\mathit{prod}}\rightarrow \mathit{fam}(\mathbb{C})$.

Then by "virtual convolution" there is a monoidal (bi)closed structure on $\mathit{Prof}(1, K^{op} \times A)$. Therefore each fibre $\mathit{fam}(\mathbb{C})^{\mathit{fam}(A)^{op}}(K)$ is a monoidal (bi)closed category. It is easy to check that reindexing functors preserve these structures.

Let me work out the concept of internal Day convolution in case $\mathbb{C} = \mathbf{Set}$ and a promonoidal structure on a small category is monoidal. The split family fibration (or more accurately, the indexed functor corresponding to the family fibration) for a locally small category $A$: $$\mathit{fam}(A) \colon \mathbf{Set}^{op} \rightarrow \mathbf{Cat}$$ is defined as follows: \begin{array}{rcl} \mathit{fam}(A)(K \in \mathbf{Set}) &=& A^K \newline \mathit{fam}(A)(K \overset{f}\rightarrow L) &=& A^L \overset{(-) \circ f}\rightarrow A^K\newline \end{array} where $K, L$ are sets and $K \overset{f}\rightarrow L$ is a function between sets. One may think of category $A^K$ as of the category of $K$-indexed tuples of objects and morphisms from A. Now, given any monoidal structure on a small category $$\langle A, \otimes \colon A \times A \rightarrow A, I \colon 1 \rightarrow A \rangle$$ the usual notion of convolution induces a monoidal structure on $\mathbf{Set}^{A^{op}}$: $$\langle F, G \rangle \mapsto F \otimes G = \int^{B, C \in A} F(B) \times G(C) \times \hom(-, B \otimes C)$$ The split fibration: $$\mathit{fam}(\mathbf{Set})^{\mathit{fam}(A)^{op}} \colon \mathbf{Set}^{op} \rightarrow \mathbf{Cat}$$ may be characterised as follows:

\begin{array}{rcl} \mathit{fam}(\mathbf{Set})^{\mathit{fam}(A)^{op}}(K \in \mathbf{Set}) &=& \mathbf{Set}^{A^{op} \times K} \newline \mathit{fam}(\mathbf{Set})^{\mathit{fam}(A)^{op}}(K \overset{f}\rightarrow L) &=& \mathbf{Set}^{A^{op} \times L} \overset{(-) \circ (\mathit{id} \times f)}\rightarrow \mathbf{Set}^{A^{op} \times K}\newline \end{array} Since $\mathbf{Set}^{A^{op} \times K} \approx (\mathbf{Set}^{A^{op}})^K$ we may think of $\mathbf{Set}^{A^{op} \times K}$ as of $K$-indexed tuples of functors ${A^{op} \rightarrow \mathbf{Set}}$. In fact: $$\mathit{fam}(\mathbf{Set})^{\mathit{fam}(A)^{op}} \approx \mathit{fam}(\mathbf{Set}^{A^{op}})$$ It is natural then to extend the monoidal structure induced on $\mathbf{Set}^{A^{op}}$ pointwise to $(\mathbf{Set}^{A^{op}})^K$: $$(F \otimes G)(k) = \int^{B, C \in A} F(k)(B) \times G(k)(C) \times \hom(-, B \otimes C)$$ where $k \in K$.

On the other hand, using the internal formula for convolution, we get (up to a permutation of arguments): \begin{array}{c} \int^{B, C \in A, \beta, \gamma \in K} F(B, \beta) \times G(C, \gamma) \times \hom(\Delta(k), \langle \beta, \gamma \rangle) \times \hom(-, B \otimes C) \newline\hline\newline\hline \int^{B, C \in A, \beta, \gamma \in K} F(B, \beta) \times G(C, \gamma) \times \hom(k, \beta) \times \hom(k, \gamma) \times \hom(-, B \otimes C) \newline\hline\newline\hline \int^{B, C \in A} F(B, k) \times G(C, k) \times \hom(-, B \otimes C) \newline \end{array} where the first equivalence is the definition of diagonal $\Delta$ --- recall that the diagonal $\Delta(k) = \langle k, k \rangle$ is represented by profunctor $\hom(\langle \overset{1}-, \overset{2}-\rangle, \Delta(\overset{3}-))$, which has profunctorial right adjoint $\hom(\Delta(\overset{1}-), \langle \overset{2}-, \overset{3}-\rangle) \approx \hom(\overset{1}-, \overset{2}-) \times \hom(\overset{1}-, \overset{3}-)$ --- and the second one is by "Yoneda reduction" applied twice.

Final remarks:

Seeing the above proof, one may wonder where the assumptions about the category $\mathbb{C}$ from the question were actually used:
- local cartesian closedness guaranteed existence of all right Kan liftings in the bi-category of internal profunctors; without this assumption, the induced monoidal structure on $\mathit{fam}(\mathbb{C})^{\mathit{fam}(A)^{op}}$ would be generally non-closed; to see that local cartesian closedness is really crucial here, recall that fibration $\mathit{fam}(\mathbb{C})$ is a cartesian closed fibration iff $\mathbb{C}$ is locally cartesian closed ---- this means that without local cartesian closedness even trivial convolution of the monoidal structure on the terminal category is not closed; moreover, which has not been stated in the answer, local cartesian closedness made it possible to speak about internal Yoneda embedding
- finite colimits (coequalisers) allowed us to define compositions of internal profunctors
To really obtain a split monoidal closed structure via convolution without moving through the equivalence between Gray monoids and monoidal bi-categories ("Coherence for Tricategories", Gordon, Power, Street), one has (of course!) to replace the monoidal bi-category of internal profunctors by equivalent Gray monoid consisting of internal categories of presheaves and internally cocontinous functors.
I think that the right setting for the concept of Day convolution is a "Yoneda monoidal bi-triangle" as sketched in this answer.

Answer by Michal R. Przybylek for About a General Definition of Profunctor

2013-04-25T22:00:09Z

As Mike wrote in his comment, this statement is true with an appropriate notion of a category $\mathcal{E}^A$ and cocontinuity.

The category $\mathcal{E}^A$ from your definition is the underlying category of a locally internal category $\mathcal{E}^{\rightarrow^A}$. In more explicit terms, $\mathcal{E}^{\rightarrow}$ may be thought as of the codomain fibration over $\mathcal{E}$, $A$ as of the small fibration corresponding to the externalization of $\mathcal{E}$-internal category $A$, and $\mathcal{E}^{\rightarrow^A}$ as of the exponent $A \Rightarrow \mathcal{E}^\rightarrow$. Then your $\mathcal{E}^A$ is a mere fibre over terminal object in $\mathcal{E}^{\rightarrow^A}$.

Because for any internal category $A^{op}$, fibration $\mathcal{E}^{\rightarrow^{A}}$ is its internal free cocompletion, we get: $$\mathit{CoCont}(\mathcal{E}^{\rightarrow^{A}}, \mathcal{E}^{\rightarrow^{B}}) \approx \hom(A^{op}, \mathcal{E}^{\rightarrow^B})$$ The above statement may be found as a special case of Theorem 3.20 in Mark Weber's "Yoneda structures from 2-toposes".

Finally: $$\hom(A^{op}, \mathcal{E}^{\rightarrow^B}) \approx \hom(1, \mathcal{E}^{\rightarrow^{A^{op} \times B}}) \approx \mathcal{E}^{A^{op}\times B}$$ where the last equivalence is an instance of fibred Yoneda lemma.

Answer by Michal R. Przybylek for Does this kind of endofunctor ever have an initial algebra?

2013-04-23T09:08:04Z

The above answers are great, but I would like to stress on one fundamental aspect here.

Contrary to some common beliefs, Cantor's diagonal argument is purely constructive and as such carries to the internal logic of elementary topos (notice, however, that it relies on impredicativity of the topos). For let us assume, there is an injection $j \colon \Omega^A \rightarrow A$. We may form a paradoxical subset of $\Omega^A$: $$P = \{x \in A \colon \forall_{y \in \Omega^A} x \in y \rightarrow x \not= j(y) \}$$ Let us consider: $$p = j(P)$$ If $p \in P$ then according to the definition of $P$: $$p \in y \rightarrow p \not= j(y) \;\;\;\;\;\;(F)$$ for all $y \in \Omega^A$, so particularly for $y = P$, we have: $$p \in P \rightarrow p \not= j(P)$$ and by using (again) the assumption $p \in P$, we can derive $p \not= J(P)$, which by the definition of $p$ produces $\bot$. Therefore we constructed a method of turning a statement $p \in P$ into absurd, that is $p \in P \rightarrow \bot$.

On the other hand, we may show that the formula (F) holds for every $y$. By the definition of $p$, it is equivalent to: $$p \in y \rightarrow j(P) \not= j(y)$$ and by the definition of the implication, to: $$j(P) = j(y) \overset{\psi \circ \phi}\rightarrow (p \in y \rightarrow \bot)$$ Now, we may use our extra assumption saying that $j$ is injective: $$j(P) = j(y) \overset{\phi}\rightarrow P = y$$ and cut it with: $$P = y \overset{\psi}\rightarrow (p \in y \rightarrow \bot)$$ which is equivalent to: $$P = y \wedge p \in y \rightarrow \bot$$ and holds because $p \in P \rightarrow \bot$ as has been shown in the first part of the proof. Therefore, (F) holds as the composition of proofs $\psi$ with the fact $\phi$ saying that $j$ is injective. Finally, by comprehension, $p \in P$. So: $$(p \in P) \wedge (p \in P \rightarrow \bot)$$ thus: $$\bot$$

This means that there can be no injection $\Omega^A \rightarrow A$ for any $A$. This also means that there can be no injection $\Omega^{\Omega^A} \rightarrow A$ (because we have an obvious injection $A \rightarrow \Omega^A$ and composition of injections is an injection). Therefore, there are no isomorphisms $\Omega^{\Omega^A} \approx A$ and by Lambek's theorem, there are no initial (nor final) (co)algebras for $\Omega^{\Omega^{(-)}}$.

More generally, by a similar argument, one may show that if there exists an injection $\Omega \rightarrow X$ then there could be no initial algebra for $X^{X^{(-)}}$.

Answer by Michal R. Przybylek for grothendieck construction for profunctors

2013-04-22T21:01:48Z

[I guess that by $x_*g$ you mean $D(\mathit{id}, g)(x)$ and by $f^*y$ you mean $D(f, \mathit{id})(y)$.]

Actually, your second construction is the usual Grothendieck construction for "$\mathbf{Cat}$-valued distributors" (BTW, this term may be misleading a bit, because in a $\mathbf{Cat}$-valued distributor $\mathbb{X}^{op} \times \mathbb{Y} \rightarrow \mathbf{Cat}$ 2-categories $\mathbb{X}$ and $\mathbb{Y}$ are not necessary degenerated). It may be universally characterised as a $(- \downarrow \mathbb{Y}) \times (\mathbb{X} \downarrow =)$-weighted colimit of $D \colon \mathbb{X}^{op}\times \mathbb{Y} \rightarrow \mathbf{Cat}$.

See: "Cosmoi of Internal Categories" by Ross Street, Transactions American Math. Soc. 258 (1980) 271-318; MR82a:18007.

Answer by Michal R. Przybylek for Exponentiable objects in a category, valued in a larger, containing category

2013-04-17T13:44:33Z

Fernando is right that it has something to do with Kan extensions. However, it is not about Kan extensions along an inclusion, but more about extension of an inclusion.

I thought about similar issues a few years ago (and recently --- yesterday) , but in a slightly different context --- after the excellent answer by Todd Trimble to my question http://mathoverflow.net/questions/59291/completion-of-a-category, I wondered if there was a general 2-categorical setting that could explain such constructions (I was mainly interested in carrying to a 2-categorical setting the highly related concept of Day convolution).

Now I try to slowly reproduce some of these ideas.

I shall introduce the concept of a Yoneda triangle (perhaps I should call it the right Yoneda triangle, because there are obvious dual concepts).

Let $\mathbb{W}$ be a 2-category. A Yoneda triangle in $\mathbb{W}$ consists of 1-morphisms $y \colon A \rightarrow \overline{A}$, $f \colon A \rightarrow B$, $g \colon B \rightarrow \overline{A}$ together with a 2-morphism $\eta \colon y \rightarrow g \circ f$ which exhibits $g$ as a pointwise left Kan extension of $y$ along $f$ and exhibits $f$ as an absolute left Kan lifting of $y$ along $g$. (BTW: these data are exactly what led Mark Weber to strengthen the definition of a Yoneda structure introduced by Street and Walters).

The idea of a Yoneda triangle is that, we have a morphism $y \colon A \rightarrow \overline{A}$ which plays the role of a "defective identity" and for a given morphism $f \colon A \rightarrow B$ we try to characterise its right adjoint up to the "defective identity" $y$.

Example: [Yoneda triangles in $\mathbf{Cat}$] If we take $\mathbb{W}$ to be the 2-category $\mathbf{Cat}$ of locally small categories, functors and natural transformations, then the condition that $G$ is a pointwise left Kan extension of $Y$ along $F$ reduces to: $$G(-) = \int^{A\in\mathbb{A}} \hom(F(A), -) \times Y(A)$$ (where the coend has to be interpreted as the colimit of $Y$ weighted by $\hom(F(=), -)$ in case the category is not tensored over $\mathbf{Set}$). And the condition that $F$ is an absolute left Kan lifting of $Y$ along $G$ reduces to: $$\hom(Y(-), G(=)) \approx \hom(F(-), =)$$

Particularly, if $Y$ is dense, than $G$ is canonically a pointwise Kan extension --- from density we have: $$G(-) \approx \int^{A\in\mathbb{A}} \hom(Y(A), G(-)) \times Y(A)$$ and using the formula for an absolute lifting: $$G(-) \approx \int^{A\in\mathbb{A}} \hom(F(A), -) \times Y(A)$$

Example: [Adjunction as Yoneda triangle] It is folklore that an adjunction $f \dashv g$ in a 2-category $\mathbb{W}$ may be equally characterised in the following way: $f$ is an absolute left lifting of the identity along $g$. In such a case $g$ is automatically a pointwise left extension of the identity along $f$ and $\mathit{id}, f, g$ together with the unit of the adjunction form a Yoneda triangle.

Example: [Yoneda triangle as a relative adjunction] There is an old concept of so called "relative adjunction", which is defined in the same way as the Yoneda triangle, but without the requirement that $g$ is a left Kan extension. Note however, that in such a case $g$ need not be uniquely determined by $f$.

Let me move to the more specific example that you asked about.

Example: [Yoneda triangle along Yoneda embedding] Let $F \colon \mathbb{A} \rightarrow \mathbb{B}$ be a functor between locally small categories (or more generally, a locally small functor). There is also an inclusion $y_\mathbb{A} \colon \mathbb{A} \rightarrow \mathbf{Set}^{\mathbb{A}^{op}}$. One may easily verify that these data may be always extended to the Yoneda triangle with $G(-) = \hom(F(=), -) \colon \mathbb{B} \rightarrow \mathbf{Set}^{\mathbb{A}^{op}}$ --- which reassembles the fact that every functor always has a "distributional" right adjoint. The same is true for internal categories and for categories enriched in a complete and cocomplete symmetric monoidal closed category, and generally (almost by definition) for any 2-category equipped with a Yoneda structure.

The essence of the above example is that because the Yoneda functor $y_\mathbb{B} \colon \mathbb{B}\rightarrow \mathbf{Set}^{\mathbb{B}^{op}}$ is a full and faithful embedding, functors $F\colon\mathbb{A} \rightarrow \mathbb{B}$ may be thought as of distributors $$y_\mathbb{B} \circ F = \hom(=, F(-))$$ Every distributor arisen in this way has a right adjoint distributor $\hom(F(=), -)$ in the bicategory of distributors. The distributor $\hom(F(=), -)$ has actually the type $\mathbb{B} \rightarrow \mathbf{Set}^{\mathbb{A}^{op}}$, which is the only think that may prevent $F$ of having the ordinary (functorial) right adjoint $G \colon \mathbb{B} \rightarrow \mathbb{A}$ --- just recall, that we say that $F$ has a right adjoint, if there exists $G$ such that: $$y_\mathbb{A} \circ G \approx \hom(F(=), -)$$ which means: $$\hom(=, G(-)) \approx \hom(F(=), -)$$

Unfortunately, as a non-mathematician I will not help you with your other examples involving highly mathematical and completely non-understandable terms like a topological space or a manifold, so perhaps you have to calculate the other examples yourself :-)

However, I will give you another example that actually led me to the above considerations. One may similarly define the concept of a Yoneda bi-triangle and a Yoneda monoidal bi-triangle.

Example: [2-powers from Yoneda triangle] The motivating example is to start with a 2-functor $J \colon \mathbb{W} \rightarrow \mathbb{D}$ equipping a 2-category $\mathbb{W}$ with proarrows, and an extension $Y \colon \mathbb{W} \rightarrow \overline{\mathbb{W}}$ embedding "small objects" into "locally small" (or large) objects in $\overline{\mathbb{W}}$. Then to extend these data to the Yoneda triangle, we have to find a functor $P \colon \mathbb{D} \rightarrow \overline{\mathbb{W}}$ representing a proarrow $A \nrightarrow B$ as a morphism $A \rightarrow P(B)$ in $\overline{\mathbb{W}}$, and a natural transformation $\eta \colon Y \rightarrow P\circ J$ playing the role of a familly of Yoneda morphisms $\eta_A \colon A \rightarrow P(A)$.

The archetypical situation is when we take $\mathbb{W} = \mathbf{cat}$, $\overline{\mathbb{W}} = \mathbf{Cat}$, $\mathbb{D} = \mathbf{Dist}$, where $\mathbf{cat}$ is the 2-category of small categories, $\mathbf{Cat}$ is the 2-category of locally small categories, and $\mathbf{Dist}$ is the bicategory of distributors between small categories. Then $J \colon \mathbf{cat} \rightarrow \mathbf{Dist}$, $Y \colon \mathbf{cat} \rightarrow \mathbf{Cat}$ are the usual embeddings, $P \colon \mathbf{Dist} \rightarrow \mathbf{Cat}$ is the covarinat 2-power pseudofunctor $\mathbf{Set}^{(-)^{op}}$ defined on distributors via left Kan extensions, and $\eta_\mathbb{A} \colon \mathbb{A} \rightarrow \mathbf{Set}^{\mathbb{A}^{op}}$ is the Yoneda embedding of a small category $\mathbb{A}$.

We know that there are isomorphisms of categories: $$\hom_{\mathbf{Dist}}(\mathbb{A}, \mathbb{B}) \approx \hom_{\mathbf{Cat}}(\mathbb{A}, \mathbf{Set}^{\mathbb{B}^{op}})$$ where $\mathbb{A}$ and $\mathbb{B}$ are small. Therefore, to show that $P$ is a (bi)pointwise left Kan extension it suffices to show that $Y$ is 2-dense. However, $Y$ is obviously 2-dense, because the the terminal category is a 2-dense subcategory of $\mathbf{Cat}$ and $Y$ is fully faithful.

The point is that in most situations $\mathbb{D}$ is a monoidal (bi)category, where the monoidal structure is inherited from the closed structure on $\mathbb{W}$. Moreover, functors and the natural transformation constituting the Yoneda triangle are (lax)monoidal. This means that monoids in $\mathbb{W}$ are mapped to the (pro)monoids in $\mathbb{D}$ which are mapped to monoids in $\overline{\mathbb{W}}$. If I am not mistaken this observation leads to an abstract characterisation of the concept of the Day convolution (and in a similar manner one may try to define a Dedekind-MacNeille completion of an object).

In our archetypical situation, a category $\mathbb{A} \times \mathbb{B}$ is mapped by $P$ to $\mathbf{Set}^{\mathbb{A}^{op} \times \mathbb{B}^{op}}$ and the missing morphisms making the unit of the triangle lax monoidal: $$\mathbf{Set}^{\mathbb{A}^{op}} \times \mathbf{Set}^{\mathbb{B}^{op}} \rightarrow \mathbf{Set}^{\mathbb{A}^{op} \times \mathbb{B}^{op}}$$ is given by the convolution of the distributional identity $\mathbb{A} \times \mathbb{B} \nrightarrow \mathbb{A} \times \mathbb{B}$: $$\langle F, G \rangle \mapsto \int^{A \in \mathbb{A}, B \in \mathbb{B}} F(A) \times G(B) \times \hom(-, A) \times \hom(=, B) = F(-) \times G(=)$$ Now, a promonoidal category $M \colon \mathbb{A} \times \mathbb{A} \nrightarrow \mathbb{A}$ is mapped by $P$ to: $$H \mapsto \int^{\langle A, B \rangle \in \mathbb{A}\times \mathbb{A}} H(A, B) \times M(-, A, B)$$ and by composing it with the above map: $$\langle F, G \rangle \mapsto \int^{\langle A, B \rangle \in \mathbb{A}\times \mathbb{A}} F(A) \times G(B) \times M(-, A, B)$$ we obtain the well-known formula for convolution.

One may also go in the other direction --- starting from the composition $P \circ J$ satisfying monoidal-like laws and try to find a right or left resolution in the category of (right/left) modules over monoid on $P \circ J$. If I am not mistaken, the left resolution (the Eilenberg-Moore object) of $P \circ J$ in our archetypical situation consists of the category of cocomplete categories and cocontinous functors and the right resolution (the Kleisli object) consists of the bicategory of distributors (i.e. the category of free cocomplete categories and cocontinous functors).

(BTW: this in some sense relates the concept of a proarrow equipment with the concept of a Yoneda structure.)

(BTW: perhaps the concept of a 2-topos should be defined as a Yoneda monoidal bi-triangle induced by the embedding of a 2-category of small objects into a category of bigger objects relatively to a category of "relations" in $\mathbb{W}$, which, for some purposes may be defined as the 2-category of discrete fibred spans, and for another purposes may be defined as the 2-category of codiscrete cofibred cospans).

Answer by Michal R. Przybylek for Is there a constructive proof of Cantor–Bernstein–Schroeder theorem ?

2013-03-19T15:44:20Z

It is well-known that Grothendieck toposes and realizability toposes (for different reasons) are models of Intuitionistic Zermelo–Fraenkel set theory. Therefore both Andrej and Todd showed in their answers (in essentially different way) that Cantor–Bernstein–Schroeder cannot be proved in IZF.

Of course, this does not mean that Cantor–Bernstein–Schroeder property is incompatible with constructive mathematics --- it just shows that IZF is too weak to prove CBS. Therefore, a complementary question could be: what are the implications of IZF+CBS; does IZF+CBS make the logic collapse to the boolean case?

If I am not mistaken, the answer is no, and the counterexample is constructed below. However, I shall start with a negative observation.

Let $\Omega$ be a Heyting algebra with countable unions. An element $v \in \Omega$ is complementable if there exists an element $w \in \Omega$ such that $v \vee w = 1$ and $v \wedge w = 0$.

We say that $\Omega$ is a boolean algebra if its every element is a finite union of complementable elements (equivalently, if every element is complementable).

We say that $\Omega$ is a pro-boolean algebra if its every element is a countable union of complementable elements.

The claim is that every elementary topos with countable colimits satisfying Cantor–Bernstein–Schroeder propery is pro-boolean (i.e. its subobject classifier is a pro-boolean algebra).

Let $v \colon V \rightarrow 1$ be a "truth" value (a monomorphism into terminal object). We shall construct two objects $X = \coprod_{\mathbb{N}} 1$ and $Y = V \sqcup X$. There are obvious monomorphisms ${\iota_X}\colon{X}\rightarrow{Y}$ given by the coproduct injection, and ${v \sqcup \mathit{id}}\colon{Y}\rightarrow{X}$. Therefore, by Cantor–Bernstein–Schroeder there is an isomorphism ${b}\colon{Y}\rightarrow{X}$. Since coproducts in a topos are extensive, we may divide each component ${\iota_0}\colon V \rightarrow{Y}$, ${\iota_k}\colon 1 \rightarrow{Y}$ of the coproduct $Y$ along $b$ through coproduct's injections ${\iota_l} \colon 1 \rightarrow{X}$ obtaining elements $\alpha_{k,l}$ such that $Y \approx \coprod_k \coprod_l \alpha_{k,l} \approx \coprod_l \coprod_k \alpha_{k,l}$ and $b = \coprod_l b_l$ with each ${b_l}\colon{\coprod_l \alpha_{l,k}}\rightarrow{1}$ being an isomorphism (using again extensivity of coproducts and the fact that pullback of an iso is iso). Because unions in a topos are effective (and coproducts are disjoint) $1 \approx \coprod_l \alpha_{l,k} = \bigcup_l \alpha_{l,k}$ and so each $\alpha_{l,k}$ is complemented by $\bigcup_{x \neq l} \alpha_{x,k}$. Since every subterminal value can sit in exactly one way in the terminal object, $V = \bigcup_l \alpha_{l,0}$ is a countable disjoint union of complementable elements.

(We cannot get more from this construction; for example in the category of sheaves over rational numbers with the usual topology, $\coprod_{\mathbb{N}} 1 \approx V \sqcup \coprod_{\mathbb{N}} 1$ for (non-complementable) truth value $V$ corresponding to the open ball $(-1, 1)$; unfortunately there are other objects in this category that can serve as counterexamples for CBS. Let me also point that the standard procedure of constructing an isomorphism from two monomorphisms would not work in this case. However, by the above argument it is clear that such an isomorphism may be constructed for any pro-boolean topos. The solution is to not shift uniformly the whole $V$ (or its pseudocomplement), but to move each of (countably many) complementable parts of $V$ separately.)

[I am terribly sorry, now I see that there is an error in the following argument; I will try to fix it (on condition it is possible --- I am not sure now). I should have checked all relevant detail before posted this as an answer.]

For a positive result, consider set: $$\mathcal{D} = \lbrace 0, 1, \frac12, \frac13, \frac14, \dotsc\rbrace$$ with topology inherited from $\mathbb{R}$ and construct the category $\mathit{Sh}(\mathcal{D})$ of sheaves over $\mathcal{D}$. Every open set in $\mathcal{D}$ can be build from singletons $\lbrace\frac1n\rbrace$ and a set of the form $[0, \frac1k]$.

Let $F, G \colon \mathcal{D}^{op} \rightarrow \mathbf{Set}$ be any sheaves and assume there are monomorphisms $m \colon F \rightarrow G$ and $n \colon G \rightarrow F$. A monomorphism between sheaves is an injection on its each component, therefore by CBS theorem for sets $F(U) \approx G(U)$ for every open set $U$. Let $\phi_U \colon F(U) \approx G(U)$ be a collection of such isomorphisms. We shall construct an isomorphism $\alpha \colon F \rightarrow G$ between sheaves inductively:

$\lambda_{[0, 1]} = \phi_{[0, 1]}$
for every nonempty $F(\lbrace\frac1k\rbrace)$ choose an element $1_{\frac1k} \in F(\lbrace\frac1k\rbrace)$; if $F(\lbrace\frac1k\rbrace)$ is empty then $\lambda_{[0, \frac1{k+1}]} = \phi_{[0, \frac1{k+1}]}$, otherwise $\lambda_{[0, \frac1{k+1}]} = G([0, \frac1{k+1}] \subset [0, \frac1{k}]) \circ h_{\frac1k}$, where $h_{\frac1k} \colon F([0, \frac1{k+1}]) \rightarrow F([0, \frac1{k}])$ is the unique morphism to the product $F([0, \frac1{k}]) = F([0, \frac1{k+1}]) \times F(\lbrace\frac1k\rbrace)$ induced by $F([0, \frac1{k+1}]) \overset{!}\rightarrow 1 \overset{1_{\frac1k}}\rightarrow F(\lbrace\frac1k\rbrace)$ and the identity on $F([0, \frac1{k+1}])$
similarly, for every nonempty $F([0, \frac1{k+1}])$ choose an element $1_{[0, \frac1{k+1}]} \in F([0, \frac1{k+1}])$; if $F([0, \frac1{k+1}])$ is empty then $\lambda_{\lbrace\frac1{k}\rbrace} = \phi_{\lbrace\frac1{k}\rbrace}$, otherwise $\lambda_{\lbrace\frac1{k}\rbrace} = G(\lbrace\frac1{k}\rbrace \subset [0, \frac1{k}]) \circ h_{{[0, \frac1{k+1}]}}$
if $U$ is a disjoint union of the form $[0, \frac1k] \sqcup \bigcup_i\lbrace\frac{1}{n_i}\rbrace$, where $[0, \frac1k]$ is the largest interval contained in $U$, then $\lambda_{U} = \lambda_{[0, \frac1k]} \times \prod_i \lambda_{\lbrace\frac{1}{n_i}\rbrace}$, where the products are determined by structures of the sheaves.

In the second and third step we have chosen the components of $\lambda$ to be upward compatible, and in the fourth step the naturality condition follows from the universal property of products. Thus $F \approx G$.

[EDIT: Let me argue that $\phi_U$ may be chosen in such a way that each $\lambda_U$ is really an isomorphism. Assume, that all $F(\lbrace \frac1k\rbrace)$ are nonempty. Define $\mathit{colim}F([0, \frac1k])$ to be the colimit of the diagram: $$F([0, 1]) \rightarrow F([0, \frac12]) \rightarrow \cdots \rightarrow F([0, \frac1k]) \rightarrow \cdots $$ We have: $$(\mathit{colim}_kF([0, \frac1k])) \times (\prod_i F(\lbrace\frac1i\rbrace)) \approx F([0, 1]) \times \mathit{colim}_k \prod_{i > k} F(\lbrace\frac1i\rbrace) \approx F([0,1])$$ and similarly for $G$. Since in a locally presentable category monomorphisms are stable under directed colimits, both: $$\mathit{colim}F([0, \frac1k]) \overset{\mathit{colim}\left(m_{[0, \frac1k]}\right)}\rightarrow \mathit{colim}G([0, \frac1k])$$ and: $$\mathit{colim}F([0, \frac1k]) \overset{\mathit{colim}\left(n_{[0, \frac1k]}\right)}\leftarrow \mathit{colim}G([0, \frac1k])$$ are monomorphisms, thus by CBS for sets $\mathit{colim}F([0, \frac1k]) \overset{\phi_0}\approx \mathit{colim}G([0, \frac1k])$. Therefore, $\phi_{[0, 1]}$ may be assumed to be of the form $\phi_0 \times \prod \phi_{\lbrace\frac1k\rbrace}$. Likewise every $\phi_{[0, \frac1k]}$. ]

(BTW, I think we are not really that far from the inverse of the above theorem, but that is for another story...)

Answer by Michal R. Przybylek for Are exponentials in categorical models of linear logic harmful?

2013-03-01T15:29:08Z

No, it does not make the structure collapse. For example consider the category of small categories $\mathbf{Cat}$ --- it is clearly complete and cocomplete cartesian closed category, and moreover it has another closed monoidal structure induced by the "funny tensor" and linear exponents $\mathbb{C} \multimap \mathbb{D}$ given by the category of functors $\mathbb{C} \rightarrow \mathbb{D}$ together with (unnatural) transformations (i.e. "natural transformations" without "naturality" requirement).

Much more is true. Every (small) monoidal category $\langle \mathbb{V}, \otimes, I\rangle$ fully embeds into complete and cocomplete cartesian closed and monoidal closed category. The embedding is given by the usual Yoneda functor $y \colon \mathbb{V} \rightarrow \mathbf{Set}^{\mathbb{V}^{op}}$ and the monoidal closed structure is inherited via the Day convolution: $$(F \otimes G)(X) = \int^{A, B \in \mathbb{V}} F(A) \times G(B) \times \hom(X, A \otimes B)$$ $$(F \overset{L}\multimap G)(X) = \int_{A, B \in \mathbb{V}} G(A)^{F(B) \times \hom(A, X \otimes B)}$$ $$(F \overset{R}\multimap G)(X) = \int_{A, B \in \mathbb{V}} G(A)^{F(B) \times \hom(A, B \otimes X)}$$ where $\overset{L}\multimap$ is the left linear exponent and $\overset{R}\multimap$ is the right linear exponent (which are isomorphic precisely when the tensor $\otimes$ in $\mathbb{V}$ is symmetric). Moreover, it is easy to verify that Yoneda functor preserves the monoidal closed structures. Therefore, in some sense, every monoidal category can be (co)completed to a cartesian closed category with coproducts.

Answer by Michal R. Przybylek for A (too?) simple notion of "closed multicategory"

2013-01-07T19:23:01Z

What an interesting question! I have never thought about such exponents before.

Nevertheless, I think you miss more coherence conditions to make exponents behave well. Take for example a category with finite products. It corresponds to a multicategory with the same objects and with arrows $a_1, \dotsc, a_n \rightarrow x$ interpreted as arrows $a_1 \times \cdots \times a_n \rightarrow x$. The bijections: $$\phi_S^A\colon \hom(a_1,\dotsc,a_m,b_1,\dotsc,b_n;x)\to \hom(a_1,\dotsc,a_m;\mathit{Exp}(b_1,\dotsc,b_n;x))$$ turn into bijections: $$\hom(a_1 \times \dotsc \times a_m \times b_1 \times \cdots \times b_n;x)\to \hom(a_1 \times\cdots \times a_m;x^{b_1 \times \cdots \times b_n})$$ A category is cartesian closed precisely when the above bjiections are natural in $a_i$'s. I guess this naturality condition is really what you miss. Your "constant" elements $c_x\in \hom(x;\mathit{Exp}(;x)))$ correspond to isomorphisms $x \rightarrow x^1$ with evaluations $x^1 \approx x^1 \times 1 \rightarrow x$ being their inverses - but this does not help much.

Here is an explicit example what can go wrong --- consider the category of $\omega$-sets (or Hyland's effective topos if you wish) and a classical set $X$ as an object in the category. Almost by definition $X \not\approx X \sqcup 1$. However, if $X$ is infinite, then $\hom(A, X) \approx \hom(A, X \sqcup 1)$ for every $\omega$-set $A$. This means that according to the above definition both $X \times X$ and $(X \times X) \sqcup 1$ are candidates for an exponent of $1 \sqcup 1$ with the classical infinite set $X$, though are not isomorphic.

Perhaps a more elementary reformulation of simple exponents would be "by universal arrows". However, I do not see how one could give an external (that is 2-categorical, or 2-multicategorical) characterisation of such exponents!

Answer by Michal R. Przybylek for Externalising monoids using the Yoneda-embedding and relation to Kleisli categories

2012-07-30T22:51:23Z

For any monoidal category $\mathbb{C}$ there exists the "underlying" monoidal functor $\hom(I, -) \colon \mathbb{C} \rightarrow \mathbf{Set}$. As is the idea of a monoidal functor, it preserves structures defined by monoidal operations. Particularly, $\hom(I, -)$ lifts to the "underlying" 2-functor from the 2-category of $\mathbb{C}$-enriched categories to the 2-category of ordinary (that is: $\mathbf{Set}$-enriched) categories $U \colon \mathbb{C}$-$\mathbf{Cat} \rightarrow \mathbf{Cat}$.

A monoid $X$ internal to $\mathbb{C}$ is precisely a $\mathbb{C}$-enriched category $1_X$ having a single object $1$ and $\hom(1, 1) = X$. From this perspective, the first construction corresponds to taking the underlying category of $1_X$.

If $\mathbb{C}$ is closed and has equalisers, then something much stronger then proposition 2.6 should be true (i.e. proposition 2.6 should hold internally to $\mathbb{C}$). The monoid $1_X$ via Yoneda $y_{1_X} \colon 1_X \rightarrow \mathbb{C}^{1_X^{op}}$ embeds into the category of presheaves on $1_X$. Now the enriched Yoneda lemma says that $X$ is isomorphic to the object of natural transformations $\mathit{nat}(\hom(-, 1), \hom(-, 1))$, which, by the definition of a natural transformation, is a regular subobject of $[X, X] \in \mathbb{C}$.

We should get the second construction by applying the underlying functor to $X \rightarrow [X, X]$.

I will try to elaborate a bit more on the subject.

Let us assume that $\mathbb{C}$ is symmetric monoidal closed and has equalisers. Then any monoid $X$ internal to $\mathbb{C}$ admits embedding $y_{1_X} \colon 1_X \rightarrow \mathbb{C}^{1_X^{op}}$. The object of natural transformations

$$\mathit{nat}(\hom(-, 1), \hom(-, 1))$$ by definition is the equaliser of $l, r \colon [X, X] \rightarrow [X, [X, X]]$ in $\mathbb{C}$, where $l$ is the transposition of: $$\mu_\mathbb{C} \circ (\mathit{id}_{[X, X]} \otimes \nabla^*) \colon [X, X] \otimes X \rightarrow [X, X]$$ $r$ is the other transposition of: $$\mu_\mathbb{C} \circ (\nabla^* \otimes \mathit{id}_{[X, X]}) \colon X \otimes [X, X] \rightarrow [X, X]$$ $\nabla^* \colon X \rightarrow [X, X]$ is the transposition of the monoidal multiplication $X \otimes X \rightarrow X$, and $\mu_\mathbb{C} \colon [X, X] \otimes [X, X] \rightarrow [X, X]$ is the internalised composition from $\mathbb{C}$.

The enriched Yoneda lemma says that $$\mathit{nat}(\hom(-, 1), \hom(-, 1)) \approx \hom(1, 1) = X$$ Therefore the "arrows part" of $hom(-, 1)$ --- $e \colon X \rightarrow [X, X]$ is the equaliser of $l, r \colon [X, X] \rightarrow [X, [X, X]]$. Furthermore, because $hom(-, 1)$ is a functor, it maps the composition in $1_X^{op}$ to the composition in $\mathbb{C}$, turning $e$ into a functor between internal monoids $E \colon 1_X \rightarrow 1_{[X, X]}$.

The second construction is given by the application of the underlying functor $U$ to $E$:

$$U(E) \colon U(1_X) \rightarrow U(1_{[X, X]})$$

One may perhaps use the weak version of the Yoneda lemma to construct $U(E)$ in case $\mathbb{C}$ is not monoidal closed with equalisers. However, there is also a more natural solution.

Let us recall that if $\mathbb{C}$ is monoidal, then its category of presheaves $\mathbf{Set}^{\mathbb{C}^{op}}$ inherits the monoidal structure via the very special case of convolution:

$$F \otimes_\mathbb{C} G = \int^{B, C} F(B) \times G(C) \times \hom(-, B \otimes C)$$

Moreover, Brian Day showed that $\otimes_\mathbb{C}$ makes $\mathbf{Set}^{\mathbb{C}^{op}}$ a monoidal (bi)closed category, with the Yoneda embedding $y_\mathbb{C} \colon \mathbb{C} \rightarrow \mathbf{Set}^{\mathbb{C}^{op}}$ preserving the structure (i.e. not only does $y_\mathbb{C}$ preserve tensors, but any existing linear exponents). This means that $y_\mathbb{C}$ rises to the 2-functor $Y \colon \mathbb{C}$-$\mathbf{Cat} \rightarrow \mathbf{Set}^{\mathbb{C}^{op}}$-$\mathbf{Cat}$. By Yoneda, the underlying functor $U \colon \mathbb{C}$-$\mathbf{Cat} \rightarrow \mathbf{Cat}$ factors through $Y$ followed by the underlying functor $V$ of $\mathbf{Set}^{\mathbb{C}^{op}}$-$\mathbf{Cat}$.

Since the Yoneda functor $y_\mathbb{C}$ also preserves equalisers, every monoid $X$ in $\mathbb{C}$ has a representation as a submonoid of $y_\mathbb{C}(X)^{y_\mathbb{C}(X)}$ in $\mathbf{Set}^{\mathbb{C}^{op}}$, and $X$ is a submonoid of $[X, X] \in \mathbb{C}$ iff the linear exponent $[X, X]$ exists in $\mathbb{C}$. "The second construction" is:

$$V(E) \colon U(1_X) = V(1_{y_\mathbb{C}(X)}) \rightarrow V(1_{[y_\mathbb{C}(X), y_\mathbb{C}(X)]})$$

Maintaining a search-optimal tree

2012-06-09T20:05:32Z

Here is a completely new reformulation of almost the same problem. I hope it is more attractive to mathematicians.

[new version]

A binary tree is either:

a leaf, denoted by $\mathit{Leaf}$, or
an internal node consisting of a pair $(L, R)$, where both $L$ and $R$ are binary trees; we shall call $L$ the left child of the node, and $R$ the right child of the node.

We say that a binary tree is optimal if the difference between its longest and shortest path (starting from the root to a leaf) is at most one. Where by a path of a tree $T$ we mean a sequence $\langle T = T_0, T_1, \dots, T_k = \mathit{Leaf} \rangle$, such that $T_{i+1}$ is either the left or right child of $T_i$.

Our game is parameterized by two natural numbers $N$ and $K$; its initial configuration is a pair $\langle N, \mathit{Leaf} \rangle$. The game consists of $2^K-1$ rounds. At each round:

player A chooses a leaf from the tree and substitutes it with “the singleton internal node” $(\mathit{Leaf}, \mathit{Leaf})$, then
player B chooses any node (either internal or a leaf) and substitutes it with any tree having the same number $M$ of leaves as the tree rooted at the chosen node; the number $N$ is substituted with $N – M + 1$.

If at the end of any round the tree is not optimal, or the number $N$ from the configuration is negative, player A wins. Otherwise, after $2^K-1$ rounds, player B wins.

Question: given $K$, for which $N$ does player $B$ have a wining strategy?

[new version]

The following question I asked on my very first course in Algorithms, just when I had started my studies. I am not interested in discrete mathematics that much anymore, but would be very delighted for any approximation of the answer (I have never got any).

[edit]A binary tree over alphabet $\Sigma$ is either:

a leaf, or
an internal node consisting of a triple $\langle L, \sigma, R\rangle$, where $\sigma \in \Sigma$ and both $L$ and $R$ are binary trees over $\Sigma$; we shall call $L$ the left subtree of the node, $R$ the right subtree of the node, and $\sigma$ an element of the node.

That is --- a binary tree over $\Sigma$ is an element of the free algebra over $X \mapsto 1 \sqcup X \times \Sigma \times X$. A binary search tree, is a binary tree over a linear order $\Sigma$, where for each node $\langle L, \sigma, R\rangle$ we have that $\sigma$ is no less than any element from its left subtree, and less than any element from its right subtree.[edit]

A binary search tree is search-optimal if the difference between its longest and shortest path (starting from the root to a leaf) is at most one.

[edit] This condition is much stronger than being an AVL tree. The height of a tree is the longest path from its root to one of its leaf. We say that a tree is AVL if at any node the difference between the heights of its left and right subtrees is at most one. For example Fibonacci trees are AVL, but may have arbitrary large difference between their longest and shortest path. [edit]

A binary search tree is perfect if at any node the difference between the numbers of internal nodes in its left and right subtrees is at most one.

Our task will be to maintain search-optimal tree during consecutive insertions. We shall use maintenance strategies based on the concept of “partial rebuilding” --- that is whenever after insertion the tree is out of search-optimal shape, we choose one of its node, and rebuild the whole subtree rooted at that node to the perfect tree (the cost of this operation is equal to the number of nodes in the subtree).

What strategy has the best worst-case complexity, and what is its complexity?

[edit] A more mathematical version of the question. Suppose that we start from the empty tree and have to maintain it during $2^k-1$ insertions. The cost of rebuilding a subtree having $n$ nodes is $n$ euros. What strategy guarantees that we spend the smallest amount of euros in the worst-case? [edit]

Notice that rebuilding a tree at the lowest possible node is not optimal --- for example in the following situation it is much better to rebuild the whole tree than its right subtree ([edit from the comment] the picture shows only internal nodes [edit]):

Answer by Michal R. Przybylek for Moore-Penrose Inverse as an adjoint

2012-06-09T14:17:03Z

I do not think the concept of Moore-Penrose Inverse and the concept of categorical adjunction have much in common (except they both try to generalise the concept of inverse):

Equations $g = gfg$ and $fgf$ do not reaseble triangle equalities. Let me focus on the first equation. The "corresponding" triangle equality says that the composition $g \to^{\eta_g} gfg \to^{g\epsilon}g$ is the identity on $g$. Obviously $\eta_g$ is an inclusion, but generally there are no reasons for $\eta_g$ to be an isomorphism. However, in the world of 2-posets (i.e. categories enriched over posets) there is a reason. If we have a pair of 2-morphisms $\mathit{id} \le gf$ and $fg \le \mathit{id}$, then we may compose the first one on the right and the second on the left with $g$, obtaining $g \le gfg$ and $gfg \le g$, therefore $g = gfg$. Notice that I have not used any triangle equality here (just the existence of an appropriate pair of 2-morphisms).
The concept of an adjunction is inherently asymmetric --- a left adjoint is the best approximation of the identity from the left, and the right adjoint is the best approximation of the identity from the right; whilst the concept of Moore-Penrose pseudoinverse is perfectly symmetric. This means that if we had a 2-category, buit upon the category of vector spaces, where every pseudoinverse was a part of an adjunction (satisfying, perhaps, some other conditions), then every morphism would have both left and right adjoint, furthermore these adjoint functors would be isomorphic to the pseudoinverse (so isomorphic to each other). For a morphism $f$ in a 2-poset being both a left and right adjoint to $g$ is just being the inverse of $g$ --- the unit and counit from one adjunction give inequalities $\mathit{id} \le gf$ and $fg \le \mathit{id}$, whereas the unit and counit of the other adjunction give inequalities $\mathit{id} \le fg$ and $gf \le \mathit{id}$, hence $\mathit{id} = gf$ and $\mathit{id} = fg$. This fully answers your precise question, since in the category of vector spaces not every pesudoinverse is an inverse.
In any 2-category adjunctions compose --- if $f \colon A \to B \dashv f^+ \colon B \to A$ and $g \colon B \to C \dashv g^+ \colon C \to B$ then $g f \colon A \to C \dashv f^+ g^+ \colon C \to A$, but Moore-Penrose pseudoinverses --- generally --- do not. This almost answers your main question, because if $f \colon A \to B$, $g \colon B \to C$ are any maps between vector spaces then from the above property: $(gf)^+ \approx f^+ g^+$, so from this point of view pseudoinverses are not stable under isomorphisms, thus are not categorical.

Weighted limits and completeness

2012-05-22T09:41:11Z

Every weighted limit can be constructed from conical limits and cotensors. However, yesterday, a friend of mine, asked a question that may be rephrased as follows.

What is the reason that in the world of $\mathbf{Set}$-enriched categories every weighted limit can be constructed from conical limits (and trivial cotensors with $1$), and in the world of $\mathbf{Cat}$-enriched categories every weighted limit can be constructed from conical limits and cotensors with $2$?

Is it directly related to the fact that every set can be built upon $1$ and every category can be built upon $2$?

Is it possible to generalise these results to arbitrary (sufficiently well-behaved) monoidal category? For example, let us say that a symmetric monoidal closed category $\mathbb{V}$ is cocomplete and there exists a set $F$ of objects from $\mathbb{V}$ such that every object in $\mathbb{V}$ is a colimit of some objects from $F$. Is it true that every $\mathbb{V}$-weighted limit can be expressed via conical limits and cotensors with objects from $F$?

Answer by Michal R. Przybylek for A programming language that can only create algorithms with polynomial runtime?

2012-02-04T13:27:46Z

Perhaps the most natural examples come from various extensions to SQL (of course, if query languages count). For example Datalog on ordered relations equals P. Generally, such languages are somewhere around P, but for most of them it is really hard to give exact characterisations.

Answer by Michal R. Przybylek for Completeness vs Compactness in logic

2011-06-25T20:43:27Z

I was to say that the answers given so far are all wrong and misleading, but thanksfully I recalled that I am not a mathematician :-)

There are mainly two approaches to the concept of "logic".

The classical (or mathematical) approach to logic. Roughly speaking, a logic consists of two classes: a set of formulae and a class of models, together with a satisfiability relation saying what formulae are true in what models. Then, we may develop a proof system (or various proof systems) for the logic, which helps us --- in a systematic and coherent way --- derive satisfiability of formulae. Desirable properties of such proof systems are soundness (what we have derived is true), completness (what is true, we can derive). There is also compactness (if something follows a theory then it follows from a finite subset of the theory) that refers to the logic itself (here: satisfiability relation). This is how mathematicians are taught logic.
Modern (or computer-scientistic) approach to logic. Logic is a kind of a formal system (deductive system). To help proving facts about such a system, we may introduce the concept of "models" (or various concepts of models) for the logic. Desirable properties of such classes of models are that the deductive system over them is sound and complete (that is --- for a given system --- we develop the appropriate concept of models, such that the proof system is sound and complete; if we add/remove some axioms/rules to the system then we have to restrict/extend our class of models; this is most easily seen in temporal logics --- for example, LTL is sound and complete in linear models). There is also compactness (if something follows a theory then it follows from a finite subset of the theory) that refers to the logic itself (here: proof system; if a logic allows only finitary proofs, then it is obviously compact). Simply, in this approach, the system is fundamental here. This is how computer scientists are taught logic.

Of course, in the presence of soundness and completeness, classical compactness and modern compactness coincide.

So, moving back to your question --- I do agree with other answers saying that completeness and compactness are just far different concepts, so neither is "deeper". However, I do not think that the classification of wht belongs to models and what belongs to proofs is that obvious --- it is just all about how you think of logic.

Answer by Michal R. Przybylek for Natural transformations as categorical homotopies

2011-05-09T17:00:56Z

What is "more natural" is strictly determined by a mathematical background one has (or more seriously --- by one’s understanding of the world) when one comes to learn a new subject. Thus, a good definition should be more about "simplicity" (with respect to its theory) than about "analogy" to other concepts (in other braches of math). Analogies are then established by theorems.

I am not a mathematician, so I have a sweet opportunity to be ignorant on some fundamental branches of math --- for example --- topology. I think of functors $\mathbb{C} \rightarrow \mathbb{D}$ as of structures in $\mathbb{D}$ of the shape of $\mathbb{C}$. Then a transformation is something that morphs one structure into another (i.e. it is a collection of morphisms indexed by the shape of a structure), whereas natural transformation is something that morphs in a coherent way.

I really like a story on "Blind men and an elephant" link text that I first red in Peter Johnstone's book "Sketches of an Elephant". He compares a topos to the elephant, and we are the blind men. Surely, we are blind men, but I do think that most concepts found in category theory (with perhaps category theory itself) are like elephants.

Answer by Michal R. Przybylek for The sets in mathematical logic

2011-04-24T14:43:34Z

You cannot get anything out of nothing :-) But do not worry.

Mathematics existed long before ZFC was formulated, and well before “formal reasoning” rose to a kind of religion. Mathematically, there is nothing more formal in a “formal reasoning” than in any other “logically justified” (i.e. commonly accepted) reasoning. The true reason of encoding math in a single theory is to gather all doubts in a single place, earn confidence that our new theory is consistent (as long as the foundations are consistent), and help communicating with other mathematicians.

Moving back to your question. Let me distinguish between four cases – according to your terminology - a theory can be:

naïve and formal – this means that by using formal reasoning we may show that there is an inconsistency in the theory (for example: ZFC with unrestricted comprehension)
naïve and informal – this means that we see that there is an inconsistency in reasoning within the theory, but a proof of this fact is outside our math (the same example)
non-naïve and formal – this means that we believe that the theory is consistent, and (sometimes) can “formally” prove its consistency relatively to another (formal or informal) commonly accepted theory
non-naïve and informal – just like above with the last part of the sentence skipped.

So, as you may see, being formal cannot make a theory consistent/inconsistent, but can provide additional arguments for/against the theory – simply – correctness is invariant under changes of formality. For most situations the picture of formality looks like follows:

there is an informal concept like “first-order logic”
there is a formal theory of sets expressible in first-order logic

If we would like to investigate foundations themselves than we could extend the picture by introducing one (or more) additional level:

there is an informal theory of sets (meta-theory; it has to be a bit stronger than the "inner" set theory to show that the "inner" set theory is consistent, but it may be far weaker to express the "inner" theory)
there is a formal first-order logic expressible in the meta-theory
there is a formal theory of sets expressible in first-order logic

Completion of a category

2011-03-23T11:54:32Z

For a poset $P$ there exists an embedding $y$ into a complete and cocomplet poset $\hat{P}$ of downward closed subsets of $P$. It is easy to verify that the embedding preserves all existing limits and no non-trivial colimits --- i.e. colimits are freely generated. $\hat{P}$ may be equally described as the poset of all monotonic functions from $P^{op}$ to $2$, where $2$ is the two-valued boolean algebra. Then we see, that $P$ is nothing more than a $2$-enriched category, $2^{P^{op}}$ the $2$-enriched category of presheaves over $P$ and that $y$ is just the Yoneda functor for $2$-enriched categories.

However, for a poset $P$ there is also a completion that preserves both limits and colimits --- namely --- Dedekind-MacNeille completion link text, embedding $P$ into the poset of up-down-subsets of $P$.

Is it possible to carry the later construction to the categorical setting and reach something like a limit and colimit preserving embedding for any category $\mathbb{C}$ into a complete and cocomplete category?

Adjunction between classic and intuitionistic logic

2011-03-16T20:12:56Z

Let $\Sigma$ be a (classic, single-sorted) signature. Denote by $\mathit{Mod}_H(\Sigma)$ the category of $H$-valued models over $\Sigma$, where $H$ is a complete Heyting algebra. Then for any first-order sentence $\phi$ over $\Sigma$ and any model $M \in \mathit{Mod}_H(\Sigma)$ the satisfaction relation $M \models \phi$ in defined in the obvious way (i.e. the semantics of $\phi$ in $M$ is the top element of $H$). Denote by $\mathit{Log}_H(\Sigma)$ the category of first-order sentences over $\Sigma$, and "proofs" induced by the relation $\models$, that is: $\phi \rightarrow \psi \Leftrightarrow \forall_M M \models \phi \Rightarrow M \models \psi$. We shall call such a triple $\langle\mathit{Mod}_H(\Sigma), \models, \mathit{Log}_H(\Sigma)\rangle$ a logical system.
A morphism from a logical system $\langle\mathit{Mod}_H(\Sigma), \models, \mathit{Log}_H(\Sigma)\rangle$ to a logical system $\langle \mathit{Mod}_K(\Sigma), \models, \mathit{Log}_K(\Sigma)\rangle$ consists of a pair of functors $F_\mathit{mod} \colon \mathit{Mod}_K(\Sigma) \rightarrow \mathit{Mod}_H(\Sigma)$ and $F_\mathit{log} \colon \mathit{Log}_H(\Sigma) \rightarrow \mathit{Log}_K(\Sigma)$ (note opposite directions) compatible with the satisfiability relation: $M \models F_\mathit{log}(\phi) \Leftrightarrow F_\mathit{mod}(M) \models \phi$.
A morphism transformation $\alpha \colon F \rightarrow G$ consists of a pair of natural transformations $\langle \alpha_\mathit{mod} \colon F_\mathit{mod} \rightarrow G_\mathit{mod}, \alpha_\mathit{log} \colon F_\mathit{log} \rightarrow G_\mathit{log}\rangle$.

Is there any interesting adjunction between $\langle\mathit{Mod}_H(\Sigma), \models, \mathit{Log}_H(\Sigma)\rangle$ and $\langle\mathit{Mod}_2(\Sigma), \models, \mathit{Log}_2(\Sigma)\rangle$, where $2$ is the two-valued boolean algebra? Note that the Kolmogorov transformation does not work here.

Appendix
The truth is that $\mathit{Mod}_H(-)$ are fibred and $\mathit{Log}_H(-)$ are op-fibred over the category of signatures. Such entities (i.e. a fibration, an opfibration and a collection of satisfaction relations) are called "institutions". What I am really looking for is an interesting adjunction between such institutions. But this (modulo the Beck-Chevalley condition, what, I guess, is not an issue here) reduces to the above case.

Answer by Michal R. Przybylek for Your favorite surprising connections in Mathematics

2011-03-13T17:28:14Z

The Curry-Howard isomorphism linking various lambda calculi with intuitionistic logics; its extension to the classic logic via the concept of continuations.
The conncetion between Borel hierarchy and arithmetical hierarchy.
Fagin's theorem --- and later the whole branch of descriptive complexity --- linking well-known complexity classes with logics over finite models.

Answer by Michal R. Przybylek for Appropiate models of numerical computation

2011-03-10T11:30:16Z

There are mainly three approaches to deal with computational complexity of continuous problems.
1. Information Based Complexity (analytical complexity). It is a very general framework that describes the complexity of a problem in terms of the number of 'operations' (specified by the problem itself) needed to solve it on condition that we are given only rough information about the initial problem. This theory is mostly about the 'real' complexity --- which is independent of any particular model of computation --- it gives lower bounds on all possible models. See 'Information-Based Complexity' by Traub, Wasilowski and Woźniakowski for more details.
2. Blum–Shub–Smale machine and that like (algebraic complexity). The idea comes from the good old days when people believed that it was possible to build analog computers that are more powerful than turing machines. I was to say that the idea of stroing infinite information in a single cell, and comparing two such cells in a finite time is a bit crazy from both practical and theoretical point of view, but I guess it is prudent to refrain from making such comments. These models are inconsistent with physical laws, so it should not be strange that they allow some 'dirty hacks' (for example there are uncomputable problems easily solvable on Blum–Shub–Smale machine; under some definitions, one may show that both $P/Poly$ and $NP$ are solvable in polynomial time).
3. Turing machines (discrete complexity). If you really want to solve a problem on a computer, then you really have to transform it into a discrete one (either symbolic or numeric). But then, there is nothing left but the classic complexity :-)

David, I do agree with your reasoning, and (so) with your conclusion. However, notice that it is always easy to falsify statements such as my remarks. Simply, the reality is so complex, that in every such proclamation there must be much more things that we have to ignore, than we are able to take into consideration. The crucial point here is that BSS allows us to perform dirty tricks and reach something paradoxical, which otherwise we would have not accepted; and that the extra power does not give us anything besides these paradoxes. Every algorithm for BSS either: has its counterpart in the standard model, or is ‘unrealizable’ (we may have an infinite precision, and infinite memory, but when we cut these infinities at any stage, we get a Turing machine). Put it differently, according to our current knowledge every ‘sensible’ ‘realization’ of a BSS has to factor through a Turing machine.

Answer by Michal R. Przybylek for Strassen Algorithm 7 multiplications

2011-03-07T21:39:06Z

I am not an expert in this field, but can hardly recall that:
- Strassen algorithm is optimal for divisions on 4 submatrices
- there are algorithms using a much larger number of submatrices and behaving slightly better.
If you are really interested in these results I can search for references, but be aware that the algorithms are of a very little practical use --- they just have big constant factors (and it is not the usual case that we are given a large dense matrix), and are not that robust (in the sense of numerical stability).

Answer by Michal R. Przybylek for "P vs NP" and "NP vs P/Poly"

2011-03-07T18:55:02Z

No, it is unknown whether $P \neq NP \Rightarrow NP \not\subset P/Poly$. However, one may show that if $NP \subset P/Poly$ then the polynomial hierarchy collapses on the second level, what is rather unlikely.

Comment by Michal R. Przybylek

2013-05-15T09:07:19Z

@Joel, +1, that's a good comment and a very interesting answer!

Comment by Michal R. Przybylek

2013-05-15T09:05:19Z

@Asaf, because you've asked an imprecise question, you get posts answering different issues of the concept of "universe". Perhaps the only answer to the question "is it sufficient..." (and take it really serious) is: "it is sufficient to define a category as number 22; it is also sufficient to define a category as number 2 --- if one does not believe in existence of such large natural numbers as 22".

Comment by Michal R. Przybylek

2013-05-15T08:45:54Z

@Andrej, a joke of a joke is a no-joke.

Comment by Michal R. Przybylek

2013-05-14T23:20:34Z

@Andrej, I've spent almost half an hour trying to prove that your sequence of nested jokes converges to a whole joke, and still can't figure out how this could be true. Are you sure that your sentence is really a joke? :-)

Comment by Michal R. Przybylek

2013-05-14T23:11:55Z

@Dan thanks for pointing this out. I've been never able to grasp the logic of voting on MO - it is definitely not as simple as one could expect: vote up if something is useful (for you), vote down if something is painful (for you). I've even read somewhere, that a lot of people use some non-commutative voting systems - where up/down-votes depend on the actual score of a post. This means that if you really want to reward a poster with points, you should actually downvote his post as soon as possible or wait with the upvote as long as you can -perhaps to the very last moment before your death :)

Comment by Michal R. Przybylek

2013-05-14T08:33:17Z

@Peter, thank you for your comment. However, the question has more upvotes than the answer --- so I may infer that not everyone is satisfied with the provided answer. I think it will be prudent to refrain from accepting it.

Comment by Michal R. Przybylek

2013-05-08T10:30:19Z

@Carnahan, ok. Now, should I accept my own answer, or leave the question open?

Comment by Michal R. Przybylek

2013-05-07T20:28:12Z

I am not sure if answering my own question is a good habit --- if it is not, I will remove the answer.

Comment by Michal R. Przybylek

2013-04-22T21:31:25Z

I am not sure if I understand your questions. However, "distributorial" composition is generally far different from composition via pullbacks.

Comment by Michal R. Przybylek

2013-04-22T20:26:50Z

@Vidit, $\int^A$ denotes coend, and $\int_A$ denotes end.

Comment by Michal R. Przybylek

2013-04-22T14:43:52Z

@Zhen, thank you --- $\textbf{FinSet}$ is a very good example to see why the external cocompleteness is not necessary here (since $\textbf{FinSet}$-internal categories are finite, the coend in the Day convolution may be expressed via finite colimits).

Comment by Michal R. Przybylek

2013-04-22T14:31:58Z

@Alex, you are right that for some of these constructions we have to assume that $\mathbb{C}$ has finite colimits (coequalisers suffice) --- thank you, I will update the question.

Comment by Michal R. Przybylek

2013-04-22T11:08:31Z

$$\int_C \hom(\int^A(\hom(J(A),C)\times F(A), \int_B F(B)^{\hom(C, J(B))})$$ the preservation of ends and coend: $$\int_{A,B,C} \hom(\hom(J(A),C)\times F(A), F(B)^{\hom(C, J(B))})$$ by currying and preservation of ends: $$\int_{A,B} \hom(F(A)\times\int^C \hom(J(A),C) \times \hom(C, J(B)) , F(B))$$ by Yoneda: $$\int_{A,B} \hom(F(A)\times \hom(J(A), J(B)), F(B))$$ by preservation of ends and fully-faithfulness of $J$: $$\int_{B} \hom(F(B), F(B))$$

Comment by Michal R. Przybylek

2013-04-22T11:08:15Z

In your first and second paragraph on "Two Extensions" $LK$ and $RK$ should probably be $LF$ and $RF$ respectively. Moreover, I do not see where you need the assumption that the category is thin (BTW, I do prefer term "degenerated"), a you can construct you $\eta$ by the following natural isomorphism (applied in the reversed order to the identity on $F$; $J\colon \mathcal{A} \rightarrow \mathcal{B}$ stays here for the inclusion): $$\hom(\int^A(\hom(J(A),-)\times F(A), \int_B F(B)^{\hom(-, J(B))})$$ by the definition of the object of natural trnasformations:

Comment by Michal R. Przybylek

2013-04-19T22:00:08Z

@David Roberts, let me know when you find any interesting examples! @David White, I have expanded the example of a 2-topos (now it is called 2-power) --- do hope it is more readable now.