Fix some alphabet . Define a profinite implication to be a pair of profinite words
, which is written by
. We say that a regular language
satisfies the implication if
The following theorem, shows that profinite implications are exactly what is needed to characterize families of languages that are closed under union and intersection (and which contain the empty and full language).
Theorem. Let be an alphabet, and let
be a class of regular subsets of
. The following conditions are equivalent:
a) contains the empty and full languages, and is closed under union and intersection;
b) there is a set of profinite implications that defines
in the sense that a language belongs to
if and only if it satisfies all implications in
.
Proof. Let us begin with the easier implication from b) to a). It is easy to see that the empty and full languages satisfy all profinite implications, and therefore they must belong to any set defined by profinite implications. It remains to show that if regular languages and
satisfy all implications in a set
, then the same holds for their union and intersection. This follows straight from the definition of satisfying implications and the following two observations:
We are left with the implication from a) to b). Suppose that contains the empty and full languages. Define
to be the set of profinite implications that are satisfied by all regular languages in
. We claim that
defines
. Clearly every language in
satisfies all implications in
. It remains to show that if a regular language
satisfies all implications in
, then it belongs to
.
Lemma. For every profinite there is some
such that
Proof. Let be a profinite word outside
. This means that
violates the profinite implication
. Since
satisfies all profinite implications in
, it follows that the profinite implication
does not belong to
, and therefore it is violated by some language in
, call it
. The language
, as a language violating
, is such that
It follows that the intersection
is contained in . By compactness, a finite subintersection is already included in
. Since
is closed under finite intersection, the proving the lemma.
From the lemma it follows the sets , ranging over
, form a cover of the set
. Since
is clopen, there is a finite subcover, i.e.
for some languages . By since the closure operator distributes across union, and the family
is closed under finite union, it follows that
is equal to
for some
. Finally, as we have shown here, the closure operator is a one-to-one correspondence between regular languages and clopen sets, and therefore
.
Leave a Reply