Source of most content: Gunhee Cho

Function

Def. Given two sets $A$ and $B$, we call $f: A \rightarrow B$ a function if we have $S_f \subseteq A \times B$ satisfying for each $a \in A$, there exists $b\in B$ uniquely s.t. $(a,b) = (a, f(a)) \in S_f \subseteq A \times B$.

Here, $A$ is the domain, $B$ is codomain and $\text{Im}f = \{ b=f(a) | a \in A \}$ is the range/image of $f$.
Let $B_1 \subseteq B$, we call $f^{-1}(B_1) := \{x\in A \mid f(x) \in B_1\}$ as the inverse image of $f$ under $B$.

Proposition

A function $f:A \rightarrow B$ satisfies for $A_i \in A$ and $B_i \in B$:

1. $f(A_1 \cup A_2) = f(A_1) \cup f(A_2)$
2. $f(A_1 \cap A_2) \subseteq f(A_1) \cap f(A_2)$
3. $f^{-1}(B_1 \cup B_2) = f^{-1}(B_1) \cup f^{-1}(B_2)$
4. $f^{-1}(B_1 \cap B_2) = f^{-1}(B_1) \cap f^{-1}(B_2)$
5. $f^{-1}(B^c) = (f^{-1}(B))^c$
6. $f(f^{-1}(B_1)) \subseteq B_1$
7. $f^{-1}(f(A_1)) \supseteq A_1$

Proof

