# 4.1.7: Structural Induction

- Page ID
- 10574

Next, while we are on the topic of induction, let’s generalise the idea of induction to also apply it to sets. This more general form of induction is often called structural induction. Structural induction is used to prove that some proposition *P*(*x*) holds for all *x *of some sort of recursively defined structure, such as formulae, lists, or trees—or recursively- defined sets. In a proof by structural induction we show that the proposition holds for all the ‘minimal’ structures, and that if it holds for the immediate substructures of a certain structure *S*, then it must hold for *S *also. Structural induction is useful for proving properties about algorithms; sometimes it is used together with in variants for this purpose.

To get an idea of what a ‘recursively defined set’ might look like, consider the follow- ing definition of the set of natural numbers N.

**Basis**: 0 ∈ N.

**Succession**: *x*∈N→*x*+1∈N.

**Exclusivity**: No other elements other than those outlined by the rules above are in N.

This definition is similar to one we have seen before, first stating that 0 ∈ N and then saying that we can add 1 to an element in N to get another element of N. The final clause is needed to ensure that other items are not part of N. Without it, you and me, as well as *π*, ‘New York City’, and ‘King Willem-Alexander’ might have been in the set. After all there was no reason for those elements not to be in there.

Now compare that recursive definition, with the method for mathematical induction we have seen before:

**Base case**: Prove that *P*(0) holds.

**Inductive case**: Prove that ∀*k *∈ N(*P*(*k*) → *P*(*k *+ 1)) holds.

**Conclusion**: ∀*n *∈ N*P*(*n*)) holds.

As we can see mathematical induction and this recursive definition show large similarities. The base case of the induction proves the property for the basis of our recursive definition and the inductive step proves the property for the succession rule. In fact, this similarity is no coincidence and we can generalise this method to get to structural induction.

Consider for instance the set *PROP*, which represents all valid formula in propositional logic:

**Atoms**: *p**i *∈*PROP*forall*i*∈N.

**Negation**: *x *∈ *PROP *→ ¬*x *∈ *PROP*.

**Binary connective**: *x*,*y*∈*PROP*→(*x*∗*y*)∈*PROP*,s.t.∗∈{∧,∨,→,↔}.

**Exclusivity**: Nothing else is in *PROP*.

Using this definition of the set *PROP *we can use structural induction to prove certain claims about *PROP*. For instance we can prove that every formula in *PROP *has equally many left parentheses ‘(’ and right parentheses ‘)’.

Proof. Let *l*(*φ*) denote the number of left parentheses in a formula *φ*. Similarly let *r*(*φ*)denote the number of right parentheses. Let *P*(*φ*) be the statement that *l*(*φ*) = *r*(*φ*). We need to prove that ∀*φ *∈ *PROP*(*P*(*φ*)).

Base case: Consider the Atoms rule of the definition of *PROP*: *l*(*p**i*) = 0 = *r*(*p**i*). Therefore *P*(*p**i*) holds.

Inductive case: We want to show that if the statement is true for *x*, *y *∈ *PROP *(where *x** *and *y *are arbitrary formula), then it is true for ¬*x *and (*x *∗ *y*) for all ∗ ∈ {∨, ∧, →, ↔}. That is, we must prove the implication (*P*(*x*) ∧ *P*(*y*)) → (*P*(¬*x*) ∧ *P*((*x *∗ *y*))). So we assume *P*(*x*) ∧ *P*(*y*), that is, we assume that for both formula *x *and *y*: *l*(*x*) = *r*(*x*) and*l*(*y*) = *r*(*y*). We want to prove *P*(¬*x*), that is, that for ¬*x l*(¬*x*) = *r*(¬*x*)

*l*(¬*x*) = *l*(*x*) by the Negation rule of *PROP*

= *r*(*x*) by the inductive hypothesis

= *r*(¬*x*) by the Negation rule of *PROP*

Secondly we prove that *P*((*x *∗ *y*)) holds for all ∗ ∈ {∨, ∧, →, ↔}:

*l*((*x *∗ *y*)) = 1 + *l*(*x*) + *l*(*y*) by the Binary connective rule of *PROP*

= 1 + *r*(*x*) + *r*(*y*) by the inductive hypothesis

= *r*((*x *∗ *y*)) by the Binary connective rule of *PROP*

