Strong induction vs. structural induction?

Printable View

March 28th 2011, 09:39 AM
posix_memalign

Strong induction vs. structural induction?

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

List the elements of S produced by the first five applications of the recursive definition.

Use strong induction on the number of applications of the recursive step of the definition to show that 5 | a + b when $(a,b) \in S$ .

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

I have the first five elements of S as follows:

(0,0), (2,3), (4,6), (6,9) and (8,12)

Using strong induction I have that:

Let P(n): 5 | a + b, where (a, b) $\in S$

Basis step: P(0): 0/5 = 0, P(1): 5/5 = 1, P(2): 10/5 = 2, P(3): 15/5 = 3, P(4): 20/5 = 4

Inductive step: Assume P(j), $0 \leq j \leq k$

Consider P(k + 1): By the inductive hypothesis we know P(k) to be true. From the definition of P(n) we have that the next recursive application will yield P(k + 1): (a + 3, b + 2), when P(k): (a, b).
5 | 5, thus if 5 | (a + b) then 5 | (a + b + 5). Q.E.D.

However (if what I did there is even correct at all) how do I prove the same thing using structural induction?
March 28th 2011, 12:36 PM
emakarov

Quote:

Using strong induction I have that:

Let P(n): 5 | a + b, where (a, b) $\in S$

P(n) must be a property of n, i.e., it must be true or false for each particular natural number n. However, there is no n after the colon, so your property does not depend on n. On the other hand, there are undefined variables a and b.

Quote:

Inductive step: Assume P(j), $0\le j\le k$

Consider P(k + 1)

Do you assume P(j) for some or for all j between 0 and k?

Quote:

I have the first five elements of S as follows:

(0,0), (2,3), (4,6), (6,9) and (8,12)

That's one possibility, but the recursion step forms two new pairs. So, at each step you could also form (a + 3, b + 2) from (a, b), not necessarily (a + 2, b + 3). In fact, the process of generating new pairs branches at each step and the order in which pairs are generated is not determined.

I believe this is the reason for strong induction. For example, one could generate pairs as follows:

$\begin{array}{c|c|c|c|c|c|c} \mbox{Step} & 0 & 1 & 2 & 3 & 4 & 5\\ \hline \mbox{Pair} & (0,0) & (2,3) & (4,6) & (3,2) & (6,9) & (5,5) \end{array}$

Here pair #3 is formed from (0,0), and pair #5 is formed from pair #3, i.e., a pair may be formed from another one that does not immediately precede it.

So, let P(n) be "if (a, b) is the pair generated after n applications of the recursive step, then 5 | a + b." In the induction step, one has to show that for all k,

P(0), ..., P(k) imply P(k + 1).

Fix some k and assume P(0), ..., P(k). Let (a, b) be the pair generated after the (k + 1)st step. Then there exists a j < k + 1 such that (a', b') is the pair generated after j steps and (a, b) is obtained by the recursion step from (a', b'). Therefore, (a, b) is (a' + 2, b' + 3) or (a, b) is (a' + 3, b' + 2). By P(j), which is a part of the induction hypothesis, 5 | a' + b', so 5 | a + b in both cases.

In the structural induction, on the other hand, one does not need to go back more than one step. You consider a binary tree whose root is (0,0) and each internal node (a, b) has two children (a + 2, b + 3) and (a + 3, b + 2). At each step, one can add two new leaves to some existing leaf. The induction hypothesis is that the sum of each node (which is a pair) in the tree is a multiple of 5. After forming two more leaves, it is clear that this property is preserved.
March 29th 2011, 06:23 PM
posix_memalign

Quote:

Originally Posted by emakarov

P(n) must be a property of n, i.e., it must be true or false for each particular natural number n. However, there is no n after the colon, so your property does not depend on n. On the other hand, there are undefined variables a and b.

Do you assume P(j) for some or for all j between 0 and k?

Sorry, I meant that P(n): 5 | a + b, where (a, b) are the n-th recursive step in the recursively defined subset S, which was previously defined.

Yes, I assume P(j) to be true for all j between 0 and k.

Quote:

That's one possibility, but the recursion step forms two new pairs. So, at each step you could also form (a + 3, b + 2) from (a, b), not necessarily (a + 2, b + 3). In fact, the process of generating new pairs branches at each step and the order in which pairs are generated is not determined.

I believe this is the reason for strong induction. For example, one could generate pairs as follows:

$\begin{array}{c|c|c|c|c|c|c} \mbox{Step} & 0 & 1 & 2 & 3 & 4 & 5\\ \hline \mbox{Pair} & (0,0) & (2,3) & (4,6) & (3,2) & (6,9) & (5,5) \end{array}$

