Induction
Problem: Prove that for an arbitrary string x of , REV(REV(x)) = x.
Proof
First let us note that can be defined recursively as follows:
Basis: , where is an empty string.
Induction: For arbitrary strings x of and a of ,
xa is also in .
ExtremalClause: As usual. Omitted.
The proof mirrors the recursive definition of .
Basis: Since
by the definition of REV (
Induction: Assume that for an arbitrary string x of
REV(REV(x)) = x holds. -- Induction Hypothesis
Then for an arbitrary symbol a of ,
REV(REV(xa)) = REV(a REV(x)) = REV(REV(x)) a by the definition of REV.
Then since by the induction hypothesis REV(REV(x)) = x, REV(REV(x)) = xa
Hence REV(REV(xa)) = xa.
End of Proof.