# Cantor's diagonal argument and ZF

Cantor's diagonalization construction, on a certain view, furnishes functions $$d_X:{\rm Injections}(X,P(X))\rightarrow P(X)$$ that satisfy $\forall X\forall i\ \ d_X(i)\not\in i(X)$

In ZF, can one prove the existence of such functions with the added requirement that $d_X(i)$ actually depends only on the image $i(X)$?

-
I suspect ZF doesn't even prove the existence of such a map in the case $X=\mathbb{N}$; see Joel David Hamkins' answer to mathoverflow.net/questions/47185/…. I don't think that answer answers this question, but it does make me suspect that in the smallest nontrivial case we've already gotten beyond ZF. –  Noah S Feb 19 '13 at 3:57
Different but related question: mathoverflow.net/questions/47185/… –  Joel David Hamkins Feb 19 '13 at 3:58
David, Cantor's argument does not use that $i$ is injective, for we can diagonalize against any countable enumeration of reals, even if there are repetitions. Was there a reason you add that restriction? –  Joel David Hamkins Feb 19 '13 at 23:34
David, it is actually unknown whether or not the well-foundedness of cardinals is equivalent to the axiom of choice. All we know that the cardinals can get very wild, including infinite decreasing sequences. But we yet to know about a model where choice fails and there is no decreasing sequence of cardinals (and even more, decreasing cardinality $\subseteq$ chain of sets); nor we know about a proof that there are no such models. –  Asaf Karagila Feb 21 '13 at 2:28
David, the order defined by surjection is commonly written as $|A|\lt^\ast|B|$. I am actually very interested in the well-foundedness of cardinals without choice; and in fact its relation to the problem of infinite antichains of cardinals (in $\leq^\ast$ more than in $\leq$ to be fair). In the presence of countable choice the two problems are equivalent, but I still don't know what happens when countable choice fails (if there is a D-finite set then there is a decreasing chain, and thus an antichain, but if there is no DF sets, I don't know much yet). –  Asaf Karagila Feb 21 '13 at 9:48

If there is such a function then there is an injection from $\omega_1$ to $2^{\omega}$.
(Set $\: X = \omega \:$, $\:$ send the finite ordinals to the corresponding singletons,
then extend to $\omega_1$ with transfinite recursion.)

If there is such a function and the continuum hypothesis holds then $\: 2^{\aleph_0} = \aleph_1 \:$.

It is consistent with ZF that the continuum hypothesis holds and $\: 2^{\aleph_0} \neq \aleph_1 \:$.

Therefore ZF does not prove the existence of such a function.

-
A special case of $ZF$ not proving the existence of an injection $\omega_1\rightarrow \mathbb{R}$: I believe that $ZF+AD$ (maybe I mean $ZF+AD+DC$?) in fact proves that there is no such injection. To be fair, this does bump the consistency strength up past that of $ZF$, which I think is unnecessary. –  Noah S Feb 19 '13 at 4:04
That's why I continued hunting after I found the link that you posted in your first comment. –  Ricky Demer Feb 19 '13 at 4:07
Very nice. –  Joel David Hamkins Feb 19 '13 at 4:14
Noah, a much simpler case where ZF does not prove there is an injection is Solovay's model, and in that model CH holds. Of course this too requires a bump in consistency, but Truss' model shows it is possible to have without inaccessible cardinals if we are willing to have $\omega_1$ singular. If you only want the prove there is no injection then it's easiest to do with the Feferman-Levy construction in which the continuum is a countable union of countable sets, one can show that $\omega_1$ does not inject into the real numbers in the Feferman-Levy model. –  Asaf Karagila Feb 19 '13 at 17:21

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].

-
Should that be "...such that $d(A) \not\in A$ for all $A \in [\mathcal{P}(X)]^X$."? –  David Roberts Feb 25 '13 at 22:42
Fixed it. Thanks! –  François G. Dorais Feb 25 '13 at 23:07
Great job, François! Will someone kindly prove or refute the conjecture? –  Joel David Hamkins Feb 26 '13 at 0:13
Joel, I am still trying to wrap my head around the amorphous case. I think I may have to call a specialist. –  Asaf Karagila Feb 26 '13 at 6:11
The remaining case is not when $X$ is Dedekind-finite but rather when $Y$ is Dedekind-finite. If $Y$ is Dedekind-infinite then $\aleph(X)\preceq Y$ and we can easily give a solution. Additionally, if $Y=X\cup\{X\}$ then it is also clear what $d$ should be. Beyond these two trivial cases, I can't really say too much. –  Asaf Karagila Feb 26 '13 at 19:40

Let me point out that in the case $X=\mathbb{N}$, the assertion seems to be simply equivalent to the existence of an injection $\omega_1\to \mathbb{R}$. Ricky has cleverly proved the forward implication. But conversely, if there is a such an injection of $\omega_1\to\mathbb{R}$, then we can define $d_X(i)$ to be the first real not in $i(X)$.

This idea generalizes to higher well-ordered cardinals as well. If $X=\kappa$, then the existence of a map as you request is equivalent to the existence of an injection $\kappa^+\to P(\kappa)$. Ricky's argument again gives the forward direction, and conversely, if there is an injection $\kappa^+\to P(\kappa)$, then we can let $d_X(i)$ be the first set on the list not in $i(X)$.

Perhaps it is true that for any set $X$, the property on $X$ is equivalent to the assertion that the Hartog number $\aleph(X)$, the first ordinal not embedding in $X$, injects into $P(X)$. The converse direction is the same as above, but it isn't clear to me whether one can push Ricky's argument through for this.

-
And I think your argument, Asaf, works for all Dedekind finite $X$. I think this is it! –  François G. Dorais Feb 19 '13 at 20:31
Francois, it seems so! We made quite the complements here! :-D –  Asaf Karagila Feb 19 '13 at 20:32
Asaf, why don't you post an answer explaining it all? –  Joel David Hamkins Feb 19 '13 at 21:57
I vote for Asaf :) –  François G. Dorais Feb 19 '13 at 22:28
Hang on. I see a problem with my argument. The choice of $d_X(i)$ should be independent of $i$, so if $i_1(X)=i_2(X)$ we should have $d_X(i_1)=d_X(i_2)$. But my construction is very dependent of the choice of $i$. –  Asaf Karagila Feb 19 '13 at 23:11