### Chapter 1: Generative Effects: Orders and Galois Connections

Goals:

- Review of notation and recap of basic notions in set theory.
- Set the stage for more advanced Applied Category Theory (ACT) topics in later chapters.
- Introduce the notion of preorder.

#### 1. Recap on notation, sets, and functions

**Elementary sets.**

- $\emptyset$: empty set; it has no elements and it is a subset of every other set.
- $\{1\}$: set with just one element (in this case, $1$); we may use other symbols, e.g. $\{\star\}$ or $\{ \square\}$.
- $\{1, 2, 3\}$, $\{\star, \square, \odot\}$: examples of sets with three elements.
- $\mathbb{B}$: set of booleans; it has two elements, `true` and `false`.
- $\mathbb{N}$: set of natural numbers, $0, 1, 2, \ldots$
- $\underset{\bar{}}{n}$ for any $n \in \mathbb{N}$: the n-th ordinal with elements $1, 2, \ldots, n$ (I prefer $[n]$).
- $\mathbb{Z}$: set of integers, $\ldots, -2, -1, 0, 1, 2, \ldots$
- $\mathbb{R}$: set of real numbers, $\pi, \sqrt{2}, 1, \ldots$

**Definition (relation).** (D1.8 and D1.13). A relation between sets $X$ and $Y$ is a subset of their Cartesian product, i.e. $R \subseteq X \times Y$, where $X \times Y := \{(x, y) : x \in X, y \in Y\}$. A binary relation on $X$ is a relation between $X$ and $X$.

Observations:

1. If $X = B_{\infty}^2(1) \subseteq \mathbb{R}^2$ and $Y = [0, 1] \subseteq \mathbb{R}$, then $X \times Y$ is a cilynder $C$ in $\mathbb{R}^3$ and a relation is any subset of $C$.
2. The identity map, denoted $id_X : X \to X$, $x \mapsto x$, can be seen as a binary relation on $X$.
3. Another important binary relation is that given by $\leq$ over the set of real numberss $\mathbb{R}$.
4. Using a symbol e.g. $\star$ and writing $a \star b$ to mean $(a, b) \in R$ is called *infix notation*.

A special class of binary relations are *equivalence relations*, which we generically denote with $\sim$ (tilde). These are binary relations that satisfy:

(a) $a \sim a$, $\forall a \in A$ (*reflexivity*)
(a) $a \sim b$ iff $b \sim a$, $\forall a, b \in A$ (*symmetry*)
(a) $a \sim b$ and $b \sim c$ implies $a \sim c$ $\forall a, b, c \in A$ (*transitivity*)

**Definition (partition).** (D1.10). A partition of a set $A$ consists of a set $P$ of labels and another set of (nonempty) subsets of $A$, $\{A_p\}_p$ called the set of parts, s.t. for each $p \in P$ it holds that it covers the whole set, i.e.

$$
A = \bigcup_{p \in P} A_p
$$
and such that the parts are pairwise disjoint.

Observations:

1. There is a one-to-one correspondence between the ways to partition $A$ and the equivalence relations on $A$.
2. (D1.16) Given $A$ and an equivalence relation $\sim$ of $A$, we say that the quotient $A/\sim$ of $A$ under $\sim$ is the set of parts of the corresponding partition.

**Definition (function).** (D1.17 and D1.23). Given sets $S$ and $T$, a function from $S$ to $T$ is a subset $F \subseteq S \times T$ s.t. for all $s \in S$, there exists a unique $t \in T$ with $(s, t) \in F$.

Observations:

1. The function $F$ is often denoted $F : S \to T$ and wr write $F(s) = t$ or $s \mapsto t$ to mean $(s, t) \in F$.
2. For any $t \in T$ the preimage of $t$ along $F$ is the subset $f^{-1}(t) := \{ s \in S : F(s) = t\}$.
3. A function is called surjective (or a surjection) if for all $t \in T$ there exists $s \in S$ with $F(s) = t$.
4. A function is called injective (or an injection) if for all $t \in T$ and $s_1, s_1 \in S$ with $F(s_1) = t$ and $F(s_2) = t$ then $s_1 = s_2$.
5. A function is called bijective (or a bijection) if it is both surjective and injective.
6. (D1.23) Given functions $F : X \to Y$ and $G : Y \to Z$, their composite is the function $X \to Z$ defined to be $G(F(x))$ for any $x \in X$, that we write $G \circ F$.
7. A partition on a set $A$ can also be understood in terms of surjective functions out of $A$.

#### 2. Running example: `PointSystem`

#### 3. Preorders

**Definition (preorder).** (D1.25). A preorder relation on a set $X$ is a binary relation on $X$, denoted $\leq$, s.t.

(a) $x \leq x$ (*reflexivity*)
(b) $x \leq y$ and $y \leq z$ implies $x \leq z$ (*transitivity*)

Observations:

1. If $x \leq y$ and $y \leq x$, we write $x \simeq y$ and say that $x$ and $y$ are *equivalent*.
2. A pair $(X, \leq)$ consisting of a set together with a preorder relation is called a *preorder*. If $\leq$ is clear from the context, we may call $X$ a preorder. We also write $X_{\leq}$.
3. What is the connection between an equivalence relation on $X$ and a preorder on $X$?
4. A preorder is a category where we have at most one arrow from $a$ to $b$ for all elements $a, b$ in the category.
5. The booleans $\mathbb{B}$ form a preorder with $false \leq true$.
6. A preorder is a partial order if $x \leq y$, $y \leq x$ then $x = y$.
7. A partial order is a "loop-less" preorder.

**Definition (graph).** (D1.31). A graph $G = (V, A, s, t)$ consists of a set $V$ whose elements are called vertices, a set $A$ whose elements are called arrows, and two functions $s, t: A \to V$ known as the source and target functions respectively. Given $a \in A$ with $s(a) = v$ and $t(a) = w$, we say that $a$ is an arrow from $v$ to $w$.

A path in $G$ is any sequence of arrows such that the target of one arrow is the source of the next.

Observations:

1. Sequences of length 1 are just arrows $a \in A$ in $G$.
2. Sequences of length 0 correspond to starting and ending in the same vertex $v$, without traversing any arrows.

#### 4. Monotone maps

**Definition (monotone map).** (D1.54). A monotone map between preorders $(A, \leq_A)$ and $(B, \leq_B)$ is a function $f : A \to B$ such that for all elements $x, y \in A$, if $x \leq_A y$ then $f(x) \leq_B f(y)$.

**Definition (isomorphism between preorders).** (D1.70). Given preorderds $(P, \leq_P)$ and $(Q, \leq_Q)$, a monotone function $f : P \to Q$ is said to be an isomorphism if there exists a monotone function $g : Q \to P$ such that $g \circ f = id_P$ and $f \circ g = id_Q$.

Observations:

1. For any $p \in P$ and $q \in Q$, we have

$$
p = g(f(p)),\qquad q = f(g(q))
$$

2. We refer to $g$ as the inverse of $f$ and vice-versa, $f$ is the inverse of $g$.
3. If there is an isomorphism $P \to Q$ we say that $P$ and $Q$ are isomorphic.
4. An isomorphism between preorders is basically a relabeling of the elements.