WEEK 9  

M: Cardinal Arithmetic. Finite, countable and uncountable sets. Examples of countable sets. 
   II.1.6. Proposition. Assume A,B,C are sets. 
              (a) Addition. A u (B u C) = (A u B) u C  and  A u B = B u A
              (b) Multiplication. A x (B x C) ~ (A x B) ~ C  and  A x B ~ B x A
              (c) Distributivity. A x (B u C) = (A x B) u (A x C)
              (d) Exponentiation. A^(B u C) ~ A^B x A^ C   for B,C disjoint
                                              (A x B)^C ~ A^C x B^C
                                              A^(B x C) ~ (A^B)^C
   II.1.7. Definition. We say that the set A is 
                                  (a) of cardinality n for n \in \omega iff A ~ n
                                  (b) finite if A is equinumerous to some element in \omega
                                  (c) countable if A is equinumerous to \omega\
                                  (d) at most countable if A is finite or countable
                                  (e) uncountable if A is not at most countable
   II.1.8. Proposition. (a) If m<n are in \omega then there is no injection from n into m.
                                   (b) If m \in \omega then there is no injection from \omega into m
   II.1.9. Corollary. If m,n are two distinct elements of \omega then they are not equinumerous.
   II.1.10. Proposition. (a) If n \in \omega then \omega x n ~ \omega
                                     (b) \omega x \omega ~ \omega
                                     (c) If A is an infinite subset of \omega then A ~ \omega 
PROBLEMS FOR DISCUSSIONS: 
   1.  Prove the following facts; you can use Schroeder-Bernstein Theorem as well as 
       all facts we have had so far in lectures and discussions
       (a) P(\omega x \omega) ~ P(\omega)
       (b) P(\omega) x P(\omega) ~ P(\omega)  (see WEEK 8, exercise W2 and Prop I.1.6(d))
       (c) Z ~ \omega where Z is the set of all integers
       (d) Q ~ \omega  where Q is the set of all natural numbers (find a suitable subset of 
             \omega x \omega that is equinumerous to Q)
       (e) \omega^\omega ~ P(\omega)  (view \omega^\omega as a set of subsets
             of \omega x \omega
  2. Assume A is a set with a well-ordering R such that all proper initial segments, 
      that is, sets of the form {x \in A | x R a } for some a \in A, are finite. Using the
      theorem on construction by recursion, show that there is a bijection f : \omega --> A.
      Hint: Proceed as in the proof of Propositon II.1.10 (a).
W: Computing cardinalities of sets obtained by unions and cartesian products.
     II.1.11. Proposition. Assume A_1, ... A_n is a finite list of sets.
                 (a) If all the sets A_1, ... , A_n are finite then so is their union
                 (b) If all the sets A_1, ... , A_n are at most countable and at least one of them
                      is infinite then their union is countable.
    II.1.12. Proposition. Assume A is a set that has a countable subset, and that B is a countable
                                     set disjoint with A. Then A u B ~ A.
    II.1.13. Proposition. Assume A is a set such that A x A ~ A. Then
                                     (a) For every n \in \omega we have A^n ~ A
                                     (b) A^<\omega ~ A x \omega (Here A^<\omega is the set of all
                                           finite sequences of elements of A, i.e. the union of all A^n.)
PROBLEMS FOR DISCUSSIONS: By Prop II.1.13, if A x A ~ A then
A^<\omega ~ A x \omega. Since \omega x \omega ~ \omega, we have
\omega^<\omega ~ \omega. Use this fact where needed in the following exercises.
   1. Give an alternative proof of the fact that \omega^<\omega ~ \omega: Let
        <p_i | i < \omega> be the increasing enumeration of all primes. Consider the map
       g : \omega^<\omega --> \omega defined by
       g(<a_0,....a_{n-1}>) = p_0^{a_0+1} . p_1^{a_1+1}. ....... . p_{n-1}^{a_{n-1}+1}
   2. Let Pol(Q) be the set of all polynomials with rational coeffitients. Show that
       the set of all Pol(Q) is countable.
       Hint: Relate polynomials from Pol(Q) to finite sequences of rational numbers.

Fix the following notation.
 -- A^n is the set of all finite sequences of elements of A of length n; 
 -- A^<\omega is the set of all finite sequences of elements of A of arbitrary length;
 -- [A]^n is the set  of all finite subsets of A of lentgh n.
 -- [A]^<\omega is the set of all finite  subsets of A (of arbitrary size).
 -- A^\omega is the set of all sequences of elements of A of length \omega, i.e. the set of 
     all maps p : \omega --> A
 -- [A]^\omega is the set of all countable subsets of  A
 -- INJ(A,<\omega) is the set of all finite injective sequences of elements of A
 -- INJ(A,\omega) is the set of all countable injective sequences of elements of A
Assume there is a linear ordering R on A.
 -- INC(A,R,<\omega) is the set of all finite strictly R-increasing sequences of elements of A;
 -- INJ(A,R,\omega) is the set of all countable strictly R-increasing sequences of A.

   3. Show that we have injections in the directions indicated by arrows:
      \omega -->  [\omega]^<\omega -->  INC(\omega,<,<\omega) -->
       --> INJ(\omega,<,<\omega) --> \omega^<\omega
      Using the fact that \omega^<\omega ~ \omega conclude that all these sets are
      equinumerous. 
      Hint: Concerning the second arrow, notice that each finite set of natural numbers can
      be viewed as a sequence.
   4. In general, assume that R is a linear ordering on A.
       a)  Construct a bijection between
           A^<\omega and INC(A,R,<\omega). Conclude: INC(A,R,\omega) ~ [R]^<\omega.
           Hint: Relate finite R-increasing sequences  in A to finite subsets of A. 
       b) Show that there are injections  as indicated by arrows. 
           A --> [A]^<\omega --> INC(A,R,<\omega) --> INJ(A,R,<\omega) -->
           --> A^<\omega --> [A x \omega]^<\omega.
           Hint: Last arrow: View any finite sequence from A^<\omega as a subset of A x \omega. 
   5. Show that we have injections in the directions indicated by arrows:
       [\omega]^\omega --> INC(\omega,<,\omega) --> INJ(\omega,<,\omega) -->
        --> \omega^\omega --> [\omega x \omega]^\omega --> [\omega]^\omega 
       Observe: This shows that all these sets are equinumerous. Also observe: By Graded
       Homework from WEEK 8, Problem 2, \omega^\omega ~ P(\omega). Hence  
       all these sets are equinumerous to P(\omega).
   6. Generalize the previous exercise: Assume that R is a linear ordering on A. Show that
       we have injections as indicated by the arrows:
       [A]^\omega --> INC(A,R,\omega) --> INJ(A,R,\omega) --> A^\omega -->
        --> [A x \omega]^\omega
   7. Show that the set of all at most countable subsets of \omega is equinumerous to
       P(\omega). Similarly show that the set of all sequences of natural numbers of length 
       at most \omega is equinumerous to P(\omega).
       Hint: Use exercises 3,6 and Prop. II.1.12.
   8. Show that the set of all infinite sequences of rational numbers is equinumerous to
       P(\omega).
       Hint: Relate this set to \omega^\omega.
