# Help explaining Structural Induction

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?

• Her we are "performing induction" not on $\mathbb N$ but of $\mathbb N \times \mathbb N$, and not all pairs $(n,m)$ will satisfy bthe property : $(1,1) \notin S$ because $1+1$ is not a multiple of $3$. – Mauro ALLEGRANZA Oct 18 '16 at 10:08
• Now for the inductive step (here the "constructor case") ; assume that the property holds for $(m,n)$ and show that it holds for $(m+5,n+1)$. – Mauro ALLEGRANZA Oct 18 '16 at 10:12

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

• Thank you, that was a great explanation. It made it immediately obvious that induction on the natural numbers is a special case of structural induction where the constructor case is $k+1$ for every $k$ in $S$. – jeremy radcliff Jan 9 '17 at 22:05
• @jeremy: You’re welcome; I’m glad that it helped. – Brian M. Scott Jan 9 '17 at 22:07

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).