MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$?

share|cite|improve this question
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…. 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 Schweber Feb 19 '13 at 3:57
Different but related question:… – 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
up vote 13 down vote accepted

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.

share|cite|improve this answer
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 Schweber 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].

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.