Here pair #3 is formed from (0,0), and pair #5 is formed from pair #3, i.e., a pair may be formed from another one that does not immediately precede it.

Thanks, I didn't consider that actually.

Quote:

So, let P(n) be "if (a, b) is the pair generated after n applications of the recursive step, then 5 | a + b." In the induction step, one has to show that for all k,

P(0), ..., P(k) imply P(k + 1).

Fix some k and assume P(0), ..., P(k). Let (a, b) be the pair generated after the (k + 1)st step. Then there exists a j < k + 1 such that (a', b') is the pair generated after j steps and (a, b) is obtained by the recursion step from (a', b'). Therefore, (a, b) is (a' + 2, b' + 3) or (a, b) is (a' + 3, b' + 2). By P(j), which is a part of the induction hypothesis, 5 | a' + b', so 5 | a + b in both cases.

Thanks, I think I understand this part of the problem now.

Quote:

In the structural induction, on the other hand, one does not need to go back more than one step. You consider a binary tree whose root is (0,0) and each internal node (a, b) has two children (a + 2, b + 3) and (a + 3, b + 2). At each step, one can add two new leaves to some existing leaf. The induction hypothesis is that the sum of each node (which is a pair) in the tree is a multiple of 5. After forming two more leaves, it is clear that this property is preserved.

I don't understand this, how exactly does this prove the statement P? It is intuitive, and I agree with it, but I don't understand how it is a proof. How does structural induction differ from normal mathematical induction?
March 30th 2011, 06:20 AM
emakarov

The exact words that are expected here may differ between courses and textbooks. In general, structural induction is a method of proving statements about recursively-defined structures. (You may also find the Wikipedia article useful.) First, one has to have rules how to build these structures. There are rules saying that some structures are minimal, or atomic, and other rules describing how to build bigger structures from existing ones. For example, natural numbers can be defined this way: 0 is a natural number, and if n is a natural number, then so is s(n) (here s is supposed to stand for "successor"; this is a so-called unary representation as opposed to binary or decimal). For another example, the set B of finite strings of 0 and 1 can be defined as follows: the empty string is in B, and if x is in B, then so are 0x and 1x. Each structure has a finite sequence of steps describing how it was built, i.e., which rules were applied and how.

To prove that some property P holds of all recursively-defined structures, one shows that P holds on minimal structures and that P holds on an arbitrary non-atomic structure provided it holds on all its immediate substructures. So, to prove P for all natural numbers, show P(0), and then for every natural number n, show P(s(n)) assuming P(n). To prove P for all binary strings, show that P holds on the empty string, and then for every string x, show P(0x) and P(1x) assuming P(x).

Let P((a,b)) be 5 | a + b. Similarly, to prove P((a,b)) for every (a,b) in S, show P((0,0)), and then for every (a,b) in S, show that P((a + 2, b + 3)) and P((a + 3, b + 2)) assuming P((a,b)).
March 30th 2011, 10:03 AM
posix_memalign

Quote:

Originally Posted by emakarov

To prove that some property P holds of all recursively-defined structures, one shows that P holds on minimal structures and that P holds on an arbitrary non-atomic structure provided it holds on all its immediate substructures. So, to prove P for all natural numbers, show P(0), and then for every natural number n, show P(s(n)) assuming P(n). To prove P for all binary strings, show that P holds on the empty string, and then for every string x, show P(0x) and P(1x) assuming P(x).

Let P((a,b)) be 5 | a + b. Similarly, to prove P((a,b)) for every (a,b) in S, show P((0,0)), and then for every (a,b) in S, show that P((a + 2, b + 3)) and P((a + 3, b + 2)) assuming P((a,b)).

But is this not the same as was done in the strong induction variant? The only difference being that we assume P(0), ..., P(k) first?
It also seems terribly similar to just normal mathematical induction, especially the structural induction. First show P(0), assume P(n) is true for every n, then under this assumption show P(n+1). The only difference here being that P takes two arguments and that it branches into two outputs, namely P((a + 2, b + 3)) and P((a + 3, b + 2)) assuming P((a,b)). Is this the difference between normal mathematical induction and structural induction, that it branches in this manner?
March 30th 2011, 02:04 PM
emakarov

I should have said that structural induction on unary natural numbers as defined above is the regular mathematical induction. It shows that natural numbers and mathematical induction are just special cases of recursively-generated structures and the associated reasoning principles. Natural numbers is the simplest objects (with one minimal object and one way to build new objects from the old ones) that give rise to an infinite set.

