p. 165
4.40 (a): We are going to prove this by general (structural) induction on
(S), that is first we prove that
the basis of (S), which is
S, is a subset of (T).
Then we prove that if any element q of
(S) is belongs to
(T), then its descendants, i.e.
(q, ),
also belong to (T).
Basis Step: By the Basis Clause of the definition of
-closure, T
(T).
Hence if S
T, then
S
(T).
Inductive Step:
Induction Hypothesis: For an arbitrary state q, if q
(S), then
q
(T).
We are going to show that
(q, )
(T).
This is immediate. For since by the induction hypothesis, if q
(S), then
q
(T), by the Inductive Clause
of the definition of -closure
(q, )
(T).
Hence if any element of
(S)
is in (T), then its descendants
(q, )
are also in (T).
End of Proof