Let $J\subseteq {\cal P}(\omega)$ be the collection of infinite subsets whose complement is also infinite.
Is there a fixed-point free bijection $\varphi:J\to J$ such that $\varphi(j)\subseteq j$ for all $j\in J$?
$\begingroup$
$\endgroup$
8
-
4$\begingroup$ This seems like a reasonable question to me and I learned something from the answer. Perhaps one of the downvoters might explain? $\endgroup$Mark Wildon– Mark Wildon2026-02-27 18:32:19 +00:00Commented yesterday
-
2$\begingroup$ Note that the bijection $\varphi$ can be constructed so that $|j\setminus\varphi(j)|=1$ for all $j\in J$. $\endgroup$bof– bof2026-02-28 03:23:15 +00:00Commented 23 hours ago
-
1$\begingroup$ @bof Do you mind sharing the construction? It’s not clear to me how to do that. It certainly does not follow from the argument in my answer. $\endgroup$David Gao– David Gao2026-02-28 07:24:33 +00:00Commented 19 hours ago
-
1$\begingroup$ @DavidGao Call two sets equivalent if their symmetric difference is finite. On each equivalence class $C$ define a bijection $\varphi_C:C\to C$ with the desired properties. (A recursive construction of length $\omega$ similar to your argument.) Take the union. $\endgroup$bof– bof2026-02-28 09:00:41 +00:00Commented 17 hours ago
-
2$\begingroup$ Here is a related question. It is known that for any $n \geq 1$ and $k \leq n/2$, there is a bijection $\varphi$ from the set of $k$-subsets of $[n]=\{1,2,\ldots,n\}$ to the set of $(n-k)$-subsets of $[n]$ such that $S\subseteq \varphi(S)$ for all $S$ (look up "symmetric chain decomposition of Boolean lattice"). Is there a bijection $\varphi$ from the finite subsets of $\{1,2,\ldots\}$ to the cofinite subsets such that $S \subseteq \varphi(S)$ for all $S$? $\endgroup$Sam Hopkins– Sam Hopkins ♦2026-02-28 14:47:50 +00:00Commented 11 hours ago
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
0
There are continuum many elements of $J$. Each $j \in J$ has continuum many proper subsets contained in $J$ as well as continuum many proper supersets contained in $J$. So, such a bijection $\varphi$ can be constructed by transfinite induction up to $\mathfrak{c}$.
For a more specific outline: fix a map $f: \mathfrak{c} \to J$ s.t. it restricts to a bijection on even ordinals and a bijection on odd ordinals. Perform transfinite induction up to $\mathfrak{c}$. At an even ordinal $\kappa < \mathfrak{c}$, if $\varphi(f(\kappa))$ is not yet defined, set it to be a proper subset of $f(\kappa)$ that is in $J$ but not yet in the range of $\varphi$. At an odd ordinal $\kappa < \mathfrak{c}$, if $f(\kappa)$ is not yet in the range of $\varphi$, set $\varphi(j) = f(\kappa)$ for a proper superset $j$ of $f(\kappa)$ with $j \in J$ but not yet in the domain of $\varphi$.
