Math 202A: Review Lecture 1

Let $\mathbf{Set}$ be the category whose objects are sets and whose morphisms are functions. In more detail, for any two sets $X$ and $Y,$ let $X \times Y$ be their Cartesian product and let $\mathcal{P}(X \times Y)$ be the power set of $X \times Y$ . Then $\mathrm{Hom}(X,Y)$ is the subset of $\mathcal{P}(X \times Y)$ defined by the condition

$f \in \mathrm{Hom}(X,Y) \iff \left[ (x,y_1)\in f \text{ and } (x,y_2) \in f \implies y_1=y_2\right].$

In particular, $\mathbf{Set}$ is a locally small category. Going forward we will use the standard functional notation $f(x)=y$ to denote $(x,y) \in f.$

A function $f \in \mathrm{Hom}(X,Y)$ is said to be injective if

$f(x_1)=f(x_2) \implies x_1=x_2,$

and surjective if

$f(X)=Y,$

where $f(X) = \{f(x) \colon x \in X\}.$ A function which is both injective and surjective is called bijective.

Problem 1.1. Prove that two sets $X,Y$ are isomorphic if and only if $\mathrm{Hom}(X,Y)$ contains a bijection.

A natural set is a set of the form $[n]=\{1,\dots,n\},$ where $n \in \mathbb{N}$ is a natural number. By Problem 1.1, two natural sets $[m]$ and $[n]$ are isomorphic if and only if $m=n,$ in which case $[m]=[n].$ Thus, the full subcategory $\mathbf{NSet}$ of $\mathbf{Set}$ whose objects are natural sets is a skeletal category.

Definition 1.1. A set $X$ is said to be finite if it is isomorphic to a natural set.

Since $\mathbf{NSet}$ is skeletal, this means that there is one and only one natural number $n \in \mathbb{N}$ such that $\mathrm{Hom}(X,[n])$ contains an isomorphism. This natural number is called the cardinality of the finite set $X,$ and we write $|X|=n.$ Let $\mathbf{FSet}$ be the full subcategory of $\mathbf{Set}$ whose objects are finite sets.

Problem 1.2. Given finite sets $X$ and $Y$ with $|X|=n$ and $|Y|=m,$ prove that $\mathrm{Hom}(X,Y)$ is a finite set and calculate its cardinality.

Problem 1.2 shows that the category $\mathbf{FSet}$ is enriched over itself. $\mathbf{FSet}$ is called the classical computational category because its objects and morphisms can be encoded using classical bits, and thus instantiated on a computer. The adjective “classical” is used to contrast $\mathbf{FSet}$ with the quantum computational category, whose objects and morphisms can presumably be instantiated on a quantum computer.

We will construct the quantum computational category in Lecture 2. In the remainder of Lecture 1, we focus on encoding objects and morphisms in $\mathbf{FSet}.$ Let $m$ and $n$ be natural numbers, and let $Z$ be a set, not necessarily finite.

Definition 1.2. An $m\times n$ matrix over $Z$ is an element of $\mathrm{Hom}([m] \times [n],Z).$

Given a matrix $M \in \mathrm{Hom}([m] \times [n],Z)$ , the notation $M_{ij}:=M(i,j)$ is used for its values, and we write $Z^{m \times n}$ instead of $\mathrm{Hom}([m] \times [n],Z)$ for the set of $m \times n$ matrices over $Z.$ This is because matrices $M \in Z^{m \times n}$ are typically thought of as two-dimensional arrays populated by elements of $Z,$

$M = \begin{bmatrix} {} & \vdots & {} \\ \dots & M_{ij} & \dots \\ {} & \vdots & {} \end{bmatrix}.$

Matrices $M \in Z^{m \times 1}$ are called column matrices because they are visualized as arrays consisting of a single column,

$M= \begin{bmatrix} \vdots \\ M_{i1} \\ \vdots \end{bmatrix},$

while matrices $M \in Z^{1 \times n}$ are called row matrices because they are visualized as arrays consisting of a single row,

$M=\begin{bmatrix} \dots & M_{1j} & \dots \end{bmatrix}.$

While these visualizations are very convenient, one should remember that an $m \times n$ matrix over $Z$ is really a function in $\mathrm{Hom}([m] \times [n],Z).$

Classical computation utilizes matrices over $B=\{0,1\},$ which are called binary matrices. Since $B$ is a finite set, binary matrices are morphisms in $\mathbf{FSet}.$ Let $X$ be a set of cardinality $n$ . Then $\mathrm{Hom}(X,[n])$ contains an isomorphism $f$ , and hence $\mathrm{Hom}([n],X)$ contains an isomorphism $g.$ An isomorphism $g \in \mathrm{Hom}([n],X)$ is referred to as an ordering of $X,$ and we write

$x_1:=g(1),\dots,x_n:=g(n).$

Using this enumeration of the elements of $X$ , we can define an injective function $[] \in \mathrm{Hom}(X,B^{n \times 1})$ by

$[x_1]=\begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0\end{bmatrix}, [x_2]=\begin{bmatrix} 0 \\ 1 \\ \vdots \\ 0\end{bmatrix},\dots,[x_n]=\begin{bmatrix} 0 \\ 0 \\ \vdots \\ 1\end{bmatrix}.$

The injection $[] \in \mathrm{Hom}(X,B^{n \times 1})$ is called the one-hot encoding of $X$ relative to the ordering $x_1,\dots,x_m,$ and the output $[x]$ is called the column matrix of $x$ relative to this ordering.

Now let $X$ and $Y$ be two sets of cardinalities $n$ and $m,$ respectively, and let $x_1,\dots,x_n$ and $y_1,\dots,y_m$ be orderings of these sets. Using these orderings, we can define an injective function $[] \in \mathrm{Hom}(\mathrm{Hom}(X,Y),B^{m \times n})$ by

$[f]_{ij} = \begin{cases} 1, \text{ if }f(x_j)=y_i \\ 0, \text{ otherwise}. \end{cases}.$

The injection $] \in \mathrm{Hom}(\mathrm{Hom}(X,Y),B^{m \times n})$ is called the binary encoding of $\mathrm{Hom}(X,Y)$ relative to the orderings $x_1,\dots,x_n$ and $y_1,\dots,y_m$ . The definition of $[f]$ may be equivalently stated as follows: for each $1 \leq j \leq n,$ column $j$ of $[f]$ is the one-hot encoding of $[f(x_j)]$ relative to the ordering $y_1,\dots,y_m$ of $Y.$

Now let $X,Y,Z$ be three finite sets of cardinalities $n,m,l,$ respectively. Let $x_1,\dots,x_n$ and $y_1,\dots,y_m$ and $z_1,\dots,z_l$ be orderings of these sets. Let $f \in \mathrm{Hom}(X,Y)$ and $\mathrm{Hom}(Y,Z)$ be given functions, and let $g \circ f \in \mathrm{Hom}(X,Z)$ be their composition. We want to understand the relationship between the matrices