If x is rational, then x2
2.
- The converse:
If x2 2, then
x is rational.
- The contrapositive: If x2 = 2, then x is irrational.
- 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.
- 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.
. 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
- 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 of2:
(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.
- 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.
- 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, ...