The wreath product then becomes:
$X \wr Y \equiv (Q_X \times Q_Y, W)$
with the action of $W$ on an element of $Q_X \times Q_Y$ being defined as:
$(f : Q_Y \rightarrow S_X, s_y : S_Y) (q_x : Q_X, q_Y : Q_Y) \equiv ( f(q_y)(q_x) , s_y (q_y))$
it's a "follow the types" sort of definition, where we edit the right component
as $r_y \mapsto t_y(r_y)$ since that's all we can do. In the case of
the left component, we have a $q_x$, and we need to produce another element
in $Q_X$, so we "must use $f$". The only way to use $f$ is to feed it
a $t_y$. This forces us into the above definition.
§ Composition of wreath products
To show that its closed under composition, let's consider $(f, s_y), (g, t_y) \in W$
with $f, g: Q_Yg \rightarrow S_X$, and $s_y, t_y \in S_Y$. The result is
going to be:
$(f, s_y) (g, t_y) = (\lambda q_y. f(q_y) \circ g(q_y), t_y \circ u_y)$
§ Equivalences of subsets of states
Let $X = (Q, S)$ be a transition system. Given subsets $(a, b, \subseteq Q)$,
we shall write $b \leq a$ if either $b \subseteq a$ or there exists some $s \in S$
such that $b \subseteq sa$, where $s(a) \equiv \{ s(a_i) : a_i \in a\}$. We can
define an equivalence relation $a \sim b \iff a \leq b \land b \leq a$.
§ Note
$b \leq a \implies |b| \leq |a|$, since
$b \leq a$ means that $b \subseteq s(a)$. Note that $s$ is actually a
function $s: Q \rightarrow Q$, and a function mapped over a set can only
ever decrease the number of elements in a set, since a function can only
xglomp elements together; it can never break an element apart into two.
Hence, $b \subseteq sa \subseteq a$, and thus $|b| \leq |a|$.
Similiarly, $a \leq b \implies |a| \leq |b|$. Therefore, $b \sim a$ means
that $|b| = |a|$.
§ Theorem
for all $a, b \in Q_X$ such that
$a ~ b$ such that $b \subseteq s(a)$, we show that $b = s(a)$, and there exists
a $t \in S_X$ such that $a = t(b)$.
§ Proof
Since $b \subseteq s(a) \subseteq a$ and $|b| = |a|$, $b = s(a)$.
Therefore $s$ is a permutation. Hence, $s$ is invertible and there exists
an inverse permutation $t$ such that $a = t(b)$. We now need to show that
$t \in S_X$. To do this, first note that if the order of the permutation
$s$ is $n$, then $t = s^{n-1}$, since $t \circ s = s^{n-1} \circ s = 1_S$.
Since the semigroup $S$ is closed under composition $t = s^{n-1}$ is in $S$,
since it is $s$ composed with itself $(n-1)$ times.
§ Subset families of interest
We will be interest in a family of subsets of $Q_X$ called $A$, of the form:
- all sets of the form $s(Q)$ for all $s \in S_X$
- the set $Q$
- the empty set $\emptyset$
- all the singleton sets $\{ q \}$ for all $q \in Q$.
In the above set, we have $\leq$ and $\sim$ as defined above.
We note that the set $A$ is closed under the action of all $s \in S_X$.
For example, the empty set is taken to the empty set. All singleton
sets are taken to other singleton sets. For the full set $Q$, we add
the sets $s(Q)$ for all $s \in S_X$.
§ Height function
A height function for a transition system $X \equiv (Q_X, S_X)$ is a function
$h: A \rightarrow \mathbb Z$ such that:
- $h(\emptyset) = -1$.
- $h(\{ q \}) = 0 \forall q \in Q$.
- $a \sim b \implies h(a) = h(b)$ for all $a, b \in A$.
- $b < a \implies h(b) < h(a)$ for all $a, b \in A$.
The notation $b < a \equiv (b \leq a) \land \lnot (a \leq b)$.
(3) + (4) imply that two elements of the same height are either equivalent
or incomparable.
§ Pavings and bricks
for $a \in A$ such that $|a| > 1$, we denote by $B_a$ the set of all $b \in A$
what are maximal subsets of $a$. That is, if $b \in B_a$ then $b \subsetneq a$,
and $\not \exists c, b \subsetneq c \subsetneq a$. Equivalently, if there
exists a $c$ such that $b \subseteq c \subseteq a$, then $b = c$ or $b = a$.
Note that we can assert that $a = \cup_{b \in B_a} b$. This is because $B_a$
contains all the singletons of $Q_X$. so we can begin by writing $a$ as
a union of singletons, and then merging elements of $B_a$ into larger elements
of $B$, terminating when we cannot merge any more elements of $B_a$.
- The set $B_a$ is called as the paving of $a$.
- The elements of $B_a$ are called as the bricks of $a$.
§ Group of permutations for $a \in A$
Let us assume that there exists a $s \in S$ such that $s(a) = a$. Let $A_a$
be the set of all elements in $A$ contained in $a$:
$A_a = \{ A_i : A_i \in A, A_i \subseteq a \}$.
Recall that the set $A$ was closed under the action of all $s$, and hence,
since $s$ is a permutation of $a$, this naturally extends into a
permutation of $A_a$: $s A_a = A_a$. Now note that this induces a permutation
of the set $B_a$. This creates a transition system:
$\begin{aligned}
&G_a \equiv \{ s \in S : s a = a \} \\
&H_a \equiv (B_a, G_a) \\
\end{aligned}$
We have already shown how if $s \in S$ defines a permutation of some set $X$
by its action, then its inverse also exists in $S$. So, this means that
$G_a$ is in fact a transition group that acts on $B_a$.
It might turn out that $G_a = \emptyset$. However, if $G_a \neq \emptyset$,
then as stated above, $G_a$ is a group.
We will call such a transition group a generalized transition group , since
either $G_a = \emptyset$ or $G_a$ is a group.
Now, the generalized transition group $H_a$ is called as the
holonomy transition system of $a$, and the group $G_a$ is called as
the holonomy group of $a$.
We have that $G_a \prec S$ since $G_a$ is a quotient of the sub-semigroup
$\{ s | s \in S, as = a \}$. (TODO: so what? why does this mean that it's $\prec$?)
§ Theorem:
If $a \sim b$, then $H_a \simeq H_b$ (similar subsets have isomorphic holonomy transition systems).
§ Proof:
Let us assume that $a \neq b$. since $a \sim b$, we have elements
of the form $s, s^{-1} \in S$ such that $b = s(a)$, $a = s^{-1}(b)$.
Recall that for $b_a \in B_a$ is such that for a member $g \in G_a$,
$g(b_a) = b_a$. $B_b$ must have the element $s(b_a)$ [TODO! ]
§ Holonomy decomposition
Let $X \equiv (Q, S)$ be a transition system and let $h$ be a height
function for $X$, such that $h(Q) > 0$. For a fixed $i$,
let $a_1, a_2, \dots a_k$ be the representatives of equivalence classes of
elements of $A$ of height equal to $i$. We define:
$H_i^\lor \equiv H_{a_1} \lor H_{a_2} \dots \lor H_{a_n}$
§ Inductive hypothesis for coverings
We will say a relational covering $X \triangleleft_{\phi} Y$ is of rank $i$
with respect to a given height function $h$ if $\phi$ relates states in $Y$
to subsets of states in $x$ that are members of $A$ and have rank at most i.
Formally, for each $p \in Q_Y$, we have that $\phi(p) \in A$ and $h(\phi(p)) \leq i$.
We prove that if $X \triangleleft_{\phi} Y$ is a relational covering of rank $i$,
then $X \triangleleft_{\phi} \overline{H_i^\lor} \wr Y$ is a relational covering
of rank $i - 1$.
The proof is a proof by induction.
§ Base case:
Start with the relational covering with $Q_Y = \{ 0 \}, S_Y = \{ id \}$,
and the cover $\phi(0) = Q_X$. Clearly, this has rank $n$ since the height
of $Q_X$ is $n$, and $\phi$ is inded a covering, since the only transition
that $Y$ can make (stay at the same state) is simulated by any transition
in $S_X$ [TODO: is this really the argument? ]
For induction, assume $X \triangleleft_{\phi} Y$ is a relational covering of rank $i$
with respect to some height function $h$. $X\equiv (Q_X, S_X)$ and
$Y \equiv (Q_Y, S_Y)$. We define
- $QY_i \equiv \{ q_y : q_y \in Q_Y, h(\phi(q_y)) = i \}$
- $QY_< \equiv \{ q_y : q_y \in Q_Y, h(\phi(q_y)) < i \}$
We know that $A$ contains elements of height exactly $i$. Let $a_1, a_2, \dots a_k$
be representatives of sets of of height $i$ in $A$. Thus, for each $qy_i \in QY_i$,
we have that:
- $\phi(qy_i) = a_j$ for a unique $1 \leq j \leq k$.
- We select elements $u, \overline{u} \in S$ such that $u(\phi(qy_i)) = a_j$and $\overline{u}(a_j) = \phi(qy_i)$.
We will show how to establish a relational covering:
- $X \triangleleft_{\phi} \wr \overline{H_i^\lor} Y$ using a relation:
- $\phi \subseteq [(B_{a_1} \cup B_{a_2} \cup \dots B_{a_k})\times Q_Y ] \times Q_X$
§ References