A Universe of Sorts

§ Categorical definition of products in painful detail

I feel like I have incorrectly understood, then un-understood, and re-understood in a slightly less broken way the definition of the product in category theory around 5 times. I'm documenting the journey here.

§ The definition

Given two objects

a, b

, in a category

C

, any 3-tuple

(p \in C, \pi_a \in Hom(p, a), \pi_b \in Hom(p, b))

is called their product , if for any other 3 tuple

(q \in C, \pi'_a \in Hom(q, a), \pi'_b \in Hom(q, b))

, we have a unique factorization map

f \in Hom(q, p)

such that

\pi'_a = \pi_a \circ f

\pi'_b = \pi_b \circ f

. (Note that I did not say the product. This is on purpose). We claim that the product is unique up to unique isomorphism. Let's choose the category to be the category of sets. Let's try and figure out what a product of the sets

a = \{ \alpha, \beta \}

and

b = \{ \gamma, \delta \}

is going to be.

§ Non-example 1: product as $\{ 1 \}$

Let's try to choose the product set as simply

\{ 1 \}

, with the maps being chosen as

\pi_a(1) = \alpha; \pi_b(1) = \gamma

     πb
p{1}--->{ γ }
  |     { δ }
  |
πa|
  v
{ α , β }

In this case, it's easy to see the failure. I can build a set

q = \{ 2 \}

with the maps

\pi'_a(2) = \alpha; \pi'_b(2) = \delta

     πb
q{2}-+  { γ }
  |  |  {   }
  |  +->{ δ }
  |
πa|
  v
{ α , β }

There is a single, unique map which takes

q

p

, which is the function

f: 2 \mapsto 1

. See that

\pi'_b(2) = \delta

, while

\pi_b(f(2)) = \pi_b(1) = \gamma

. Hence the universal property can never be satisfied. Thus

(\{ 1 \}, 1 \mapsto \alpha, 1 \mapsto \gamma)

is not a product of

\{ \alpha, \beta \}

and

\{ \gamma, \delta \}

as it is unable to represent a pair

(\alpha, \delta)

§ Non-example 2: product as $\{ 1, 2, 3, 4, 5 \}$

In this case, we shall see that we will have too much freedom , so this will violate the "unique map" aspect. Let's pick some choice of

\pi_a

and

\pi_b

. For example, we can use:

\begin{aligned} (&p = \{ 1, 2, 3, 4\}, \\ &\pi_a = 1 \mapsto \alpha, 2 \mapsto \alpha, 3 \mapsto \beta, 4 \mapsto \beta, 5 \mapsto \beta\\ &\pi_b = 1 \mapsto \gamma, 2 \mapsto \delta, 3 \mapsto \gamma, 4 \mapsto \delta, 5 \mapsto \delta) \end{aligned}

Now let's say we have a set

q = \{ 42 \}

such that

\pi'_a(42) = \beta, \pi'_b(42) = \delta

. If we try to construct the map

f: q \rightarrow p

, notice that we get \emph{two} possible legal maps. We can set

f(42) = 4

, or

f(42) = 5

, because both

4

and

5

map into

(\beta, \delta)

. This violates the uniqueness condition of the product. Thus, the set

\{1, 2, 3, 4, 5\}

is not a product of

\{\alpha, \beta \}

and

\{\gamma, \delta \}

because it does not provide a unique map from

q

into

p

. Alternatively, it does not provide a unique representation for the tuple

(\beta, \delta)

. Thus it can't be a product.

§ Checking an example: $\{ \alpha, \beta \} \times \{ \gamma , \delta \}$ as $\{1, 2, 3, 4\}$

I claim that a possible product of

a

and

b

is:

\begin{aligned} (&p = \{ 1, 2, 3, 4\}, \\ &\pi_a = 1 \mapsto \alpha, 2 \mapsto \alpha, 3 \mapsto \beta, 4 \mapsto \beta,\\ &\pi_b = 1 \mapsto \gamma, 2 \mapsto \delta, 3 \mapsto \gamma, 4 \mapsto \delta) \end{aligned}

p       πa            a
   1------------*--->{α}
   |  2--------─┘    { }
   |  | 3-------*--->{β}
   |  | | 4----─┘
   +----* |
πb |  |   |
   |  *---+
   |      |
   v      v
b {γ      δ}

Now given a 3-tuple

(q, \pi'_a \in Hom(q, a), \pi'_b \in Hom(q, b))

, we construct the factorization map

f: q \rightarrow p

, where:

f: q \rightarrow p; \quad f(x) \equiv \begin{cases} 1 & \pi'_a(x) = \alpha \land \pi'_b(x) = \gamma \\ 2 & \pi'_a(x) = \alpha \land \pi'_b(x) = \delta \\ 3 & \pi'_a(x) = \beta \land \pi'_b(x) = \gamma \\ 4 & \pi'_a(x) = \beta \land \pi'_b(x) = \delta \\ \end{cases}

That is, we build

f(x)

such that on composing with

\pi_a

and

\pi_b

, we will get the right answer. For example, if

\pi'_a(x) = \alpha

, then we know that we should map

x

to an element

y \in p

such that

\pi(y) = \alpha

. So we need

y = 1 \lor y = 2

. Then looking at

\pi'_b(x)

allows us to pick a unique y. There is zero choice in the construction of

f

. We need exactly 4 elements to cover all possible ways in which

q

could map into

a

and

b

through

\pi'_a, \pi'_b

