Consider a set equipped with a well quasi-order
. For the application to piecewise testable languages, the set
is the set of all words over a given finite alphabet, and
is the Higman ordering. Nevertheless, result presented here is true for well quasi-ordered sets in general, so we present it like that.
For two subsets , define an zigzag between
and
to be a sequence
which alternates between and
, i.e. if one element is in
then the next one is in
, and vice versa. Zigzags can be finite or infinite. If
and
have a common element
, then there
is a zigzag of infinite length.
Zigzag Theorem. Let be subsets of a set
equipped with a well quasi-order. Then the following conditions are equivalent
The rest of this page is devoted to proving the Zigzag Theorem.
1 implies 2. Suppose that and
can be separated by a set
which is a Boolean combination of upward closed sets
As we progress along a zigzag, elements of the zigzag belong to more and more of the sets among , and therefore all but finitely many elements of the zigzag must belong to the set
, so it cannot be a separator.
2 implies 3. Consider the following graph, call it the zigzag graph: the vertices are elements of . There is an edge from every
to all elements in
, and likewise there is an edge from every
to all elements in
. A zigzag is the same thing as a path in the zigzag graph. Consider also the optimised zigzag graph, where the vertices are the same, but there are edges from
only to the minimal elements
, and likewise for
there are edges only to minimal elements of
. The point of the optimised zigzag graph is that it every vertex has finite degree (i.e. finitely many outgoing edges), because the outgoing edges yield an antichain, and antichains are finite.
It is not difficult to see that for every path in the zigzag graph, there is a path of same length in the optimised zigzag path (conversely, every path in the optimised zigzag graph is a path in the zigzag graph) . Therefore, to prove the implication from 2 to 3, it suffices to prove that if the optimised zigzag graph contains arbitrarily long paths, then it contains an infinite path. The optimised zigzag graph is actually a finite union of trees, whose roots correspond to minimal elements in , and therefore the König Lemma proves that if it contains arbitrarily long paths, then it contains an infinite path.
3 implies 1. Let us assume that zigzags between and
have length at most
. For
, define
so that is the set those elements of
which admit zigzags of length at most
. Here is a picture of these sets for
, including a zigzag of length 4 that begins in
Define and
to be empty. By induction on
, we prove that there exists a Boolean combination of upward closed sets
which separates
from
. This is illustrated in the following picture for
and
.
The induction base is when , in which case
is empty and therefore
can also be empty.
Consider the induction step, i.e. assume that the property has been proved for now want to prove it for
. Consider the upward closure of the set
. We know that this upward closure is is disjoint with
, Likewise, the upward closure of
is disjoint with
. This situation is shown in the following picture for
and
.
Therefore, can be defined to be the upward closure of
minus the upward closure of
and then finally plus
.
Leave a Reply