Image-catching families in $\omega$

Question

Let $[\omega]^\omega$ be the collection of infinite subsets of the set of nonnegative integers $\omega$, and let $\newcommand{\I}{\cal{I}}\I=$ $\{S\in[\omega]^\omega: (\omega\setminus S)\in[\omega]^\omega\}$.

We say that a collection $\cal{C}\subseteq \I$ is image-catching if for every bijection $\varphi:\omega\to\omega$ there is $C\in {\cal C}$ such that the image of $C$ under $\varphi$, that is $\varphi(C)$, is again a member of $\cal{C}$. Clearly, $\I$ itself is image-catching.

Question. Does every image-catching family have cardinality ${\frak c}=2^{\aleph_0}$?

Answer 1

Original partial answer:

Here is some information: An easy diagonalization shows that every image-catching family is uncountable. And more generally, MA implies that every image-catching family has cardinality $2^{\aleph_0}$. For suppose $A\subseteq\mathcal{I}$ has cardinality $\kappa<2^{\aleph_0}$. Consider Cohen forcing, in the form of forcing a bijection $\varphi:\omega\to\omega$ with conditions are triples $(X,Y,\pi)$ where $X,Y\subseteq\omega$ are finite sets and $\pi:X\to Y$ is a bijection, ordered by extension, i.e. $(X',Y',\pi')\leq(X,Y,\pi)$ if $X\subseteq X'$ and $Y\subseteq Y'$ and $\pi\subseteq\pi'$. (So from a sufficiently generic filter $G$, $\varphi=\bigcup G$ is the generic bijection.) Given $C,D\in A$, the set of conditions $(X,Y,\pi)$ which force $\varphi``C\neq D$ is dense. Since there are only $\kappa$-many such pairs $(C,D)$ (and meeting the countably many dense sets which ensure $\varphi:\omega\to\omega$ is a bijection), we get a bijection $\varphi$ demonstrating that $A$ is not image-catching.

EDIT:

Yes, every image-catching family has cardinality $2^{\aleph_0}$ (under ZFC).

Claim: There is a family $\left<\varphi_x\right>_{x\in{^\omega}2}$ of bijections $\varphi_x:\omega\to\omega$ such that for all $x,y\in{^\omega}2$, if $x\neq y$ then there is a unique infinite set $A\subseteq\omega$ such that $\varphi_x``A=\varphi_y``A$, and moreover, this $A$ is cofinite.

(This claim easily proves that every image-catching family $F$ has cardinality $2^{\aleph_0}$. For suppose $F$ has cardinality $\kappa<2^{\aleph_0}$. For $x\in{^\omega}2$, let $C_x\in F$ be such that $\varphi_x``C_x\in F$. Then there is a set $X\subseteq{^\omega}2$ of cardinality $\kappa^+$ such that $C_x=C_y$ for all $x,y\in X$. Since $\varphi_x``C_x\in F$ for all $x\in X$, there must be $x,y\in X$ such that $\varphi_x``C_x=\varphi_y``C_y$. But then by the property of the claim, $C_x=C_y$ is cofinite, hence not in $\mathcal{I}$.)

To construct the family as in the claim, we will construct a family $\left<\varphi_s,D_s,R_s\right>_{s\in{^{<\omega}}2}$ such that $D_s,R_s\subseteq\omega$ are finite sets and $\varphi_s:D_s\to R_s$ is a bijection with $\mathrm{lh}(s)\subseteq D_s\cap R_s$, where $\mathrm{lh}(s)$ denotes the length of $s$. We will then set $\varphi_x=\bigcup_{n<\omega}\varphi_{x\upharpoonright n}$, for $x\in{^\omega}2$.

We start with $\varphi_\emptyset=D_\emptyset=R_\emptyset=\emptyset$.

Suppose we have constructed $\varphi_s,D_s,R_s$ for all $s\in{^n}2$ where $n<\omega$. We must now construct $\varphi_{t},D_t,R_t$ for $t\in{^{n+1}}2$.

(The intention: For $x,y\in{^\omega}2$ and $u\in {^k}2$ such that $u=x\upharpoonright k=y\upharpoonright k$ but $x(k)\neq y(k)$, we will arrange that (i) $x(i)\neq y(i)$ for all $i\notin D_u$. (And $x(i)=y(i)=\varphi_u(i)$ for all $i\in D_u$.) Further, (ii) we will arrange that $\omega\setminus D_u$ is the unique infinite set $A\subseteq\omega$ such that $\varphi_x``A=\varphi_y``A$. The plan for the latter is, considering one of the proofs of the Cantor-Schr"oder-Bernstein theorem, to ensure that $A\subseteq\omega$ is the unique infinite set closed under both $\varphi_y^{-1}\circ\varphi_x$ and $\varphi_x^{-1}\circ\varphi_y$.)

First let us handle the requirement that $n+1\subseteq D_t\cap R_t$, keeping the above intention in mind. Let $N_n$ be the least integer $N$ such that $\bigcup_{s\in{^n}2} (D_s\cup R_s)\subseteq N$. For each $t\in {^{n+1}}2$, if $n\notin D_{t\upharpoonright n}$, define $\varphi_t(n)$ to be some value $\geq N_n$, and such that for all $t_1,t_2\in{^{n+1}}2$ with $t_1\neq t_2$ and $n\notin D_{t_1\upharpoonright n}\cup D_{t_2\upharpoonright n}$, we have $\varphi_{t_1}(n)\neq\varphi_{t_2}(n)$. (We only need to use finitely many new output values for this, so it is no problem.) Let $N'_n$ be the maximum of the output values just defined, $+1$, or $N'_n=N_n$ if none were defined. Now, similarly, for each $t\in {^{n+1}}2$, if $n\notin R_{t\upharpoonright n}$, define $\varphi_t^{-1}(n)$ as some value $\geq N'_n$, making these new inverse images all pairwise distinct. Thus, we will have $n\in D_t\cap R_t$ for each $t\in{^{n+1}}2$, once we have defined $D_t,R_t,\varphi_t$.

We now want to handle item (ii) of the intention above. Let $\left<t^0_k,t^1_k\right>_{k<A_n}$ enumerate all pairs $(t^0,t^1)\in{{n+1}}2$ with $t^0\neq t^1$ and $t^0<_{\mathrm{lex}}t^1$ (that is, the lexicographic ordering on tuples). In $A_n$ stages $k<A_n$, we will extend the functions $\varphi_{t^0_k}$ and $\varphi_{t^1_k}$, adding finitely many input/output pairs to these functions at this stage (hence also adding elements to the sets $D_{t^0_k},R_{t^0_k}$ and $D_{t^1_k},R_{t^1_k}$). At stage $k$, let $M_k$ be the least integer above all inputs and outputs of any $\varphi_{s}$, for $s\in{^n}2$, or of any of the inputs and outputs specified for any of the $\varphi_{t}$, for $t\in{^{n+1}}2$, either in the preceding paragraph, or at one of the stages $k'<k$ just mentioned. Within stage $k$, whenever we define $\varphi_{t^i_k}(x)=y$ for some $i\in\{0,1\}$ and some $x,y$, then we will either have $x\geq M_k$ or $y\geq M_k$ (possibly both).

Let $f$ be the approximation to what will be the eventual $\varphi_{t^0_k}$ that we have produced so far (i.e. after the previous paragraph and after the end of stage $k-1$, if $k>0$). Let $g$ be the approximation to $\varphi_{t^1_k}$. Say that a sequence $(x_0,x_1,x_2,\ldots,x_\ell)$ is an $(f,g^{-1})$-chain if $x_{2i+1}=f(x_{2i})$ for each $2i+1\leq\ell$ and $x_{2i+2}=g^{-1}(x_{2i+1})$ for each $2i+2\leq\ell$. Say a sequence as above is a *$(g^{-1},f)$-chain if $x_{2i+1}=g^{-1}(x_{2i})$ for each $2i+1\leq\ell$ and $x_{2i+2}=f(x_{2i+1})$ for each $2i+1\leq\ell$.

An $(f,g^{-1})$-chain, or a $(g^{-1},f)$-chain, as above, is a cycle if $x_i=x_j$ for some $i<j\leq\ell$ with $i,j$ of the same parity. An $(f,g)$-chain as above is good if there is no $(f,g)$-chain of form $(x_0,x_1,\ldots,x_\ell,y)$, and no $(g^{-1},f)$-chain of form $(y,x_0,x_1,\ldots,x_\ell)$. Likewise define good for $(g^{-1},f)$-chains.

Let $s=t^0_k\cap t^1_k$. Let $x\in D_s$. Note then that $y=f(x)=g(x)\in R_s$, and $(x,y,x)$ and $(y,x,y,x,y,x)$ are cycles, for example. Say such cycles (alternations of some $x,y=f(x)$ with $x\in D_s$) are trivial. Note that no cycle is maximal.

At the beginning of stage $k$, we will have inductively maintained that the only cycles (w.r.t. the $f,g$ above) are trivial. In fact, we will have the same fact with respect to all other pairs $f',g'$ with $f'$ the stage-$k$-approximation to $\varphi_{u^0}$ and $g'$ the stage-$k$-approximation to $\varphi_{u^1}$, where $u^i\in{{n+1}}2$ and $u^0<_{\mathrm{lex}}u^1$ (where $(f',g')$-chain, cycle and trivial are all defined using $(f',g')$).

In stage $k$, we extend $f,g$ to $f^+,g^+$, such that whenever we add a new input/output pair $f^+(i)=j$ or $g^+(i)=j$, then $\max(i,j)\geq M_k$. Note that with finitely many such new input/output pairs, we can arrange that there is a unique sequence which is either a maximal $(f^+,g^+)$-chain or a maximal $((g^+)^{-1},f^+)$-chain, and moreover, which of these two options holds is uniquely determined. To arrange this, we just take the various distinct maximal chains, put them in some linear order, and add in links between them using appropriate new input/output values. This completes stage $k$.

At the end of all stages $k<A_n$, we have completed the constructions of all $\varphi_t:D_t\to R_t$, completing stage $n+1$ of the entire construction, and hence the entire construction.

We claim that this gives a family with the desired properties. The main thing is to see that in stage $k$ above, and also in the step handling item (i) (prior to stage $0$), we don't add any non-trivial cycles with respect to the approximations $f'$ to $\varphi_{u^0}$ and $g'$ to $\varphi_{u^1}$, where $u^i\in{{n+1}}2$ and $u^0<_{\mathrm{lex}}u^1$. Consider stage $k$. If we did add such a cycle, it must be that $t^0_k=u^0$ or $t^1_k=u^0$ or $t^0_k=u^1$ or $t^1_k=u^1$. Certainly at most one of these 4 options holds. But then because all new input/output pairs $x,y$ have $\max(x,y)\geq M_k$, we can't add such a cycle at this stage. (That is, although some of the $(f',(g')^{-1})$-chains or $((g')^{-1},f')$-chains might get extended, they can only extend at most one step at each end, and only with respect to the same ``side'' (corresponding to $f'$ or $g'$), and this must involve some integer not already present in the former chain. This easily implies it cannot produce a cycle.)

Finally note that if $x\in{^\omega}2$ then $\varphi_x:\omega\to\omega$ is a bijection, and if $x\neq y\in{^\omega}2$ and $C$ is infinite and $\varphi_x``C=\varphi_y``C$, then $C=\omega\setminus\{i\bigm|\varphi_x(i)=\varphi_y(i)\}$, and $\{i\bigm|\varphi_x(i)=\varphi_y(i)\}=D_s$ where $s=x\upharpoonright n$ is largest such that $s=y\upharpoonright n$. This is because for every $m>n$, there was a stage $k<A_m$ at which we handled (ii) with respect to the pair $x\upharpoonright m,y\upharpoonright m$.