ACT4E - Session 2 - Connection

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
• 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

Backlinks

• [[endorelation]]
• [[functions are a special type of relation]]
• [[relations]]