4
$\begingroup$

Cantor used the notion of an "injection" to formalize the size of two sets: A is "smaller" than B if A injects into B.

Simply put, the question is - how does this situation change if we use surjections instead of injections in our notion of size? And if we use "surjections both ways" to define equivalence classes rather than "injections both ways?"

If we are working in ZFC, these should be equivalent. Without AC, I don't think they will be. Basically, I am wondering if surjections are "better behaved" than injections if there is no AC. For example, without AC, the reals don't even inject into the ordinals, but do the ordinals surject onto the reals?

To be really clear, I think there is some added subtlety in that without AC you don't necessarily get the "dual CBS theorem" - that surjections from sets $A \to B$ and $B \to A$ give you a bijection $A \leftrightarrow B$. In other words, without AC, the existence of a bijection can be stronger than the existence of two surjections, so that the latter should yield coarser equivalence classes than the former - which is what I am asking about.

So summarizing, let's define the "surjective cardinals" as equivalence classes of sets that mutually surject onto one another (or the least-rank representative of each such class). Then I am curious about basic questions like (all assuming no $AC$):

  • What is the general structure of these "surjective cardinals" without AC?
  • Do the surjective cardinals have any nice ordering properties wrt surjections (are they linearly ordered, or well-ordered, or ...)?
  • Are the ordinals "surjectively larger" than the reals, without AC?
  • If so, is there some least ordinal that is surjectively larger than the reals? (Regardless of if we know which one it is)
  • Is there a corresponding notion of CH for surjective cardinals?

Are these well-studied? Does anyone have any references?

$\endgroup$
  • 2
    $\begingroup$ A trivial but not necessarily idiotic point is that the surjective cardinal (may I propose the term "cardoutal"?) of the empty set is incomparable with that of any other set, since the existence of a surjection $\varnothing\to X$ or $X\to\varnothing$ both imply $X=\varnothing$. $\endgroup$ – Gro-Tsen Jan 30 '19 at 6:37
  • $\begingroup$ Also worth nothing: if $Y$ is well-orderable, the existence of a surjection $f\colon Y\to X$ implies the existence of an injection $X\to Y$ (take each $x\in X$ to the smallest element of $f^{-1}(x)$). $\endgroup$ – Gro-Tsen Jan 30 '19 at 6:40
  • $\begingroup$ I have written many words on these questions. I might write a few more later today. $\endgroup$ – Asaf Karagila Jan 30 '19 at 7:56
  • 2
    $\begingroup$ @Gro-Tsen one can fix the $\emptyset$ issue by declaring that $X$ is greater than $Y$ if some subset of $X$ has a surjection onto $Y$. (If $Y$ is non-empty, it's choice-free equivalent to the existence of a surjection of $X$ onto $Y$.) $\endgroup$ – YCor Jan 30 '19 at 15:01
7
$\begingroup$

It is a studied concept. I'm not sure what it's called but it's often defined with the empty set as a special case to deal with the issue Gro-Tsen mentioned. I've seen it notated $A \leq^\ast B$ to distinguish it from the ordinary ordering. I get the impression that it's generally more poorly behaved than the injective ordering.

Any question about the ordering of cardinals without AC is extremely sensitive to the particulars of the particular model of set theory in question so I don't know if there can be a good answer to your first bullet point without some serious specification (such as: assuming large cardinals in $V$ what does the $\leq^\ast$ order look like in $L(\mathbb{R})$?).

With regards to your second bullet point there is a well-known result that under ZF if the cardinals are linearly ordered (under the ordinary injective ordering) then AC holds. I heavily suspect the same is true for the surjective ordering, but I have to think about it. I also heavily suspect that $\leq^\ast$ isn't necessarily well-founded under ZF alone. EDIT: Assume that $\leq^\ast$ is a linear ordering on the cardinals. For any set $A$, ZF proves that there is a least well-ordered cardinal $\aleph^\ast(A)$ such that $\aleph^\ast(A) \not\leq^\ast A$. Since $\leq^\ast$ is a linear order we must have $A\leq^\ast\aleph^\ast(A)$, which implies that $A$ can be well-ordered. So every set can be well-ordered and choice holds.

As Gro-Tsen also alluded to if there were a surjection of an ordinal onto the reals, then the reals would be well-orderable. Since the reals can fail to be well-orderable in ZF there can fail to be a surjection of an ordinal onto the reals. There is something that is studied a lot which is the least well-ordered cardinal that the reals do not surject onto. This is called $\Theta$ and is discussed in this question. One thing to note is that it's very large.

CH becomes trickier to state in the absence of choice. I'm not sure what people consider to be the 'correct' formalization.

Here are some relatively basic facts regarding this relationship that I have written down in some notes. (I believe these are from the book 'Combinatorial Set Theory' by Halbeisen.)

  • $A \leq B \Rightarrow A \leq^\ast B$
  • $2^A \not\leq ^\ast A$ (analog of Cantor's theorem).
  • $A \leq^\ast B \Rightarrow 2^A \leq 2^B$
  • $A\leq^\ast \aleph\Rightarrow A \leq \aleph$, where $\aleph$ is any aleph number (i.e. a well-orderable cardinality, this is Gro-Tsen's comment).
  • If $A$ is infinite, then $\aleph(A)\leq^\ast 2^{A^2}$, where $\aleph(A)$ is the Hartogs number of $A$, the least aleph number that does not inject into $A$.
  • $\aleph_1 \leq ^\ast 2^{\aleph_0}$, whereas $\aleph_1 \leq 2^{\aleph_0}$ is independent of ZF.

And finally my favorite is that while with some work you can prove in ZF that $2^A\leq A^2 \Rightarrow A \leq 4$, it is unkown whether or not $2^A \leq^\ast A^2\Rightarrow A\leq 4$.

$\endgroup$
  • $\begingroup$ The notation $\Theta$ usually means the least ordinal that the power set does not surject onto. I think $\aleph^*$ is a better choice of notation. (I named those Lindenbaum numbers, since Lindenbaum proved the analogue theorem for $<*$ of Hartogs.) $\endgroup$ – Asaf Karagila Jan 30 '19 at 8:05
  • $\begingroup$ Ah yes that is better notation. $\endgroup$ – James Hanson Jan 30 '19 at 8:09
  • $\begingroup$ Note that $2^A \not\leq ^\ast A$ is in fact what the diagonal argument shows directly. $\endgroup$ – David Roberts Apr 26 '19 at 4:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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