MATH5301 Elementary Analysis. Homework 3
Let X denote the universal set. Two subsets A and B are said to have the same cardinality if there is a bijection
f : A → B. Notation: |A| = |B|.
(a) Prove that |A| = |B| is an equivalence relation on the set of all subsets of X.
(b) Is it true that if |A1| = |B1| and |A2| = |B2| then |A1 ∪ A2| = |B1 ∪ B2|?
Finish the prove of the Cantor-Bernstein theorem: For the sets A and B, such that |A| 6 |B| and |B| 6 |A| define
A∞ as the set of all elements of A having infinite order, A0 as the set of all elements of A having even order and A1
the set of all elements of A having odd order. Similarly for B.
(a) Show that |A∞| = |B∞|
(b) Construct an injective mapping A1 → B0
(c) Show that this mapping is surjective
Set A is called countable if |A| 6 |N|. Prove that the following sets are countable
(a) Set Z+ of all non-negative integer numbers
(b) Set 2N of all even numbers
(c) Set Z
2 of all ordered pairs of integer numbers
(d) Set Q of all rational numbers
(e) Set Q2 of all ordered pairs of rational numbers
Prove that the following sets are countable
(a) Set P5(Z) of all polynomials of degree 5 with integer coefficients
(b) Any collection of non-intersecting discs on a plane
(c) Any collection of non-intersecting T-shapes on a plane. T-shape consists of two perpendicular line segments such
that one of the segments is attached by one of its endpoints to the center of the other segment. The lengths of
these segments can be arbitrary. The orientation of the T-shape can be arbitrary.
(d) Set P of prime numbers.
(e) Set A of all algebraic numbers, i.e. the numbers which are roots of some polynomials with integer coefficients.
Prove that for any infinite set A there exists B ⊆ A, so that |B| = |N|.
Prove that the following sets have the same cardinality (avoid using decimal representation of real numbers)