Chapter 2 Set Theory
** Discrete Mathematics **
CHAPTER 2
Let the universal set be $\mathbb{Z}$. Let $A=\{1,2,3,4\}, B=\{2 k+1: k \in \mathbb{Z}\}$ (the set of odd integers) and $C=\{n \in \mathbb{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 \backslash B, B \backslash 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 \mathbb C $ ) and $ B=\{ f(z):z\in \mathbb 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,\pi /2 ) \}$ , find $E$.
Let $\mathbb E $ denote the set of even integers and $ \mathbb O $ denote the
set of odd integers. Determine each of these sets.
- $\mathbb E \cup \mathbb O$
b) $\mathbb E \cap \mathbb O$
c) $\mathbb Z − \mathbb E$
d) $\mathbb Z -\mathbb O$
Show that $\mathbb R \sim (0,1) $
Show that $ (0,1)\sim [0,1] $ .
A function $f: A \rightarrow 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 \mathbb{N},$ and let $X_{1}, X_{2}, \ldots, X_{n}$ be nonempty countable sets. Then $\prod_{i=1}^{n} X_{i}=X_{1} \times X_{2} \times$$\cdots \times X_{n}$ is countable
Show that the set of irrational numbers is an uncountable set.
Show that every open set in $\mathbb{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 $\mathbb{R}^{d} .$ Then, for every $\epsilon>0$,show that
(i) There exists an open set $\mathcal{O}$ with $E \subset \mathcal{O}$ and $m(\mathcal{O}-E) \leq \epsilon$
(ii) There exists a closed set $F$ with $F \subset E$ and $m(E-F) \leq \epsilon$.
(iii) If $m(E)$ is finite, there exists a compact set $K$ with $K \subset E$ and $m(E-K) \leq \epsilon$
(iv) If $m(E)$ is finite, there exists a finite union $F=\bigcup_{j=1}^{N} Q_{j}$ of closed cubes such that
$m(E \triangle F) \leq \epsilon$
In the unit interval [0,1] consider a subset$E=\{x \mid$ 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-2x+2x-\log x $
Then $ h(x)=e^x -2x,j(x) =
2x-\log x $,we have $h(x)\geq 2 -2\log 2,g(x)\geq 1 + \log 2 $. $ h(x)=2-\log 2 \ \mathrm{ iff } x=\log 2 ,g(x)=1+\log 2 \ \mathrm {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\left(a_{1}\right)=f\left(a_{2}\right)$ for some $a_{1}, a_{2} \in A .$ Then $f^{-1}\left(f\left(a_{1}\right)\right)=f^{-1}\left(\left(f\left(a_{2}\right)\right)\right.$ and so $a_{1}=a_{2} .$ Hence $f$ is injective.
Let $b \in B$ with $a=f^{-1}(b) \in \mid 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 \rightarrow A,$ as required.
** Solution of 10:**
Suppose that $X$ and $Y$ are countable. In fact , there exists surjective functions
$$
f: \mathbb{N} \rightarrow X \text { and } g: \mathbb{N} \rightarrow Y \text { . }
$$
Define a function $h: \mathbb{N} \rightarrow(X \cup Y)$ by
$$
h(k)=\left\{\begin{array}{ll}
f\left(\frac{k}{2}\right) & k \text { is even } \\
g\left(\frac{k+1}{2}\right) & k \text { is odd }
\end{array}\right.
$$
Since $f$ and $g$ are surjective, we have $h(\mathbb{N})=f(\mathbb{N}) \cup g(\mathbb{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 $\Delta=\left\{c_{j} \mid j \in \mathbb{N}\right\}$. Now for any $\epsilon>0$ choose the sequence of radii $r_{j}=2^{-j-1} \epsilon$, then clearly $\bigcup_{j \in \mathbb{N}} B_{r_{j}}\left(c_{j}\right)$ contains $\Delta$ (since it contains every $c_{j} \in \Delta$ as centre of a ball) and we have $\sum_{j=1}^{\infty} r_{j}=\sum_{k=0}^{\infty} 2^{-k \frac{\epsilon}{4}}=\frac{\epsilon}{2}<\epsilon$.
** Solution of 15:**
Suppose $E=\bigcup_{i=1}^{\infty} E_{j},$ where each $E_{j}$ is measurable. Given $\epsilon>0,$ we choose for each $j$ an open set $\mathcal{O}_{j}$ with $E_{j} \subset \mathcal{O}_{j}$ and $m_{*}\left(\mathcal{O}_{j}-E_{j}\right) \leq \epsilon / 2^{j} .$ Then $\mathcal{O}=\bigcup_{j=1}^{\infty} \mathcal{O}_{j}$ is open, $E \subset \mathcal{O},$ and $(\mathcal{O}-E) \subset \bigcup_{j=1}^{\infty}\left(\mathcal{O}_{j}-E_{j}\right),$ so monotonicity and sub-additivity of the
outer measure imply
$$ \qquad \qquad
m_{*}(\mathcal{O}-E) \leq \sum_{j=1}^{\infty} m_{*}\left(\mathcal{O}_{j}-E_{j}\right) \leq \epsilon
$$
** 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}+$ $\cdots=1,$ then we have $m(E) =0$
$ $
$ $
$ $
$ $
$ $
$ $
$ $
$ $
$ $
$ $
$ $
$ $
$ $
