## Solutions to exercises due Wednesday, September 20

Posted: Oct 3, 2000

1. We were supposed to consider the following statement, about a real number:

If  x  is rational, then  x2 2.

1. The converse:   If  x2 2,  then  x  is rational.
2. The contrapositive:   If  x2 = 2,  then  x   is irrational.
3. The converse is false.   We can use  x =  as a counterexample. One can prove that  is irrational by the same method that we used in class to prove that   is irrational.
4. The contrapositive is true.   Any statement of the form "If P, then Q" is equivalent to its contrapositive. Since we proved in class that is irrational, you can either cite that fact, or give a suitably adapted proof.

2. In class, we gave a 1-to-1 correspondence between the positive integers and . By striking out alternate lines of the chart in the text, we get a 1-to-1 correspondence between the positive integers and the positive rationals. Similarly, we get a 1-to-1 correspondence between the negative integers and the negative rationals. We finish by letting 0 in correspond to 0 in

3. ...
1. We have a 1-to-1 correspondence between the positive integers and . So, we can list the rational numbers as:
= {a1, a2, a3, ... }.

Now, consider the following chart, listing the elements of 2:
 (a1,a1) (a1,a2) (a1,a3) . . . (a2,a1) (a2,a2) (a2,a3) . . . (a3,a1) (a3,a2) (a3,a3) . . . . . . . . . . . .

So, the point is to go through this chart in a diagonal fashion, similarly to the proof on pp. 5 and 6 of the text.

2. Yes, there is a 1-to-1 correspondence from   to  2 .
One approach is to use the fact that there is a 1-to-1 correspondence between and the power set P() of .
By the same method as in part a., there is a 1-to-1 correspondence between and 2. We can use these two facts to construct a 1-to-1 correspondence between 2 and P()P().
There is another approach, perhaps with more intuitive content. This is easier to explain if we construct a 1-to-1 correspondence between the open interval  (0,1)  and  (0,1)(0,1). We begin by constructing a map from  (0,1)(0,1)  to  (0,1),   sending      (0.a1a2a3..., 0.b1b2b3...)   to   0.a1b1a2b2a3b3...   This map is 1-to-1 but it is not onto, because of issues about decimal expansions that end with a pattern of 9's in alternate places. Fortunately, however, there are LOTS of 1-to-1 maps in the opposite direction. So, we can apply the Bernstein-Schroeder theorem to get the desired 1-to-1 correspondence.

4. ...
• Version 1 We have a 1-to-1 mapping  g: (0,1) --> [0,1),  given by  g(x) = x,  and similarly we have a 1-to-1 mapping  f: [0,1) --> (0,1),  given by (for instance)  f(x) = (x + 1)/2.   (Note that neither of these maps is onto.)   Applying the Bernstein-Schroeder theorem, we conclude that there is a 1-to-1 correspondence between  (0,1)  and  [0,1).

• Version 2   (Some exploratory comments first.) If we apply the method of the proof of the Bernstein-Schroeder theorem (on pages 8 and 9 of the text) to the mappings  f and  g, from the solution to Version 1, we find that the points in [0,1) with an even number of preimages are  0, 1/2, 3/4, ...,  while the points in (0,1) with an odd number of preimages are  1/2, 3/4, 7/8, ...
These two sets are supposed to correspond to each other.   (aha!!)
Now, the solution: We get a 1-to-1 correspondence  h: [0,1) --> (0,1)   as follows. We set   h(x) = x   if  x  is not an element of the exceptional set {0, 1/2, 3/4, ... }, and we define  h  for elements of this (obviously countable) exceptional set by shifting them over to the next place. Explicitly:  h(1 - 2-n) = 1 - 2-n-1   for n = 0, 1, 2, ...