• tags :: category theory

• source :: ACT4E - Session 2 - Connection on Vimeo

Notes

• Example: electrical distribution network

  • Power plants -> high voltage nodes -> low voltage nodes -> consumers

  • Can be represented as a directed graph

• Relation :: A set X to a set Y is a subset of $X \times Y$ (cartesian product)

  • Example: Given $X {x_1,x_2,x_3}, Y {y_1,y_2,y_3,y_4}$, relation $R \subseteq X \times Y$ is given by $R = \{ \langle x_1,y_1 \rangle, \langle x_2,y_3 \rangle, \langle x_2,y_4 \rangle \}$

  • Note that this is not the whole cartesian product!

• We could write the above relation as $X \xrightarrow{\text{R}} Y$, or $R: X \to Y$

• Relations are a type of morphism

• Relations can be composed

  • Given $X \xrightarrow{\text{R}} Y$, $Y \xrightarrow{\text{S}} Z$, we can compose the relation $R \circ S$

  • $R \circ S := \{\langle x, z \rangle \in X \times Z | \exists y \in Y: \langle x, y \rangle \in R \land \langle y, z \rangle \in S \}$ which is the relation $X \to Z$

• The category Rel (Relation of sets and relations:

  • Objects: all sets

  • Homsets: given sets X and Y: $Hom_{Rel}(X,Y) := \mathcal{P}(X \times Y)$ = all subsets of $X \times Y$

  • Identity morphisms

  • Composition (above)

• Functions are *special types of relations*

  • $R_f := \{\langle x,y \rangle \in X \times Y | y = f(x)\}$

• A function $f: X \to Y$ is a relation $R_f \subseteq X \times Y$ such that:

  1. $\forall x \in X \exists y \in Y : \langle x,y \rangle \in R_f$ - every element of the source X gets mapped by f to some element of the target Y

  2. $\exists \langle x_1,y_1 \rangle, \langle x_2,y_2 \rangle \in R_f$ holds: $x_1 x_2 \Rightarrow y_1 y_2$

• Functions must therefore be defined everywhere

  • For all values in X, there should be a corresponding Y value

  • The opposite is not necessarily true

• Lemma: Composition of relations generalizes the composition of functions

  • $X \xrightarrow{\text{f}} Y \xrightarrow{\text{g}} Z$ implies $R_f \circ R_g = R_{f \circ g}$

• Properties of relations:

  • Surjective: $\forall y \in Y \exists x \in X : \langle x,y \rangle \in R$

  • Injective:

  • Defined everywhere

  • Single valued

• Relations can be transposed

  • $R^T := \{\langle y,x \rangle \in Y \times X | \langle x,y \rangle \in R\}$

  • For $R: X \to Y$, the transpose is $R^T: Y \to X$

• The transpose of the transpose of R is R

• The transpose relation holds all the same properties as the original relation

• An Endorelation on set X is a relation $X \to X$

  • Equality, for example, is an endorelation

  • "Less than or equal" is also an endorelation

• An endorelation is symmetric if:

  • $\forall x,x' \in X: \langle x,x' \rangle \in R \Leftrightarrow \langle x',x \rangle \in R$

  • Example: x1 -> x2 and x2 -> x1

  • Example: The relation "less than or equal" on all natural numbers is not symmetric

• An endorelation is relfexive if:

  • $\forall x \in X : \langle x,x \rangle \in R$

  • Example: less than or equal on all natural numbers in reflexive

    • n <= n is reflexive

• An endorelation is transitive if:

  • $\langle x,x' \rangle \in R$ and $\langle x',x'' \rangle \in R \Rightarrow \langle x,x'' \rangle \in R$

  • "Less than or equal" is transitive on all natural numbers

    • l <= m and m <= n -> l <= n

  • This property is reminiscent of composition in a category

• An equivalence relation is an endorelation that is symmetric, relfexive, and transitive

  • Notation: $x \sim x'$ if $\langle x,x' \rangle \in R$

• Partition of set X is a collection of subsets which are disjoint pairwise

• Category theory formalizes different notions and degrees of sameness