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: deprecated: logic

Topic: Tukey category

Brian Pinsky (Apr 23 2020 at 20:48):

I've encountered the following category in a set theory context. It is too nice not to be a special case of a nicer, more general picture, but I don't know what that picture is. I was hoping someone here might be able to help.

THE TUKEY CATEGORY:
Objects are triples $\mathbf{A} = (A_-, A_+, A)$, where $A_-$ and $A_+$ are sets, and $A\subseteq A_-\times A_+$ is a relation from $A_-$ to $A_+$.
A morphism from $\mathbf{A} = (A_-, A_+, A)$ to $\mathbf{B} = (B_-, B_+, B)$ is a pair $(\varphi_-, \varphi_+)$ where $\varphi_-\colon A_-\to B_-$ and $\varphi_+ \colon B_+\to A_+$ are "adjoint functions", i.e. $\forall a\in A_- \forall b\in B_+\ \varphi_- (a) B b \iff a A \varphi_+(b)$
This category comes with a nice endofunctor $-^{op}$ sending $(A_-, A_+, A)$ to $(A_+,A_-,\neg A^{op})$

WHY SET THEORISTS CARE (i.e. motivating examples. You can skip this section):
For an object $\mathbf{A}$ in this category, we can associate cardinals $\mathfrak{d}(\mathbf{A})$ and $\mathfrak{b}(\mathbf{A})$. These are the minimal size of a dominating family in $A_+$ or an unbounded family in $A_-$, respectively.
More formally, we say a family $F\subseteq A_+$ is dominating if $\forall a\in A_- \exists b\in F\ aAb$, and similarly a subset $G\subseteq A_-$ is unbounded if $\forall b\in A_+ \exists a\in G\ \neg aAb$ (this is equivalent to being a dominating family in $\mathbf{A}^{op}$
Many interesting cardinals between $\aleph_0$ and $2^{\aleph_0}$ can be defined in this framework; for instance, the bounding number $\mathfrak{b}=\mathfrak{b}(\omega^\omega, \omega^\omega, \leq^*)$ (\mathfrak{b} is the smallest set of sequences of naturals which no sequence that is eventually bigger than all of them. A diagonal argument shows this is uncountable)
You can show that if $\exists \varphi \colon \mathbf{A}\to\mathbf{B}$, then $\mathfrak{d}(\mathbf{A})\leq \mathfrak{d}(\mathbf{B})$. So, giving explicit morphisms in this category is a nice way to show cardinal inequalities. It also nicely explains some dualities we observe.

WHAT I WANT TO KNOW:
How is this related to the category of categories with adjoint functor pairs as morphisms? I'm sure that category has been studied, but I don't know much about it (not even a name to know what to google).
Is there a nice 2-category structure here? I don't obviously see one, but I'm not especially practiced.
If this reminds you of anything else, I'm sure I'd like to hear that too.

OBLIGATORY CITATION:
here's a citation. It contains nothing relevant that I haven't already said, but it's where I got the name "Tukey" from.

Dan Doel (Apr 23 2020 at 20:51):

This seems like it's related to the Chu construction.

sarahzrf (Apr 23 2020 at 20:55):

turkey category

Dan Doel (Apr 23 2020 at 20:55):

E.G. is your category the same as $\mathsf{Chu}(\mathsf{Set},2)$ I think?

sarahzrf (Apr 23 2020 at 20:55):

yeah im pretty sure this—what dan said

Dan Doel (Apr 23 2020 at 20:56):

There's a whole website about Chu spaces, too.

sarahzrf (Apr 23 2020 at 20:57):

i worked out Chu(Cat, Set) yesterday and this is basically the (0, 0) version of that :)

zigzag (Apr 23 2020 at 23:48):

It reminds me of http://vcvpaiva.github.io/includes/pubs/2017-samuel-card.pdf (Chu/Dialectica constructions are not too far from each other iirc; the main difference is that you impose only the forward implication of your adjointness condition)

Mike Shulman (Apr 24 2020 at 02:58):

Wow, set theorists have independently invented Chu spaces? That's pretty cool. Do you have a reference that actually defines this category? I couldn't find the word "category" used in the category-theorist's sense at your supplied link.

Reid Barton (Apr 24 2020 at 03:20):

Well, Definition 2.4 defines the morphisms and I guess there are not many possibilities for the identity/compositions.

Mike Shulman (Apr 24 2020 at 03:32):

Hmm, usually I read "whenever" as meaning "if", not "if and only if". Is that what's meant here? If so then it really is a Dialectica category rather than a Chu category.

Mike Shulman (Apr 24 2020 at 03:35):

@Brian Pinsky 's original post in this thread said $\Leftrightarrow$ rather than $\Rightarrow$, so his category is the Chu construction. But the self-duality he mentioned is the Dialectica one, not the Chu one, since it involves a $\neg$.

