Wilke’s Lemma

Mikołaj Bojańczyk

zajęcia / courses

What is a finite $\infty$ -monoid? A natural definition would be that the universe is finite. However, since the product operation is a function of type $M^\infty \to M$ , in principle it could be impossible to write down in a finite way. Fortunately, the situation is not so bad, because as Thomas Wilke showed, the product operation is already uniquely determined by a small subset of its arguments. This is analogous to the idea that for finite words, the monoid operation $M^* \to M$ is determined by its identity element and its binary part.

Lemma. An $\infty$ -monoid $M$ is uniquely determined by the values of its product operation on arguments of the form

$\epsilon \quad m \cdot n \quad m^\omega \qquad \text{with $m,n \in M$}$

Proof. Suppose that we want to determine $\pi(w)$ for some $w \in M^\infty$ . We want to do this without having full knowledge of $\pi$ , but only knowing that it is a legal product operation, and knowing its values for arguments as given in the statement of the lemma. As in a finite monoid, one observes that the value of the product operation on finite words is uniquely determined by its value on words of length zero and two (for words of length one, the operation must be the identity, by definition of an $\infty$ -monoid).

Therefore, it remains to consider the case when $w$ is infinite. By the Ramsey theorem, there exists a factorisation

$w = w_0 w_1 w_2\cdots$

such that all the words $w_i$ are nonempty, and there is some $m \in M$ such that

$\pi(w_1) = \pi(w_2) = \cdots = m$

This factorisation, and the value $m$ , are all determined by the information that we have about $\pi$ . By associativity, we know that

$\pi(w) = \pi(w_0 \cdot \pi(w_1) \cdot \pi(w_2) \cdots ) = \pi (w_0 mmm \cdots)$

Again by associativity, the above is equal to

$\pi(w_0 \pi(mmm\cdots))$

The value of $\pi(mmm \cdots)$ is determined by the information given in the statement of the lemma, using it we have reduced computing the value of $\pi(w)$ to computing the value of a finite word. $\Box$

zajęcia / courses

Wilke’s Lemma

Leave a Reply