Set theory
집합=Set = Collection = Family={definable objects} '기준'이 제시된 대상' -> True/False
$X= \{ 1, 2 \} $
멱집합, Power set of C, Set of Collection: $\mathcal{P}(X)=2^X = \{ \varnothing , \{ 1 \} , \{ 2 \} , \{ 1, 2 \} \} $
자연수 집합: $\mathbb{N} = \{ 1, 2, 3, 4, \cdots \} $
정수 집합: $\mathbb{Z} = \{ \cdots , -3, -2, -1 , 0 , 1, 2, 3, \cdots \}$
유리수 집합: $\mathbb{Q} = \{ \frac{q}{p} \mid p, q \in \mathbb{Z} , q \ne 0 \} $
실수 집합: $\mathbb{R} = \{ real \#s \}$
복소수 집합: $\mathbb{C} = \{complex \#s \}$
유리수 = rational number (ratio를 의미 -> 분수꼴)
~rational # = irrational number, 무리수
$X$: 전체집합, Universal Set
Let, $A, B \subseteq X$ ($\subseteq = \subset$)
$A \cup B = \{ x \mid x \in A\ \text{or}\ x \in B \} $
$A \cap B = \{ x \mid x \in A\ \text{and}\ x \in B \} $
$A^c = \{ x \mid x \notin A \} $
Def.
Let, $A, B \subseteq X$
$A=B$
$\Leftrightarrow$ $A \subseteq B $ and $B \subseteq A$
$\Leftrightarrow$ If $x \in A$, then $x \in B$,
and if $y \in B$, then $y \in A$
Proposition.
Let, $A,B,C \subseteq X$
(a) $A \cap (B \cup C) = (A \cap B) \cup ( A \cap C) $
Proof.
Need to Show(NTS):
$A \cap (B \cup C) \subset (A \cap B) \cup ( A \cap C) $
and $(A \cap B) \cup ( A \cap C) \subset A \cap (B \cup C) $
$\Leftrightarrow$ If $x \in A \cap ( B \cup C)$
$\Leftrightarrow$ $x \in A\ and\ ( x \in B\ or\ x \in C)$
$\Leftrightarrow$ $(x \in A\ and\ x \in B)\ or\ (x \in A\ and\ x \in C)$
$\Leftrightarrow$ $x \in A \cap B\ or\ x \in A \cap C$
$\Leftrightarrow$ $x \in (A \cap B) \cup (A \cap C)$
위의 2가지를 동시에 쌍방향으로 증명(Q.E.D ■)
(b) $\ A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
(c) $ \ (A \cup B)^c = A^c \cap B^c $
(d) $ \ (A \cap B)^c = A^c \cup B^c $
Def.
Given a set A,
$\mathcal{P}(A)= \{ B \subset A \}$. the collection of subsets of A. the power set of A.
Given two sets A, B,
곱집합: $ A \times B = \{(a, b) \mid a \in A, \ b \in B\} $ (순서쌍으로 정의)
If A has n elements, then show that $\mathcal{P}(A)$ has $2^n$ elements.
Functions
Def.
Given two sets A, B,
We call $ f : A \rightarrow B $ is a function, if
A, B라는 2개의 집합이 주어졌으므로
$A \times B$ 정의 가능
이것의 부분집합을 $S_f$로 정의하고 함수라 부름.
$S_f \subset A \times B$는 다음을 만족.
for each $a \in A$, there exists $b \in B$ uniquely such that $(a,b) \in S_f$.
A: domain(정의역)
B: codomain(공역)
Imf = $\{ b = f(a) \mid a \in A \}$: range, image(치역)
Proposition.
Given $ f : A \rightarrow B $ be a function,
Let, $A_1 , A_2 \subset A $
(a)
$\begin{align} f(A_1 \cup A_2) &= \{ f(x) \mid x \in A_1 \cup A_2 \} \\ &= f(A_1) \cup f(A_2) \end{align}$
(b)
$f(A_1 \cap A_2) \subseteq f(A_1) \cap f(A_2)$
Def.
Given $ f : A \rightarrow B $ be a function,
Let, $B_1 \subset B$
Define $f^{-1}(B_1) = \{ x \in A \mid f(x) \in B_1 \}$ called the inverse image(역상) of $f$ under $B_1$.
Proof.
Let, $ f : A \rightarrow B $ be 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)$
(c)
$f^{-1}(B_1^c) = \left( f^{-1}(B_1) \right)^c$
Exercise.
Let, $ f : A \rightarrow B $ be a function.
Let, $A_1 \subset A$, $B_1 \subset B$
(a) $f(f^{-1}(B_1)) \subset B_1$ (과거로 갔다오면 작아지고)
(b) $f^{-1}(f(A_1)) \supset A_1$ (미래로 갔다오면 커짐)
$ f(A_1) = \{ f(x) \mid x \in A_1 \} $
(c) "="가 성립하지 않는 반례
함수의 1to1 대응과 상관있음
Def.
Let, $ f : A \rightarrow B $ be a function.
(a) f is 1-1(injective)
if $f(x_1) = f(x_2) $ then $x_1 = x_2$
if $x_1 \ne x_2 $ then $f(x_1) \ne f(x_2) $
(b) f is onto(surjective) if Imf$(=f(A)) =B$(codomain)
i.e., for any $y \in B$, there exists $a \in A$ such that $f(a)=b$.
Rmk-def.
Let, f be a 1-1 + onto(bijective) $f_n , f : A \rightarrow B$ (일대일대응)
We can define $f^{-1} : B \rightarrow A$, called the inverse function of f.
$b = f(a)$, a exists uniquely.
i.e., $S_{f^{-1}} = \{ (y , x) \in B \times A \mid f(x)=y \} \subset B \times A $.
Def.
Given two function $ f : A \rightarrow B $, $ g : B \rightarrow C $,
define $g \circ f : A \xrightarrow{f} B \xrightarrow{g} C$
$x \rightarrow f(x) \rightarrow g(f(x))$
i.e., $(g \circ f)(x) = g(f(x))$
$S_{g \circ f} = \{ (x, g(f(x))) \mid x \in A \} \subset A \times C$.
일대일대응 -> 역함수 정의
Exercise.
Given two sets $A,B ( \subset X)$
given $f : A \rightarrow B$
i.e., $id_A : A \rightarrow A$ ($x \rightarrow x$)
Then
a) f is 1-1(injective)
if and only if there exists $g : B \rightarrow A$ such that $g \circ f = id_A$
b) f is onto(surjective)
if and only if there exists $g : B \rightarrow A$ such that $f \circ g = id_B$
Proof.
a) onto가 아니기 때문에
(핑크색 : 치역, 보라색 : 치역 제외 공역)
Pick any $P \in A$
Define $g(=g_P) : B \rightarrow A $ (P에 의존된 함수)
$$ b \rightarrow\begin{cases} a & \text{if}\ b \in Imf=f(A)= \text{there exists unique}\ a \in A\ \text{such that}\ b=f(a) \\ P & \text{if}\ b \notin Imf \end{cases}$$
Then g is well-defined, because if $b=f(a)=f(a')$,
since f is 1-1, $a=a'$.
Then it is easy to see $g \circ f = id_A$.
b) Suppose f is onto(surjective)
Necessary ingredient) clarify for each $y \in B$, assign $x \in A$ such that $y=f(x)$
so that we can define $g : B \rightarrow A$, $y \rightarrow x$
문제는 대응되는 x가 1개가 아닐 수가 있음
그렇다고 각 y마다 x를 지정하기에는 y가 무한개있으면 불가능
따라서, g를 정의하기 위해서는 공리가 필요.
In fact, the existence of such a g requires the "Axiom of choice".
Equivalence relations and partitions
$f : A \rightarrow B$ is a subset of $A \times B$.
= for each $x \in A$, there exists unique.
$y=f(x) \in B$ satisfying $(x,y)=(x,f(x)) \in S_f \subset A \times B$.
We can observe that every x has a "relation" with some element in B.
Def.
Given two sets A, B,
a relation R is a subset of $A \times B$.
i.e., $R \subset A \times B$.
For each $(a,b) \in R$, denote $a \sim_R b$.
ex) $A=\{1,2 \}$, $B= \{4,5 \}$,
$A \times B = \{ (1,4), (1,5), (2,4), (2,5) \}$.
$R = \{ (1,4), (2,5) \}$.
$ \Leftrightarrow 1 \sim_R 4, \ 2 \sim_R 5$.
ex) $f : A \rightarrow B$ a function $\Leftrightarrow \underbrace{S_f}_{\text{relation}} \subset A \times B $
ex) $S= \{ \text{Students in college} \}$
$a \sim_R b \Leftrightarrow$ a가 b를 친구로 생각한다. $a,b \in S$.
$\rightarrow R \subset S \times S$
Q. $a \sim_R a$?
Q. If $a \sim_R b$ then $b \sim_R a$?
Q. If $a \sim_R b$ and $b \sim_R c$ then $a \sim_R c$?
Def.
Let, $R \subset A \times A$ be a relation.
We say that R is an equivalence relation(동치관계)
if R satisfies (1), (2), (3):
(1) Reflexive(반사) : for each $x \in A$, $(x,x) \in R$. i.e., $x \sim_R x$
(2) Symmetric(대칭) : If $(x, y) \in R$ then $(y, x) \in R$. i.e., if $x \sim_R y$ then $y \sim_R x$
(3) Transitive(전이) : If $(x, y) \in R$ and $ (y, z) \in R$ then $(x, z) \in R$. i.e., if $x \sim_R y$ and $y \sim_R z$ then $ x \sim_R z$
(1)번은 각 $x$마다 반드시 만족해야하지만 (2), (3)은 조건문이기 때문에 반드시는 아님. 있을경우에만.
ex) $A= \{1,2,3,4 \}$
$R = \{ \underbrace{(1,1), (2,2), (3,3), (4,4)}_{\text{Necessary Condition}}, \underbrace{(1,2), (2,1)}_{\text{Optional: equiv. rel.}} \}$
(1, 2)를 만약 넣는다면 동치가 되려면 (2, 1)이 있어야됨.
ex) Given a set $A$, consider $F = \mathcal{P}(A) = \{ \text{subsets of A} \}$.
Define $R := \{ (X \times Y) \in F \times F \mid \text{there exists a 1-1, onto function } f: X \to Y \}$
($X$, $Y$는 $A$의 부분집합)($f$가 있을 때, 집합 $X$, $Y$가 relation이 있음)
Then $R$ is an equivalence.
Q. Reflexive?
For each $X \in F$, we have $id_x : X \rightarrow X$, $x \rightarrow x$ : 1-1, onto.
Q. Symmetric?
Suppose $X \sim_R Y$. i.e., there exists a 1-1, onto $ f : X \rightarrow Y$.
there exists $g : Y \rightarrow X$.
Such that $g \circ f = id_x$ and $f \circ g = id_y$.
Exercise.
Given $f : A \rightarrow B$ and $g : B \rightarrow C$,
(1) If $g \circ f : A \rightarrow C$ is onto, then $g$ is onto.
(2) If $g \circ f : A \rightarrow C$ is 1-1, then $f$ is 1-1.
By (1), (2), the above $g$ must be 1-1, onto.
(In fact, $g=f^{-1}$) Hence $Y \sim_R X$.
Q. Transitive?
Suppose $X \sim_R Y$ and $Y \sim_R Z$.
i.e., there exists $f:X \rightarrow Y$ 1-1, onto, $g: Y \rightarrow Z$ 1-1, onto.
consider $g \circ f : X \xrightarrow{f} Y \xrightarrow{g} Z$
이게 1-1, onto인지만 확인하면 됨.
Exercise.
(3) If $f : X \rightarrow Y$, $g : Y \rightarrow Z$ are 1-1,
then $g \circ f : X \rightarrow Z$ is 1-1.
(4) If $f : X \rightarrow Y$, $g : Y \rightarrow Z$ are onto,
then $g \circ f : X \rightarrow Z$ is onto.
Hence $g \circ f : X \rightarrow Z$ is 1-1 and onto.
i.e., $X \sim_R Z$.
Partition
Def.
Given a set $E$,
consider the index set $I$
(i.e., for each $\alpha \in I$, there exists $E_{\alpha} \subset E$)
Define
$\mathcal{F} := \{ E_{\alpha} \subset E \mid \begin{cases} (1) E_{\alpha} \ne \emptyset. \\ (2) \text{If } \alpha \ne \beta, \alpha , \beta \in I, \text{then } E_{\alpha} \cap E_{\beta} = \emptyset. \\ (3) \bigcup_{\alpha in I} E_{\alpha} = E \end{cases} \}$
($\bigcup_{\alpha \in I} E_\alpha = \{ x \in E \mid \text{there exists } \alpha \in I \text{ such that } x \in E_\alpha \}$)
We call $\mathcal{F}$ the partition of $E$
ex) Let $\mathbb{Z}$ be set of integers.
Denote $[k] = \{ x \in \mathbb{Z} \mid x=3a+k,\ a \in \mathbb{Z} \}$. (3으로 나누면 나머지가 $k$인 집합)
$\Rightarrow [0],[1],[2] \subset \mathbb{Z}$
$[0],[1],[2] \neq \emptyset$
$[0] \cap [1] = [1] \cap [2] = [2] \cap [0] = \emptyset$
$[0] \cup [1] \cup [2] = \mathbb{Z}$
$\mathcal{F} = \{ [0], [1], [2] \} : \text{partition of}\ \mathbb{Z}$
Remark.
(1) Given a set $X$, consider the equivalence relation $\sim_R$ ($R \subset X \times X$)
For each $x \in X$, define $[x] = \{ y \in X \mid x \sim_R y \}$ the equivalence class of $x$.
($x$의 동치류)
Exercise.
$\mathcal{F} = \{ [x] \mid x \in X \}$ becomes a partition of $X$.
(2) Conversely, given a set $X$,
consider a partition $\mathcal{F} = \{ E_{\alpha} \mid \alpha \in I \}$ of $X$.
Define $x \sim_R y,\ x, y \in X$, if there exists $\alpha \in I$ such that $x,y \in E_{\alpha}$.
Exercise.
"$\sim_R$" is an equivalence relation.
Remark (1)은 equivalence relation이 있으면 partition을 만들어내고, (2)는 partition이 있으면 equivalence relation을 만들어냄.
(3) Consequently, there is the 1-1 correspondence(일대일대응) between
$$\left\{ \text{equiv. relations on } X \right\} \longleftrightarrow \left\{ \text{partitions on } X \right\}$$
$$ \sim_R \longrightarrow \{ [x]_R \mid x \in X \} $$
$$ \sim_{R(P)} \longleftarrow P(\text{Partition})$$
따라서, equivalence relation과 partition은 같은 개념.
