Massachusetts Institute of Technology Handout 9 6.042J/18.062J: Mathematics for Computer Science September 19, 2000 Professors Nancy Lynch and Shlomi Dolev

Problem Set 3

Due: 2:35pm in lecture, September 26, 2000.

Self-study: More set theory Read: Velleman, Sections 1.3, 1.4, 2.3. Self-study problems (not to be handed in): Velleman §1.3, Exercise 4, §1.4 Exercises 1, 3, 4, 5, 6, 8, §2.3 Exercises 2, 3, 5, 6

Reading: Velleman, Chapter 4 Rosen, Sections 3.2, 3.3, 3.4, Chapter 6.

Problem 1 Well-Ordering A set is well-ordered if every nonempty subset of the set has a least element. Determine whether each of the following sets is well-ordered. Explain your reasons.

(a) The set of integers.

(b) The set of integers greater than −100.

(c) The set of positive rationals.

(d) The set of positive rationals with denominator less than 100.

Problem 2 Structural Induction

The set SSS of “super-symmetric strings” is defined as follows:

1. The length one strings consisting of individual letters of the alphabet, a, b, c, d, ... z, are in SSS.

2. If α and α′ are two strings in SSS then the string αα′α is in SSS.

3. SSS contains nothing else.

(a) Which of the following are super-symmetric strings? i. a ii. aaaba iii. abcbacabcba iv. λ, the empty string v. abaabcbaaba

(b) Prove by induction that in any super-symmetric string α, exactly one letter appears an odd number of times.

2 Handout 9: Problem Set 3 Problem 3 Induction and Recursive Algorithms

(a) Rosen §3.4, Exercise 18, and prove correctness of your algorithm. Problem 4 Relations

(a) Velleman §4.2, Exercise 3

(b) Velleman §4.2, Exercise 7 Problem 5 Relations — Ordering Velleman §4.3, Exercise 9. Problem 6 Relations — Properies

(a) Velleman §4.4, Exercise 1.

(b) Velleman §4.4, Exercise 5. Problem 7 Relations — Equivalence relations

(a) Velleman §4.5, Exercise 3.

(b) Velleman §4.5, Exercise 5.

(c) Velleman §4.5, Exercise 12. Problem 8 Relations — Topological sorting

(a) Find two total orders that are topological sorts of the divisibility relation for the set of natural numbers 1-8.

(i) One with the MOST POSSIBLE pairs out of numerical order. (ii) One with the FEWEST POSSIBLE pairs out of numerical order.