# Category theory without codomains?

A surjection is a function whose range equals its codomain. Thus, the distinction between functions and surjections requires the notion of a codomain. Similarly, a bijection is an injection whose range equals its codomain. So this distinction, too, requires the notion of a codomain.

However, codomains seem like a very artificial idea, to myself and many others; and so we avoid using them. Thus, we speak of functions $f:X \rightarrow Y$ and functions $f: X \twoheadrightarrow Y$, the latter being a substitute for the notion of a surjection. And we speak of injections $f:X \rightarrow Y$ and injections $f:X \twoheadrightarrow Y$, the latter being a substitute for the notion of a bijection.

That's all well and good, but there's a tension here lurking beneath the surface. The source of the tension is category theory, which stipulates that morphisms have not only domains but also codomains. So unless we can reformulate category theory without codomains, we're sort of trapped.

Has anyone managed to do this?

If not, here's my very preliminary attempt at doing so. A category* will consist of the following data: a class of objects, a class of isomorphisms (not homomorphisms), each of which has a unique domain and range; an operation that composes isomorphisms; and two partial order relations defined on the class of objects, namely the relation "is a subobject of" and "is a quotient object of".

So for example, the statement "$f$ is monomorphism $X \rightarrow Y$" would be interpreted as "There exists a subobject of $Y$, call it $B$, such that $f$ is an isomorphism with domain $X$ and range $B$." And the statement "$f$ is a morphism $X \twoheadrightarrow Y$" would be interpreted as "There exists a quotient object of $X$, call it $A$, such that $f$ is an isomorphism with domain $A$ and range $Y$."

Anyway, I'd be interested in hearing people's opinion on the matter.

EDIT. Just to clarify, this approach would appeal to people whom prefer to define functions (etc.) as their graph, rather than as a triple.

-
How do you define subobjects and quotient objects here? In conventional theory the definition of these use codomains of morphisms. –  Espen Nielsen Nov 19 '12 at 22:17
This is a terrible idea, as it makes composition very difficult, not to mention it renders useless the notion of cokernel. To be entirely frank: if you think maps should always be surjective, then you have not done enough mathematics. –  Zhen Lin Nov 19 '12 at 22:32
Also let me quote Mac Lane (1988) on the topic: "At that time, a homomorphism in algebra always meant a surjective homomorphism (a mapping onto). Now homomorphisms also arise for homology groups of spaces; in such cases they are not necessarily onto – the familiar map $x \mapsto e^{2 \pi i x}$ of the real line to the circle is onto the circle, but the induced homomorphism in homology is not onto. [...] The problems forced on us the consideration of homomorphisms (and other maps) which are not necessarily surjective or injective." –  Zhen Lin Nov 19 '12 at 22:32
Who are these "many others"? How many of them are there? –  Qiaochu Yuan Nov 20 '12 at 7:14
I posit that the notion of "codomain" is not artificial if you have great difficulty describing things without invoking it. –  Hurkyl Nov 20 '12 at 9:17

I agree with Zhen's assessment in the comments that if you think maps should always be surjective you have not done enough mathematics. To be blunt, I can think of so many reasons that maps should not always be surjective that I am having trouble organizing all of my thoughts on this question, so I'm just going to blurt things out (as it were).

First, here are some objections to your specific proposal.

1. You are implicitly assuming some kind of factorization of morphisms into epimorphisms and monomorphisms. As I pointed out recently, such factorizations neither exist nor are unique in general categories.

2. "Subobject" and "quotient object" are not relations. A given object can be a subobject resp. a quotient object of another object in different ways given by different isomorphism classes of monomorphisms resp. epimorphisms. This isn't a particularly esoteric claim; it already happens in the category of sets for quotient objects.

Here are some general objections to what you are trying to do, in no particular order.

1. There are issues here that I don't know a standard language for talking about, so for lack of a better word I'm going to call them "decidability issues." Sometimes it takes a lot of effort to construct a map. After you've constructed it, sometimes it takes a lot of effort to decide whether it's injective or surjective. Maybe it is, maybe it isn't. Before you've determined this, what are you going to call what you've constructed?

2. Codomains are not an artificial idea at all once you move past thinking of categories of sets and functions and onto more interesting kinds of categories. For example, there are "physical categories" where objects are states of a system and morphisms are ways of transitioning from one state to another. There are "logical categories" where objects are propositions and states are proofs of one proposition from another. There are "cobordism categories" where objects are manifolds and morphisms are ways of connecting those manifolds together using manifolds of one dimension higher. And so forth.

3. There are general machines (that is, functors) for turning morphisms into other morphisms, and these machines do not preserve epimorphisms in general. This is a general version of the specific point brought up by Mac Lane via Zhen in the comments.

4. In general, in mathematics we often don't study specific examples of something, but instead study families of examples. For example, we often don't study numbers, but families of numbers (e.g. sequences). In category theory, we often don't study morphisms, but families of morphisms, in particular the family of all morphisms from an object $x$ to an object $y$. It is sensible to group all of these morphisms together even though some of them may not be epimorphisms, and this grouping has good formal properties.

