Recall that a sequence is a function f: N rightarrow R. Writing a_i = f(i), we c
ID: 3032106 • Letter: R
Question
Recall that a sequence is a function f: N rightarrow R. Writing a_i = f(i), we can think of the sequence given by f as an infinite ordered list of real numbers a_1, a_2, a_3, ... (where the list can have repeats). Let X be the set of all sequences f: N rightarrow R such that the image of f is contained in {0, 1}. For example, one such sequence is f: N rightarrow R given by f(n) = {0 n is even 1 n is odd. In other words this sequence looks like 1, 0, 1, 0, 1, 0, ... Prove that X is uncountable. (Use a variation of Cantor's diagonal trick). Let Y be the set of all subsets of N, in other words Y = P(N) is the power set of N. Let X be the set of all sequences with image in {0, 1} considered in problem 2. Show that X and Y are equipotent. Conclude that Y is uncountable. Let Z be the set of all finite subsets of N. Show that Z is countable. Let W be the set of all infinite subsets of N. Show that W is uncountable. (Note that Y = Z U W).Explanation / Answer
a) We can de¯ne an injection U ! Q X Q by sending the interval (q; r) to the
ordered pair (q; r) So U is countable because |Q X Q| =
|N| X |N| = |N|.Hence we get that y is uncountable.
b) Let U be an open set. Given x 2 U, there exists " > 0 with (x ¡ "; x + ") ½ U.
By the density of the rationals, there exists a rational q with x ¡ " < q < x
and there exists a rational r with x < r < x + ". Thus, x 2 (q; r) 2 U, and
(q; r) ½ (x ¡ "; x + ") ½ U. Therefore it is countable
c) Let X denote the set of all open subsets of R. Show that jX j = jRj. (Hint: recall
that |R| = |P(N)|.)
We can de¯ne an injection R ! X by sending x 2 R to the interval (x¡1; x+1).
We need to de¯ne an injection X ! R. Using the hint, we need to de¯ne an
injection X ! P(N). Since |N| = |U|, we have |P(N)| = |P(U)|. We therefore
want to de¯ne an injection f : X ! P(U). For U 2 X, So W is uncountable.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.