# 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$. Oct 18, 2016 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)$. Oct 18, 2016 at 10:12
• Here is a video attempting to explain structural induction: youtu.be/u21QV-MlVDY Aug 8 at 15:44

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

• 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$. Jan 9, 2017 at 22:05
• @jeremy: You’re welcome; I’m glad that it helped. Jan 9, 2017 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).