Solutions to Kolmogorov and Fomin: Second problem set (previous blog)

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 M \sim M \bigcup A.

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, M \sim B. Also, any two countable sets are equivalent, by definition. So, M \sim B \sim A \sim M \bigcup A. 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 \frac{p}{10^{q}}=\alpha, say. Let us say, that the “height” of \alpha is given by |p|+q. For example, \frac{1}{10^{1}}=0.1000\ldots=0.09999\ldots has “height” 2; and \frac{2}{10^{1}} 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 |Q \times Q| = |N \times N|=|N|=\aleph_{0}. 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 |Q \times Q|=|N \times N|=|N|=\aleph_{0}, so also

|Q^{n}|=|N|=\aleph_{0}. QED.

Problem 4:

A number \alpha 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:

p(x) = a_{0}+a_{1}x+a_{2}x^{2}+\ldots+a_{m}x^{m}=0 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 \mathscr{P} of all polynomials p(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots + a_{m}x^{m} with integral coefficients is countable:

It is as follows: For each pair of non-negative integers (n,m), let P(n,m) be the set of all polynomials of degree m. in which |a_{1}|+|a_{2}|+\ldots+|a_{m}|=n. Note that P(n,m) is finite. Hence, \mathscr{P}=\bigcup (P(n,m) : \hspace{0.1in} (n,m) \in N \times N) is countable since it is a countable family of countable sets. But \mathscr{P} is not finite; hence, \mathscr{P} 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: p(x) = a_{0} + a_{1}x + a_{2}x^{2}+\ldots+a_{m}x^{m}=0 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 E = \{ p_{1}(x)=0, p_{2}(x)=0, \ldots\} so that E is the set of polynomial equations.

Define: A_{k} = \{ x: x \hspace{0.1in}is \hspace{0.1in}a \hspace{0.1in}solution \hspace{0.1in}of \hspace{0.1in} p_{k}(x)=0\}.

Since a polynomial of degree n can have at most n roots, each A_{k} is finite. Therefore, A = \bigcup \{ A_{k}: k \in \mathscr{Z}^{+}\} 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:

\mathscr{R} is union of algebraic and transcendental numbers, and since the set of algebraic numbers is countable, whereas \mathscr{R} 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 [0,1] 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: \chi_{A}: A \rightarrow \{ 0,1\} as f(x)=1 when x \in A, and f(x)=0 when x \notin A.

So, now, we first prove the following: Let A be any set and let C(X) be the family of characteristic functions of X, that is, the family of functions f:[0,1]. Then \mathscr{P}(X) \sim C(X), 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 A \in \mathscr{P}(X). Let f: \mathscr{P}(X) \rightarrow C(X) be defined by f(A) = \chi_{A}, that is, f maps each subset A of X into the characteristic function \chi_{A} of A. Also, f is bijective. Hence, \mathscr{P}(X)  \sim C(X). QED.

Problem 7:

Give an indirect proof of the equivalence of the closed interval [a,b], the open interval (a,b) and the half-open interval [a,b) or (a,b]

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 A_{1} equivalent to B, while B contains a subset B_{1} 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.