# Is it a category?

Sets are my objects and as arrows, those $f : A \rightarrow B$ such that for all $b \in B$, the subset $f^{-1}(b) \subseteq A$ has at most two elements (rather than one). I want to prove whether it is a category.

NOTE : Please also points out deficiency in my mathematical language (argument).

This is my attempt.

1. Identity 'morphism' can be proven by showing that it exists. A simple 'one-to-one mapping' from a set to itself will do the job.

2. To form a concrete example to show one instance of 'composition', I take three sets $A = \{1, 2, 3 \}$, B = { p, q }, C = { a, b, c }. Let $f : A \rightarrow B$ and $g : B \rightarrow C$ then $f = \{(1, w), (2, w), (2, x), (3, x) \}$ and $g = \{ (w, a), (w, b), (x, a), (x ,c) \}$. Now I try to compose $f$ and $g$. Since both $f$ and $g$ multi-valued 'function', I am not sure whether following is the right step. $f \bullet g = \{ (1,a), (1, b), (2, a), (2, b), (2, a), (2, c), (3, a), (3, c) \} = \{ (1,a), (1, b), (2, a), (2, b), (2, c), (3, a), (3, c) \}$. This indeed is some morphism $X : A \rightarrow C$. But it violates the given constrains on co-domain on the 'function' since for $a \in C$, $X^{-1}(a)$ has more than two elements. They are $\{1, 2, 3\}$.

Thus, this thing is not a category

Now I am having trouble with finite case, namely when $f^{-1}(b)$ is finite, or infinite?

I have constructed a proof for finite case on similar arguments and it proves that this is a category.

What about infinite case? Can I prove it without using the concept from vector spaces?

-
No, you're right. It's not a category because morphisms aren't closed under composition and that's all you need to say. – Qiaochu Yuan Jul 3 '11 at 5:03
@Qiaochu: Perhaps, you can add what you said as an answer – user9413 Jul 3 '11 at 6:27

I think your example is correct that this does not form a category.

If I understood correctly, you want to know also want to know if we can form a category by the following data:

Objects: Ordinary sets Morphisms: Functions $f:A\rightarrow B$ with the property that $f^{-1}(b)$ is finite, for any $b\in B$.

I believe this is a category. Identities are obviously present. Composition is associative (if it exists), being the ordinary composition of functions. We only need to show that the composition actually exist.

Let $f:A\rightarrow B$, and $g:B\rightarrow C$. We want to know if $(g\circ f)^{-1}(c)$ is finite. Obviously $g^{-1}(c)$ is finite. Now $f^{-1}(b)$ is finite for any $b\in g^{-1}(c)$. Thus $f^{-1}(g^{-1}(c))$ is a finite union of finite sets, hence finite.

Edit: Obviously it does not work in the infinite setting. There are no identities.

-