Does this count as a proof by structural induction?

Question

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

Basis Step: $(0, 0) \in S$

Recursive Step: If $(a, b) \in S$, then $(a + 2,b + 3) \in S$ and $(a+3,b+2) \in S$.

Use structural induction to show that $5 | (a+b)$ when $(a,b) \in S$

$S = \left\{{(0,0), (2,3), (3, 2), (4,6), (5,5), (5,5),(6,4),...}\right\}$

Let $A$ be a set which contains all the instances of $(a, b)$ in $S$ as the sum of the two.

We can generate $A$ recursively by starting with the basis step: $(0,0) \in A$

Recursive Step: if $a \in A$, then $(a + 5) \in A$. This is just a simplification of the recursive step for $S$.

Proof that $5|a$ for each $a \in A$:

Basis Step: $5|0$ since every number divides zero.

Recursive Step: $A$ only contains products of 5 since, its elements are generated by adding 5 to 0 recursively, so all the elements in $A$ are divisible by 5.

P.S. I don't quite understand what structural induction really is....

Thanks!!!

Answer 1

I think that you were trying to say that $A=\{a+b:\langle a,b\rangle\in S\}$; your goal is indeed to prove that if $a\in A$, then $5\mid a$. However, this isn’t what you’ve tried to prove: what you’ve tried to prove is that if $5\mid a$, and $a\ge 0$, then $a\in A$.

Let’s forget $A$ and work directly with members of $S$.

Theorem. If $\langle a,b\rangle\in S$, then $5\mid a+b$.

The proof is by structural induction: we’ll show that it’s true for any basis elements of the definition of $S$, and we’ll show that any growth clauses of that definition preserve the property that the sum of the elements of the pair is a multiple of $5$.

Proof. The only basis element of $S$ is $\langle 0,0\rangle$: that’s the only pair explicitly stated to belong to $S$. And it’s certainly true that $5\mid 0=0+0$, so $\langle 0,0\rangle$ has the desired property.

Now we show that the growth clause $-$ what you call the recursive step $-$ of the definition of $S$ preserves the desired property. Suppose that $\langle a,b\rangle\in S$ has the property that $5\mid a+b$; we need to show that $\langle a+2,b+3\rangle$ and $\langle a+3,b+2\rangle$ have the property as well. In other words, we’re assuming that $5\mid a+b$, and we want to prove that $$5\mid(a+2)+(b+3)\tag{1}$$ and $$5\mid(a+3)+(b+2)\;.\tag{2}$$ This is easy. Since $5\mid a+b$, there is an integer $n$ such that $a+b=5n$. Now both $$(a+2)+(b+3)$$ and $$(a+3)+(b+2)$$ are equal to $a+b+5$, and $a+b+5=5n+5=5(n+1)$; certainly $n+1$ is an integer, so $a+b+5$ is a multiple of $5$, and $(1)$ and $(2)$ are true, as desired. $\dashv$

Perhaps the following brief discussion will help you to understand better what structural induction is and how and why it works.

In general, suppose that you’ve defined some set $S$ by explicitly specifying some of its members and giving some construction rules for building new members from old ones. Suppose further that you want to show that every member of $S$ has some property $P$. Structural induction is a very common way to do this. It always works the same way:

1. Prove that all of the explicitly given members of $S$ have the property $P$. This is your basis step, corresponding to the basis of the recursive definition of $S$.

2. Prove that if you apply any of the construction rules to things that have property $P$, the new object that you construct also has property $P$. This is the induction step of the argument, corresponding to the recursion step of the definition of $S$.

If you can do both of these, you may conclude that every member of $S$ has property $P$, because every member of $S$ is obtained by starting with one of the base objects $-$ the ones given explicity $-$ and applying construction rules a finite number of times. And you’ve just proved that if you start with something that has property $P$ and apply the construction rules, you get only objects that also have $P$. They never take you outside the class of objects that have $P$.