-
"You are implicitly assuming some kind of factorization of morphisms into epimorphisms and monomorphisms. As I pointed out recently, such factorizations neither exist nor are unique in general categories." Yes this completely undermines the approach I was hoping to take; which is why I chose your answer. –  goblin Nov 22 '12 at 7:49

Category theory can be formulated entirely without any objects, so that your idea of getting rid of codomains can be realized with an added bonus that you can also get rid of domains. Objects in category theory, formally, are auxiliary notions. Their only purpose in life is to serve as domains and codomains of arrows, but it is the arrows that are important, and nothing else.

A formal way of getting rid of objects is to define a category to be a class of arrows, together with a partial binary operation on the class of arrows. That partial binary operation is called composition. After defining some of the most elementary properties one expects of this composition partial operation, one can 'recover' objects by identifying certain special arrows that behave like identities. So the slogan is: in a category objects can be identified with identity arrows, and thus be disposed of.

A more detailed account can be found in Mac Lane's Categories for the Working Mathematician. A related question, is Category Theory with and without Objects.

That said, there is little to gain (at least conceptually) from disposing of objects (there is something to gain logically since it is easier to describe the first order theory of categories in an object-free manner). Your objection to using objects (codomains specifically) is understandable but your solution seems to introduce a lot of complications and is (pardon my opinion here) far from elegant. The use of domains and codomains really has no adverse consequences. What is so horrible in distinguishing between functions and surjections? do you really want every function to be surjective by working out its image explicitly? If so, then here is a little exercise: Find the codomain of the function $f:[0,1]\to D$ where $f(x)=\sin(x)\cos(x)e^x*1/(1+\sin(x))*\ln(|\sin(x)|+|\cos(x)|)$. I hope you will agree it's a lot easier to simply say: the codomain of $f$ is $\mathbb{R}$ and call it a day.

Later addition incorporating comments and chat information: A situation where functions do not have specified domains or codomains can be incorporated within category theory as follows. Let $Par$ be the category of sets and partial functions. Fix some universal set $U$ in $Par$, then the full subcategory of $Par$ spanned by $U$ can be interpreted as a world where functions can always be composed (albeit sometimes their composition is the empty function).

-
With your example with $f$, you would simply write $f : [0,1] \rightarrow \mathbb{R}$. This does not mean $f$ has codomain $\mathbb{R}$, however. It means $f$ has range that is a subset of $\mathbb{R}$. –  goblin Nov 19 '12 at 22:45
I'm not sure what you mean by that. –  Ittay Weiss Nov 19 '12 at 22:46
How is that different than Y being the codomain of f? (seeing that your initial objection was that not every function is surjective). –  Ittay Weiss Nov 19 '12 at 22:58
@IttayWeiss While what you say is all correct, I suspect the heart of the contention is that the OP believes two functions are equal when their graphs are equal. In order to use the categories-without-objects formulation, it is essential that we do not identify functions with their graphs. (The fact that the domain of a function is recoverable from its graph is an accident of our demand that functions be total; if we worked with partial functions instead then the situation is more symmetrical and neither domain nor codomain are recoverable from the graph.) –  Zhen Lin Nov 19 '12 at 23:09
There is no category theory that supports it, because this is a far too concrete notion. A category is fundamentally a system of arrows that can be joined head-to-tail in an associative way: the fact that the first and foremost examples of such things are functions is purely an accident of history. –  Zhen Lin Nov 19 '12 at 23:26

I would rather do something like: consider all functions, then we can define the composition of any two of them (if you want to keep the domains, then the domain of $f\circ g$ will consist of course of those elements $x$ such that $g(x)\in Dom f$).

So, it would result in a semigroup of the functions, instead of a category, probably the empty function and the (partial) identities would be of special use. An interesting consequence is that this semigroup would have a unit element only if the total set (the 'set' of all sets) existed..

If, in addition, we presume the partial order of these codomainless functions (meaning $f\subseteq g$ iff $\ \exists f(x)\Rightarrow g(x)=f(x)$), then the (identities of the) objects can be recovered as the 'local units': those $e$ functions which satisfy $e\circ f\subseteq f$ and $f\circ e\subseteq f$ for all functions $f$. [If $e$ is not an identity, then there is $x: e(x)\ne x$, then we need an arbitrary $f$ which maps different values to $e(x)$ and $x$.]

-
strictly speaking, a semigroup is a category so considering all functions in this way will result in a category. It is the full subcategory of the category of partial functions spanned by a single set U, the universal set. –  Ittay Weiss Nov 20 '12 at 19:59
Well, yes. And there are no codomains here. –  Berci Nov 20 '12 at 20:01
yes, this seems to be what OP wanted. To consider all functions, with no codomains (nor domains thus as well), such that any two functions are composable. So he is thinking of partial endo-functions on a universal set. –  Ittay Weiss Nov 20 '12 at 20:03
This might work, but how would you define the "categorical product" of two sets, for example? With only one object, I can't quite see how to do it. EDIT: Ittay Weiss expressed exactly this idea in a private chat context. –  goblin Nov 21 '12 at 19:26
Also, Ittay's statement that "one can 'recover' objects by identifying certain special arrows that behave like identities," sounds helpful in this regard. –  goblin Nov 21 '12 at 19:29