1. $f(A_1 \cup A_2) := \{f(x) \mid x \in A_1 \cup A_2\} = f(A_1) \cup f(A_2)$
2. To prove, show (a) $\subseteq$ holds but (b) $\supset$ does not.
   • NB; If $A_1 \subseteq A_2$ then $f(A_1) \subseteq f(A_2)$.
   • (a) $\subseteq$: Since $A_1 \cap A_2 \subseteq A_1, A_2$, $f(A_1 \cap A_2) \supseteq f(A_1), f(A_2)$ which implies $f(A_1 \cap A_2) \supseteq f(A_1) \cap f(A_2)$.
   • (b) $\supset$: Let $A_1=\{0, 1\}$ and $A_2 = \{1, 2\}$ and function $f := \{(0,a), (1, b), (2,a)\}$. Then, $f(A_1 \cap A_2) = \{a\} \not\supset f(A_1) \cap f(A_2) = \{(a,b\}$.
3. $f^{-1}(B_1 \cup B_2) := \{x \in A \mid f(x) \in B_1 \cup B_2\} = f^{-1}(B_1) \cup f^{-1}(B_2)$.
4. To prove, show (a) $\subset$ and (b) $\supset$ hold respectively.
   • (a) $\subset$: Take any $x \in f^{-1}(B_1 \cap B_2)$ $\Leftrightarrow f(x)\in B_1 \cap B_2 \Leftrightarrow f(x) \in B_1 \text{ and } f(x) \in B_2 \Leftrightarrow x \in f^{-1}(B_1) \text{ and } f^{-1}(B_2) \Leftrightarrow x \in f^{-1}(B_1 \cap B_2)$.
   • (b) $\supset$: Similarly to (a).
5. Take any $x \in f^{-1}(B^c) \Leftrightarrow f(x) \in B^c \Leftrightarrow f(x) \notin B \Leftrightarrow x \in (f^{-1}(B))^c$. So, $f^{-1}(B^c)=(f^{-1}(B))^c$.
6. Take any $y \in f(f^{-1}(B_1)) \leadsto \exists x \in f^{-1}(B_1)\text{ s.t. } f(x) =y \Leftrightarrow y \in B_1$. So, $f(f^{-1}(B_1)) \subseteq B_1$.
7. Take any $x \in A_1 \Leftrightarrow \{x\} \subseteq A_1 \Leftrightarrow f(\{x\})\subseteq f(A_1) \Leftrightarrow x \in f^{-1}(f(A_1))$. So, $f^{-1}(f(A_1)) \supseteq A_1$.

---

Class of function

Let $f:A \rightarrow B$ be a function.

1. $f$ is one-to-one (injective) if $f(x_1)=f(x_2) \text{ then } x_1 = x_2 $.
2. $f$ is onto (surjective) if $\text{Im}f = f(A) =B$ i.e., for any $y\in B, \exists x \in A: f(a)=b$.
3. $f$ is bijective if $f$ is injective and surjective. Then, we can define inverse function $f^{-1}: B \rightarrow A$.

Proposition

Ginve functions $f:A \rightarrow B$, ${Id}_A: A \rightarrow A \ (x \mapsto x)$ and ${Id}_B: B \rightarrow B (y \mapsto y)$.

1. $f$ is injective iff $\exists g:B\rightarrow A \text{ s.t. } g\cdot f = {Id}_A$.
2. $f$ is surjective iff $\exists g:B\rightarrow A \text{ s.t. } f\cdot g = {Id}_B$.

Proof

$x_i \in A, y_i \in B$ and $[ E ]$ is from Iverson bracket.

1. • ($\Rightarrow$): pick any $z \in A$. Define $g_z: B \rightarrow A$ s.t. $a[b \in \text{Im}f]+z[b \notin \text{Im}f]$. Then, $g_z$ is well-defined because if $b=f(a)=f(a’)$ then $a=a’$ since $f$ is injetive.
   • ($\Leftarrow$): If $f(x_1) = f(x_2)$, then $g\cdot f(x_1) = x_1 = g\cdot f(x_2) = x_2$.
2. • ($\Rightarrow$): Suppose $f$ is surjective and for each $y\in B$, assign $x\in A$ s.t. $y=f(x)$. Then, we can define $g: B \rightarrow A \ ( y \mapsto x)$.
     NB; only assume $f$ is surjective, so existence of $g$ requires axiom of choice.
   • ($\Leftarrow$): For any $y\in B$, $f(g(y)) = y$, which implies that $\exists x \in A$ s.t. $f(x)=y$.

---

Relation

A function $f:A \rightarrow B$ is a subset of $A\times B$. More precisely, for each $x \in A$, $\exists! y = f(x) \in B$ s.t. $(x,y)=(x,(f(x)) \in S_f \subseteq A\times B$, where $S_f$ is relation. This shows that every $x$ has a relation with some elements in $B$.

Def. Given two set $A, B$, a relation $R$ is a subset of $A\times B$. For each $(x,y)\in R$, denote $x \sim_R y$.

Def. Let $R \subseteq A\times A$ be a relation. $R$ is an equivalence relation if $R$ satisfies:

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., $x \sim_R y \Leftrightarrow y \sim_R x$.
3. (Transitive) if $(x,y)\in R \land (y,z) \in R$, then $(x,z)\in R$, i.e., $x \sim_R y \land y \sim_R z$ then $x \sim_R z$.

Def. Given a set $E$, consider index set $I$, i.e., for each $\alpha \in I, \exists E_\alpha \subset E$. Define $F := \{ E_\alpha \subseteq E \mid E_\alpha \ne \emptyset; \text{ if } \alpha \ne \beta, \alpha, \beta \in I, \text{ then }E_\alpha \cap E_\beta = \emptyset; \cup_I E_\alpha = E \}$, which we call partition of E.

Remark

1. Given a set $X$, consider equivalence relation $\sim_R (R \subset X\times X)$. For each $x\in X$, define $[ x ]=\{y \in X \mid x \sim_R y \}$ which is the equivalence class of $x$. Then, $F = \{ [x] \mid x \in X \}$ becomes partition of $X$.

2. Conversely, given a set $X$, consider a partition $F=\{E_\alpha \mid \alpha \in I \}$ of $X$. Define $x \sim_R y, x,y\in X$ if $\exists \alpha \in I$ s.t. $x,y \in E_\alpha$. Then, $R$ is an equivalence relation.

3. By Remark 1 and 2, there is one-to-one correspondence between equivalence relations on $X$ and partition of $X$. i.e., $\sim_R \mapsto \{ [ x ]_{R} \}$and $P \mapsto \sim_{R_P}$.