Take the 2-minute tour ×

We denote by $\frak p\le q$ the abbreviation that there is $f:\frak p\to q$ which is injective, and by $\frak p\le^\ast q$ we abbreviate that there is a surjection from $\frak q$ onto $\frak p$.

If $X$ is a set in a universe of ZF, denote by $H(X)=\min\lbrace\alpha\mid\alpha\nleq X\rbrace$ known as The Hartog number of $X$. It is clear that $H(X)\nleq X$.

Under the axiom of choice $X\leq Y\iff X\leq^\ast Y$, however without the axiom of choice the $\leq^\ast$ order can behave quite strangely. For example, it is possible that $\omega_1\nleq2^\omega$, but it is always true that $\omega_1\leq^\ast2^\omega$. This may occur when the continuum is a countable union of countable sets, or if we are in a Solovay-like model.

Monro showed in [1] that it is consistent to have for every $\kappa$ an infinite set $p$ such $H(p)=\omega$ and $\kappa\leq^\ast p$.

In those two instances we have examples where the axiom of choice fails, and $H(x)\leq^\ast x$. If we do not wish to add large cardinal into the mix both the examples above are such that the axiom of countable choice already fails in.


  1. How much choice can we have while still finding sets with the property $H(x)\leq^\ast x$?

  2. How consistent is this property with the different type of weak choice principles (e.g. if it is consistent with DC/AC/W for some $\kappa$, would it also be consistent with BPI and its relatives)?


  1. G.P. Monro, Independence results concerning Dedekind finite sets. Journal of the Australian Mathematical Society (Series A) (1975), 19 : pp 35-46.
share|improve this question

3 Answers 3

Since you specifically asked about the Boolean prime ideal theorem, let me point out that BPI holds in the basic Cohen model (that's how Halpern and Levy showed that BPI doesn't imply AC). In this model, the set $A$ of explicitly added Cohen reals is a Dedekind-finite dense subset of the reals. Since it's Dedekind-finite (but not really finite), $H(A)=\omega$. Since it's dense in $\mathbb R$, it maps onto $\mathbb Z$ (by rounding to the nearest integer) and thus also maps onto $\omega$.

share|improve this answer
Ah, of course. It can be shown in many other equivalent ways too (I can come up with at least three claims that will guarantee $\leq^\ast$, none of which is as constructive as yours :-)). Thanks! –  Asaf Karagila Jan 7 '12 at 20:52

