proving antisymmetry of partition refinement

263 Views Asked by At

Suppose $P$ is the set of all partitions of some set $S$. $R$ is a binary relation on $P$, the refinement relation, defined as $(\Pi_1,\Pi_2) \in R $ if and only if for every $S_1 \in \Pi_1$, there exists an $S_2\in\Pi_2$ such that $S_1\subseteq S_2$. How do I prove that this relation is antisymmetric?

1

There are 1 best solutions below

0
On BEST ANSWER

HINT: Suppose that $\Pi_1$ refines $\Pi_2$ and vice versa. Let $X\in\Pi_1$ then there is some $Y\in\Pi_2$ such that $X\subseteq Y$, similarly there is some $Z\in\Pi_1$ such that $Y\subseteq Z$.

Conclude that $X=Y=Z$, and therefore $\Pi_1=\Pi_2$.