congruence

Definition

• Context:
  • A monoid $\mathcal{M}: (M, e, *)$
• A congruence on $\mathcal{M}$ is an equivalence relation $\sim$ on $\mathcal{M}$ such that $\forall m, m', n, n' \in \mathcal{M}$, if $m \sim m'$ and $n \sim n'$, then $m * n \sim n' \sim m'$
• An equivalence relation that interacts well with the multiplication formula of a monoid is called a congruence on that monoid

Equivalence relation

• for a set $X$, an equivalence relation on it is a subset $R \subseteq X \times X$ that satisfies reflexivity, symmetry, and transitivity

Path Equivalence Declaration (PED)

• Context:
  • let $G = (V, A, src, tgt)$ be a graph
  • let $\text{Path}_G$ denote the set of paths in $G$
• A PED is an expression of the form $p \simeq q$, where $src(p) = src(q)$ and $tgt(p) = tgt(q)$
• A congruence on G is a relation $\simeq$ on $\text{Path}_G$ that has the following properties
  • it’s an equivalence relation
  • if $p \simeq q$ then $src(p) = src(q)$
  • if $p \simeq q$ then $tgt(p) = tgt(q)$
• Any set of path equivalence declarations (PEDs) generates a congruence

reference:

• Category Theory for the Sciences]