Chapter 2 Set Theory

104

Discrete Mathematics

CHAPTER 2

Let the universal set be $Z$ . Let $A = {1, 2, 3, 4}, B = {2 k + 1 : k \in Z}$ (the set of odd integers) and $C = {n \in Z : - 5 \leq n \leq 0} .$ Write out the following:
(i) $A \cap B, A \cap C, B \cap C$
(ii) $A \cup B, A \cup C$ .
(iii) $A ∖ B, B ∖ C$ .
(iv) $B^{c}, C^{c}$ .

Show that $(A \cup B) - (A \cap B) = (A - B) \cup (B - A)$ .

Calculate $A \cap B$ where $A$ is the unit disk ( $A \subset C$ ) and $B = {f (z) : z \in C, | z | < 1, f (z) = \frac{a - z}{1 - \bar{a} z}}$

Let $f$ and $g$ be the functions from the set of integers to the set of integers defined by
$f (x) = e^{x}$ and $g (x) = \sin x$ . What is the composition of $f$ and $g$ ? What is the composition of $g$ and $f$ ?

Let $E = {x : f (g (x)) - \log \sin x \leq 3 - \log 2, x \in (0, π / 2)}$ , find $E$ .

Let $E$ denote the set of even integers and $O$ denote the
set of odd integers. Determine each of these sets.

$E \cup O$
b) $E \cap O$
c) $Z - E$
d) $Z - O$

Show that $R \sim (0, 1)$

Show that $(0, 1) \sim [0, 1]$ .

A function $f : A \to B$ is invertible if and only if $f$ is a bijection.

Show that $X$ and $Y$ are countable sets, then $X \cup Y$ is also a countable set.

Let $n \in N,$ and let $X_{1}, X_{2}, \dots, X_{n}$ be nonempty countable sets. Then $\prod_{i = 1}^{n} X_{i} = X_{1} \times X_{2} \times$ $\dots \times X_{n}$ is countable

Show that the set of irrational numbers is an uncountable set.

Show that every open set in $R^{n}$ is measurable.

Show that $m (E) = 0$ where $E$ is a countable set

A countable union of measurable sets is measurable.

Suppose $E$ is a measurable subset of $R^{d} .$ Then, for every $ϵ > 0$ ,show that
(i) There exists an open set $O$ with $E \subset O$ and $m (O - E) \leq ϵ$
(ii) There exists a closed set $F$ with $F \subset E$ and $m (E - F) \leq ϵ$ .
(iii) If $m (E)$ is finite, there exists a compact set $K$ with $K \subset E$ and $m (E - K) \leq ϵ$
(iv) If $m (E)$ is finite, there exists a finite union $F = ⋃_{j = 1}^{N} Q_{j}$ of closed cubes such that
$m (E △ F) \leq ϵ$

In the unit interval [0,1] consider a subset $E = {x ∣$ in the decimal expansion of $x$ there is no 4 $}$ Show that $E$ is measurable and calculate its measure.

Solution

** Solution of 3:**
The answer is the unit disk.

** Solution of 5:**
We will prove that $e^{x} - \log x > 3 - \log 2.$ Let $p (x) = e^{x} - \log x = e^{x} - 2 x + 2 x - \log x$
Then $h (x) = e^{x} - 2 x, j (x) = 2 x - \log x$ ,we have $h (x) \geq 2 - 2 \log 2, g (x) \geq 1 + \log 2$ . $h (x) = 2 - \log 2 iff x = \log 2, g (x) = 1 + \log 2 iff x = 1 / 2 .$ Then we have $h (x) + j (x) > 3 - \log 2$ . Hence $e^{\sin x} - \log \sin x > 3 - \log 2$ ,the answer is $\emptyset .$

** Solution of 7:**

** Solution of 9:**

Assume that $f$ is invertible with inverse $f^{- 1} .$ Let $f (a_{1}) = f (a_{2})$ for some $a_{1}, a_{2} \in A .$ Then $f^{- 1} (f (a_{1})) = f^{- 1} ((f (a_{2}))$ and so $a_{1} = a_{2} .$ Hence $f$ is injective.

Let $b \in B$ with $a = f^{- 1} (b) \in∣ A .$ Then $f (a) = b$ and so $f$ is surjective. Therefore $f$ is a bijection.
assume that $f$ is a bijection. This means that for every $b \in B$ there is a unique $a \in A$ with $f (a) = b$ and we can define $f^{- 1} (b) = a$ . This defines the inverse function $f^{- 1} : B \to A,$ as required.

** Solution of 10:**

Suppose that $X$ and $Y$ are countable. In fact , there exists surjective functions
$f : N \to X and g : N \to Y .$
Define a function $h : N \to (X \cup Y)$ by
$h (k) = {\begin{cases} f (\frac{k}{2}) & k is even \\ g (\frac{k + 1}{2}) & k is odd \end{cases}$
Since $f$ and $g$ are surjective, we have $h (N) = f (N) \cup g (N) = X \cup Y,$ and thus $h$ is a surjective function. Hence, we have $X \cup Y$ is countable.

** Solution of 14:**

　　　　　　
By assumption, we can enumerate $Δ = {c_{j} ∣ j \in N}$ . Now for any $ϵ > 0$ choose the sequence of radii $r_{j} = 2^{- j - 1} ϵ$ , then clearly $⋃_{j \in N} B_{r_{j}} (c_{j})$ contains $Δ$ (since it contains every $c_{j} \in Δ$ as centre of a ball) and we have $\sum_{j = 1}^{\infty} r_{j} = \sum_{k = 0}^{\infty} 2^{- k \frac{ϵ}{4}} = \frac{ϵ}{2} < ϵ$ .

** Solution of 15:**

Suppose $E = ⋃_{i = 1}^{\infty} E_{j},$ where each $E_{j}$ is measurable. Given $ϵ > 0,$ we choose for each $j$ an open set $O_{j}$ with $E_{j} \subset O_{j}$ and $m_{*} (O_{j} - E_{j}) \leq ϵ / 2^{j} .$ Then $O = ⋃_{j = 1}^{\infty} O_{j}$ is open, $E \subset O,$ and $(O - E) \subset ⋃_{j = 1}^{\infty} (O_{j} - E_{j}),$ so monotonicity and sub-additivity of the
outer measure imply
$m_{*} (O - E) \leq \sum_{j = 1}^{\infty} m_{*} (O_{j} - E_{j}) \leq ϵ$

** Solution of 17:**
Consider the complement of $E$ . It has a digit 4 in the $n$ -th place of the decimal expansion of $x$ . Then such numbers consists of the whole half interval of length $(1 / 10)^{n}$ . There are countably many such intervals. The union of them is measurable. Hence $E$ is measurable.
The complement of $E$ has measure $1 / 10 + 9 (1 / 10)^{2} +$ $\dots = 1,$ then we have $m (E) = 0$