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$.


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$.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.