3. Equivalent relations and partitions

Equivalent relations and partitions.

Recall that ” $f:A⟶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\to 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\to Y$. 

Then $R$ is an equivalence (Exercise).

Q1. Reflexive?

For each $X\in F$, we have idx: $X⟶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\to Y$

By previous (2nd) lecture, there exists  $g:Y\to X$ $$such that $g\circ f=i{d}_X$ and $f\circ g=i{d}_Y$.

Exercise. Given $f:A⟶B$ and $g:B\to C$,

1) If $g\circ f:A\to C$ is onto, then $g$ is onto.

2) If $g\circ f:A⟶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⟶Y$, $g:Y\to Z$ which are both 1-1 and onto.

Consider the composition $g\circ f:X\stackrel{f}{⟶}Y\stackrel{g}{⟶}Z$. 

Exercise 3) If $f:X\to Y,g:Y\to Z$ are 1-1, then $g_{\circ }{f}_{:}X⟶Z$ is 1-1.

4) If $f:X\to Y$ and $g:Y\to Z$ are onto then $g\circ f:X⟶Z$ is onto
Hence $g\circ f:X\to 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=3a+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]=\varnothing$
$F=\{[0],[1],[2]\}$ : partition of $\mathbb{Z}$

Remark. 

1) Given a set $X$, consider the equivalence relation ${\sim }_R(R\subset X_{x}X)$. For each $x\in X$, define $[x]=\{y\in x\mid x{\sim }_{R}y\}\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=\{E_{\alpha }\mid \alpha \in I\}$ 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{array}{rl}& \{\text{ equivalent relations on }X\}⟷\left\{\begin{array}{r}\text{ Partitions on }X\end{array}\right\}\end{array}$$

Exercise. Let $f:X\to Y,g:Y\to 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.