Mathematics for Computer Science

7.5. Induction in Computer Science 175

Constructor cases:

Iff;gare F18’s, then so are

1.fCg,fg,eg(the constante),

2. the inverse functionf.1/,


3. the compositionfıg.

(a)Prove that the function1=xis an F18.

Warning:Don’t confuse1=xDx^1 with the inverse, id.1/of the identity func-
tion id.x/. The inverse id.1/is equal to id.

(b)Prove by Structural Induction on this definition that the Elementary 18.01
Functions areclosed under taking derivatives. That is, show that iff.x/is an F18,
then so isf^0 WWDdf=dx. (Just work out 2 or 3 of the most interesting constructor
cases; you may skip the less interesting ones.)

Problem 7.4.
Here is a simple recursive definition of the set,E, of even integers:

Definition. Base case: 02 E.
Constructor cases: Ifn 2 E, then so arenC 2 andn.

Provide similar simple recursive definitions of the following sets:

(a)The setSWWDf 2 k 3 m 5 njk;m;n 2 Ng.

(b)The setTWWDf 2 k 3 2kCm 5 mCnjk;m;n 2 Ng.

(c)The setLWWDf.a;b/ 2 Z^2 j 3 j.ab/g.
LetL^0 be the set defined by the recursive definition you gave forLin the previous
part. Now if you did it right, thenL^0 DL, but maybe you made a mistake. So let’s
check that you got the definition right.

(d)Prove by structural induction on your definition ofL^0 that

L^0 L:

(e)Confirm that you got the definition right by proving that

LL^0 :

(f)See if you can give anunambiguousrecursive definition ofL.