Proving a property of recursively generated objects using numerical induction requires that you assign a natural number to each object. In the original problem, each pair had an associated step number at which it was formed.

In structural induction, you don't use numbers at all. You pass from immediate sub-objects to objects according to whatever recursive rules are used to build objects.

Let L be a set of some labels. Consider binary trees given by the following recursive definition: a label from L is a tree, and if T1, T2 are tree, then node(T1, T2) is a tree. If L are natural numbers, then node(0, node(1, 2)) is a tree than can be represented as follows.

Code:

1 2 \/ 0 node \/ node

Suppose you want to prove something for all trees (such as that the number of leaves is one greater than the number of internal nodes). To use numeric induction, you could, for example, assign a height to every tree (2 in the example above) and then prove that if a property holds for all trees of height n, then it holds for all trees of height n + 1. In structural induction, you assume that the property holds for two arbitrary trees T1 and T2 and prove that it holds for node(T1, T2).

Quote:

First show P(0), assume P(n) is true for every n, then under this assumption show P(n+1).

You can't assume that P(n) is true for every n: this is what you are proving by induction. Instead, for every n, you assume P(n) and prove P(n + 1).
April 1st 2011, 07:07 PM
Deveno

as i understand it, the difference between the two is the inductive step.

structural induction: [P(a) & (P(k) -->P(k+1))] --> P(n)&(a≤n)

strong induction: [P(a) & [(P(k)&(k<m))-->P(m)]] --> P(n)&(a≤n) (these schema get simpler if a = 0)

the difference being that in structural induction, you only assume "just the previous step" whereas in strong induction you can assume "any previous step".

in this particular case, you could use either one, but strong induction is more convenient.

as i see it, the problem calls for an explicit list of all 32 elements produced after 5 steps, not just 5 elements produced along any set of paths whose lengths total 5.
April 2nd 2011, 08:56 AM
emakarov

Quote:

as i understand it, the difference between the two is the inductive step... the difference being that in structural induction, you only assume "just the previous step" whereas in strong induction you can assume "any previous step".

No, the difference is that in structural induction, the property P being proved depends not on numbers but on recursively defined objects.

Consider the problem from the OP. In the numerical induction, P(n) says that something is true about the pair generated at the nth step. In structural induction P((a,b)) directly says that something is true about the pair (a,b). In structural induction, numbers are not generally mentioned at all.

Whether the induction hypothesis depends on the immediately "previous" element (number or pair) or all previous elements is not a difference between numerical and structural induction; both options can be used in both forms of induction.
April 18th 2011, 11:13 AM
posix_memalign

Quote:

Originally Posted by emakarov

So, let P(n) be "if (a, b) is the pair generated after n applications of the recursive step, then 5 | a + b." In the induction step, one has to show that for all k,

P(0), ..., P(k) imply P(k + 1).

Fix some k and assume P(0), ..., P(k). Let (a, b) be the pair generated after the (k + 1)st step. Then there exists a j < k + 1 such that (a', b') is the pair generated after j steps and (a, b) is obtained by the recursion step from (a', b'). Therefore, (a, b) is (a' + 2, b' + 3) or (a, b) is (a' + 3, b' + 2). By P(j), which is a part of the induction hypothesis, 5 | a' + b', so 5 | a + b in both cases.

In the structural induction, on the other hand, one does not need to go back more than one step. You consider a binary tree whose root is (0,0) and each internal node (a, b) has two children (a + 2, b + 3) and (a + 3, b + 2). At each step, one can add two new leaves to some existing leaf. The induction hypothesis is that the sum of each node (which is a pair) in the tree is a multiple of 5. After forming two more leaves, it is clear that this property is preserved.

I feel sad to bring this up again. I realize that I don't understand this at all, even though I've read several definitions of strong inductions and tried different tasks.

Quote:

In the structural induction, on the other hand, one does not need to go back more than one step.

But in the use of strong induction you only go back one step? You consider j < k + 1 which is the step immediately prior to k + 1, i.e. k. k - 1, k - 2 or even lower are not considered as far as I can see?

Why couldn't this be solved by just normal mathematical induction?

I.e.

Prove P(0), which is trivial, 5 | 0.
Prove that under the assumption that for all k P(k) holds, then P(k) implies P(k+1): This can be done by considering the only two cases defined by the recursive definition. Let P(k) have produced the pair (a, b). P(k + 1) can then only produce (a + 2, b + 3) and (a + 3, b + 2). We know that 5 | a + b, we also know that 5 | 5, and 5 = 2 + 3 = 3 + 2. Thus 5 | a + b + 5.
This completes the proof.

