The Lumenary · Grades 9–12

Products by maps: a first universal property

Name: ______________________

Date: ______________________

You will learn to

Given $f : X \to A$ and $g : X \to B$ , construct the pairing $\langle f, g \rangle : X \to A \times B$ and prove it is the only $h$ with $\pi_A \circ h = f$ and $\pi_B \circ h = g$
Draw the commuting diagram of the universal property and explain what "exactly one" means, with examples where existence or uniqueness fails
Prove that functions $X \to A \times B$ correspond one-to-one with pairs of functions, and deduce $|A \times B|^{|X|} = |A|^{|X|} \cdot |B|^{|X|}$
Prove that any set $P$ with maps to $A$ and $B$ having the same property is in bijection with $A \times B$ by exactly one bijection compatible with the maps
Recognise products described by maps in other settings, such as coordinates, continuous maps and greatest common divisors

1.
Let $X = \{1, 2, 3\}$ , $f : X \to \{\text{red}, \text{blue}\}$ with $f(1) = \text{red}$ and $f(2) = f(3) = \text{blue}$ , and $g : X \to \Z$ with $g(n) = n^2$ . What is $\langle f, g \rangle(2)$ ?
- A. $(\text{blue}, 4)$
- B. $(4, \text{blue})$
- C. $(\text{blue}, 2)$
- D. $(\text{red}, 4)$
2.
Let $|X| = 2$ , $|A| = 2$ and $|B| = 3$ . How many functions $X \to A \times B$ are there?
3.
Let $A = B = \{0, 1\}$ . Which of these $(P, p, q)$ are products of $A$ and $B$ ? (Choose all that apply.)
- A. $P = \{0, 1, 2, 3\}$ , $p(n) = n \bmod 2$ , $q(n) = \lfloor n/2 \rfloor$
- B. $P = A \times B$ with $p(a, b) = b$ and $q(a, b) = a$
- C. $P = \{0, 1, 2\}$ , $p(n) = \min(n, 1)$ , $q(n) = \lfloor n/2 \rfloor$
- D. $P = \{0, 1, \dots, 7\}$ , $p(n) = n \bmod 2$ , $q(n) = \lfloor n/2 \rfloor \bmod 2$
4.
In the proof of Theorem 3 we showed that $\psi \circ \varphi = \mathrm{id}_P$ . Which fact justifies that final equality?
- A.Both $\psi \circ \varphi$ and $\mathrm{id}_P$ are compatible with $p$ and $q$ , and the universal property of $P$ (with $X = P$ ) allows only one such map.
- B. $\psi$ was defined to be the inverse of $\varphi$ .
- C. $\varphi$ is injective.
- D.The universal property of $A \times B$ .
5.
Let $P = A \times B \times \{0, 1\}$ , with $p(a, b, c) = a$ and $q(a, b, c) = b$ . Let $X$ have $3$ elements and fix $f : X \to A$ and $g : X \to B$ . How many functions $h : X \to P$ satisfy $p \circ h = f$ and $q \circ h = g$ ?
6.
Given p : P → A, q : P → B, f : X → A and g : X → B, which Lean proposition says "there is exactly one $h$ compatible with $f$ and $g$ "?
- A.∃! h : X → P, p ∘ h = f ∧ q ∘ h = g
- B.∃ h : X → P, p ∘ h = f ∧ q ∘ h = g
- C.∀ h : X → P, p ∘ h = f ∧ q ∘ h = g
- D.∃! h : X → P, p ∘ h = f ∨ q ∘ h = g
7.
Represent a finite function as a Python dict. Write pairing(f, g), which takes two dicts with the same keys and returns the dict $x \mapsto (f(x), g(x))$ , and components(h), which takes a dict whose values are pairs and returns the two dicts $(\pi_A \circ h, \pi_B \circ h)$ . Check that the two are inverse to each other (Theorem 2).
Computational — Practice
8.
Let $|A| = 3$ and $|B| = 4$ , and suppose a set $P$ with maps $p : P \to A$ and $q : P \to B$ has the universal property of the product. How many elements must $P$ have?
9.
Make the positive integers into a category: there is one arrow $x \to y$ exactly when $x$ divides $y$ (and no arrow otherwise). A product of $12$ and $18$ is a number $P$ with arrows $P \to 12$ and $P \to 18$ such that every $X$ with arrows $X \to 12$ and $X \to 18$ has an arrow $X \to P$ (uniqueness is automatic, as there is at most one arrow between two numbers). What is $P$ ?
- A. $6$
- B. $36$
- C. $216$
- D. $3$

