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).

(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.

MScMathematics

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

Leave a Reply Cancel reply

Mathematics Hothouse shares:

Like this:

Related

Leave a Reply Cancel reply