F: The equinumerosity  of the set of real numbers R with P(\omega). Cantor theorem. 
    II.1.14. Proposition. (a) If a<b are real numbers then the open interval (a,b) is equinumerous 
                                           to the open interval (0,1). Consequently, any two nonempty bounded
                                           open intervals are equinumerous.
                                      (b) R is equinumerous to any open nonempty interval, in particular
                                           to the interval (0,1)
   II.1.15. Theorem. (Cantor). If A is an arbitrary set then there is no surjection f : A --> P(A)
                                                where P(A) is the power set of A.
PROBLEMS FOR DISCUSSIONS:
   1. In general, show that if A,B are sets and B contains at least two distinct elements then
       there is no surjection f : A --> B^A
   2. Show that R is equinumerous to intervals of the form (a,\infty) and (-\infty,a).
   3. Show that the set of all solutions x \in R to all polynomial equations of the form
       a_0 + a_1.x + a_2 . x^2 + ... + a_n . x^n = 0 with rational coeffitients is countable.
       Conclude that there is a real number that is not a solution to any such equation. 
       Hint: Relate such polynomials to finite sequences of rational numbers and use
                the fact that the set of all rational numbers is countable.
   4. Show that the set of all infinite sequences of real numbers is equinumerous to R.
       Hint: Use the fact that R is equinumerous to all infinite 0-1-sequences.
   5. Show that the set of all finite sequences of real numbers is equinumerous to R.
       Hint:  Find injections R --> R^<\omega --> R^\omega. Then use exercise 4 and the
                Schroeder-Bernstein Theorem.
   6. Show that the number of all functions f : Q --> R is continuum. Here Q is the set of
       all rational numbers. 
       Hint: Use the facts that Q is countable and R ~ {0,1}^\omega. Also Prop II.1.6.
   7. Show that the number of all functions f : R --> R is strictly larger than continuum, 
       i.e. there is no surjection F: R --> R^R. 
       Hint: Show there is a surjection G: R^R --> P(R). You can also argue in a different
                way by showing that there is an injection of P(R) into R^R. 
   8. Show that the number of all  continuous functions f : R --> R is continuum. 
       Hint: Use  Exercise 6 and the fact from analysis that any continuous map is uniquely 
                 determined by its values on rational arguments. 
   9. We say that a subset A of R is open  iff A can be expressed as the union (possibly
       infinite) of open intervals. Notice that such a set need not be an interval and may be
       very complicated. Show that the number of all open subsets of R is continuum. 
       Hint: Show that any open set can be written as the union of a set of intervals with
                 rational endpoints.