Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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