Equivalent relations and partitions.
Recall that ” $f: A \longrightarrow B$ ” is a certain subset of $A \times B$.
More precisely, for each $x \in A$, there exists unique $y=f(x) \in B$ Satisfying $(x, y)=(x, f(x)) \in S_{f} \subseteq A \times B$.
We can observe that every $x$ has a “relation” with some element in B.
Definition. 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$, we 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)\}$.
$1 \sim_R 4, 2\sim_R 5$.
Ex) Let $f: A \rightarrow B$ abe function . Then $ S_f \subseteq A \times B$ is a relation.
Definition. Let $R \subseteq A \times A$ be a relation. We say that $R$ is an equivalent 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_{R} z$ then $x \sim_{R} z$.
Ex) $A=\{1,2,3,4\}$. $R=\{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1)\}$.
Ex) Given a set $A$, consider $F=P(A)$ the power set of $A$.
Define a relation $R$ in $F\times F$, by $X\sim Y$ iff there exists one to one, onto function $f : X \rightarrow Y$.
Then $R$ is an equivalence (Exercise).
Q1. Reflexive?
For each $X \in F$, we have idx: $X \longrightarrow X$ mapping $x \mapsto x$ : this map should be 1-1 and onto.
Q2. Symmetric?
Suppose $X \sim_{R} Y$. i.e., there exists a 1-1, onto $f: X \rightarrow Y$
By previous (2nd) lecture, there exists $g:Y\rightarrow X$ $\ $such that $g \circ f=id_X$ and $f \circ g=id_Y$.
Exercise. Given $f: A \longrightarrow 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 \longrightarrow C$ is 1-1, then $f$ is1-1.
By 1) and 2), the above $g$ must be 1-1, onto.
Thus $g=f^{-1}$.
Hence $Y\sim_R X$.
Q3. Transitive?
Suppose X$\sim_R Y$ and Y$\sim_R Z$.
i.e., there exists $f {:} X \longrightarrow Y$, $g: Y \rightarrow Z$ which are both 1-1 and onto.
Consider the composition $g \circ f: X \stackrel{f}{\longrightarrow} Y\stackrel{g}{\longrightarrow} Z$.
Exercise 3) If $f: X \rightarrow Y, g: Y \rightarrow Z$ are 1-1, then $g_{\circ} f_{:} X \longrightarrow Z$ is 1-1.
4) If $f: X \rightarrow Y$ and $g: Y \rightarrow Z$ are onto then $g \circ f: X \longrightarrow Z$ is onto
Hence $g \circ f: X \rightarrow Z$ is 1-1 and onto. i.e., $X \sim_{R}$
Definition. Given a set $E$, consider the index set I. (i.e., for each $\alpha \in I$, there exists $E_\alpha \subset E$).
(3) $\cup_{\alpha \in I} E_{\alpha}=E$.
We call $F$ the partition of $E$.
ex). Let $\mathbb{Z}$ be set of integers.
Denote $[k]=\{x \in \mathbb{Z} \mid x=3 a+k, a \in \mathbb{Z}\}$.
$\Rightarrow[0],[1],[2] \subseteq \mathbb{Z}$
$[0] \cap[1]=[1] \cap[2]=[2] \cap[0]=\varnothing$ $[0] \cup[1] \cup[2]=\mathbb{\varnothing}$
$F=\{[0],[1],[2]\}$ : partition of $\mathbb{Z}$
Remark.
1) Given a set $X$, consider the equivalence relation $\sim_{R}\left(R \subset X_{x} X\right)$. For each $x \in X$, define $[x]=\left\{y \in x \mid x\sim _{R} y\right\} \text { the equivalence class of x }$.
Then $\mathcal{F}=[x] \mid x \in x\}$ becomes a partition of $X$ (Exercise).
2) Conversely, given a set $X$, consider a partition $F=\left\{E_{\alpha} \mid \alpha \in I\right\}$ of $X$.
Define $x \sim_{R} y, x, y \in x$, if there exists $\alpha \in I$ sach that $x, y \in E_{x}$.
Then ” $\sim_{R}$ ” is an equivalence Relation (Exercise).
3) Consequently, there is the 1-1 correspondence between
$$
\begin{aligned}
& \{\text { equivalent relations on } X\} \longleftrightarrow\left\{\begin{array}{r}
\text { Partitions on $X$}
\end{array}\right\}
\end{aligned}
$$
Exercise. Let $f: X \rightarrow Y, g: Y \rightarrow Z$ be functions.
1) If $f, g$ are 1-1, then $g \circ f$ is 1-1
2) If $g \circ f$ is onto, then $g$ is onto.
If $g \circ f$ is 1-1, then $f$ is 1-1.