4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Mauro ALLEGRANZA Oct 18 '16 at 10:08
  • $\begingroup$ 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)$. $\endgroup$ – Mauro ALLEGRANZA Oct 18 '16 at 10:12
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – jeremy radcliff Jan 9 '17 at 22:05
  • $\begingroup$ @jeremy: You’re welcome; I’m glad that it helped. $\endgroup$ – Brian M. Scott Jan 9 '17 at 22:07
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.