Using strong/simple induction instead of structural induction.

Question

Let S be the set of ordered pairs of integers defined recursively by

$(0,0) \in S$

If $(a,b) \in S$, then both $(a+1, b+1) \in S$ and $(a+3,b) \in S$

And define the set $S'$ = {$(x,y) \in \mathbb{N} \times \mathbb{N}$ | $x \ge y$ and $ 3 |(x-y)$}

Prove that $S \subseteq S'. $

Im able to prove this by structural induction, but im wondering if it's possible to use only simple or strong induction to prove this. And if so what should i do induction on?

Answer 1

Those operations are commutative, so let's suppose that all of the $+1$'s come before all of the $+3$'s in an element of $S$. Then we can define $S$ as $\cup_{n \in \mathbb{N}} T((n,n))$ where $T(x,y)$ contains $(x,y)$ and for all $(a,b) \in T(x,y)$, $(a+3, b) \in T(x,y)$.

Then we can define a successor operation in the $T$ sets and prove by regular induction that each of them is a subset of $S'$, so their union is also a subset of $S'$.