Let $T$ be the set defined recursively as follows:
- $(0,3) \in T$
- If $(x, y) \in T$, then $(x + 2, y - 1) \in T$ and $(x - 3, y) \in T$.
- Every element of $T$ can be obtained from 1. by applying 2. a finite number of times.
Prove that for all $(x, y) \in T, x \equiv y \ (\mod 3)$ (That is, $x - y$ is divisible by $3$).
For me the hard part is just understanding structural induction with recursively defined sets. Mathematical and Strong induction I get but structural is confusing.
Hint $\ $ It is true for the base case $\,(0,3),\,$ and $\,\color{#c00}{x\equiv y}\,\Rightarrow\,\color{#c00}x+2\equiv \color{#c00}y+2\equiv y-1,\,$ and also implies $\,x-3\equiv \color{#c00}{x\equiv y},\,$ i.e. if true for $(x,y)$ then it is true for $\,(x+2,y-1)$ and $(x-3,y).\,$Therefore, by structural induction, it is true for all elements of $\,T$.
If you view the proof that $(a,b)\in T\,$ as a tree with branches $(x,y) \to (x+2,y-1)\,$ or $\,(x-3,y)$ then this structural induction can be viewed as induction on the height of the branch that yields the proof that $\,(a,b) \in T$.