April 25, 2024
A relation is a subset of the cartesion product of sets. The domain of a relation R\subseteq X\times Y is \operatorname{dom}R = \{x\in X\mid(x,y)\in R\text{ for some }y\in Y\}. The codomain is \operatorname{cod}R = \{y\in Y\mid(x,y)\in R\text{ for some }x\in X\}. Write xRy for (x,y)\in R. The right coset of x\in X is xR = \{y\in Y\mid xRy\}\subseteq Y and XR = \cup_{x\in X}xR = \operatorname{cod}R. The left coset of y\in Y is Ry = \{x\in X\mid xRy\}\subseteq X and RY = \cup_{y\in Y}Ry = \operatorname{dom}R.
If R\subseteq X\times Y and S\subseteq Y\times Z are relations their composition is SR\subseteq X\times Z where x(SR)z if and only if xRy and ySz for some y\in Y. This is equivalent to xR\cap Sz not being empty. If 1_U is the identity relation \{(u,u)\mid u\in U\}, then R1_X = R and 1_YR = R.
Exercise. If R\subseteq X\times Y, S\subseteq Y\times Z, and T\subseteq Z\times W then (TS)R = T(SR).
The set of all relations \mathbf{Rel} is a category.
The transpose, or conjugate, of a relation R\subseteq X\times Y is R'\subseteq Y\times X where yR'x if and only if xRy, x\in X, y\in Y.
Exercise. If R\subseteq X\times Y and S\subseteq Y\times Z are relations then (SR)' = R'S'.
A monoid is a set M with an associative binary operation μ\colon M\times M\to M and an identity element 1\in M; μ(a,μ(b,c)) = μ(μ(a,b),c) and μ(m,1) = m = μ(m,1), m\in M. The set of relations on X\times X is a monoid.
A relation R\subseteq X\times X is transitive if RR \subseteq R. A relation R\subseteq X\times X is reflexive if 1_X \subseteq R.
A relation R\subseteq X\times X is symmetric if R = R' and antisymetric if R\cap R' = 1_X.
Product projections are indexing.
A set is the coproduct of its elements.
Total order is bijection n \leftrightarrow S.
X^n is n\to X. π_i\colon X^n\to X. X^{n\times m} is n\times m\to X is n\to(m\to X). Multidimensional indexing is currying.
Currying does not have a good notation.
F_A(X) = X \times A, G_B(Y) = Y^B = B\to Y are adjoint functors.
The adjunction is an isomorphism so left or right doesn’t matter.
f\colon X\times Y\to Z, f_1\colon X\to(Y\to Z).
f\colon F_Y(X)\to Z, f_1\colon X\to G_Y(Z).
g\colon X\to(Y\to Z), g^1\colon X\times Y\to Z.
g\colon X\to G_Y(Z), g^1\colon F_Y(X)\to Z.