10
$\begingroup$

[Background: I asked a vague question the other day, but as a result of the answers, particularly Andrej Bauer's, I now have a precise question]

Summary of question: the inclusions are a particularly "good" class of morphisms in the category of sets. I've written down a bunch of properties they have, and reserve the right to write down more. Are there other classes of morphisms which share these properties?


Technical point. in ZFC if you define a function to be a collection of ordered pairs $(x,f(x))$ then two functions with different codomains can be equal as sets (and hence as functions). In this question, when I talk about a morphism $f:X\to Y$ in the category of sets, I mean the data of $f$ and $X$ and $Y$, as is normal in category theory. A function has a well-defined domain and codomain.


Set-up

I am looking for the following piece of data. For each set $X$ I want a set $P(X)$ of injections $f_i:A_i\to X$ in the category of sets, called the "good morphisms to $X$", with the following properties.

1) [representing injections]. For every injective map $g:Y\to X$ in the category of sets, there is a unique good $f:A\to X$ such that $g$ is isomorphic to $f$ in the sense that there's an isomorphism $Y\to A$ which makes the obvious triangle commute.

For conditions (2) and (3) we have injections $f:A\to B$ and $g:B\to C$ with composition $h:=g\circ f:A\to C$.

2) [closure] If $f:A\to B$ is good and $g:B\to C$ is good then $h := g\circ f:A\to C$ is good.

3) [g,h good implies f good] If $h:A\to C$ and $g:B\to C$ are both good, then $f$ is good too.


An example of a good class of maps is the set of all inclusions $i:A\to B$ where $A$ is a subset of $B$.

The question

The question (for which the answer is surely "yes of course") is: are there any other ways to choose a good class of maps with these properties?


I hesitate to put any more conditions, for example conditions about products of maps, because an object like $X\times Y$ is only defined up to unique isomorphism in the category of sets. This question is not at all "natural" in the category-theory sense, because if I replace my category by an equivalent category then I can't easily move my data from one to the other (as far as I can see). On the other hand, there are "canonical" (whatever that weasel word means!) constructions of products and limits in the category of sets, so I reserve the right to add more conditions about the behaviour of "nice" maps under limits if this question gets spiked too easily. In fact the more I think about it the more I wonder whether adding more criteria using these "canonical" constructions of limits (as an actual subset of a product, with the crucial observation being that subsets are being used) can actually turn this question into one with a positive answer, i.e. classifying the inclusions as those morphisms satisfying a bunch of properties, not all of them as "canonical" as one might like...

NB the word "canonical" does not have a definition in my mind, and mathematicians sometimes use it in a way where it can actually be replaced by a formal definition, but sometimes they use it to mean something which just looks like a good idea. I am trying to work out if inclusions are "canonical" monomorphisms, and this is a great example of a poor usage of the word in the sense that once you start digging you realise that you cannot supply a definition. I am attempting to supply a definition and still strongly suspect that I have failed.

$\endgroup$
  • 7
    $\begingroup$ @AsafKaragila I"m pretty sure "technically" is intended to mean "if you define a function as simply a suitable set of ordered pairs, without specifying a codomain". So all empty functions are technically equal. The OP wants a function to have a specified codomain, so $\varnothing$ has different functions into different sets. $\endgroup$ – Andreas Blass Dec 9 '18 at 12:58
  • 3
    $\begingroup$ Mike Shulman’s answer to your earlier question is very relevant here, pointing to the notions of M-categories and (directed) (structural) systems of inclusions in the literature. The latter are a specific axiomatisation the properties of inclusions, which I don’t recall completely off the top of my head but had at least a similar flavour to your axioms here. The former are a more general abstraction of the overall structure formed. So your question could be written as something like “Does Set carry other systems of inclusions?”, [cont’d] $\endgroup$ – Peter LeFanu Lumsdaine Dec 9 '18 at 14:57
  • 2
    $\begingroup$ and to make it a bit more non-trivial, one could add something like “…which are not equivalent, as M-categories, to the standard one”? (Since one can certainly produce systems that are not equal to the usual one, by transporting the usual one under an automorphism of Set that doesn’t respect it.) $\endgroup$ – Peter LeFanu Lumsdaine Dec 9 '18 at 15:01
  • 9
    $\begingroup$ Choose two sets $X$ and $Y$ and an isomorphism $e:X\cong Y$ that is not the identity. Define $F:{\rm Set}\to{\rm Set}$ by $F(X)=Y$, $F(Y)=X$, and $F(A)=A$ for all other sets $A$, and define the action of $F$ on arrows by composing with the chosen isomorphism $e$ whenever needed. Note that $F$ is an "automorphism" in the strict sense, i.e. a self-isomorphism (not equivalence), so any system of inclusions can be transported across it. But a subset inclusion $i:X'\hookrightarrow X$ is sent to an injection $e i : X' \to Y$ that is not an inclusion. $\endgroup$ – Mike Shulman Dec 9 '18 at 22:44
  • 3
    $\begingroup$ @AsafKaragila Which is similar to what Peter suggested as a way to nontrivialize the question: "... which are not equivalent, as M-categories, to the standard one'. $\endgroup$ – Mike Shulman Dec 10 '18 at 15:49
