0PDA
Proof. Let . Let .
We show by induction on that there exists
such that .
Assume . Let such that .
There is a decomposition as in §7.4.6.
We define
by
for ,
and
.
We have and .
Assume now . Consider a decomposition
as in
Lemma 7.4.27. There exists
and such that
and .
Let . We have .
Let . We have .
Let and . If ,
then . Assume .
We have . Since
,
it follows that .
Since , we deduce that .
The case of follows from that of applied to
, cf Remark 8.2.6.
∎