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](https://en.wikipedia.org/wiki/Partition_of_a_set) 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$. 
> 
> 
> 



Minimizing the set of "wrong" edges in $K_\omega$ with $\{0,1\}$-weights
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$.


