Ramsey Decomposition Proof Lab

Ramsey decompositionTheorem. Every omega-word alpha belongs to U·V-omega for some classes U, V of a finite-index congruence (=), with V·V contained in V.Running example. The automaton has states s0, s1, s2 with F = {s1} and transitions s0-a->s1, s1-b->s2, s2-c->s2 (self-loop), s2-a->s1. The word alpha = abc·abcc·abccc··· has ever-growing gaps of c's and is not ultimately periodic, yet every block abc^n produces the same behaviour, so alpha decomposes as [epsilon]·V-omega for a single class V.Strategy. Build a second finite-index equivalence on the positions of alpha by colouring each pair of positions with the (=)-class of the segment between them. Pigeonhole gives an infinite pairwise-merging set of positions; persistence (congruence applied to a shared future suffix) makes that merge survive forever. A separate pigeonhole on cumulative-prefix classes gives infinitely many prefixes in one class V; persistence then transfers V's class onto each gap, turning them into genuine consecutive V-blocks. One witnessed concatenation transports, via congruence, to V·V contained in V.Proof outline.

Setup. The congruence (=) compares the finite segments between positions, not positions themselves; so build a relation on positions, colouring a pair (k, k') by the (=)-class of the shared-future segments alpha(k, m) and alpha(k', m).

Pigeonhole on positions. That relation inherits finite index from (=), so among any r+1 positions two must merge; run over all of N to get an infinite pairwise-merging sequence k0 < k1 < k2 < ...

Persistence. (=) is right-invariant, so appending the shared suffix to both sides shows: once two positions merge at some checkpoint m, they merge at every later checkpoint m' >= m.

Pigeonhole on segments. Independently, pigeonhole the cumulative prefixes alpha(k0, ki): infinitely many share one class V. This gives alpha in U·(infinitely many V-prefixes), but not yet consecutive blocks.

Thinning. Thin the sequence so that k0, ..., ki all merge at k(i+1); persistence transfers alpha(k0, k(i+1)) in V onto the gap, giving alpha(ki, k(i+1)) in V. Every consecutive block lies in V, so alpha in U·V-omega.

Idempotence. For one witnessed pair a = alpha(k0, k1), b = alpha(k1, k2) with ab in V, congruence gives xy = ab in V for all x = a, y = b in V; hence V·V contained in V.

Conclusion. alpha in U·V-omega with V·V contained in V — the Ramsey decomposition, holding even when alpha is not ultimately periodic.