6
$\begingroup$

We say that a family ${\cal S}\subseteq{\cal P}(\mathbb{N})$ is bijection-dodging if there is a bijection $\varphi:\mathbb{N}\to\mathbb{N}$ with $\varphi(T)\notin {\cal S}$ for all $T\in{\cal S}$.

Given a bijection-dodging family ${\cal S}\subseteq{\cal P}(\mathbb{N})$, is there necessarily a bijection-dodging ${\cal S}_0\subseteq{\cal P}(\mathbb{N})$ with ${\cal S}\subseteq{\cal S}_0$, and for every $X\in{\cal P}(\mathbb{N})\setminus{\cal S}_0$ we have that ${\cal S}_0\cup\{X\}$ is no longer bijection-dodging?

(Of course, one reflex is to use Zorn's Lemma, but there is a chain of bijection-dodging families with their union no longer being bijection-dodging.)

Improve this question
$\endgroup$
14
  • 5
    $\begingroup$ @HenrikRüping: Each $S_i$ has its own $\varphi_i$. $\endgroup$
    – Keith Kearnes
    Commented Jun 18 at 7:52
  • 2
    $\begingroup$ @ClaudeChaunier I must be misunderstanding something, but it seems to me that if $X=\{0011\}^\omega$ then $X\notin\mathcal S$ and $\mathbb N\setminus X\notin\mathcal S$. $\endgroup$
    – bof
    Commented Jun 24 at 22:34
  • 2
    $\begingroup$ @ClaudeChaunier My bad, I typed $=$ when I meant $\neq$. Bijection-dodging: there is a bijection $\varphi$ such that $\mathcal S\cap\varphi(\mathcal S)=\varnothing$. Not bijection-dodging: for every bijection $\varphi$ we have $\mathcal S\cap\varphi(\mathcal S)\neq\varnothing$. $\endgroup$
    – bof
    Commented Jun 25 at 7:14
  • 1
    $\begingroup$ @bof, you are right, about $X=(0011)^\omega$ too, thanks. I got my justification wrong and ${\mathcal P}({\mathbb N}) = (\{00, 11\}^*01\{0,1\}^\omega)\sqcup(\{00, 11\}^*10\{0,1\}^\omega)\sqcup(\{00,11\}^\omega)$. Truly, ${\cal S}_0 = \{00, 11\}^*01\{0,1\}^\omega$ is maximal because suppose there is a bijection $\varphi$ with $({\cal S}_0\cup\{X\})\cap\varphi({\cal S}_0\cup\{X\})=\varnothing$. Then $\varphi(1)=0$ and $\varphi(0)=1$ otherwise there would be room enough to send some $Y\in 01\{0,1\}^\omega\subseteq{\cal S}_0$ into ${\cal S}_0$ with some elementary juggling... $\endgroup$
    – Claude Chaunier
    Commented Jun 25 at 8:01
  • 1
    $\begingroup$ ... Then as well $\varphi(3)=2$ and $\varphi(2)=3$ and so on and $\varphi = \varphi_0 = (1\;0)(3\;2)\dots(2k+1\;\;k)\dots\;$. Now if you took $X\in\{00,11\}^\omega$ you would get $\varphi(X)=X$, a contradiction. Or you took $X\in\{00, 11\}^*10\{0,1\}^\omega$ and you would get $\varphi(X)\in{\cal S}_0$ a contradiction too. $\endgroup$
    – Claude Chaunier
    Commented Jun 25 at 8:02

0

Reset to default

You must log in to answer this question.