Return to Answer

Joel David Hamkins, Asaf Karagila and I have made some progress characterizing which sets have such a function. There is still one open case left, but Joel's conjecture holds so far.

Let $[Y]^{X}$ denote the set of all $A \subseteq Y$ such that $A \approx X$. The question is to characterize the sets $X$ for which there is a function $d:[\mathcal{P}(X)]^{X}\to\mathcal{P}(X)$ such that $d(A) \notin A$ for all $A \in [\mathcal{P}(X)]^X$. We will instead try to answer the more general question when there is such a function $d:[Y]^X\to Y$ for arbitrary sets $X, Y$ with $X \preceq Y$. (If $X \npreceq Y$ then $[Y]^X = \varnothing$ and the question is not interesting.) An obviously necessary condition is that $\newcommand{\napprox}{\not\approx}X \napprox Y$ but this is not sufficient as Ricky illustrated. Joel conjectured that such a function exists if and only if $\aleph(X) \preceq Y$, where $\aleph(X)$ is the Hartog number of $X$, the smallest ordinal that does not inject into $X$. We will show that this conjecture is true for all Dedekind infinite sets $X$ (i.e. when $\aleph_0 \preceq X$). Since the statement is obviously true when $X \prec \aleph_0$, the only remaining case is when $X$ is infinite but Dedekind finite (i.e. when $n \prec X$ for every $n \prec \aleph_0$ but $\aleph_0 \npreceq X$).

If there is an injection $f:\aleph(X)\to Y$, then there is such a $d:[Y]^X\to Y$ can be defined as $d(A) = f(\alpha_0)$ where $\alpha_0 = \min\lbrace \alpha \lt \aleph(X) : f(\alpha) \notin A\rbrace$. This last set is always nonempty otherwise composing $f:\aleph(X)\to A$ with a bijection from $A$ onto $X$ contradicts the fact that $\aleph(X) \npreceq X$.

For the converse, the hope is to define an injection $f:\aleph(X)\to Y$ by transfinite recursion where at each stage $\alpha\lt\aleph(X)$, we choose some $f(\alpha) \notin \lbrace f(\beta) : \beta \lt \alpha \rbrace$. To make these choices we would need a function $\hat{d}:[Y]^{\prec\aleph(X)}\to Y$ such that $\hat{d}(A) \notin A$ for every $$A \in [Y]^{\prec\aleph(X)} \colon= \lbrace Z \subseteq Y : Z \prec \aleph(X)\rbrace.$$ What we are given is a function $d:[Y]^X\to Y$ with $d(A) \notin A$ for every $A \in [Y]^X$. A simple idea is to fix some $A_0 \in [Y]^X$ and define $$\hat{d}(A) = d(A \cup A_0)$$ for all $A \in [Y]^{\prec\aleph(X)}$ but this only makes sense when $A \cup A_0 \approx X$. In general, we only know that $$X \preceq A \cup A_0 \preceq A + X,$$ so this strategy will work provided that $\alpha + X \approx X$ for every $\alpha \lt \aleph(X)$. This last statement holds precisely when $X$ is empty or Dedekind infinite. Indeed, $X \approx 1+X$ already implies that $X$ is Dedekind infinite and then $X \approx \alpha + X$ follows from the fact that $\alpha + \alpha \preceq \max(\aleph_0,|\alpha|)$ for every ordinal $\alpha \lt \aleph(X)$.

Joel David Hamkins, Asaf Karagila and I have made some progress characterizing which sets have such a function. There is still one open case left, but Joel's conjecture holds so far.

Let $[Y]^{X}$ denote the set of all $A \subseteq Y$ such that $A \approx X$. The question is to characterize the sets $X$ for which there is a function $d:[\mathcal{P}(X)]^{X}\to\mathcal{P}(X)$ such that $d(A) \notin A$ for all $A \in [\mathcal{P}(X)]^X$. We will instead try to answer the more general question when there is such a function $d:[Y]^X\to Y$ for arbitrary sets $X, Y$ with $X \preceq Y$. (If $X \npreceq Y$ then $[Y]^X = \varnothing$ and the question is not interesting.) An obviously necessary condition is that $\newcommand{\napprox}{\not\approx}X \napprox Y$ but this is not sufficient as Ricky illustrated. Joel conjectured that such a function exists if and only if $\aleph(X) \preceq Y$, where $\aleph(X)$ is the Hartog number of $X$, the smallest ordinal that does not inject into $X$. We will show that this conjecture is true for all Dedekind infinite sets $X$ (i.e. when $\aleph_0 \preceq X$). Since the statement is obviously true when $X \prec \aleph_0$, the only remaining case is when $X$ is infinite but Dedekind finite (i.e. when $n \prec X$ for every $n \prec \aleph_0$ but $\aleph_0 \npreceq X$).