Valeria de Paiva (Apr 24 2020 at 13:38):

Mike Shulman said:

Wow, set theorists have independently invented Chu spaces? That's pretty cool. Do you have a reference that actually defines this category? I couldn't find the word "category" used in the category-theorist's sense at your supplied link.

well, yes. it's in Blass paper "Questions and Answers" https://arxiv.org/abs/math/9309208 and in Justin Moore, Michael Hruˇs´ak, and Mirna Dˇzamonja. Parametrized :diamonds: principles. Trans. Amer.
Math. Soc, 356, no 6:2281–2306, 2004

Brian Pinsky (Apr 24 2020 at 15:03):

@Mike Shulman zigzag's post before yours links an article defining this category. Chasing their references, it appears the this category arising in two places was first pointed out by blass here. In retrospect, I should have known blass would have written about this (there's only so many categorically inclined set theorists out there, and having seen the chu construction, the connection is pretty obvious).

Brian Pinsky (Apr 24 2020 at 15:16):

Dan Doel said:

E.G. is your category the same as $\mathsf{Chu}(\mathsf{Set},2)$ I think?

It's the same as a category, but I have an extra negation in the $-^{op}$ functor (which is necessary to get $\mathfrak{b}$ and $\mathfrak{d}$ to be dual to each other) (as @Mike Shulman pointed out), so it's not exactly the same. Perhaps this suggests a slight generalization of Chu categories, where you allow an extra involution in the dualizing functor, would be of interest elsewhere.

Thanks everyone for the responses. It seems "Chu cateogry" (and the related Dialectica one) were exactly the things I needed to google, and your links seem to answer more or less every question I had (although I haven't finished reading them all yet; perhaps I'll have more questions after that).

Mike Shulman (Apr 24 2020 at 17:27):

@Brian Pinsky And you're sure that you want $\Leftrightarrow$, rather than $\Rightarrow$ as in your citation?

Mike Shulman (Apr 24 2020 at 17:29):

I think one way to see the extra $\neg$ categorically is that the Chu construction is functorial on (lex closed symmetric monoidal) categories equipped with an object. So any automorphism $d\cong d$ induces an automorphism of $\mathrm{Chu}(C,d)$. When $d=2$ you can take negation as the automorphism, and then combine the resulting automorphism of Chu(Set,2) with its standard $\ast$-autonomous involution to obtain your involution. I wonder whether it is also $\ast$-autonomous with this modified involution, and whether Chu-theorists have studied it?

Brian Pinsky (Apr 24 2020 at 18:23):

Mike Shulman said:

Brian Pinsky And you're sure that you want $\Leftrightarrow$, rather than $\Rightarrow$ as in your citation?

Oh I see the confusion; I appear to have misread my source. He did mean just $\Rightarrow$; that is sufficient for all of the applications he has in mind (and the reverse implication fails in most of the examples).
So I guess I didn't mean $\Leftrightarrow$.

Mike Shulman (Apr 24 2020 at 19:22):

Ah, in that case you really do have a Dialectica category with its standard involution, rather than a Chu category with a nonstandard involution.

Valeria de Paiva (Apr 24 2020 at 20:03):

Mike Shulman said:

Ah, in that case you really do have a Dialectica category with its standard involution, rather than a Chu category with a nonstandard involution.

yep. actually the set-theoretical version also satisfies a non-triviality condition (which usual Dialectica does not, this says that neither A+ nor A- should be empty). we call it the MHD condition for Moore, Hrusak, and Dzamonja in Dialectica categories, cardinalities of the continuum and combinatorics of ideals

Valeria de Paiva (May 21 2020 at 21:38):

Brian Pinsky said:

Dan Doel said:

E.G. is your category the same as $\mathsf{Chu}(\mathsf{Set},2)$ I think?

It's the same as a category, but I have an extra negation in the $-^{op}$ functor (which is necessary to get $\mathfrak{b}$ and $\mathfrak{d}$ to be dual to each other) (as Mike Shulman pointed out), so it's not exactly the same. Perhaps this suggests a slight generalization of Chu categories, where you allow an extra involution in the dualizing functor, would be of interest elsewhere.

Thanks everyone for the responses. It seems "Chu cateogry" (and the related Dialectica one) were exactly the things I needed to google, and your links seem to answer more or less every question I had (although I haven't finished reading them all yet; perhaps I'll have more questions after that).

Well, I take offense at "this suggests a slight generalization of Chu categories" because as a model of LL Dialectica is a better model: to define "! "(the hard part of modelling LL) Lafont and Streicher needed the help of the dialectica models and say so in their paper Y. Lafont & T. Streicher, Games Semantics for Linear Logic, in Logic in Computer Science (LICS 91), p. 43-50, IEEE Computer Society Press (1991).