Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Don't really understand how to use structural induction The question is: Use structural induction to prove that if (x,y)∈S then x+y is multiple of 7.
Let S be the set of ordered pairs of integers defined recursively by
(i) (3, 4) ∈ S
(ii) If (x, y) ∈ S, then (x + 7, y) ∈ S and (x − 1, y − 6) ∈ S.
(iii) The only elements of S are those which are obtained from (i) by applying (ii) a finite number of times.
You have a set defined recursively, meaning that you’re explicitly given one or more initial members of the set $S$ and one or more rules for building new members of $S$ from old ones. In this case you’re explicitly given one member, $\langle 3,4\rangle$, and two rules for building new ones: if $\langle x,y\rangle\in S$, they so are $\langle x+7,y\rangle$ and $\langle x-1,y-6\rangle$.
To carry out a proof by structural induction that each member of $S$ has a certain property, you need to do two things: you must show that each of the explicitly given initial members has the property, and you must show that the building rules preserve the property.
As with the ordinary induction with which you’re probably more familiar, the first of these is often very easy, and that’s the case here: $3+4=7=7\cdot1$ is certainly a multiple of $7$.
Now you have to show that the building rules preserve this property, meaning that if $x+y$ is a multiple of $7$, then so are $(x+7)+y$ and $(x-1)+(y-6)$. If $x+y$ is a multiple of $7$, then $x+y=7n$ for some integer $n$. Clearly $(x+7)+y=(x+y)+7=7n+7=7(n+1)$ is also a multiple of $7$. I’ll leave it to you to check the other building rule. Once you’ve done that, you’ll have completed the proof by structural induction and will know that every member of $S$ has the property.
The proof works because of clause (iii): the only way an ordered pair gets into $S$ is by being the initial pair $\langle 3,4\rangle$ or by being derived from the initial pair by repeated application of the building rules. We checked that the initial pair has the desired property, and we checked that each application of a building rule preserves the property, so everything in $S$ must have that property.
