Proof by Structural Induction

Proof method used widely in Graph Theory Used to prove some Logical Predicate $P(x)$ holds for all $x$ of some recursively defined structure.

Structure

1. Define $P(x)$

Base Case

1. With $x$ as a recursive structure
   1. Prove $P(x)$

Induction Step

1. Suppose $P(x)$ holds for sub-structures used in recursive step of definition
   1. Prove $P$ holds for the recursively constructed structure

Regex Structure

1. Define $P(x)$ to be that a given regex is in $\mathcal{R}\mathcal{E}$

Base Case

• Suppose $\varnothing ,ϵ$, single letter $a$ are in $\mathcal{R}\mathcal{E}$
• Show $P(\varnothing ),P(ϵ),P(a)$

Inductive Step

If regexes $S$ and $T$ are in $\mathcal{R}\mathcal{E}$, then show:

• $P(S),P(T)⟹P(S+T)$
• $P(S),P(T)⟹P(ST)$
• $P(S),P(T)⟹P(S^{\ast })$

Examples

• Structural Induction Set Example
• Structural Induction String Example
• Structural Induction Regular Expression Example