Help explaining Structural Induction

Question

I am trying to wrap my head around structural induction. Can someone break it down and explain it around this problem?

Let S, a subset of $\mathbb{N}*\mathbb{N}$, be defined recursively by:

Base case: $(0,0)$ $\in S$

Constructor case: If $(m,n) \in S$, then $(m+5,n+1) \in S$

Prove that if $(m,n) \in S$, then m+n is a multiple of 3.

How is it different than normal induction (using this example please) and what is the point of a Constructor case? Can someone wright the proof out so i can see what this structural induction proof looks like?

Answer 1

The set $S$ is defined recursively: certain base elements of $S$ are specified, in this case just the ordered pair $\langle 0,0\rangle$, and a rule is given that allows ‘new’ elements of $S$ to be constructed from ‘old’ ones. Here each ‘old’ element $\langle m,n\rangle$ gives rise to just one ‘new’ one, $\langle m+5,n+1\rangle$. Thus, in this case

$$S=\{\langle 0,0\rangle,\langle 5,1\rangle,\langle 10,2\rangle,\langle 15,3\rangle,\ldots\}\;.$$

There is also a rule, often (as in this case) left unstated, to the effect that the only members of $S$ are the objects that can be obtained by repeatedly applying the constructor rule(s) to the base elements.

We can show that every member of $S$ has some property $P$ by first verifying that each of the base elements has $P$ and then showing that the construction process preserves the property $P$: that is, if we apply the construction process to objects that have $P$, the new objects also have $P$. If we can do this, we can conclude by structural induction that every member of $S$ has $P$.

In your problem an ordered pair $\langle m,n\rangle$ has the property $P$ if and only if $m+n$ is a multiple of $3$. This is clearly the case for the one base element $\langle 0,0\rangle$: $0+0=0=3\cdot 0$ is a multiple of $3$. That’s the base case of your structural induction. For the induction step assume that $\langle m,n\rangle\in S$ has $P$, i.e., that $m+n$ is a multiple of $3$. When we apply the construction process to $\langle m,n\rangle$, we get the pair $\langle m+5,n+1\rangle\in S$, and we want to show that it also has $P$, i.e., that $(m+5)+(n+1)$ is a multiple of $3$. By hypothesis $m+n=3k$ for some integer $k$, so

$$(m+5)+(n+1)=m+n+6=3k+6=3(k+2)\;;$$

and $k+2$ is an integer, so $(m+5)+(n+1)$ is indeed a multiple of $3$. We’ve now shown

• that the base element $\langle 0,0\rangle$ has the desired property, and
• that the construction process preserves this property: when applied to a pair $\langle m,n\rangle$ such that $m+n$ is a multiple of $3$, it produces another pair whose components sum to a multiple of $3$.

These are the base case and induction step of a proof by structural induction; between them they constitute a proof that $m+n$ is a multiple of $3$ for each $\langle m,n\rangle\in S$.

Answer 2

Mathematical induction is defined over natural number and it is based on two fundamental facts :

• there is an "initial" number : $0$

• every number $n$ has a unique successor : $n+1$.

Structural induction generalize this type of proof to "structures" on which a well-founded partial order is defined, i.e.

• that have an "initial" or minimal element

and

• they have a partial order.

It applies to structures recursively defined (such as lists or trees).