what is the partial order on $\Lambda_n$ that corresponding to the partial order on $\pi_n$?

Question

let $\pi_n$ denote the set of all partitions of the set {1,2......n} into nonempty sets. given two partitions $\pi$ and $\sigma$ in $\pi_n$, define $\pi\leq \sigma$, provided that each part of $\pi$ is contained in part of $\sigma$. Thus the partitions $\pi$ can be obtained by partitioning the parts of $\sigma$. This rotation is usually expressed by sampling that $\pi$ is a refinement of $\sigma$

we know that there is one to one correspondence between $\pi_n\;$ and the set $\Lambda_n$ of all equivalence relation on {1,2,3...n}. what is the partial order on $\Lambda_n$ that corresponding to the partial order on $\pi_n$ ?

theorem: Let ~ be equivalence relation on set X. Then the distinct equivalence class partition X into nonempty parts. conversely given any partition of x nonempty parts, there is an equivalence relation on X whose equivalence classes are the parts of the partition

Answer 1

HINT: This is basically a matter of working through the definitions. Suppose that $E_0$ and $E_1$ are equivalence relations on $[n]=\{1,\ldots,n\}$, and let $\sigma_0$ and $\sigma_1$ be the corresponding partitions of $[n]$ into equivalence classes. We want a partial order $\preceq$ on $\Lambda_n$ such that $\sigma_0\le\sigma_1$ if and only if $E_0\preceq E_1$.

You know that $\sigma_0\le\sigma_1$ if and only if each part of $\sigma_0$ is a subset of some part of $\sigma_1$. This means that each $E_0$-equivalence class is a subset of some $E_1$-equivalence class. Let $k\in[n]$, and let

$$E_0(k)=\{\ell\in[n]:k\mathrel{E_0}\ell\}$$

be the $E_0$-equivalence class of $k$. You know that $k\mathrel{E_0}k$, so $k\in E_0(k)$.

• If $E_1(k)$ is the $E_1$-equivalence class of $k$, show that $E_0(k)\subseteq E_1(k)$.

Suppose that $k,\ell\in[n]$, and $k\mathrel{E_0}\ell$. Use the bullet point to say something about $k$ and $\ell$ in terms of $E_1$. Then try to find and prove a statement of the following form:

$\sigma_0\le\sigma_1$ if and only if whenever $k,\ell\in[n]$ and $k\mathrel{E_0}\ell$, then ... [something about $E_1$].

The condition on $E_0$ and $E_1$ following if and only if is the condition that you need to use to define the partial order $\preceq$.