Notebook 20: Finite-Index Congruences & Saturation
Congruences and Saturation
The algebraic route to complementation partitions finite words into finitely many classes, then describes infinite words by products of classes. The whole idea rests on two everyday intuitions.
A congruence \(\equiv\) on \(\Sigma^{*}\) is an equivalence relation that is respected by concatenation: if \(u\equiv u'\) and \(w\equiv w'\) then \(uw\equiv u'w'\). It has finite index if it has finitely many classes. The simplest non-trivial example — think even/odd — is parity of length over \(\Sigma=\{a,b\}\): \[ u \equiv_{\mathrm{par}} u' \iff |u|\equiv|u'| \pmod 2. \] Two classes: E (even length, including \(\varepsilon\)) and O (odd length). The symbols read are irrelevant; only length parity matters.
A language \(L\) is saturated by \(\equiv\) if it is a union of whole classes — equivalently, \(u\equiv u'\) never separates a member from a non-member. Saturation is exactly the property that lets us complement by flipping which classes we keep.
Widget 1: classes and concatenation
Type two words. Each gets a class; their concatenation lands in the class predicted by the class arithmetic (E acts like \(0\), O like \(1\), modulo \(2\)) — never depending on which letters were used.
| · | E | O |
|---|---|---|
| E | E | O |
| O | O | E |
Class of a word = parity of its length. The table is just addition mod 2 — that concatenation respects it is what makes ≡par a congruence.
Widget 2: is \(L\) saturated?
A language is saturated iff every class lies entirely inside or entirely outside it. The widget probes each class with two representatives; if one is in \(L\) and the other is not, the class is split and \(L\) is not saturated by \(\equiv_{\mathrm{par}}\).
Parity is a toy congruence — it only saturates length-parity languages. The chapter’s real congruence, \(\approx_{\mathcal A}\), is much finer: it remembers which states an automaton can traverse on a word, and it saturates the language of any Büchi automaton. That is the subject of Notebook 21.