Answer key — Products by maps: a first universal property

1.
$\langle f, g \rangle(2) = (f(2), g(2)) = (\text{blue}, 2^2) = (\text{blue}, 4)$ . Projecting back: $\pi_A(\text{blue}, 4) = \text{blue} = f(2)$ and $\pi_B(\text{blue}, 4) = 4 = g(2)$ .
2.
$|A \times B| = 6$ , and each of the $2$ elements of $X$ can go to any of the $6$ pairs: $6^2 = 36$ . Check with Theorem 2: there are $2^2 = 4$ functions $X \to A$ and $3^2 = 9$ functions $X \to B$ , so $4 \cdot 9 = 36$ pairs $(f, g)$ , matching the $36$ functions into $A \times B$ one-to-one.
3.
A set $P$ with maps $p, q$ is a product exactly when $u \mapsto (p(u), q(u))$ is a bijection $P \to A \times B$ . In (a) the values are $(0,0), (1,0), (0,1), (1,1)$ — a bijection. In (b) the map $(a, b) \mapsto (b, a)$ is a bijection. In (c) only $3$ elements cannot cover $4$ pairs: existence fails. In (d) $8$ elements hit each of the $4$ pairs twice: uniqueness fails.
4.
We computed $p \circ (\psi \circ \varphi) = p$ and $q \circ (\psi \circ \varphi) = q$ . The identity of $P$ satisfies the same two equations. The universal property of $P$ , applied with $X = P$ , $f = p$ , $g = q$ , says there is exactly one map $P \to P$ with these properties, so $\psi \circ \varphi = \mathrm{id}_P$ .
5.
At each $x \in X$ we must have $h(x) = (f(x), g(x), c_x)$ with $c_x \in \{0, 1\}$ free. Three independent binary choices give $2^3 = 8$ compatible maps. Existence holds but uniqueness fails, so $P$ is not a product.
6.
∃! h : X → P, p ∘ h = f ∧ q ∘ h = g. In the lesson's Lean file, IsProduct p q asks for this for every type X and all f, g.
7.
```
def pairing(f, g):
    return {x: (f[x], g[x]) for x in f}


def components(h):
    return {x: h[x][0] for x in h}, {x: h[x][1] for x in h}
```
components(pairing(f, g)) == (f, g) is the computation $\pi_A \circ \langle f, g \rangle = f$ , $\pi_B \circ \langle f, g \rangle = g$ ; pairing(*components(h)) == h is the uniqueness half: a function into pairs is determined by its two components.
8.
By Theorem 3, $P$ is in bijection with $A \times B$ , so $|P| = 3 \cdot 4 = 12$ . Directly: with $X = \{\star\}$ , each pair $(a, b)$ determines exactly one $u \in P$ with $(p(u), q(u)) = (a, b)$ , and every $u$ arises from its own pair $(p(u), q(u))$ . So $u \mapsto (p(u), q(u))$ is a bijection onto the $12$ pairs.
9.
We need $P \mid 12$ , $P \mid 18$ , and $X \mid P$ for every common divisor $X$ . The common divisors of $12$ and $18$ are $1, 2, 3, 6$ , and each divides $6$ . So $P = \gcd(12, 18) = 6$ . In this category, products are greatest common divisors.