# Prove that all elements in the set $T$ is divisible by $3$ using structural induction.

Let $T$ be the set defined recursively as follows:

1. $(0,3) \in T$
2. If $(x, y) \in T$, then $(x + 2, y - 1) \in T$ and $(x - 3, y) \in T$.
3. 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$.
• As I said, a branch is one of the indicated arrows, e.g. $\,(0,3)\to (2,2)\to (4,1)\to (1,1)$ yields a proof that $\,(1,1)\in T\,$ of height $3$. Mar 28, 2014 at 17:19