Topology on profinite words

Mikołaj Bojańczyk

zajęcia / courses

The key property of a profinite word is that for profinite word, we can send regular queries to it, i.e. we can ask if it belongs to a regular language. For a regular language $L \subseteq \Sigma^*$ , define $\bar L$ to be the set of profinite words which answer yes to this language. In the definition of Cauchy sequences, this is the set of Cauchy sequences where some tail is contained in $L$ , while in the definition of profiles, this is the set of families that contain $L$ .

Let us define the distance between two profinite words to be the size of the smallest regular $L$ such that $\bar L$ separates between the two profinite words. As in the case of the distance on normal words, this is a distance, even an ultrametric.

Lemma. The set of profinite words is a compact metric space.

Proof. We need to show that every sequence of profinite words has a convergent subsequence. We do this by considering some enumeration of all regular languages, and for each $n$ we choose a profinite word $w_n$ from the sequence such that infinitely elements of the sequence agree with $w_n$ on the first $n$ regular languages. $\Box$

To understand this metric space, it is a good exercise to think of the open balls. Consider some profinite word $w$ (we use the same notation for word as profinite words). Straight from the definition, the ball of radius $\epsilon$ around $w$ consists of those profinite words which agree with $w$ on languages of size at most $1/\epsilon$ . Since there are finitely many such languages, one can take their intersection, call it $L$ , and therefore the open ball is the set of those profinite words that belong to $L$ . In other words, this open ball is $\bar L$ . Therefore, the set $\bar L$ , ranging over regular languages $L$ , form a basis of the topology.

In the space of profinite words, the profinite words that correspond to normal words (i.e. constant Cauchy sequences) are a dense subset. This is because for every profinite word and every size $n$ , one can choose a normal word which belongs to the intersection of all size $\le n$ languages in the profile of the profinite word. Also observe that every normal word $w$ is an isolated point in the profinite space, because it is the only inhabitant of the open ball $\overline{\set{w}}$ .

Regular languages are clopen. Recall that a clopen set is one that is both closed and open.

Lemma. The mapping $L \mapsto \bar L$ is a one-to-one correspondence between regular languages of finite words and clopen sets of profinite words.

Proof. We first show that if $L \subseteq \Sigma^*$ is regular, then $\bar L$ is clopen. If two profinite words are at distance at most $1/|L|$ then they give the same answer to $L$ , and therefore $L$ is open (as a union of open balls). The same argument works for the complement of $L$ , and therefore $L$ is closed as well.

The mapping $L \mapsto \bar L$ is injective, because different regular languages contain different words, and these words are special cases of profinite words.

Finally, let us prove that every clopen set of profinite words is of the form $\bar L$ . Let $X$ be a clopen set. As an open set, $X$ is a union of balls. As a closed subset of a compact space, from any cover of $X$ one can extract a finite subcover, and therefore $X$ is a finite union of open balls. Every open ball is of the form $\bar L$ for some regular language $L$ . Finally, it is not difficult to see that

$\overline{L \cup K} = \bar L \cup \bar K$

and the result follows by closure of regular languages under finite union. $\Box$

Concatenation of profinite words. In all of the results presented so far, it was not really important that regular languages were used. One could take any countable family $L_1,L_2,\ldots$ of languages, e.g. the decidable languages, and define the distance between two words to $1/n$ where $n$ is the index of the first language separating the two words. We now discuss a result where regularity is used, and which would not work for classes including nonregular languages, e.g. the decidable languages. The concatenation of profinite words is defined most easily on Cauchy sequences: by concatenation the two Cauchy sequences pointwise (i.e. the $n$ -th word in the concatenation sequence is the concatenation of the $n$ -th words in the argument sequences).

Lemma. The operation defined above is well-defined (i.e. it depends only on the profiles of the Cauchy sequences being concatenated) and it is a uniformly continuous function from pairs of profinite words to profinite words.

Proof. Let us first prove that the operation is well-defined. It is easy to see that the profile of a Cauchy sequence is uniquely determined by saying, for each monoid homomorphism

$h : \Sigma^* \to M,$

what is the value of the tail of this sequence under the homomorphism (this value must be unique). If one Cauchy sequence has value $m_1$ , and another Cauchy sequence has value $m_2$ , then concatenating the two sequences pointwise will give the product $m_1 \cdot m_2$ , and this result is stable under replacing Cauchy sequences by equivalent ones.

Let us now prove the uniform continuity. We need to show that for every $\epsilon > 0$ there is some $\delta > 0$ such that

$\distance(w,w'), \distance(v,v') \le \delta \quad \Rightarrow \quad \distance(wv,w'v')\le\epsilon.$

As we have already discussed, two profinite words are at distance at most $\epsilon$ if and only they belong to the same regular languages of size at most $1/\epsilon$ . Let

$h : \Sigma^* \to M$

be a monoid homomorphism which recognizes all languages of size at most $1/\epsilon$ . If we define $\delta$ to be $1/|M|$ then the implication above is easily seen to be true. $\Box$

zajęcia / courses

Topology on profinite words

Leave a Reply