Prove the following statements.

1. Every infinite set contains a subset that is countable.

2. Every subset of a countable set is countable.

3. A countable union of countable sets is countable.

4. If A infinite and B is countable, then |A È B| = |A|.

5. Cardinality of an infinite set is not affected by the removal of a countable subset, provided that the

set that remains is infinite.

6. The set of irrational numbers is uncountable.

7. The set of polynomials with integer coefficients is countable.

8. The set of algebraic numbers is countable.

9. The set of transcendental numbers is uncountable.

10. Cardinality of the set of irrational numbers is c.

11. Cardinality of the set of transcendental numbers is c.

12. |N ´ R| =|R|.

13. If |A| = c and |B| = c, then |A È B| = c.

14. The union of a countable number of sets of cardinality c has the cardinality c.

15. How many subsets or R has the cardinality c ?

16. If |A| = À ₀ and |B| = c, then |A È B| = c.

17. If |A| = c and |B| = c, then |A ´ B| = c.

Find the cardinality of the following sets.

1. Set of two element subsets of N.

2. Set of finite subsets of N.

3. Set of infinite subsets of N.

4. Set of three element subsets of R.

5. Set of finite subsets of R.

6. Set of countable subsets of R.

7. Set of uncountable subsets of R.

8. Set of infinite subsets of R.

9. Set of constant functions from R to R.

10. Set of constant functions from R to N.

11. Set of functions from N to R.

12. Set of functions from R to N.

13. Set of linear functions from R to R.

14. Set of polynomial functions from R to R.

15. Set of continuous functions from R to R.

16. Set of real numbers whose decimal representation end in an infinite sequence of 24.

17. Set of real numbers whose decimal representation does not have the digits 2 or 3.

18. { x | x º 2 ( mod 7 ) }

18. { (x, y) | y = x², 0 < x < 1 }

19. Set of circles in the coordinate plane with rational radii and centers at points with rational

coordinates.

20. Set of non-overlapping circles in the plane.

Functions and Schroder-Bernstein

1. Finish the sentence:- A relation can be one-one, ………

Sketch graphs to illustrate each case (equations are not necessary!).

2. Finish the sentence:- A function can be one-one,………

Sketch graphs to illustrate each case.

3. Suppose A = { 0, 1, 2 } and B = { a, b }. Define an onto function from A to B. Can you define

another one? Can you define an onto function from B to A ? Can you define an one-one function in

any direction ?

4. Suppose A is an unknown set and B = { 7 }. Can you define (without any ambiguity) a function

from A to B ?

5. Suppose there is a one-one function f from set A to set B, and a one-one and onto function g from

set B to set C. Using a diagram explain why there is a subset of C ( let's call it C₀ ), from which

there exists an onto function to the set A. Use f and g to define C₀ , and the new onto function from

C₀ to A.

6. Suppose there are onto functions from A to B and from B to A. Show |A| = |B|.

7. Suppose |S| £ |T|. Prove there exists an onto function from T to S.

8. Prove if the domain of a function is countable, then its range is also countable.

9. Suppose A Í B Í C Í D, and |A| = |D|. Prove |A| = |B| = |C| = |D|.

10. Suppose A Ê B and |B| = |B È C|. Prove |A| = |A È C|.

11. Suppose A Ê C, B Í D, and |C È D| = |C|. Prove |A È B| = |A|.