A relation on `S` is a subset of `S^2`. Note that this can have two different representations, as a set of tuples `R \subseteq S \times S` and as a predicate on tuples `S \to 2`.

A particularly well-behaved class of relations is called equivalences that satisfy:

• Reflexivity: `\forall a \in S.\sim a \sim a`;
• Symmetry: `\forall a, b \in S.\sim a \sim b \Longrightarrow b \sim a`;
• Transitivity: `\forall a, b, c \in S.\sim a \sim b \land b \sim c \Longrightarrow b \sim c`.

We denote the set of all equivalences on a set `S` as `\text{Eq}(S)`.

Given two equivalence relations `R_1` and `R_2`, `R_2` is finer than `R_1` if `x\sim R_2\sim y` implies `x\sim R_1\sim y`, but not necessarily vice versa. This can be expressed as `R_2 \subseteq R_1` if we represent relations as subsets of `S^2`.

"Finer than" is a partial order on the `Eq(S)`. Does this partial order have an upper bound, the finest equivalence relation? The answer is yes, and it is called equality, `=`, which corresponds to the diagonal `\{ (a, a) | a \in S \} \subseteq S^2`.

Similarly to how we have defined relations on a set `S`, we define relations between two sets `A` and `B` as either a subset of `A \times B` or a predicate on pairs `A \times B \to 2`.