Altogether, we have shown that *P*(*p**i*) holds and that, for all *x*,*y *∈ *PROP *and ∗ ∈ {∨, ∧, →, ↔}, (*P*(*x*) ∧ *P*(*y*)) → (*P*(¬*x*) ∧ *P*((*x *∗ *y*)) is true. Therefore, by the principle of structural induction, *P*(*φ*) is true for all *φ *∈ *PROP*, so for all propositional formula the number of left parentheses equals the number of right parentheses. This completes the proof by structural induction.

Such structural induction proofs can be applied on any recursively defined set of numbers, formulae or even strings (pieces of text) or lists or trees, making this a very powerful generalised proof method.

**Exercises**

1. If we don’t make the assumption that *a*, *b*, and *c *are distinct, then the set denoted by {*a*, *b*, *c*}might actually contain either 1, 2, or 3 elements. How many different elements might the set{ *a*, *b*, {*a*}, {*a*, *c*}, {*a*, *b*, *c*} } contain? Explain your answer.

2. Compute *A *∪ *B*, *A *∩ *B*, and *A *∖ *B *for each of the following pairs of sets

a)*A*={*a*,*b*,*c*}, *B*=∅

b) *A *= {1,2,3,4,5}, *B *= {2,4,6,8,10}

c) *A *= {*a*,*b*}, *B *= {*a*,*b*,*c*,*d*}

d) *A *= {*a*,*b*,{*a*,*b*}}, *\(B=\{\{a\},\{a, b\}\}\)*

3. Draw a Venn diagram for each of the four sets of the last exercise.

4. Recall that N represents the set of natural numbers. That is, N = {0, 1, 2, 3, . . . }. Let *X *={*n *∈ N | *n *≥ 5}, let *Y *= {*n *∈ N | *n *≤ 10}, and let *Z *= {*n *∈ N | *n *is an even number}. Find each of the following sets:

a) *X *∩ *Y *b) *X *∪ *Y *c) *X *∖ *Y *d) N ∖ *Z*

e) *X *∩ *Z *f) *Y *∩ *Z *g) *Y *∪ *Z *h) *Z *∖ N()

5. Find P {1, 2, 3} . (Hint: It has eight elements.)

6.Assumethat*a*and*b*areentitiesandthat*a *. Let *A *and *B *be the sets defined by*A** *={ *a*, {*b*}, {*a*, *b*} } and *B *= { *a*, *b*, {*a*, {*b*}} }. Determine whether each of the following statements is true or false. Explain your answers.

a) *b *∈ *A *b) {*a*, *b*} ⊆ *A *c) {*a*, *b*} ⊆ *B*

d) {*a*, *b*} ∈ *B *e) {*a*, {*b*}} ∈ *A *f) {*a*, {*b*}} ∈ *B*

7. Since P(*A*) is a set, it is possible to form the set P P(*A*) . What is P P(∅) ? What is P P({*a*,*b*}) ? (Hint: It has sixteen elements.)

- In the English sentence, “She likes men who are tall, dark, and handsome”, does she like an intersection or a union of sets of men? How about in the sentence, “She likes men who are tall, men who are dark, and men who are handsome”?
- If
*A*is any set, what can you say about*A*∪*A*? About*A*∩*A*? About*A*∖*A*? Why? - Suppose that
*A*and*B*are sets such that*A*⊆*B*. What can you say about*A*∪*B*? About*A*∩*B*?About

*A*∖*B*? Why? - Suppose that
*A*,*B*, and*C*are sets. Show that*C*⊆*A*∩*B*if and only if (*C*⊆*A*) ∧ (*C*⊆*B*).

12. Suppose that *A*, *B*, and *C *are sets, and that *A*⊆*B *and *B*⊆*C*. Show that *A*⊆*C*.

- Suppose that
*A*and*B*are sets such that*A*⊆*B*. Is it necessarily true that P(*A*) ⊆ P(*B*) ? Why or why not? - Let
*M*be any natural number, and let*P*(*n*) be a predicate whose domain of discourse includes all natural numbers greater than or equal to*M*. Suppose that*P*(*M*) is true, and suppose that*P*(*k*) →*P*(*k*+ 1) for all*k*≥*M*. Show that*P*(*n*) is true for all*n*≥*M*. - Prove that the number of propositional variables is always at most one more than the number of connectives for every formula
*φ*∈*PROP*.