If there is an injection $f:\aleph(X)\to Y$, then there is such a $d:[Y]^X\to Y$ can be defined as $d(A) = f(\alpha_0)$ where $\alpha_0 = \min\lbrace \alpha \lt \aleph(X) : f(\alpha) \notin A\rbrace$. This last set is always nonempty otherwise composing $f:\aleph(X)\to A$ with a bijection from $A$ onto $X$ contradicts the fact that $\aleph(X) \npreceq X$.

For the converse, the hope is to define an injection $f:\aleph(X)\to Y$ by transfinite recursion where at each stage $\alpha\lt\aleph(X)$, we choose some $f(\alpha) \notin \lbrace f(\beta) : \beta \lt \alpha \rbrace$. To make these choices we would need a function $\hat{d}:[Y]^{\prec\aleph(X)}\to Y$ such that $\hat{d}(A) \notin A$ for every $$A \in [Y]^{\prec\aleph(X)} \colon= \lbrace Z \subseteq Y : Z \prec \aleph(X)\rbrace.$$ What we are given is a function $d:[Y]^X\to Y$ with $d(A) \notin A$ for every $A \in [Y]^X$. A simple idea is to fix some $A_0 \in [Y]^X$ and define $$\hat{d}(A) = d(A \cup A_0)$$ for all $A \in [Y]^{\prec\aleph(X)}$ but this only makes sense when $A \cup A_0 \approx X$. In general, we only know that $$X \preceq A \cup A_0 \preceq A + X,$$ so this strategy will work provided that $\alpha + X \approx X$ for every $\alpha \lt \aleph(X)$. This last statement holds precisely when $X$ is empty or Dedekind infinite. Indeed, $X \approx 1+X$ already implies that $X$ is Dedekind infinite and then $X \approx \alpha + X$ follows from the fact that $\alpha + \alpha \preceq \max(\aleph_0,|\alpha|)$ for every ordinal $\alpha \lt \aleph(X)$.

Asaf Karagila and I have made a little more progress on the case where $X$ and $Y$ are both Dedekind finite. In that case $Y \approx X + Z$ and the complement in $Y$ of any element of $[Y]^X$ has size exactly $Z$ and vice versa. Therefore, the existence of a $d:[Y]^X\to Y$ such that $d(A) \notin A$ for each $A \in [Y]^X$ is precisely equivalent to the existence of a choice function $c:[Y]^Z \to X$. In particular, if $Y \approx X+1$ then there is such a $d:[Y]^X \to Y$ since there clearly is a choice function $c:[Y]^1\to Y$. This does contradict the extension of Joel's conjecture to arbitrary $Y$ but not Joel's original conjecture where $Y = \mathcal{P}(X)$. Unfortunately, we still do not know what happens when $X$ and $Y = \mathcal{P}(X)$ are both infinite but Dedekind finite.

The existence of choice functions $[Y]^Z\to Y$ is a very intricate problem. For example, it is known that the existence of a choice function $[Y]^2\to Y$ is equivalent to the existence of a choice function $[Y]^4\to Y$ but that this does not imply the existence of a choice function $[Y]^3\to Y$! These intricate implications have been examined by John Conway in the article Effective implications between the "finite" choice axioms [Cambridge Summer School in Mathematical Logic, Lecture Notes in Mathematics 337 (1973), 439–458. MR0360275, doi:10.1007/BFb0066784].

Joel David Hamkins, Asaf Karagila and I have made some progress characterizing which sets have such a function. There is still one open case left, but Joel's conjecture holds so far.

