Lesson 1

Basic Problems.

1. (5 points) Prove that if \(A\) and \(B\) are equinumerous, then \(A \times A\) and \(B \times B\) are equinumerous.
2. (10 points) Consider the set of infinite sequences over \(\{0, 1, 2\}\) where the sum of any two consecutive digits is not equal to \(2\). What is the cardinality of this set?
3. (10 points) Prove that the set of algebraic numbers (i.e., roots of nonzero polynomials with integer coefficients) is countable.
   Hint:

   Recall that a polynomial of degree \(n\) has at most \(n\) roots.
4. (15 points) Prove the uncountability of the interval \([0,1]\) without using infinite binary sequences.
   Hint:

   Assume that the set \([0,1]\) is countable. For each number \(0 \le x \le 1\), consider its unique infinite representation. Construct a real number that cannot possibly appear in the enumeration.
5. (15 points) Prove that a set is infinite if and only if it is equinumerous to its proper subset.
6. (15 points) Prove that every infinite set contains an infinite number of pairwise disjoint countable subsets.
7. (15 points) Prove that the set of infinite sequences of reals is equinumerous to \(\mathbb{R}\).
8. (15 points) Is it possible to partition the plane \(\mathbb{R}^{2}\) into two sets \(A\) and \(B\) such that \(A\) intersects every horizontal line in a finite set, and \(B\) intersects every vertical line in a finite set?