1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This amazingly natural argument totally escaped me - great answer!! $\endgroup$
    – Dominic van der Zypen
    Commented Jan 14, 2023 at 18:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .