We say that a bijection $\varphi:\omega\to\omega$ *parity-separates* $a\neq b\in \omega$ if $\varphi(a)$ is even and $\varphi(b)$ is odd, or vice versa.


Is there a finite set $\Phi$ of bijections such that for all $a\neq b\in\omega$ there is $\varphi\in\Phi$ such that $\varphi$ parity-separates $a,b$? If yes, how small can $|\Phi|$ be?



Can $\omega$ be parity-separated with finitely many bijections?
No, because if you have $n$ functions, then the number of possible parity patterns to be exhibited by a number with respect to them is $2^n$. So by the pigeon-hole principle there must be infinitely many numbers with the same pattern. So it doesn't separate those numbers.