Let $[Y]^{X}$ denote the set of all $A \subseteq Y$ such that $A \approx X$. The question is to characterize the sets $X$ for which there is a function $d:[\mathcal{P}(X)]^{X}\to\mathcal{P}(X)$ such that $d(A) \notin A$ for all $A \subseteq [\mathcal{P}(X)]^X$. We will instead try to answer the more general question when there is such a function $d:[Y]^X\to Y$ for arbitrary sets $X, Y$ with $X \preceq Y$. (If $X \npreceq Y$ then $[Y]^X = \varnothing$ and the question is not interesting.) An obviously necessary condition is that $\newcommand{\napprox}{\not\approx}X \napprox Y$ but this is not sufficient as Ricky illustrated. Joel conjectured that such a function exists if and only if $\aleph(X) \preceq Y$, where $\aleph(X)$ is the Hartog number of $X$, the smallest ordinal that does not inject into $X$. We will show that this conjecture is true for all Dedekind infinite sets $X$ (i.e. when $\aleph_0 \preceq X$). Since the statement is obviously true when $X \prec \aleph_0$, the only remaining case is when $X$ is infinite but Dedekind finite (i.e. when $n \prec X$ for every $n \prec \aleph_0$ but $\aleph_0 \npreceq X$).

If there is an injection $f:\aleph(X)\to Y$, then there is such a $d:[Y]^X\to Y$ can be defined as $d(A) = f(\alpha_0)$ where $\alpha_0 = \min\lbrace \alpha \lt \aleph(X) : f(\alpha) \notin A\rbrace$. This last set is always nonempty otherwise composing $f:\aleph(X)\to A$ with a bijection from $A$ onto $X$ contradicts the fact that $\aleph(X) \npreceq X$.

For the converse, the hope is to define an injection $f:\aleph(X)\to Y$ by transfinite recursion where at each stage $\alpha\lt\aleph(X)$, we choose some $f(\alpha) \notin \lbrace f(\beta) : \beta \lt \alpha \rbrace$. To make these choices we would need a function $\hat{d}:[Y]^{\prec\aleph(X)}\to Y$ such that $\hat{d}(A) \notin A$ for every $$A \in [Y]^{\prec\aleph(X)} \colon= \lbrace Z \subseteq Y : Z \prec \aleph(X)\rbrace.$$ What we are given is a function $d:[Y]^X\to Y$ with $d(A) \notin A$ for every $A \in [Y]^X$. A simple idea is to fix some $A_0 \in [Y]^X$ and define $$\hat{d}(A) = d(A \cup A_0)$$ for all $A \in [Y]^{\prec\aleph(X)}$ but this only makes sense when $A \cup A_0 \approx X$. In general, we only know that $$X \preceq A \cup A_0 \preceq A + X,$$ so this strategy will work provided that $\alpha + X \approx X$ for every $\alpha \lt \aleph(X)$. This last statement holds precisely when $X$ is empty or Dedekind infinite. Indeed, $X \approx 1+X$ already implies that $X$ is Dedekind infinite and then $X \approx \alpha + X$ follows from the fact that $\alpha + \alpha \preceq \max(\aleph_0,|\alpha|)$ for every ordinal $\alpha \lt \aleph(X)$.

Joel David Hamkins, Asaf Karagila and I have made some progress characterizing which sets have such a function. There is still one open case left, but Joel's conjecture holds so far.

Let $[Y]^{X}$ denote the set of all $A \subseteq Y$ such that $A \approx X$. The question is to characterize the sets $X$ for which there is a function $d:[\mathcal{P}(X)]^{X}\to\mathcal{P}(X)$ such that $d(A) \notin A$ for all $A \in [\mathcal{P}(X)]^X$. We will instead try to answer the more general question when there is such a function $d:[Y]^X\to Y$ for arbitrary sets $X, Y$ with $X \preceq Y$. (If $X \npreceq Y$ then $[Y]^X = \varnothing$ and the question is not interesting.) An obviously necessary condition is that $\newcommand{\napprox}{\not\approx}X \napprox Y$ but this is not sufficient as Ricky illustrated. Joel conjectured that such a function exists if and only if $\aleph(X) \preceq Y$, where $\aleph(X)$ is the Hartog number of $X$, the smallest ordinal that does not inject into $X$. We will show that this conjecture is true for all Dedekind infinite sets $X$ (i.e. when $\aleph_0 \preceq X$). Since the statement is obviously true when $X \prec \aleph_0$, the only remaining case is when $X$ is infinite but Dedekind finite (i.e. when $n \prec X$ for every $n \prec \aleph_0$ but $\aleph_0 \npreceq X$).

