18.100B Problem Set 2

Due in class Tuesday, February 19. You may discuss the problems with other students, but you should write solutions entirely on your own.

1. Text, page 23, number 17.

2. Text, page 43, number 2.

3. Text, page 43, number 5.

4. Text, page 43, number 6.

5. This problem is about the relationship between the formal idea of lexicographic order (discussed in the supplementary notes handed out February 8 and 11) and real numbers.

Let L be the set of all infinite words formed from the two letters 0 and 1:

L = {x = a_{1}a_{2}a_{3} ⋯ | a_{i} ∈ {0, 1}}.

(The difference from the definition of “long words” in the notes is that blanks are not allowed. I’ve used just two letters and eliminated blanks to simplify the problem.) Define the lexicographic order on L as in the notes, using the order 0 < 1 on the two letters. Your task is to find a function f from L to the unit interval [0, 1] (the set of all real numbers between 0 and 1) having the properties

1. f(000 ⋯) = 0, and f(111 ⋯) = 1.

2. If x and y are in L and x ≤ y, then f(x) ≤ f(y). (You don’t need to prove that the function f you define has these two properties; just invent something that ought to work.)

For which x and y in L is f(x) = f(y)? (Again, you don’t have to prove that your answer is correct.)

A hint for this whole problem is the equation

.9999 … = 1.0000 …