Why can't it be done this way? What is the point with strong induction in this problem?

And as for structural induction, that is even less clear to me.

How exactly does it prove the property? Just by drawing the binary tree and considering it?
April 18th 2011, 12:05 PM
emakarov

Quote:

But in the use of strong induction you only go back one step? You consider j < k + 1 which is the step immediately prior to k + 1, i.e. k. k - 1, k - 2 or even lower are not considered as far as I can see?

We must be clear on what the induction statement P(k) is. It says that the pair obtained at step k has elements whose sum is a multiple of 5. My guess is that the intention of the problem's authors, who suggested using strong induction, was that a single pair is generated at each step. Now, the important point is that the pair obtained at step k is not necessarily formed from the pair obtained at step k - 1. In my first post, pair #3 is formed from (0,0), and pair #5 is formed from pair #3. Therefore, to prove P(k + 1) we need not only P(k), but all of P(0), ..., P(k).

Quote:

Why couldn't this be solved by just normal mathematical induction?

This is beyond the scope of this question, but strong induction can be derived from the regular one, so this fact can ultimately be proved using regular induction. Also, it is important that if you generate pairs in such a way that all members of S are eventually enumerated, then there necessarily will be pairs that are formed from other pairs that go back more than one step.

Quote:

Let P(k) have produced the pair (a, b). P(k + 1) can then only produce (a + 2, b + 3) and (a + 3, b + 2).

Here there is some confusion about what P(k) is. If P(k) is as I described above, we generate a single pair at each step, so we can't say that both (a + 2, b + 3) and (a + 3, b + 2) are formed at step k + 1. To repeat this once more, in this case, step k + 1 may produce not (a + 2, b + 3), but an unrelated pair formed from some other pair several steps back.

If, on the other hand, we posit that step k generates 2^k pairs at once from 2^{k-1} pairs obtained in the previous step, then indeed we don't need strong induction. We must only describe precisely what pairs are generated at step k and formulate P(k) accordingly.

In structural induction, we don't talk about the step number. We must only show that if all pairs generated up to now satisfy some property, then the pairs generated by the application of the recursive step also satisfy the property.

I must admit that the distinction between regular and structural induction here seems a little fuzzy. Properly speaking, structural induction is applied not to recursively defined sets of simple objects (such as pairs of numbers), but to objects that have a recursive structure, such as trees, lists, syntactic expressions, etc. The the induction step consists of proving a property for some object assuming it holds of all sub-objects, e.g., it holds of a list provided it holds of the same list without the head.
April 18th 2011, 04:06 PM
Deveno

Quote:

Originally Posted by emakarov

No, the difference is that in structural induction, the property P being proved depends not on numbers but on recursively defined objects.

Consider the problem from the OP. In the numerical induction, P(n) says that something is true about the pair generated at the nth step. In structural induction P((a,b)) directly says that something is true about the pair (a,b). In structural induction, numbers are not generally mentioned at all.

Whether the induction hypothesis depends on the immediately "previous" element (number or pair) or all previous elements is not a difference between numerical and structural induction; both options can be used in both forms of induction.

i see we have been talking about 2 (3?) different things:

regular induction: P(k)-->P(k+1)
strong induction: P(k<n)-->P(n)
structural induction P(S(n)) <--> P(S(k<n)) ( i have written S(n) to indicate that S is a recursively defined object).

it is still my contention that the original problem refers to to set of ALL possible elements produced in 5 iterations, which would be 32 possible paths of a tree of length 5.

it seems to me that stuctural induction is a proof of strong induction by contradiction.

now, i concur that in this example, we don't know "which" element of S we're dealing with at step n. S is a tree, and we might have taken any branch to get to the leaf we're at.

so it makes sense to show that any new generation of leaves preserves the divisibility by 5 property that the shorter tree of the previous generation had.

i think i get where you're coming from. it's one thing to do induction on the number of iterations that produces each new generation of S, and quite another to say: any previous tree that had this property passes it on, and the seed (root?) had this property.
April 20th 2011, 04:38 AM
emakarov

Quote:

Originally Posted by Deveno

i see we have been talking about 2 (3?) different things:

regular induction: P(k)-->P(k+1)
strong induction: P(k<n)-->P(n)
structural induction P(S(n)) <--> P(S(k<n)) ( i have written S(n) to indicate that S is a recursively defined object).

This is a somewhat loose use of notation. In S(n), S is applied to an object, but in S(k < n), it is applied to a proposition. More importantly, there are no numbers in structural induction, and, correspondingly, no comparison of numbers. One has to explain what is meant by <.

