0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ if you put together a complete ordering of the set so that $x+1$ made sense for $x \in S$, it might be possible. But I doubt it would be straightforward. $\endgroup$
    – genisage
    Sep 25, 2014 at 21:54

1 Answer 1

Reset to default
0
$\begingroup$

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

$\endgroup$

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.