Let M be (s, t) where s is a set of states, and t is a subset of s×s, called the transitions. 

We say that f : s → W, where W is an arbitrary set, is *invariant* over M iff
    f(x) = f(y) for all (x,y) in t

S = set of squares on a chess board
f(s) = color of square s (in S)