The Lumenary · Early undergraduate

Universal properties

Name: ______________________

Date: ______________________

You will learn to

State the universal properties of products in $\cat{Set}$ , $\cat{Grp}$ and $\cat{Top}$ , of quotient sets and quotient groups, and of free monoids, and prove that the familiar constructions satisfy them
Prove that any two objects with the same universal property are isomorphic by a unique isomorphism compatible with the structure maps
Derive the first isomorphism theorem for groups from the universal property of quotients
Explain why a universal property characterises an object without guaranteeing that it exists, using fields that have no product
Recognise constructions such as the field of fractions and the tensor product as defined by universal properties

1.
Let $|X| = 2$ , $|A| = 2$ and $|B| = 3$ . How many functions $X \to A \times B$ are there? (Use the universal property: such a function is the same as a pair of functions $X \to A$ , $X \to B$ .)
2.
The free monoid on a one-element set $\{a\}$ is isomorphic to which monoid?
- A. $(\mathbb{N}, +, 0)$
- B. $(\mathbb{Z}, +, 0)$
- C. $(\mathbb{Z}/2, +, 0)$
- D.The trivial monoid $\{1\}$
3.
Let $\bar f$ be the unique monoid homomorphism from the free monoid on $\{a, b\}$ to $(\mathbb{Z}, +, 0)$ with $\bar f(a) = 2$ and $\bar f(b) = -1$ . What is $\bar f(abbab)$ ?
4.
Let $A, B$ be non-empty sets and $P = A \times B \times \{0, 1\}$ , with $p(a, b, i) = a$ and $q(a, b, i) = b$ . Which part of the universal property of the product does $(P, p, q)$ fail?
- A.Uniqueness: for every $X$ and every pair $f, g$ there are several compatible maps $X \to P$ (for non-empty $X$ ).
- B.Existence: some pairs $f, g$ have no compatible map.
- C.Both existence and uniqueness.
- D.Neither — it is a product, isomorphic to $A \times B$ .
5.
In the proof that two universal arrows $(F, \eta)$ and $(F', \eta')$ are isomorphic, we know $U(\psi \circ \varphi) \circ \eta = \eta$ . What exactly lets us conclude $\psi \circ \varphi = \mathrm{id}_F$ ?
- A.The uniqueness clause for $(F, \eta)$ applied to $f = \eta$ : both $\psi \circ \varphi$ and $\mathrm{id}_F$ are morphisms $g : F \to F$ with $U(g) \circ \eta = \eta$ .
- B.The existence clause for $(F, \eta)$ .
- C. $\eta$ is a monomorphism, so it can be cancelled.
- D. $U$ is faithful, so $U(\psi \circ \varphi) = U(\mathrm{id}_F)$ implies $\psi \circ \varphi = \mathrm{id}_F$ .
6.
Regard the positive integers ordered by divisibility ( $a \to b$ when $a \mid b$ ) as a category. Which statements are true? Choose all that apply.
- A.The product of $12$ and $18$ is $6$ .
- B.The coproduct of $12$ and $18$ is $36$ .
- C. $1$ is an initial object.
- D.The product of $12$ and $18$ is $12 \cdot 18 = 216$ .
- E.There is a terminal object.
7.
In the Lean structure UniversalArrow X U, with fields obj, unit : X ⟶ U.obj obj and lift, which field states the uniqueness clause? (Recall unit ≫ U.map g means $U(g) \circ \eta$ .)
- A.uniq : ∀ {E} (f : X ⟶ U.obj E) (g : obj ⟶ E), unit ≫ U.map g = f → g = lift f
- B.fac : ∀ {E} (f : X ⟶ U.obj E), unit ≫ U.map (lift f) = f
- C.∀ {E} (g g' : obj ⟶ E), g = g'
- D.∀ {E} (f : X ⟶ U.obj E) (g : obj ⟶ E), g = lift f → unit ≫ U.map g = f
8.
An equivalence relation on a finite set is given by its list of classes, e.g. [{0, 3}, {1, 4}, {2, 5}], and a function by a dict. Write descend(f, classes) that returns the induced function $\bar f$ on classes — a dict from each class (as a frozenset) to a value, with $\bar f([x]) = f(x)$ — or None if $f$ is not constant on some class (so that no $\bar f$ with $\bar f \circ q = f$ exists).
Computational — Practice

Answer key — Universal properties

1.
By the universal property, functions $X \to A \times B$ correspond to pairs $(f, g)$ with $f : X \to A$ , $g : X \to B$ . There are $2^2 \cdot 3^2 = 4 \cdot 9 = 36$ such pairs. Check directly: $|A \times B|^{|X|} = 6^2 = 36$ .
2.
The words are $a^n$ for $n \ge 0$ , multiplied by $a^m a^n = a^{m+n}$ , so $a^n \mapsto n$ is an isomorphism onto $(\mathbb{N}, +, 0)$ . It has the universal property directly: a homomorphism from $(\mathbb{N}, +)$ to a monoid $M$ is determined by the image $x$ of $1$ , as $n \mapsto x^n$ .
3.
$\bar f(abbab) = 2 + (-1) + (-1) + 2 + (-1) = 1$ . In general $\bar f(w) = 2 \cdot \#_a(w) - \#_b(w)$ . Note that $\bar f$ is not injective ( $ab$ and $ba$ both go to $1$ ): the universal property promises uniqueness of the homomorphism, not injectivity.
4.
Existence holds ( $x \mapsto (f(x), g(x), 0)$ ), but uniqueness fails: the last coordinate of each $h(x)$ can be chosen freely, giving $2^{|X|}$ compatible maps. Without uniqueness the proof that products are unique up to isomorphism breaks down, and indeed $P \not\cong A \times B$ .
5.
Both $\psi \circ \varphi$ and $\mathrm{id}_F$ are morphisms $g : F \to F$ with $U(g) \circ \eta = \eta$ . The universal property of $(F, \eta)$ , applied to the morphism $f = \eta : X \to U(F)$ , says there is exactly one such $g$ . So they are equal. This is the step where the uniqueness clause is indispensable.
6.
Products are greatest common divisors and coproducts least common multiples: $12 \times 18 = \gcd(12, 18) = 6$ and $12 + 18 = \mathrm{lcm}(12, 18) = 36$ in this category. $1$ is initial since it divides everything; there is no terminal object, since no positive integer is divisible by all others. (If we included $0$ , which is divisible by everything, it would be terminal.)
7.
uniq says that any g with unit ≫ U.map g = f equals lift f: the factorisation is unique. fac is existence. In Lumenary.UniversalProperties.UniversalArrow.hom_ext the two are combined: two morphisms that agree after the unit are both equal to the same lift.
8.
```
def descend(f, classes):
    result = {}
    for C in classes:
        values = {f[x] for x in C}
        if len(values) != 1:
            return None
        result[frozenset(C)] = values.pop()
    return result
```
This is the proof of the universal property of the quotient, as an algorithm: $\bar f$ is defined by $\bar f([x]) = f(x)$ , and the check that $f$ is constant on classes is exactly the "well defined" step. Uniqueness is visible too: there was never a choice to make. In the test, $x \mapsto x^2 \bmod 3$ descends to $\mathbb{Z}/3$ , while $x \mapsto x \bmod 2$ does not ( $0$ and $3$ are in the same class but have different parities).