such that we cover all possibilities with no redundancy. This choice of product is goldilocks : it does not have too few elements such that some elements are not representable; it also does not have too many elements such that some elements are redundant.

§ Non uniqueness: product as $\{10, 20, 30, 40\}$

Note that instead of using

p = \{1, 2, 3 4\}

, I could have used

p = \{10, 20, 30, 40 \}

and nothing would have changed. I have never depended on using the values

1, 2, 3, 4

. Rather, I've only used them as \emph{labels}.

§ Non uniqueness: product as $\{ (\alpha, \gamma), (\alpha, \delta), (\beta, \gamma), (\beta, \delta) \}$

Indeed, our usual idea of product also satisfies the product, since it is in unique isomorphism to the set

\{1, 2, 3, 4\}

we had considered previously. But this might be strange: Why is it that the categorical definition of product allows for so many other "spurious" products? Clearly this product of tuples is the best one, is it not? Of course not! Inside the category of sets, anything with the same cardinality is isomorphic. So nothing inside the category can distinguish between the sets

\{1, 2, 3, 4\}

and

\{ (\alpha, \gamma), (\alpha, \delta), (\beta, \gamma), (\beta, \delta) \}

. Hence, the usual product we are so used to dealing with is not privileged. This should make us happy, not sad. We have removed the (un-necessary) privilege we were handing to this one set because it "felt" like it was canonical, and have instead identified what actually makes the product of sets tick: the fact that their cardinality is the product of the cardinalities of the individual sets!

§ How to think about the product

Since we are specifying the data of

(p, \pi_a, \pi_b)

, we can simply think of elements of

p

as being "pre-evaluated", as

(x \in p, \pi_a(x), \pi_b(x))

. So in our case, we can simplify the previous situation with

(p = \{ 10, 20, 30, 40 \}, \pi_a, \pi_b)

by writing the set as

p = \{ (10, \alpha, \gamma), (20, \alpha, \delta), (30, \beta, \gamma), (40, \beta, \delta) \}

. This tells us "at a glance" that every element of

a \times b

is represented, as well as what element it is represented by.

§ Proof of uniqueness upto unique isomorphism

Assume we have two products $(p, \pi_a, \pi_b)$ and $(q, \pi_a, \pi_b)$ , which are products of $a$ and $b$
By the universality of $p$ wrt $q$ , we get a unique! map $q2p$ such that the diagaram commutes.
By the universality of $q$ wrt $p$ , we get a unique! map $p2q$
We get a map $q2p \cdot p2q : p \rightarrow p$ . by the universality of $p$ with respect to $p$ , we get a unique! map that makes the diagram commute.But we have two such maps: $id_p$ as well as $q2p . p2q$ . Hence we must have $id_p = q2p \cdot p2q$ . In pictures:

          ∃!id(p)
          +---+
          |   |
          |   v
+---------ppppp--------+
| πa      |   ^     πb |
v      ∃!p2q  |        v
a         |   |        b
^         |  ∃!q2p     ^
| π'b     v   |    π'b |
+---------qqqqq--------+

The full diagram commutes.
By definition of identity/commutativity of the diagram, $\pi_a \circ id_p = \pi_a$ .
By definition of identity/commutativity of the diagram, $\pi_b \circ id_p = \pi_b$ .
By the commutativity of the diagram, we have $\pi_a \circ (q2p \circ p2q) = \pi_a$ .
By the commutativity of the diagram, we have $\pi_b \circ (q2p \circ p2q) = \pi_b$ .
We can consider the universal property of the product, where we have $(p, \pi_a, \pi_b)$ as one product, and $(p, \pi_a , \pi_b)$ as another product.
This gives us a unique map $h$ such that $\pi_a \circ h = \pi_a$ , and $\pi_b \circ h = \pi_b$ .
We have two candidates for $h$ : $h = id_p$ and $h = p2q \circ q2p$ . Hence, by the uniqueness of $h$ , we have that $id_p = p2q \circ q2p$ .

§ Wrapping up

Link to a misconception of the proof I had carried around for ages

§ Categorical definition of products in painful detail

§ The definition

§ Non-example 1: product as {1}\{ 1 \}{1}

§ Non-example 2: product as {1,2,3,4,5}\{ 1, 2, 3, 4, 5 \}{1,2,3,4,5}

§ Checking an example: {α,β}×{γ,δ}\{ \alpha, \beta \} \times \{ \gamma , \delta \}{α,β}×{γ,δ} as {1,2,3,4}\{1, 2, 3, 4\}{1,2,3,4}

§ Non uniqueness: product as {10,20,30,40}\{10, 20, 30, 40\}{10,20,30,40}

§ Non uniqueness: product as {(α,γ),(α,δ),(β,γ),(β,δ)}\{ (\alpha, \gamma), (\alpha, \delta), (\beta, \gamma), (\beta, \delta) \}{(α,γ),(α,δ),(β,γ),(β,δ)}

§ How to think about the product

§ Proof of uniqueness upto unique isomorphism

§ Wrapping up

§ Non-example 1: product as $\{ 1 \}$

§ Non-example 2: product as $\{ 1, 2, 3, 4, 5 \}$

§ Checking an example: $\{ \alpha, \beta \} \times \{ \gamma , \delta \}$ as $\{1, 2, 3, 4\}$

§ Non uniqueness: product as $\{10, 20, 30, 40\}$

§ Non uniqueness: product as $\{ (\alpha, \gamma), (\alpha, \delta), (\beta, \gamma), (\beta, \delta) \}$