Functions between two sets `A` and `B` are left-total functional relations (sometimes this representation of functions as relations is called function's graph). A relation `R` is left-total if `\forall a \in A. \exists b \in B. \langle a, b\rangle \in R`. A relation is functional if `\langle a, b\rangle \in R \Longrightarrow \neg\exists b_{1} \in B. b \neq b_{1} \land \langle a, b_{1}\rangle \in R`, or in other words there is at most one `b` related to any given `a`; yet another way of stating this, which doesn't require negation, is `\langle a, b_1\rangle \in R \land \langle a, b_2\rangle \in R \Longrightarrow b_1 = b_2`. Both requirements can be expressed together as `\forall a \in A. \exists! b \in B. \langle a, b\rangle \in R`.

The collection of all functions from a set `A` to a set `B` is itself a set, denoted `B^A`.

Functions can be sequentially composed as relations, `F \circ G = { \langle a, c\rangle \in A \times C | \exists b \in B. \langle a, b\rangle \in G \land \langle b, c\rangle \in F }`. Notice that the left-totatily of `F` and `G` implies left-totality of `F \circ G` and similarly for functionality. If we think of composition as searching for a path `A \to B \to C` through the adjacent function graphs, it becomes clear that composition is associative.

Given two sets `A \subseteq B`, the inclusion gives rise to an injection `i : A \rightarrow B` that sends every object to itself, `i = \{ \langle a, a\rangle | a \in A \}`. In the case of `A = B` this corresponds to the identity function on `A`, `\forall a \in A. id(a) = a`.

If `f : A \to B` and `S \subseteq A`, then `f(S) := { b \in B | \exists a \in S. b = f(a) }`. `f(A)` is called the image of `f`, denoted `im f`.

`f|_S` denotes a restriction of `f` to the subset `S`: a function `f|_S : S \rightarrow B`, such that `\forall s \in S f|_S(s) = f(s)`. In other words, it's the composition with inclusion function, `f \circ i`. Note that `f(S) = im f|_S`.

A multiset is a function `f : A \rightarrow \mathbb{N}_{+}` or alternatively a functional relation between `A` and `\mathbb{N}_{+}`. Conceptually multisets are sets with possible repetitions.

An indexed set `\{a_{i}\}_{i \in I}` is a function `I \rightarrow A`. If `I` is `\{1, ... n\}` for some `n \in \mathbb{N}`, then `\{a_i\}` is usually called a sequence. Note that an infinite sequence of elements can be represented as `\mathbb{N} \rightarrow A`.

A function `f : A \rightarrow B` is injective (or an injection or one-to-one) if `a_1 \neq a_2 \Longrightarrow f(a_1) \neq f(a_2)`, or alternatively `f(a_1) = f(a_2) \Longrightarrow a_1 = a_2` (contrapositive). Conceptually, injections send different elements to different elements. Another way of stating that `f` represented as a graph `F \subseteq A \rightarrow B` is injective is `\langle a_{1}, b\rangle \in F \land \langle a_{2}, b\rangle \in F \Longrightarrow a_{1} = a_{2}`, compare this to functionality condition (1).

A function `f : A \rightarrow B` is surjective (or an surjection or onto) if `\forall b \in B. \exists a \in A. f(a) = b`, or alternatively `\neg\exists b \in B. \forall a \in A. f(a) \neq b`, or `im f = B`. Conceptually, surjections "cover" the entirety of their target set. Compare the first definition to left-totality condition (2).

Injections are written as `f : A \hookrightarrow B` and surjections as `f : A \twoheadrightarrow B`.

If `f` is both injective and bijective, it is called bijective (or a bijection or one-to-one and onto or isomorphism of sets). If f is an isomorphism, we can denote it as `f : A \leftrightarrows B` (notation in the book is different).

Suppose that `f : A \leftrightarrows B` has graph `F \subseteq A \times B`. Notice how (1) and (2) imply that if we flip `F` around, `F^* = \{ \langle b, a\rangle \in B \times A | \langle a, b\rangle \in F \}`, we'll get a left-total and functional relation. A function corresponding to such a graph is called `f`'s inverse and is denoted `f^{-1} : B \leftrightarrows A`. If we compose `f` with `f^{-1}` on either side, we'll get an identity function, either on `A` or `B`. From our construction it also follows that `f^{-1}` is an isomorphism itself. Strictly speaking, `f^{-1}` is not just a function but also a proof that `f` is bijective (since it is required to prove that `f^{-1}` is a function), therefore `f^{-1}` is meaningless unless `f` is a bijection.

Given some `f : A \leftrightarrows B`, `f \circ f^{-1} = id^{B}` and `f^{-1} \circ f = id^{A}` specify `f^{-1}` uniquely, since `f \circ a = id^{B} \land f \circ b = id^{B} \land a \circ f = id^{A} \land b \circ f = id^{A}` implies `a = a \circ f \circ b = b`. `(f \circ g) \circ (g^{-1} \circ f^{-1}) = f \circ (g \circ g^{-1}) \circ f^{-1} = id`, which means that `(f \circ g)^{-1} = g^{-1} \circ f^{-1}`. This can be generalized to an arbitrary `(f_{1} \circ f_{2} \circ f_{3} \circ ...)^{-1}`.

Identity function is bijective.

`A \cong B` is defined as `\exists f : A \leftrightarrows B`. From the previous three paragraphs it follows that `\cong` is a reflexive (identities are bijective), symmetric (`f^{-1}` is an isomorphism), and transitive (uniqueness + the construction for `(f \circ g \circ h)^{-1}`) relation. Therefore, `\cong` is an equivalence relation on sets. It is the same equivalence as the equality of set cardinalities, `|A| = |B|`, which can be easily shown for finite sets.

Given an `f : A \rightarrow B`, `g : B \rightarrow A` together with a proof `f \circ g = id^{B}` is called right-inverse of `f`, and `g : B \rightarrow A` together with a proof `g \circ f = id^{A}` is called left-inverse of `f`.

Suppose that `F` is some relation, and `F* = \{ \langle b, a\rangle \in B \times A | \langle a, b\rangle \in F \}`. Then `F \circ F^* = \{ \langle b_{1}, b_{2}\rangle \in B \times B | \exists a \in A. \langle b_{1}, a\rangle \in F^* \land \langle a, b_{2}\rangle \in F \} = \{ \langle b_{1}, b_{2}\rangle \in B \times B | \exists a \in A. \langle a, b_{1}\rangle \in F \land \langle a, b_{2}\rangle \in F \}`, similarly `F^* \circ F = \{ \langle a_{1}, a_{2}\rangle \in A \times A | \exists b \in B. \langle a_{1}, b\rangle \in F \land \langle a_{2}, b\rangle \in F \}`. We can see that `F \circ F^*` is diagonal iff `(\exists a \in A. \langle a, b_{1}\rangle \in F \land \langle a, b_{2}\rangle \in F) \Longleftrightarrow b_{1} = b_{2}` and `F^* \circ F` is diagonal iff `(\exists b \in B. \langle a_{1}, b\rangle \in F \land \langle a_{2}, b\rangle \in F) \Longleftrightarrow a_{1} = a_{2}`.

Let's deal with `F \circ F^*` first. Decompose `(\exists a \in A. \langle a, b_{1}\rangle \in F \land \langle a, b_{2}\rangle \in F) \Longleftrightarrow b_{1} = b_{2}` into two implications:

• (`\Longrightarrow`) Pulling `\exists` out of implication we get the condition of left-functionality of `F`.
• (`\Longleftarrow`) `\forall b \in B. \exists a \in A. \langle a, b\rangle \in F` is right-totality of `F`.

Therefore right-totality and left-functionality imply the existence of a right-inverse of a relation. Surjectivity (right-totality) implies the existence of a right-inverse of a function.

Dually (from the symmetry between `F` and `F^*`), left-totality and right-functionality imply the existence of a left-inverse of a relation. Injectivity (right-functionality) implies the existence of a right-inverse of a function.

The existence of a left-inverse `G` of a relation `F` means that `G \circ F = \{ \langle a_{1}, a_{2}\rangle \in A \times A | \exists b \in B. \langle a_{1}, b\rangle \in F \land \langle b, a_{2}\rangle \in G \}` is diagonal. This is equivalent to `(\exists b \in B. \langle a_{1}, b\rangle \in F \land \langle b, a_{2}\rangle \in G) \Longleftrightarrow a_{1} = a_{2}`. * (`\Longleftarrow`) `\forall a \in A. \exists b \in B. \langle a, b\rangle \in F \land \langle b, a\rangle \in G` - right-totality of `G` and left-totality of `F`. * (`\Longrightarrow`) `\langle a_{1}, b\rangle \in F \land \langle b, a_{2}\rangle \in G \Longrightarrow a_{1} = a_{2}`. Let `\langle a_{1}, b\rangle \in F \land \langle a_{2}, b\rangle \in F`. Assume `G` is left-total, then `\exists x \in A. \langle b, x\rangle \in G`, and both `\langle a_{1}, b\rangle \in F \land \langle b, x\rangle \in G \Longrightarrow a_{1} = x` and `\langle a_{2}, b\rangle \in F \land \langle b, x\rangle \in G \Longrightarrow a_{2} = x`, hence `\langle a_{1}, b\rangle \in F \land \langle a_{2}, b\rangle \in F \Longrightarrow a_{1} = a_{2}`.

Therefore existence of a left-inverse of a relation implies its left-totality. If left-inverse is a left-total, then the relation is right-functional (injective if it's a function).

Dually, existence of a right-inverse of a relation implies its right-totality (surjectivity if it is a function). If right-inverse is right-total, then the relation is left-functional.

If there is both a left- and a right-inverse, then the relation is both left and right total. It is bijective if it is a function.

If a function is not a bijection, `f^{-1}` is sometimes still used to indicate the relation `F^*` as we defined it above where `f^{-1}(T) := { a \in A | f(a) \in T }`.

A function `f : A \rightarrow B` is a monomorphism (or monic) if `\forall Z \in \text{Set}. \forall \alpha_{1}, \alpha_{2} \in Z \rightarrow A. f \circ \alpha_{1} = f \circ \alpha_{2} \Longrightarrow \alpha_{1} = \alpha_{2}`.

If a function is injective, it has a left-inverse. From associativity, `\alpha_{1} = f^{-1} \circ f \circ \alpha_{1} = f^{-1} \circ f \circ \alpha_{2} = \alpha_{2}` given that `f \circ \alpha_{1} = f \circ \alpha_{2}`. So injectivity implies that a function is monic.

Suppose a function is monic, `f \circ \alpha_{1} = f \circ \alpha_{2} \Longrightarrow \alpha_{1} = \alpha_{2}`. We want to prove that `f` is right-functional, `\langle a_{1}, b\rangle \in F \land \langle a_{2}, b\rangle \in F \Longrightarrow a_{1} = a_{2}`. Take `\alpha_{1}` and `\alpha_{2}` to be functions that map some singleton set `\{*\}` to `a_{1}` and `a_{2}`. Since `f` maps to `b`, both `f \circ \alpha_{1}` and `f \circ \alpha_{2}` map `*` to `b`. Therefore they are equal as functions, and hence `\alpha_{1} = \alpha_{2}`, `a_{1} = a_{2}`.

A function is injective iff it is monic.

A function `f : A \rightarrow B` is an epimorphism (or epic) if `\forall Z \in \text{Set}. \forall \alpha_{1}, \alpha_{2} \in B \rightarrow C. \alpha_{1} \circ f = \alpha_{2} \circ f \Longrightarrow \alpha_{1} = \alpha_{2}`.

If a function is surjective, it has a right-inverse. Similarly to the injectivity case, we can prove that surjective ⟹ epic.

Suppose a function `f` is epic. We would like to prove that `f` is right-total, `\forall b \in B \exists a \in A. \langle a, b\rangle \in F`. Let `C = \{0, 1, 2\}`. For any `b \in B`, construct two functions `\alpha_{1}` and `\alpha_{2}` that map it to `1` and `2` respectively and the rest of the elements to `0`. `\alpha_{1} \neq \alpha_{2}`, and since `f` is epic, we get `\alpha_{1} \circ f \neq \alpha_{2} \circ f`, which means that `b` must be in the image of `f`, hence it is surjective.

A function is surjective iff it is epic.

Some basic examples include projections from products (surjective and epic) and injections into coproducts (injective and monic).

If `\sim` is an equivalence relation on a set `A`, there is a canonical projection `A \twoheadrightarrow A/\sim`, mapping each element of `A` to its equivalence class.

Given a function `f : A \rightarrow B`, we can define an equivalence relation `\sim` on `A` as follows: `a_{1} \sim a_{2} \Longleftrightarrow f(a_{1}) = f(a_{2})`. This allows us to decompose the function as `A \twoheadrightarrow A/\sim \leftrightarrows im f \hookrightarrow B`, where the first function is the canonical projection onto equivalence classes.