Minimizing the set of "wrong" edges in $K_\omega$ with $\{0,1\}$-weights

Question

For any set $X$, let $[X]^2 = \big\{\{x,y\}:x\neq y\in X\big\}$.

Let $f:[\omega]^2\to\{0,1\}$ be a function. The principal goal is to find a partition of $\omega$ such that if $m\neq n\in \omega$ are in the same block of the partition, then $f(\{m,n\}) = 0$, and if $m,n$ are not in the same block, then $f(\{m,n\})= 1$.

It is easy to see that given $f:[\omega]^2\to\{0,1\}$ it is not always possible to find such a "perfect" partition that meets the requirement above.

So for any partition $P$ of $\omega$ we define the collection of wrong members of $[\omega]^2$, denoted by $W_P\subseteq [\omega]^2$ in the following way.

• $W_P^{(0)} = \big\{e\in[\omega]^2\setminus\big(\bigcup\{[b]^2:b \in P\}\big): f(e) = 0\big\}$, that is the set $W_P^{(0)}$ is the set of all $e\in[\omega]^2$ such that $e$ is not inside some block, but $f(e) = 0$ , and

• $W_P^{(1)} = \big\{e\in\bigcup\{[b]^2:b \in P\}: f(e) = 1\big\}$, that is the set $W_P^{(0)}$ is the set of all $e\in[\omega]^2$ such that $e$ is indeed inside some block, but $f(e) = 1$.

The intuition is that the members of $W_P^{(0)}$ are "falsely" labelled with $0$ by $f$, and the members of $W_P^{(1)}$ are "falsely" labelled with $1$ by $f$. Finally, we let $$W_P = W_P^{(0)} \cup W_P^{(1)}.$$

Question. Is there $f:[\omega]^2\to\{0,1\}$ with the following property?

Given any partition $P$ of $\omega$, is it always possible to find a partition $P_2$ of $\omega$ such that $W_{P_2}\subseteq W_P$ and $W_{P_2} \neq W_P$.

Answer 1

I believe not: let $f$ be any colouring and take a maximal equivalence relation $\sim$ on $\omega$ with the property that $m\sim n$ implies $f(\{m,n\})=0$. Note that $\sim$ can be extreme: the identity relation if $f$ is constant with value $1$, and $\sim$ is $\omega^2$ of $f$ is constant with value $0$. For the corresponding partition $P$ we have $W^{(1)}_P=\emptyset$. This means that if $Q$ is a partition with $W_Q\subseteq W_P$ then $W^{(1)}_Q=\emptyset$. Therefore we have $\bigcup\{[c]^2:c\in Q\}\subseteq f^{-1}(0)$ and since $W^{(0)}_Q\subseteq W^{(0)}_P$ we get $\bigcup\{[b]^2:b\in P\}\subseteq\bigcup\{[c]^2:c\in Q\}$ and this implies that $\sim$ is a subset of the equivalence relation that determines $Q$; by maximality it follows that $P=Q$.