6
$\begingroup$

The consensus seems to be that this is an answer to the question as stated (though I didn't originally realize that it was), so I'll go ahead and post it as one.

There are other ways to choose such a class of "good maps". For instance, you can transfer any class of good maps (such as the "standard" one consisting of inclusions) across an isomorphism of categories ${\rm Set} \cong {\rm Set}$ (though not necesarily across an equivalence of categories). To produce a nontrivial isomorphism ${\rm Set} \cong {\rm Set}$, choose two sets $X$ and $Y$ and an isomorphism $e:X≅Y$ that is not the identity. Define $F:Set→Set$ by $F(X)=Y$, $F(Y)=X$, and $F(A)=A$ for all other sets $A$, and define the action of $F$ on arrows by composing with the chosen isomorphism $e$ whenever needed. Then $F$ is an isomorphism ${\rm Set} \cong {\rm Set}$, under which a subset inclusion $i:X′↪X$ (for $X' \neq X,Y$) is sent to an injection $ei:X′→Y$ that is not (usually) an inclusion. More generally, you can construct an automorphism of ${\rm Set}$ that essentially arbitrarily permutes each bijection-equivalence-class of sets.

A way to make the question more interesting, as suggested by Peter Lumsdaine and Asaf Karagila, is to ask whether there is a class of good maps that is not related to the inclusions by such an automorphism of ${\rm Set}$, or similarly that is not equivalent as an M-category to the standard M-category of sets, functions, and inclusions. I don't know the answer to this version of the question.

$\endgroup$
  • $\begingroup$ At the risk of reaching well beyond the limits of my knowledge, assuming a negative answer to the extended question, I'd imagine one possible way to solve this would be to somehow find a "richer structure" which one cannot access with "just functors", but can be described as some type theoretic construction starting from sets (so a functor is a 1st order, this counterexample would be a 2nd order, etc.) and then one could ask about eventual equivalence (which may or may not be somehow related to univalence, this is where I'm losing grip on terminology)... $\endgroup$ – Asaf Karagila Dec 10 '18 at 18:37
4
$\begingroup$

The example Mike Shulman gives in the comments answers the question. Here is another example illustrating that more complicated things can happen as well: even identity maps need not be good morphisms by the OP's definition. (This cannot happen in an $M$-category or a system of inclusions, where all identity maps have to be inclusions.)

If $X=\operatorname{Hom}(\{\emptyset\},X')$ for some $X'$, let the good morphisms to $X$ be the inclusions. For all other $X$ let the good morphisms to $X$ be $e\circ i$, where $i:Z\to\operatorname{Hom}(\{\emptyset\},X)$ is an inclusion and $e$ is evaluation at $\emptyset$.

As raised in Asaf Karagila's comment, this does come from an endofunctor of $\operatorname{Set}$, namely $F(X)=X$ if $X=\operatorname{Hom}(\{\emptyset\},X')$ and $F(X)=\operatorname{Hom}(\{\emptyset\},X)$ otherwise (and do the obvious thing to morphisms). One could do something similar for any idempotent endofunctor.

If one is allowed to mess with the construction of products/limits then one can arrange for this to respect these operations. If one insists on constructing them in a (the?) standard way, then I'm not sure.

Edit: Here is a formulation of the "is it always the same M-category" question which allows for cases like this one and the one in user44191's answer. To a notion of good morphisms associate the following data. There is a functor $F:\operatorname{Set}\to\operatorname{Set}$ with $F\circ F=F$, and there is an isomorphism $f_X:F(X)\to X$ for each $X$, such that $f_{F(X)}=\operatorname{id}_{F(X)}$ and the elements of $P(X)$ are all morphisms $f_X \circ i $ for some injections $i: Z\to F(X)$.

To get hold of these, let $g: A\to X$ be the good morphism corresponding to $\operatorname{id}_X$, take $F(X)=A$ and $ f_X= g$. Properties 2, 1 and then 3 applied to $f_X\circ f_{F(X)}$ give $F\circ F=F$ and $f_{F(X)}=\operatorname{id}_{F(X)}$.

Is there always an automorphism of $\operatorname{Set}$ making the maps $i$ into inclusions (in the ordinary sense)?

$\endgroup$
  • $\begingroup$ Let $F: \text{Set} \rightarrow \text{Set}$ be as in my answer, except that there are $3$ $1$-element sets (and $F$ takes each of those to itself). This should be a fine endofunctor, and the $f_X$ are obvious. This should lead to no possibility for such an automorphism, right? $\endgroup$ – user44191 Dec 11 '18 at 7:11
  • $\begingroup$ @user44191 actually there is no such automorphism even for your original example, since in that case all good maps from singletons have the same domain, so all maps $i$ from singletons have the same domain, so they can't all be inclusions. I will think about what I should have said. $\endgroup$ – Simon L Rydin Myerson Dec 11 '18 at 22:53
  • $\begingroup$ Why couldn't they all be inclusions? The $F(X)$ are all ordinals, so they include the singleton ordinal. The $i$ in my example are order-preserving maps between ordinals, if I've understood your answer correctly, and so are injections - meaning the identity automorphism works. $\endgroup$ – user44191 Dec 12 '18 at 0:09
  • $\begingroup$ Every injection from a singleton has to factor through a good map. So for each element of each ordinal there must be an $i$ having that element as its image. So the $i$ are injections, but can't all be inclusions. $\endgroup$ – Simon L Rydin Myerson Dec 12 '18 at 8:41
3
$\begingroup$

For this post, I'm going to assume that the set-universe has a well-order on objects (including sets). This is true if your universe is the constructible universe (as such an order can be built inductively).

Then the class of all order-preserving injections from ordinals is a "good" class, which is not equivalent to the usual class of injections.

Property 1: for every injective map $f: Y \rightarrow X$, the image of $f$ is a subset of a well-ordered set ($X$; the well-ordering comes from the universal well-ordering), and so is well-ordered. It therefore has a unique bijection to some ordinal.

Property 2: The composition of an injection from an ordinal and any injection will be an injection from an ordinal.

Property 3: If $h: A \rightarrow C$ is an injection from an ordinal, then $f: A \rightarrow B$ must be an injection and start with an ordinal.

This is not equivalent to the original, if I've understood the proper idea of equivalence; very few sets act as domains for "good" maps for this class, while in the original, every set was the domain for a "good" map.


I think it may be better to look at classes of "good" maps instead as endofunctors $P: \text{Set} \rightarrow \text{Set}$. Given a class of "good" maps, define $i_X: P(X) \rightarrow X$ as the unique map and domain (under property 1) corresponding to $id_X: X \rightarrow X$. Then for any function $f:Y \rightarrow X$, define $P(f) = i_X \circ f \circ i_Y^{-1}$. This defines an endofunctor of $\text{Set}$.

I think this collapses the equivalent classes of "good" maps discussed in the commments, in that those two classes result in the same endofunctor, and that "goodness" may be possible to determine using the endofunctor itself.

$\endgroup$
  • 1
    $\begingroup$ I think you mean well order, not total order. $\endgroup$ – Asaf Karagila Dec 10 '18 at 23:06
  • $\begingroup$ It seems to me that you only need the axiom of choice, and not the global well-order as you have requested. You use AC in order to show that every injection is isomorphic to an injection from an ordinal. You don't seem to need to pick them uniformly. Also, you could use just the cardinals, instead of all ordinals. $\endgroup$ – Joel David Hamkins Dec 11 '18 at 13:17
  • $\begingroup$ @JoelDavidHamkins I originally thought so, but without a pre-chosen well-order on $X$, there is no uniqueness to the "good" map. And since the pre-chosen well-order could have any well-order, that required all ordinals, not just cardinals. $\endgroup$ – user44191 Dec 11 '18 at 16:31
  • $\begingroup$ Ah, yes, I had misunderstood something about the situation. You are right. $\endgroup$ – Joel David Hamkins Dec 11 '18 at 16:50
  • $\begingroup$ @JoelDavidHamkins I am curious, though - how strong is the assumption of existence of a global well-order? Is it guaranteed by ZFC? Is the answer sufficiently not-obvious to need a separate question? $\endgroup$ – user44191 Dec 11 '18 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.