If there is an injection $f:\aleph(X)\to Y$, then there is such a $d:[Y]^X\to Y$ can be defined as $d(A) = f(\alpha_0)$ where $\alpha_0 = \min\lbrace \alpha \lt \aleph(X) : f(\alpha) \notin A\rbrace$. This last set is always nonempty otherwise composing $f:\aleph(X)\to A$ with a bijection from $A$ onto $X$ contradicts the fact that $\aleph(X) \npreceq X$.

For the converse, the hope is to define an injection $f:\aleph(X)\to Y$ by transfinite recursion where at each stage $\alpha\lt\aleph(X)$, we choose some $f(\alpha) \notin \lbrace f(\beta) : \beta \lt \alpha \rbrace$. To make these choices we would need a function $\hat{d}:[Y]^{\prec\aleph(X)}\to Y$ such that $\hat{d}(A) \notin A$ for every $$A \in [Y]^{\prec\aleph(X)} \colon= \lbrace Z \subseteq Y : Z \prec \aleph(X)\rbrace.$$ What we are given is a function $d:[Y]^X\to Y$ with $d(A) \notin A$ for every $A \in [Y]^X$. A simple idea is to fix some $A_0 \in [Y]^X$ and define $$\hat{d}(A) = d(A \cup A_0)$$ for all $A \in [Y]^{\prec\aleph(X)}$ but this only makes sense when $A \cup A_0 \approx X$. In general, we only know that $$X \preceq A \cup A_0 \preceq A + X,$$ so this strategy will work provided that $\alpha + X \approx X$ for every $\alpha \lt \aleph(X)$. This last statement holds precisely when $X$ is empty or Dedekind infinite. Indeed, $X \approx 1+X$ already implies that $X$ is Dedekind infinite and then $X \approx \alpha + X$ follows from the fact that $\alpha + \alpha \preceq \max(\aleph_0,|\alpha|)$ for every ordinal $\alpha \lt \aleph(X)$.

Joel David Hamkins, Asaf Karagila and I have made some progress characterizing which sets have such a function. There is still one open case left, but Joel's conjecture holds so far.

Let $[Y]^{X}$ denote the set of all $A \subseteq Y$ such that $A \approx X$. The question is to characterize the sets $X$ for which there is a function $d:[\mathcal{P}(X)]^{X}\to\mathcal{P}(X)$ such that $d(A) \notin A$ for all $A \subseteq [\mathcal{P}(X)]^X$. We will instead try to answer the more general question when there is such a function $d:[Y]^X\to Y$ for arbitrary sets $X, Y$ with $X \preceq Y$. (If $X \npreceq Y$ then $[Y]^X = \varnothing$ and the question is not interesting.) An obviously necessary condition is that $\newcommand{\napprox}{\not\approx}X \napprox Y$ but this is not sufficient as Ricky illustrated. Joel conjectured that such a function exists if and only if $\aleph(X) \preceq Y$, where $\aleph(X)$ is the Hartog number of $X$, the smallest ordinal that does not inject into $X$. We will show that this conjecture is true for all Dedekind infinite sets $X$ (i.e. when $\aleph_0 \preceq X$). Since the statement is obviously true when $X \prec \aleph_0$, the only remaining case is when $X$ is infinite but Dedekind finite (i.e. when $n \prec X$ for every $n \prec \aleph_0$ but $\aleph_0 \npreceq X$).

If there is an injection $f:\aleph(X)\to Y$, then there is such a $d:[Y]^X\to Y$ since we can define $d(A) = f(\alpha_0)$ where $\alpha_0 = \min\lbrace \alpha \lt \aleph(X) : f(\alpha) \notin A\rbrace$. This last set is always nonempty otherwise composing $f:\aleph(X)\to A$ with a bijection from $A$ onto $X$ contradicts the fact that $\aleph(X) \npreceq X$.

