Set and Function
Lemma 1.1.0 (De Morgan’s law)
(1) $(\cup_{i\in I} A_i)^c = \cap_{i\in I}A^c_i$
(2) $(\cap_{i\in I}A_i)^c = \cup_{i\in I}A^c_i$
<proof>
(a)
\[\begin{align} \begin{split} w\in (\cup_{i\in I} A_i)^c &\iff w \not\in \cup_{i\in I} A_i \\ &\iff w \not\in A_i \text{ for all } i \in I \\ &\iff w\in A^c_i \text{ for all } i \in I \\ &\iff w \in \cap_{i\in I}A^c_i \end{split} \end{align}\](b)
\[\begin{align} \begin{split} w \in (\cap_{i\in I}A_i)^c &\iff w\not\in \cap_{i\in I} A_i \\ &\iff w \in A^c_i \text{ for some }i \in I\\ &\iff w \in \cup_{i\in I}A^c_i \end{split} \end{align}\] \[\tag*{$\square$}\]Theorem 1.1.1
$(a):A\cap (B\cup C) = (A\cap B) \cup (A\cap C)$
$(b): A\cup (B\cap C) = (A\cup B) \cap (A\cup C)$
$(c): C\setminus (A\cap B) = (C\setminus A) \cup (C\setminus B)$
<proof>
$(a)$ Let $x \in A\cap(B\cup C)$ be given. That is $x\in A$ and $x\in B\cup C$.
If $x\in A$ and $x\in B$, $x\in A\cap B$. So, $x\in (A\cap B)\cup(A\cap C).$
If $x\in A$ and $x\in C$, then $x\in A\cap C$. Thus, $x\in (A\cap B)\cup (A\cap C).$
$\therefore A\cap (B\cup C) \subset (A\cap B)\cup (A\cap C).$
Conversely, let $x\in (A\cap B)\cup (A\cap C)$ be given. Then, $x\in A\cap B$ or $x\in A\cap C$. If $x\in A\cap B$, then $x\in A$ and $x\in B$. Since $B\subset (B\cup C)$, $x\in B\cup C$. Clearly, $x \in A$. Thus, $x\in A$ and $x\in B\cup C.$
If $x\in A\cap C,$ then $x\in A$ and $x\in C.$ Since $C\subset (B\cup C), x\in (B\cup C).$ So, $x\in A$ and $x \in B\cup C.$
$\therefore A\cap (B\cup C) = (A\cap B)\cup (A\cap C)$ by the double inclusion.
$(b)$ Let $x\in A\cup (B\cap C)$ be given. That is $x\in A$ or $x\in B\cap C.$ Suppose $x \in A$. Since $A \subset (A\cup B)$ and $A\subset (A\cup C)$, $x\in (A\cup B)$ and $x\in (A\cup C)$.
Otherwise, $x\in B\cap C$. Since $(B\cap C) \subset B \subset (A\cup B), x\in A\cup B.$ Similarly, $x\in A\cup C$ because $(B\cap C) \subset C \subset (A\cup C)$.
$\therefore x\in (A\cup B)\cap (A\cup C)$.
Conversely, let $x\in (A\cup B)\cap (A\cup C)$ be given. Since $A \subset (A\cup B)$ and $A \subset (A\cup C), A\subset (A\cup B)\cap (A\cup C).$ So, if $x\in A, x\in A\cup(B\cap C).$
Otherwise, $x\in (B\setminus A)\cap (C\setminus A)$ because $x \in (A\cup B) \cap (A\cup C).$ Then it implies that $x\in B$ and $x\in C$ because $(B\setminus A)\subset B$ and $(C\setminus A)\subset C$.
$\therefore x\in A\cup (B\cap C)$.
$\therefore A\cup (B\cap C) = (A\cup B) \cap (A\cup C).$
$(c)$ \(\begin{align} \begin{split} C\setminus (A\cup B) &= C\cap (A\cup B)^c \\ &=C\cap (A^c\cap B^c) \\ &=(C\cap A^c)\cap (C\cap B^c) \\ &=(C\setminus A)\cap (C\setminus B) \end{split} \end{align}\)
The second equality holds by de Morgan’s law and the third equality holds by $(b)$.
$(d)$ \(\begin{align} \begin{split} C\setminus (A\cap B) &= C\cap (A\cap B)^c \\ &=C \cap (A^c \cup B^c) \\ &=(C\cap A^c)\cup (C\cap B^c) \\ &=(C\setminus A)\cup (C\setminus B) \end{split} \end{align}\)
The second equality holds by de Morgan’s law and the third equality holds by $(a)$.
\[\tag*{$\square$}\]Definition 1.2.1
Let $A,B$ be subsets of $\mathbb{R}$. $f:A\to B$ is a function if
\[\begin{align} \forall x\in A, \exists ! y\in B \text{ such that } y=f(x). \end{align}\]Definition 1.2.2
$f: A\to B$ is a function.
\[\begin{align} \begin{split} f \text{ is injective } &\iff [f(x_1)=f(x_2) \Rightarrow x_1 = x_2 ]\\ &\iff \forall y \in f(A), \exists ! x\in A \text{ s.t. } y= f(x) \end{split} \end{align}\]Definition 1.2.3
$f: A\to B$ is a function.
\[\begin{align} \begin{split} f \text{ is surjective } &\iff f(A) = B\\ &\iff \forall y \in B, \exists x\in A \text{ s.t. } y= f(x) \end{split} \end{align}\]Definition 1.2.4
$f: A\to B$ is a function. If $f$ is bijective if and only if the function is injective and surjective.
Theorem 1.2.5
$f:A\to B$ is a function and $A_1, A_2 \subset A$.
$(a):f(A_1\cup A_2) = f(A_1) \cup f(A_2)$
$(b):f(A_1 \cap A_2) \subset f(A_1)\cap f(A_2)$
$(c):f$ is injective $\Rightarrow f(A_1) \cap f(A_2) \subset f(A_1 \cap A_2)$
<proof>
$(a)$ Let $y \in f(A_1 \cup A_2)$ be given. Then $y= f(x)$ for some $x\in A_1 \cup A_2.$ So $y=f(x)$ for some $x\in A_1$, which is equivalent to $y\in f(A_1)$, or $y=f(x)$ for some $x\in A_2$, which is equivalent to $y\in f(A_2)$.
$\therefore y\in f(A_1) \cup f(A_2)$
Conversely, let $y\in f(A_1) \cup f(A_2)$ be given. If $y\in f(A_1)$, then $y=f(x)$ for some $x\in A_1$. Since $A_1\subset (A_1\cup A_2), x\in A_1\cup A_2$.
$\therefore f(x) \in f(A_1\cup A_2)$.
If $y\in f(A_2)$, then $y=f(x)$ for some $x\in A_2$. Since $A_2\subset (A_1\cup A_2), x\in A_1\cup A_2$.
$\therefore f(x) \in f(A_1\cup A_2)$.
$\therefore f(A_1\cup A_2) = f(A_1) \cup f(A_2)$
$(b)$ Let $y\in f(A_1\cap A_2)$ be given. Then $y=f(x)$ for some $x\in A_1$ and $x\in A_2$. Thus, $y=f(x) \in f(A_1)$ and $y=f(x) \in f(A_2)$.
$\therefore f(A_1 \cap A_2) \subset f(A_1) \cap f(A_2).$
$(c)$ Let $y\in f(A_1)\cap f(A_2)$ be given. Then for the same $y, y=f(x_1)$ for some $x_1 \in A_1$ or $y=f(x_2)$ for some $x_2 \in A_2$.
Since $f$ is bijective, $x_1=x_2=x\in A_1\cap A_2$, i.e. $y=f(x)$ for some $x\in A_1\cap A_2$.
$\therefore y\in f(A_1 \cap A_2)$
\[\tag*{$\square$}\]Theorem 1.2.6
$f:A\to B$ is a function, $B_1,B_2 \subset B$.
(a) $f^{-1}(B_1\cup B_2) = f^{-1}(B_1)\cup f^{-1}(B_2)$ (b) $f^{-1}(B_1\cap B_2) = f^{-1}(B_1)\cap f^{-1}(B_2)$
where $f^{-1}(B_1)$ is preimage defined as follows:
\[\begin{align} f^{-1}(B_1) := { x\in A| f(x)\in B_2 } \end{align}\]<proof>
(a)
\[\begin{align} \begin{split} f^{-1}(B_1\cup B_2) &= {x\in A: f(x) \in B_1\cup B_2 } \\ &={x\in A: f(x)\in B_1 \text{ or } f(x)\in B_2 } \\ &={x\in A: x\in f^{-1}(B_1) \text{ or } x\in f^{-1}(B_2)} \\ &={x\in A: x\in f^{-1}(B_1) \cup f^{-1}(B_2) } \end{split} \end{align}\](b)
\[\begin{align} \begin{split} f^{-1}(B_1\cap B_2) &= {x\in A: f(x)\in B_1\cap B_2}\\ &={x\in A: f(x)\in B_1 \text{ and } f(x)\in B_2 } \\ &= {x\in A: x\in f^{-1}(B_1) \text{ and } x\in f^{-1}(B_2) } \\ &={x\in A: x\in f^{-1}(B_1)\cap f^{-1}(B_2) } \end{split} \end{align}\] \[\tag*{$\square$}\]Remark (Well-ordering principle)
Every nonempty subset of $\mathbb{N}$ has a smallest element.
Theorem 1.3.1
For each $n\in \mathbb{N}$, let $p(n)$ be a statement about $n$. If
$(a):p(1)$ is true, and
$(b):p(k)$ is true $\Rightarrow p(k+1)$ is true
then $p(n)$ is true for all $n\in \mathbb{N}$.
<proof>
Suppose that $p(n)$ is false for some $n\in\mathbb{N}$. If we set
\[\begin{align} A:=\{k\in \mathbb{N}: p(k) \text{ is false} \} \end{align}\]then $A$ is a nonempty subset of $\mathbb{N}.$ By the well-ordering principle, there is the smallest element $k_0 \in A, k_0 \geq 2$. Since $k_0$ is the smallest element of $A$, $p(k_0 -1)$ is true. By our assumption, however, $p(k_0)$ is also true, which is a contradiction.
$\therefore p(n)$ is true for all $n\in\mathbb{N}$.
\[\tag*{$\square$}\]Examples 1.3.3
(a) $p(n) = r+r^2+\cdots + r^{n-1} +r^n=\frac{r(1-r^n)}{1-r}$, where $r\neq 1$.
(b) (Bernoulli’s inequality): $p(n): h >-1, (1+h)^n \geq 1+ nh$.
<proof>
(a) For $n=1$, $p(1) = r = \frac{r(1-r)}{1-r}$. Assume that the statement holds true for $n=k-1$.
\[\begin{align} \begin{split} p(k) &= 1+ r^2 + \cdots + r^{k-1} + r^{k} \\ &=p(k-1) + r^k \\ &=\frac{r(1-r^{k-1})}{1-r} + r^k \\ &=\frac{r(1-r^{k-1})+ r^k(1-r)}{1-r} \\ &=\frac{r-r^k+r^k-r^{k+1}}{1-r} \\ &=\frac{r-r^{k+1}}{1-r} \\ &=\frac{r(1-r^{k})}{1-r} \end{split} \end{align}\]Thus, $p(k)$ holds.
$\therefore$ By the mathematical induction $p(n)$ is always true.
(b) For $n=1$, the left hand side is $(1+h)^1 = 1+h$ and the right hand side is $1+1\cdot h=1+h$.
Assume that $p(k) = (1+h)^k \geq 1+k\cdot h$ is true.
\[\begin{align} \begin{split} (1+h)^{k+1} &= (1+h)(1+h)^k \\ &\geq (1+kh)(1+h) \\ &=1+h+kh+kh^2 \\ &\geq 1+(k+1)h \end{split} \end{align}\]Thus, $p(k+1)$ holds.
$\therefore$ By the mathematical induction, $p(n)$ is always true.
Reference
- Manfred Stoll, 『Introduction to Real Analysis』, Pearson