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.


1 Answer 1


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$.

  • $\begingroup$ what do you mean by branch? can you clarify. $\endgroup$
    – user138699
    Mar 28, 2014 at 17:14
  • $\begingroup$ 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$. $\endgroup$ Mar 28, 2014 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.