For the converse, the hope is to define an injection $f:\aleph(X)\to Y$ by transfinite recursion where at each stage $\alpha\lt\aleph(X)$, we choose some $f(\alpha) \notin \lbrace f(\beta) : \beta \lt \alpha \rbrace$. To make these choices we would need a function $\hat{d}:[Y]^{\prec\aleph(X)}\to Y$ such that $\hat{d}(A) \notin A$ for every $$A \in [Y]^{\prec\aleph(X)} \colon= \lbrace Z \subseteq Y : Z \prec \aleph(X)\rbrace.$$ What we are given is a function $d:[Y]^X\to Y$ with $d(A) \notin A$ for every $A \in [Y]^X$. A simple idea is to fix some $A_0 \in [Y]^X$ and define $$\hat{d}(A) = d(A \cup A_0)$$ for all $A \in [Y]^{\prec\aleph(X)}$ but this only makes sense when $A \cup A_0 \approx X$. In general, we only know that $$X \preceq A \cup A_0 \preceq A + X,$$ so this strategy will work provided that $\alpha + X \approx X$ for every $\alpha \lt \aleph(X)$. This last statement holds precisely when $X$ is empty or Dedekind infinite. Indeed, $X \approx 1+X$ already implies that $X$ is Dedekind infinite and then $X \approx \alpha + X$ follows from the fact that $\alpha + \alpha \preceq \aleph_0 + \alpha$ for every ordinal $\alpha \lt \aleph(X)$.

Joel David Hamkins, Asaf Karagila and I have made some progress characterizing which sets have such a function. There is still one open case left, but Joel's conjecture holds so far.

Let $[Y]^{X}$ denote the set of all $A \subseteq Y$ such that $A \approx X$. The question is to characterize the sets $X$ for which there is a function $d:[\mathcal{P}(X)]^{X}\to\mathcal{P}(X)$ such that $d(A) \notin A$ for all $A \subseteq [\mathcal{P}(X)]^X$. We will instead try to answer the more general question when there is such a function $d:[Y]^X\to Y$ for arbitrary sets $X, Y$ with $X \preceq Y$. (If $X \npreceq Y$ then $[Y]^X = \varnothing$ and the question is not interesting.) An obviously necessary condition is that $\newcommand{\napprox}{\not\approx}X \napprox Y$ but this is not sufficient as Ricky illustrated. Joel conjectured that such a function exists if and only if $\aleph(X) \preceq Y$, where $\aleph(X)$ is the Hartog number of $X$, the smallest ordinal that does not inject into $X$. We will show that this conjecture is true for all Dedekind infinite sets $X$ (i.e. when $\aleph_0 \preceq X$). Since the statement is obviously true when $X \prec \aleph_0$, the only remaining case is when $X$ is infinite but Dedekind finite (i.e. when $n \prec X$ for every $n \prec \aleph_0$ but $\aleph_0 \npreceq X$).

If there is an injection $f:\aleph(X)\to Y$, then there is such a $d:[Y]^X\to Y$ can be defined as $d(A) = f(\alpha_0)$ where $\alpha_0 = \min\lbrace \alpha \lt \aleph(X) : f(\alpha) \notin A\rbrace$. This last set is always nonempty otherwise composing $f:\aleph(X)\to A$ with a bijection from $A$ onto $X$ contradicts the fact that $\aleph(X) \npreceq X$.

For the converse, the hope is to define an injection $f:\aleph(X)\to Y$ by transfinite recursion where at each stage $\alpha\lt\aleph(X)$, we choose some $f(\alpha) \notin \lbrace f(\beta) : \beta \lt \alpha \rbrace$. To make these choices we would need a function $\hat{d}:[Y]^{\prec\aleph(X)}\to Y$ such that $\hat{d}(A) \notin A$ for every $$A \in [Y]^{\prec\aleph(X)} \colon= \lbrace Z \subseteq Y : Z \prec \aleph(X)\rbrace.$$ What we are given is a function $d:[Y]^X\to Y$ with $d(A) \notin A$ for every $A \in [Y]^X$. A simple idea is to fix some $A_0 \in [Y]^X$ and define $$\hat{d}(A) = d(A \cup A_0)$$ for all $A \in [Y]^{\prec\aleph(X)}$ but this only makes sense when $A \cup A_0 \approx X$. In general, we only know that $$X \preceq A \cup A_0 \preceq A + X,$$ so this strategy will work provided that $\alpha + X \approx X$ for every $\alpha \lt \aleph(X)$. This last statement holds precisely when $X$ is empty or Dedekind infinite. Indeed, $X \approx 1+X$ already implies that $X$ is Dedekind infinite and then $X \approx \alpha + X$ follows from the fact that $\alpha + \alpha \preceq \max(\aleph_0,|\alpha|)$ for every ordinal $\alpha \lt \aleph(X)$.