Under AD, one can have DC plus there is no $\omega_1$-sequence of distinct reals. So this is a case where one can have DC, plus $\omega_1\not\leq \mathbb{R}$, but as you noted, there is always a surjection from $\mathbb{R}$ onto $\omega_1$, since every countable ordinal is coded by a real, and so $\omega_1\leq^\ast\mathbb{R}$. So this is a case where $H(\mathbb{R})=\omega_1\leq^\ast\mathbb{R}$ and DC holds. (I don't think you need full AD to get this situation.)

Do you want more choice than DC? For which choice principle specifically are you aiming?

Perhaps one should look at the model $L(V_{\lambda+1})$, the higher analogue of $L(\mathbb{R})$, to get a greater degree of choice, but by analogy one might still expect that $H(V_{\lambda+1})=\lambda^+\leq^\ast V_{\lambda+1}$.

share|improve this answer
I am wondering whether or not in ZF it is consistent to have $H(X)\le^\ast x$ coupled with higher choice principles than $DC$. I am not sure why $H(V_{\lambda+1})=\lambda$, but it would seem to me that for such results one would also have to assume some large cardinals live in the background? –  Asaf Karagila Jan 7 '12 at 18:52
Sorry, I meant $\lambda^+$, and have edited. –  Joel David Hamkins Jan 7 '12 at 18:55
And yes, the large cardinal I meant was $j:L(V_{\lambda+1})\to L(V_{\lambda+1})$, one of the very strongest large cardinal axioms. –  Joel David Hamkins Jan 7 '12 at 18:57
Joel, I just saw this. DC and no $\omega_1$-sequence of reals is equiconsistent with an inaccessible cardinal. One direction follows from considering Solovay's model. For the other, one notices that $\omega_1>\omega_1^{L[r]}$ for any real $r$, and therefore $\omega_1$ is inaccessible in $L$ (and in all $L[r]$). –  Andres Caicedo Jun 19 '12 at 0:21
up vote 4 down vote accepted

I originally posted this question in hope that someone else knew of a reference for an answer, however it seemed to me that indeed the best way is to solve this on my own. I tried to imitate Monro's proof, to a certain extent, and I believe that I have succeeded: $\renewcommand{\Dom}{\operatorname{Dom}}\renewcommand{\Htg}{\operatorname{Htg}}$

Let $M$ be a model of ZFC, $\kappa$ is an uncountable regular. Consider the notion of forcing $(P,\le)$ where $p\in P$ is a function from a subset of $\kappa\times\kappa$ into $2$, and $|\Dom(p)|<\kappa$.

Let $M[G]$ be a generic extension, $G_i = \lbrace\alpha<\kappa\mid\exists p\in G: p(i,\alpha)=1\rbrace$ and $H=\lbrace G_i\mid i<\kappa\rbrace$. We give them "canonical" names, $\dot G_i = \lbrace\langle p,\check n\rangle \mid p(i,n)=1\rbrace$ and $\dot H=\lbrace\langle 1, \dot G_i\rangle\mid i < \kappa\rbrace$.

We now proceed to define the symmetric model. If $\pi$ is a permutation of $\kappa$ we can think of $\pi$ as an automorphism of $P$ by: $$\pi p =\lbrace \langle\pi i,\alpha,j\rangle\mid \langle i,\alpha,j\rangle\in p\rbrace$$

Let $\mathscr G$ be the permutation group of these automorphisms. Let the subgroups filter be generated by countable support, that is $\dot f$ is a symmetric name if and only if there is a countable set of conditions such that whenever they are fixed pointwise, $\dot f$ is fixed.

We note two things:

  • For $\pi$ fixes (pointwise) countably many conditions then only $<\kappa$ many points must be fixed by $\pi$.
  • For $i<\kappa$ we have $\pi\dot G_i = \dot G_{\pi i}$, so all the $\dot G_i$ are symmetric and trivially hereditarily symmetric. From this follows that $\dot H$ is also hereditarily symmetric.

Let $N$ be the symmetric model, we will show the following:

  1. $H\in N$, which is obvious since $\pi(\dot G_i)=\dot G_{\pi i}$ so $\pi(\dot H)=\dot H$ for every $\pi\in\mathscr G$.
  2. $N\models DC$:

    Let $S\in N$ be a non-empty set and $R\in N$ a binary relation defined on all elements of $S$. In $M[G]$ we have a function which witnesses $DC$. For every $n\in\omega$ we have $n,f(n)\in N$ therefore $\langle n,f(n)\rangle\in N$. Each ordered pair has a countable support, and the union of this countable collection is countable (in $M$) therefore supports $\dot f$ as a symmetric name, as wanted.

  3. $N\models\Htg(H)=\aleph_1$:

    Assume towards contradiction that $\dot f$ is a symmetric name such that for some $p_0\in G$ we have $p_0\Vdash\dot f:\check\omega_1\to H\text{ injective}$. Let $E$ be a support for $\dot f$. There exists $i<\kappa$ that for every $\alpha$ and $p\in E$ the pair $\langle i,\alpha\rangle\notin\Dom(p)$.

    Let $p\le p_0$ be an extension of $p$ such that for some $\alpha<\omega_1$ we have: $$p\Vdash \dot f(\check\alpha)=\dot G_i$$ We choose now $j<\kappa$ which for every $\alpha$ and $q\in E\cup\lbrace p\rbrace$ we have $\langle j,\alpha\rangle\notin\Dom(q)$, and define $\pi$ to be induced by the 2-cycle: $(i\ j)$.

    We have that $\pi$ fixes $E$ pointwise, since neither $i$ nor $j$ appear in relevant coordinates in the conditions of $E$; we have that $\pi p$ and $p$ are compatible since if $x$ is in the shared domains then $i$ and $j$ do not appear in relevant positions and so the value given to $x$ by the two conditions is similar. Lastly $\pi p\Vdash (\pi\dot f)(\pi\check\alpha)=\pi(G_i)$, since $\pi$ fixes $\dot f$ and $\check\alpha$ we have: $$\pi p\Vdash\dot f(\check\alpha)=\dot G_{\pi i}$$

    Thus we arrive the wanted contradiction since $\pi p\cup p$ extends $p_0$, but it contradicts $p_0$ by forcing that $\dot f$ is not a function.

  4. $N\models\kappa\leq^\ast H$:

    We define from $f:H\to\kappa$ by $f(G_i) = \min\{\beta\mid\beta\notin G_i\}$. Since $G_i\in N$ for all $i$ and $H\in N$ we have that indeed $f\in N$. Now we only have to show that it is onto $\kappa$, this is a simple genericity argument:

    Given $\beta<\kappa$, and a condition $p\in P$ there exists $i<\kappa$ such that $\langle i,\alpha\rangle\notin\Dom(p)$ for all $\alpha$. Therefore $p\cup\lbrace\langle i,\alpha,1\rangle\mid\alpha<\beta\rbrace\cup\lbrace\langle i,\beta,0\rangle\rbrace\le p$ as wanted. By genericity there is some $i<\kappa$ such that $f(G_i)=\beta$.

In this model $N$ described above we have $DC$ therefore we have no infinite Dedekind finite sets, however we have a non-well orderable set which can be mapped onto an ordinal (possibly) much higher than its Hartog number. I suspect that this easily generalized to higher cardinalities as well.

share|improve this answer

Your Answer


