COMP2922: Models of Computation (Adv) Tutorial 2: Induction
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.
2023-08-24