2
$\begingroup$

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?

  • 0
    @Qiaochu: Perhaps, you can add what you said as an answer2011-07-03

1 Answers 1

1

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.