6
$\begingroup$

Let $DF$ denote the category whose objects are categories and whose morphisms $F\colon R\to S$ are the discrete fibrations. This category has applications to the real-world problem of structuring data. You can think of any discrete fibration $R\to S$ as providing a schematic structure $S$ for more raw data $R$. This question is about finding a best such structure for given data.

For any category $R$, one can define the coslice category $$DF_{R/}$$ of discrete fibrations out of $R$. Given a discrete fibration $R\to S$, call $S$ the base space. I want to find a minimal base space $R^{min}$ for a given $R$. To get at that idea, I'll ask for some kind of universal object.

I once asked on the categories mailing list whether $DF_{R/}$ has a terminal object in general. As was explained to me by Mark Weber and Thorston Palm, it does not. Basically, if $R=\emptyset$ then we're asking for a terminal object in $DF$, and by cardinality arguments, this does not exist.

But in fact I was asking the wrong question. If I want minimal models, I actually want my discrete fibrations to be surjective. The counter-examples provided to me by Weber and Palm fail to cause a problem in that context. So here's the question.

Question: Define $DFS$ to be the subcategory of $DF$ in which the morphisms are discrete fibrations $F\colon R\to S$, required to be surjective on objects. Then does $DFS_{R/}$ have a terminal object $R^{min}$ for a given category $R$?


Edit provenance: An earlier version of this question got very little attention, so I've edited it to explain an intended application and to clarify the question a bit. The latter edit involved replacing "discrete opfibration" (and notation $DopF$, $DopFS$) with "discrete fibration" (and notation $DF$, $DFS$) throughout, because it looked cleaner.

$\endgroup$
4
  • $\begingroup$ In your last sentence I guess you mean $DopFS_{/C}$. Also, the notation is wrong: $S_{/C}$ means the slice category of $S$ over $C$, so I think you want $S_{C/}$, or $C/S$ (the slice category under $C$). $\endgroup$
    – David Roberts
    Commented Feb 14, 2014 at 3:58
  • $\begingroup$ Suppose that $C$ is a monoid, viewed as a one-object category. A discrete opfibration $F : C \to D$ over another one-object category $D$ corresponds to an injective homomorphism, and so there is an initial such one corresponding to the identity functor $C \to C$. What do you have in mind for the terminal discrete opfibration from $C$? $\endgroup$ Commented Feb 14, 2014 at 12:32
  • $\begingroup$ @David Roberts, thanks for mentioning the typos -- corrected. $\endgroup$ Commented Feb 15, 2014 at 15:57
  • $\begingroup$ @NoamZeilberger. Suppose $C$ is a monoid and $F:C\to D$ is a discrete opfibration that's surjective on objects. Then $D$ is a monoid. But a discrete opfibration between monoids is always an isomorphism. So the identity $C\to C$ is terminal in $DopFS_{C/}$. $\endgroup$ Commented Feb 15, 2014 at 16:02

1 Answer 1

3
$\begingroup$

In general, the answer is "No": the category $DFS_{C/}$ of surjective discrete fibrations under $C$ need not have a terminal object. This is due to the following:

Lemma. Let $C$ be the codiscrete category with $n$ objects. For any group $G$ with $n$ elements, there is a surjective discrete fibration $C \to \mathsf{B}G$ (where $\mathsf{B}G$ is the delooping of $G$).

Proof. The regular action of $G$ on itself by right multiplication gives rise to a functor $\mathsf{B}G^{op} \to \mathsf{Set}$ whose category of elements is isomorphic to $C$. $\square$

When $n$ is composite, there are at least two non-isomorphic groups $G \not\cong H$ with $n$ elements, and these will give rise to non-isomorphic discrete fibrations $p \colon C \to \mathsf{B} G$ and $q \colon C \to \mathsf{B} H$. Further, any maps out of $p$ and $q$ in $DFS_{C/}$ will necessarily be isomorphisms (as noted by David's reply to Noam). So if there were a terminal discrete fibration $t \colon C \to S$, we must have $\mathsf{B}G \cong S \cong \mathsf{B}H$, which contradicts our assumption that $G \not\cong H$.

But $p$ and $q$ above are minimal in some sense: all maps out of them are isomorphisms. So while $DFS_{C/}$ has no terminal objects, it does have multiple minimal ones. (Still, any attempt to classify minimal objects in $DFS_{C/}$ for all (finite) categories $C$ must include the classification of all (finite) groups!)

However, if we are willing to restrict the categories $C$ that we want to consider, then we have:

Theorem. Let $C$ be such that for all $x \in C$, the slice $C/x$ has no non-trivial automorphisms. Then $DFS_{C/}$ has a terminal object.

I've written the proof in this draft. The idea is to construct a category $S$ with one object for each isomorphism class $[C/x]$ of slice categories in $C$, and then show that we have a discrete fibration $C \to S$.

$\endgroup$
1
  • $\begingroup$ This is great; thanks! Here's another one, that's also relevant to database theory (when one might have missing data). Discrete fibrations into C correspond to functors C^{op}->Set. What if we consider functors C^{op}->Par, the category of sets and partial functions; these correspond to functors F: X->C such that for each x2:X and g:c1->F(x2) in C, there is at most one map f: x1->x2 in X with F(f)=g. Let's call such F's "discrete quasi-fibrations". Question: In what cases is there a terminal discrete quasi-fibration out of X? $\endgroup$ Commented Oct 19, 2019 at 0:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .