Problem 1:
Prove that a set with a uncountable subset is itself uncountable.
Proof 1:
That is, to prove that: if a set X has an uncountable subset Y, then set X itself is uncountable.
That is, to prove that (contra-positive): If a set X is NOT uncountable, then the set X does NOT contain an uncountable subset.
That is, to prove that: if a set X is countable, then the set X contains a countable subset, which is quite true.
Problem 2:
Let M be any infinite set and set A is any countable set. Prove that .
Proof 2:
We know that an infinite subset is equivalent to a proper subset of itself. And, that every infinite set contains a countable subset. So, here, set M is equivalent to a proper countable subset, say B of it. Hence, . Also, any two countable sets are equivalent, by definition. So,
. QED.
Problem 3:
Prove that each of the following sets is countable:
(a) The set of all numbers with two distinct decimal expansions (like 0.50000….and 0.49999…)
(b) The set of all rational points in the plane (that is, points with rational co-ordinates).
(c) The set of all rational intervals (that is, intervals with rational end points).
(d) The set of all polynomials with rational coefficients.
Proof 3a:
Such numbers are of the form , say. Let us say, that the “height” of
is given by
. For example,
has “height” 2; and
has “height” 3 etc. Clearly, all such numbers can be arranged in one-one correspondence with the set of positive integers, and it is therefore countable. (For details, refer text section or a previous blog detailing why rational numbers are countable.) QED.
Proof 3b:
Because . QED.
Proof 3c:
This is a subset of the set in 3b. And, we know that every subset of a countable set is countable. QED.
Proof 3d:
this deals with a cardinality of cross product of two sets, and more than two sets.
Just as , so also
. QED.
Problem 4:
A number is called algebraic if it is a root of a polynomial equation with rational coefficients. Prove that the set of all algebraic numbers is countable.
Instead, we prove the following:
(PS: the proof of the above is almost same as 3d.)
A real number r is called an algebraic number if r is a solution to a polynomial equation:
with integral coefficients. Prove that the set A of algebraic numbers is countable.
Proof:
Once again, we need to prove the following first: The set of all polynomials
with integral coefficients is countable:
It is as follows: For each pair of non-negative integers , let
be the set of all polynomials of degree m. in which
. Note that
is finite. Hence,
is countable since it is a countable family of countable sets. But
is not finite; hence,
is countable.
In part 2 we want to prove the following: a real number r is called an algebraic number if r is a solution to a polynomial equation: with integral coefficients. Prove the set A of algebraic numbers is countable.
So, by the preceding sub-problem and its proof, the set of polynomial equations is countable. Let so that E is the set of polynomial equations.
Define: .
Since a polynomial of degree n can have at most n roots, each is finite. Therefore,
is a countable family of countable sets. So, A is countable.
QED.
Problem 5:
Prove that there exist uncountably many transcendental numbers, that is, numbers which are not algebraic.
Proof 5:
is union of algebraic and transcendental numbers, and since the set of algebraic numbers is countable, whereas
is not, this implies that the set of transcendental numbers is uncountable. In fact, it has the power of the continuum.
Problem 6:
Prove that the set of all real functions (more generally, functions taking values in a set containing at least two elements) defined on a set M is of power greater than the power of M. In particular, prove that the power of the set of all real functions (continuous and discontinuous) defined in the interval is greater than c. Hint: Use the fact that the set of all characteristic functions (that is, functions taking only the values 0 and 1 ) on M is equivalent to the set of all subsets of M.
Proof 6:
We first use the following:
Given a non-empty set A with at least two elements, define its characteristic function as follows: as
when
, and
when
.
So, now, we first prove the following: Let A be any set and let be the family of characteristic functions of X, that is, the family of functions
. Then
, that is, the power set of X and the set of continuous functions on X are isomorphic, that is, there exists a bijection between these two.
Toward that end, let A be any other subset of X, that is, let . Let
be defined by
, that is, f maps each subset A of X into the characteristic function
of A. Also, f is bijective. Hence,
. QED.
Problem 7:
Give an indirect proof of the equivalence of the closed interval , the open interval
and the half-open interval
or
Proof 7:
This is a direct application of the Cantor-Bernstein theorem: Given any two sets A and B, suppose that A contains a subset equivalent to B, while B contains a subset
equivalent to A. Then, A and B are equivalent.
QED.
Problem 8:
Prove that the union of a finite or countable number of sets each of power c is itself a power of c.
Proof 8:
Because the union is still an uncountable set. In more polished language, the cardinal number of union of two sets is the sum of the cardinals. QED.
Problem 9:
Prove that each of the following sets has the power of continuum:
9a) the set of all infinite sequences of positive integers.
9b) the set of all ordered n-tuples of real numbers.
9c) the set of all infinite sequences of real numbers.
Solution :
Solution 9a:
In this case, each sequence can be uniquely “represented” by a “real decimal number” lying between zero and one. Hence, such a set has the power of the continuum.
Solution 9b and 9c:
Similar argument.
QED.