Quote:

it is still my contention that the original problem refers to to set of ALL possible elements produced in 5 iterations, which would be 32 possible paths of a tree of length 5.

This is quite possible. I decided to go with 5 individual pairs because, first, that would require the use of strong, rather than regular, induction, as the problems seems to say and, second, because 32 is a lot of pairs to list.

Quote:

it seems to me that stuctural induction is a proof of strong induction by contradiction.

I repeat that structural induction does not involve numbers, or, rather, it applies to all recursively defined objects, not just numbers. Also, I don't see why proof by contradiction is relevant here. Both numeric and structural induction have the same shape: if a property holds for minimal objects and is preserved by the recursion step, then it holds for all recursively generated objects.

I said earlier that structural induction is used when there are objects with recursive structure. Strictly speaking, what this problem defines by recursion are not pairs or sets of pairs (which don't have a recursive structure), but rather derivations, or proofs, that a given pair belongs to S. Derivations are sequences of pairs defined as follows.

(1) A sequence containing one pair (0,0) is a derivation.
(2) If s is a derivation ending in (a, b), then s appended with (a + 2, b + 3) and s appended with (a + 3, b + 2) are derivations.

A pair is called derivable if there is a derivation that ends with this pair. Then the set S is defined as the set of derivable pairs.

Suppose one wants to prove a property P for all pairs in S. Let Q be a property of a derivation saying that its last pair satisfies P. Then one can use structural induction to prove that Q holds for every derivation. For this, one shows Q((0,0)) and that Q(s) implies Q(s') for all derivations s and s' such that s' is obtained from s by rule (2) above.
April 20th 2011, 10:39 PM
posix_memalign

Quote:

Originally Posted by emakarov

We must be clear on what the induction statement P(k) is. It says that the pair obtained at step k has elements whose sum is a multiple of 5. My guess is that the intention of the problem's authors, who suggested using strong induction, was that a single pair is generated at each step. Now, the important point is that the pair obtained at step k is not necessarily formed from the pair obtained at step k - 1. In my first post, pair #3 is formed from (0,0), and pair #5 is formed from pair #3. Therefore, to prove P(k + 1) we need not only P(k), but all of P(0), ..., P(k).

This is beyond the scope of this question, but strong induction can be derived from the regular one, so this fact can ultimately be proved using regular induction. Also, it is important that if you generate pairs in such a way that all members of S are eventually enumerated, then there necessarily will be pairs that are formed from other pairs that go back more than one step.

Here there is some confusion about what P(k) is. If P(k) is as I described above, we generate a single pair at each step, so we can't say that both (a + 2, b + 3) and (a + 3, b + 2) are formed at step k + 1. To repeat this once more, in this case, step k + 1 may produce not (a + 2, b + 3), but an unrelated pair formed from some other pair several steps back.

If, on the other hand, we posit that step k generates 2^k pairs at once from 2^{k-1} pairs obtained in the previous step, then indeed we don't need strong induction. We must only describe precisely what pairs are generated at step k and formulate P(k) accordingly.

In structural induction, we don't talk about the step number. We must only show that if all pairs generated up to now satisfy some property, then the pairs generated by the application of the recursive step also satisfy the property.

I must admit that the distinction between regular and structural induction here seems a little fuzzy. Properly speaking, structural induction is applied not to recursively defined sets of simple objects (such as pairs of numbers), but to objects that have a recursive structure, such as trees, lists, syntactic expressions, etc. The the induction step consists of proving a property for some object assuming it holds of all sub-objects, e.g., it holds of a list provided it holds of the same list without the head.

Thank you for the help.

So structural induction is very much akin to normal mathematical induction except that the "step number" is an omitted notion as numbers are not required, only a recursive definition of some property.
In both structural induction and mathematical induction we assume that for all k P(k) holds, and then we want to show that under this assumption P(k+1) also holds, except that in structural induction we don't use the notion "k+1" we simply speak of the next recursive step assuming all other steps in the recursion stack are valid?

So for this particular problem, in structural induction, we assume that for all arbitrary pairs generated so far by the recursive definition they (the sum of the two elements in each pair) are multiples of 5. Then we simply show that under this assumption the next recursive step must also yield pairs that are a multiple of 5.

Is this correct at all? Please tell me if this is true or if I still fail to understand this. :-)
April 21st 2011, 12:36 AM
emakarov

Yes, this is correct. Note also that the recursive step may take not just one but several, or infinitely many, sub-objects and form a new object from them. This happens for binary trees where a tree is formed from two subtrees. Then there are several inductive hypotheses: one for each sub-object.