Consider a directed graph and a partition $P$ of its set of vertices. We construct a new partition $P'$ of this set as follows: declare $v_1$ and $v_2$ to be in the same part of the partition $P'$ if for every $p\in P$, $v_1$ arrows into $x\in p$ for some $x$ iff $v_2$ arrows into $y\in p$ for some $y$. The problem is to prove or give a counterexample to the statement that the finer the original partition is, the finer the new partition will be. (By finer I mean either the same or strictly finer.)
I haven't been able come up with a counterexample, so I'm trying to prove this. Suppose this is false. Let $P_1$ and $P_2$ be two partitions. Denote by $P_i'$ the corresponding new partition. By assumption, $P_2'$ is not finer than $P_1'$. So there is $x\in P_2'$ such that for all $y\in P_1'$ it is not the case that $x\subset y$. I need to show that then there is $X\in P_2$ such that for all $Y\in P_1$ it is not the case that $X\subset Y$. But I don't quite understand how to use the definition of the new partition to deduce this. Any help?
I think that a direct proof is more simple than a proof to the contrary. Assume that $P_2$ is finer than $P_1$. Consider any $p’_2\in P_2’$. Let $v,u\in p’_2$ be any vertices and $p_1\in P_1$ be any element. If $v$ arrows to $x$ for some $x\in p_1$ then, since $P_2$ is finer than $P_1$, there exist $p_2\in P_2$ with $x\in p_2\subset p_1$. Since $v,u\in p’_2$, there exists $y\in p_2\subset p_1$ such that $u$ arrows to $y$. Similarly we can show that if $u$ arrows to $x$ for some $x\in p_1$ then there exists $y\in p_1$ such that $v$ arrows to $y$. Thus $v$ and $u$ are in the same part of the partition $P’_1$. So $P’_2$ is finer than $P'_1$.