The Lumenary · Early undergraduate

Categories

Name: ______________________

Date: ______________________

You will learn to

State the axioms of a category and verify them for $\cat{Set}$ , $\cat{Grp}$ , $\cat{Vect}_k$ , $\cat{Top}$ , a category of matrices and a poset regarded as a category
Recognise a monoid as a category with one object and a preorder as a category with at most one morphism between any two objects
Define isomorphisms in a category and prove that inverses are unique
Prove that in $\cat{Set}$ the monomorphisms are the injections and the epimorphisms are the surjections, and that $\Z \to \Q$ is an epimorphism of rings that is not surjective
Form the opposite category and use the duality principle to turn one theorem into two

1.
Which of these are categories (with the obvious composition)? Choose all that apply.
- A.Objects: positive integers. One morphism $m \to n$ exactly when $m$ divides $n$ .
- B.Objects: integers. One morphism $m \to n$ exactly when $m < n$ .
- C.Objects: sets. Morphisms: injective functions.
- D.Objects: sets. Morphisms: functions that are at most two-to-one.
- E.Objects: natural numbers. Morphisms $m \to n$ : $n \times m$ real matrices, composed by multiplication.
2.
Regard the set $\{1, 2, 3, 6\}$ , ordered by divisibility, as a category. How many morphisms does it have in total, including the identities?
3.
Let $M = (\mathbb{Z}/12, \times, 1)$ be the monoid of residues modulo $12$ under multiplication, and $\mathbf{B}M$ its one-object category. How many of the $12$ morphisms of $\mathbf{B}M$ are isomorphisms?
4.
In the proof that a left inverse $g$ and a right inverse $h$ of $f : A \to B$ are equal, $g = g \circ \mathrm{id}_B = g \circ (f \circ h) = (g \circ f) \circ h = \mathrm{id}_A \circ h = h,$ which axiom justifies the step $g \circ (f \circ h) = (g \circ f) \circ h$ ?
- A.Associativity of composition
- B.The unit laws
- C.Commutativity of composition
- D.The hypothesis $f \circ h = \mathrm{id}_B$
5.
Which of these are epimorphisms that are not surjective? Choose all that apply.
- A.The inclusion $\mathbb{Z} \to \mathbb{Q}$ in the category of rings
- B.The inclusion $(\mathbb{N}, +) \to (\mathbb{Z}, +)$ in the category of monoids
- C.The inclusion $\{0\} \to \{0, 1\}$ in $\mathbf{Set}$
- D.The homomorphism $n \mapsto 2n$ from $(\mathbb{Z}, +)$ to $(\mathbb{Z}, +)$ in the category of groups
6.
Theorem: in every category, if $g \circ f$ is a monomorphism then $f$ is a monomorphism. What does the duality principle give us for free?
- A.If $g \circ f$ is an epimorphism then $g$ is an epimorphism.
- B.If $g \circ f$ is an epimorphism then $f$ is an epimorphism.
- C.If $f$ is a monomorphism then $g \circ f$ is a monomorphism.
- D.If $g \circ f$ is an isomorphism then $f$ is an isomorphism.
7.
Mathlib writes composition in diagrammatic order: a ≫ f means "first a, then f", i.e. $f \circ a$ . Which statement says that f : X ⟶ Y is a monomorphism?
- A.∀ (T : C) (a b : T ⟶ X), a ≫ f = b ≫ f → a = b
- B.∀ (T : C) (a b : Y ⟶ T), f ≫ a = f ≫ b → a = b
- C.∀ x y : X, f x = f y → x = y
- D.∃ g : Y ⟶ X, f ≫ g = 𝟙 X
8.
A function between finite sets $\{0, \dots, m-1\} \to \{0, \dots, n-1\}$ is stored as a tuple f of length $m$ with values in range(n). Write is_epi(f, n) that decides whether f is an epimorphism directly from the definition, by testing cancellation against all pairs of maps $k, l : \{0, \dots, n-1\} \to \{0, 1\}$ (that is, k ∘ f == l ∘ f must force k == l). Do not test surjectivity directly!
Computational — Practice

Answer key — Categories

1.
The divisibility order, injections, and matrices are categories. Strict $<$ has no identities, and at-most-two-to-one maps are not closed under composition (two-to-one after two-to-one can be four-to-one).
2.
The pairs with $a \mid b$ are $(1,1), (2,2), (3,3), (6,6)$ (identities) and $(1,2), (1,3), (1,6), (2,6), (3,6)$ . That is $4 + 5 = 9$ morphisms.
3.
Isomorphisms in $\mathbf{B}M$ are the units of $M$ . The residues coprime to $12$ are $1, 5, 7, 11$ , and each is its own inverse ( $5^2 = 25 \equiv 1$ , $7^2 = 49 \equiv 1$ , $11^2 = 121 \equiv 1$ ). So there are $4$ .
4.
The step regroups $g$ , $f$ , $h$ without reordering them: it is associativity. The unit laws give the first and last equalities, and the hypotheses $f \circ h = \mathrm{id}_B$ and $g \circ f = \mathrm{id}_A$ give the second and fourth.
5.
The first two. For $\mathbb{Z} \to \mathbb{Q}$ in rings and $\mathbb{N} \to \mathbb{Z}$ in monoids, the values on the smaller object force the values on inverses, because inverses are unique — so the inclusion is right-cancellable without being surjective. In $\mathbf{Set}$ and in groups, epimorphisms are surjective, and explicit pairs of maps (the identity and a constant; the quotient $\mathbb{Z} \to \mathbb{Z}/2$ and zero) show the other two are not epic.
6.
Apply the theorem in $\mathbf{C}^{\mathrm{op}}$ to the composite $f^{\mathrm{op}} \circ g^{\mathrm{op}} = (g \circ f)^{\mathrm{op}}$ : if it is monic in $\mathbf{C}^{\mathrm{op}}$ (i.e. $g \circ f$ is epic in $\mathbf{C}$ ), then the first factor $g^{\mathrm{op}}$ is monic in $\mathbf{C}^{\mathrm{op}}$ , i.e. $g$ is epic in $\mathbf{C}$ . So: if $g \circ f$ is epic then $g$ is epic.
7.
a ≫ f = b ≫ f → a = b translates to $f \circ a = f \circ b \Rightarrow a = b$ , the definition of a monomorphism (this is Mathlib's Mono.right_cancellation). The second statement is the definition of an epimorphism, the third needs elements, and the fourth defines a split monomorphism.
8.
```
from itertools import product

def compose(g, f):
    return tuple(g[x] for x in f)

def is_epi(f, n):
    maps = list(product((0, 1), repeat=n))
    for k in maps:
        for l in maps:
            if k != l and compose(k, f) == compose(l, f):
                return False
    return True
```
Why a two-element test set is enough: if some $b$ is missed by $f$ , the indicator of $\{b\}$ and the zero map agree after $f$ but differ, exactly as in the proof of Theorem 2. The test with $(), 1$ is the empty function into a one-element set: it is not surjective, and indeed the two maps $\{0\} \to \{0,1\}$ agree on the (empty) image.