Do we still have a category of sets if the inverse image has more than one element?

Question

I'm kinda lost at one example in Awodey's: Category Theory.

I am trying to check this example, for that, I made a simple example function:

With this, I mean that there is one function $f$ which associates each element of the codomain. In this case, I can't have an inverse function - I'm not sure if this invalidates it being a category, but I faintly believe it does. Because it seems that in this universe of discourse, the arrows are functions. But I guess I could counter this by creating two pseudo-inverse functions (?!) in the following way:

It doesn't seem to violate the rules, except a little doubt for one of them: The definitions of composition. If I compose $f_{1}^{-1} \circ f$, I have:

$$cod(f)=dom(f_{1}^{-1})$$

$$cod(f_{1}^{-1})=dom(f)$$

I believe this is valid because he speaks about codomain instead of image. But it feels weird, $f_{1}^{-1}$ doesn't goes back entirely to $dom(f)$, that is: It doesn't takes all the elements of $dom(f)$.

Or perhaps I'm utterly confused/lost/stupid/in_need_of_help_for_mental_illness and completely missed the point.

Answer 1

The main problem is that the composition of functions with at most two preimages is not necessarily a function with at most two preimages. In this wanna-be category, there does exist an arrow $\{1,2,3,4\}\to\{1,2\}$ (in fact several) and an arrow $\{1,2\}\to\{1\}$, but no arrow from $\{1,2,3,4\}$ to $\{1\}$.

For the restriction with finite pre-images, this problem does not occur, and you can verify that we indeed obtain a category.

Answer 2

In this case, I can't have an inverse function - I'm not sure if this invalidates it being a category, but I faintly believe it does.

No. Morphisms in categories don't necessarily have inverses. For instance, the category $\mathsf{Set}$ of sets with functions for morphisms includes functions which have no inverse (i.e. non-bijections). Most categories we work with will include noninvertible morphisms ($\mathsf{Top,Ring,Grp,Mod,Pos}$ etc.).

Your "pseudoinverses" are called right-inverses (since $f\circ f_1=\mathrm{id}$ has $f_1$ on the right), or what I would call a "pre-inverse" (since one applies $f_1$ before $f$ to get the identity map). In any case, these aren't really relevant to your exercise. As is mentioned in the comments, $f^{-1}(b)$ stands for the preimage of $b$ under $f$, i.e. $\{a\in A:f(a)=b\}$, and it is defined (but possibly empty) whether or not $f$ is invertible in the category.

Simple concepts in mathematics tend to come with definitions that are a ready-made checklist of things to verify in order to confirm that the definition applies to something. So if you want to check that sets and functions with fibers bounded in size by $2$ is a category, you look at the properties in the definition of a category and check that each one is true. Does this category include the identity function for every set? Yes.

The key thing is checking that it's closed under composition. Hagen gives the simplest example of how this can fail. Consider the composition of functions $\{1,2,3,4\}\xrightarrow{g}\{a,b\}\xrightarrow{f}\{x\}$ given by

$\hskip 1.5in$

As you can see, $g^{-1}(a)=\{1,2\}$, $g^{-1}(b)=\{3,4\}$ both have cardinality less than or equal to $2$, and $f^{-1}(x)=\{a,b\}$ has cardinality less than or equal to $2$, however $(f\circ g)^{-1}(x)=\{1,2,3,4\}$ has cardinality greater than $2$. This illustrates how functions with fibers bounded by $2$ in size are not closed under composition.