next up previous
Next: About this document ... Up: Observations on Coset Enumeration Previous: Bibliography

10. Appendix

Lemma 8   Let $\sim$ be the least right congruence such that ${\cal H}$ is contained in a block B. Then for all $h \in {\cal H}$ we have $Bh \subseteq B$, i.e. ${\cal H}$ is contained in the fixing monoid of B.

Proof : 1.11.1 
We show that for each $b \in B$ we have $b \circ h \in B$. Since $b, \lambda \in B$, we have $b \sim \lambda$, and hence as $\sim$ is a right congruence $b \circ h \sim \lambda \circ h = h$ holds. Now $h \in B$ implies $b \circ h \in B$ and we are done.
q.e.d.


1.11

The following lemma is necessary to prove Theorem 6

Lemma 9   For some $h \in {\cal H}$ and $x \in {\cal M}$ we have $h \circ x \in B_{{\cal H}}$ if and only if $x \in B_{{\cal H}}$.

Proof : 1.11.1 
Since $h, \lambda \in {\cal H}$ and $\sim$ is a right congruence, $h \sim \lambda$ implies $h \circ x \sim x$, and as $h \circ x \in B_{{\cal H}}$ we can conclude $x \in B_{{\cal H}}$.
On the other hand we show that $x \in B_{{\cal H}}$ implies $h \circ x \in B_{{\cal H}}$ by showing $hB_i \subseteq B_i$ by induction on i where $x \in B_i$. If i=0 we find $h,x \in B_0 = {\cal H}$ and hence $h \circ x \in B_0$. Hence let us assume that for all $h \in {\cal H}$, $x \in B_{i-1}$ we have $h \circ x \in B_{i-1}$. Now take $x \in B_i \backslash B_{i-1}$ and hence $x = b \circ x'$ for some $b \in B_{i-1}$, $x' \in B_i$. The induction hypothesis implies $h \circ b \in B_{i-1}$ and hence $(h \circ b) \circ x' = h \circ x \in B_{i}$.
q.e.d.


1.11

Proof of Theorem 6: 1.11.1 
$1 \Longrightarrow2:$


next up previous
Next: About this document ... Up: Observations on Coset Enumeration Previous: Bibliography
| ZCA Home | Reports |