Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP2922: Models of Computation (Adv)

Tutorial 2: Induction

August 13, 2023

Recap: Recursively-Defined Sets and Structural Induction

Both N and the set of propositional formulae are examples of recursively-defined sets (also known as inductively-defined sets). When you define a collection of things recursively, the definition usually splits into the following three kinds of clause:

1. Base clauses: establish the ”base objects” or ”atoms”. e.g. 0 ∈ N and atomic formulae.

2. Recursive clauses: provide ways of constructing ”new” objects out of objects already in the collection. e.g. the successor operator on N and the connectives ¬, ∧, ∨ for propositional formulae.

3. Extremal clause: nothing else is in the collection.

The extremal clause of course actually means...

3. If A is any set such that

❼ all of the ”atoms”/”base objects” are in A, and

❼ A contains all of the objects which can be constructed from objects in A using the recursive clauses,

then A contains all of the objects in the collection.

Extremal clauses allow us to justify inductive proof frameworks for recursively-defined sets, as follows.

If you want to prove that P is true for all objects in a recursively-defined set:

1. Base case: prove that P(x) is true for all ”atoms”/”base objects” x.

2. Inductive hypothesis: assume that P is true of some list of arbitrary objects x1, x2, . . . , xk in the collection. (However many you need for the inductive step. For propositional formulae, k = 2 suffices.)

3. Inductive step: using the inductive hypothesis, prove that P is true of the objects constructible using the recursive clauses, applied to the objects x1, x2, . . . , xk.

You can additionally define recursive functions on recursively-defined sets without fear of ill-definition, provided that the following properties also hold:

❼ The recursive construction rules are injective.

❼ The recursive construction rules don’t yield base elements.

❼ The images of the recursive construction rules are disjoint from one another.

Exercises

Problem 1

Let F be a propositional formula. Denote by mF the amount of connectives in F (i.e. ¬, ∧, ∨), and nF the amount of atoms in F.

Prove that nF ≤ mF + 1.

Problem 2

Let L be a language over alphabet {a, b}. Assume the following properties hold:

❼ ε ∈ L.

❼ Whenever u, v ∈ L for any strings u and v, also ub ∈ L, aubv ∈ L, and buav ∈ L.

❼ Nothing else is in L.

Using structural induction or otherwise, show that L ⊆ {s ∈ {a, b} ∗ | |s|b ≥ |s|a}.

(Recall that |s|a denotes the amount of occurrences of the symbol a in the string s.)

Problem 3

Consider the function Rev : Σ∗ → Σ ∗ , defined recursively as follows:

1. Rev(ε) = ε

2. Rev(xa) = aRev(x)

The following is an ”inductive” proof that Rev(bx) = Rev(x)b.

1. Base case: if x = ε: then Rev(bx) = Rev(bϵ) = bRev(ϵ) = bϵ = ϵb = Rev(ϵ)b = Rev(x)b

2. Inductive hypothesis: assume true for x, i.e. assume that Rev(bx) = Rev(x)b.

3. Inductive step: prove true for xa. i.e. assume Rev(bx) = Rev(x)b, prove Rev(bxa) = Rev(xa)b.

Rev(bxa) = aRev(bx) (by def 2)

= aRev(x)b (by ind hyp)

= Rev(xa)b (by def 2)

The structure of this proof appears to leverage a recursive structure on Σ∗ = S n∈N Σ n :

1. ε ∈ Σ ∗ .

2. If x ∈ Σ ∗ and a ∈ Σ, then also xa ∈ Σ ∗ .

3. Nothing else is in Σ∗ .

Clearly clauses 1 and 2 above are true of Σ∗ . Interpreting the third clause as an extremal clause, prove that it is true, and justify the inductive proof framework that the above proof relies upon.