# Partial order on cardinalities without the axiom of choice

Cardinality can still be defined without choice, e.g. as equivalence class of equipotent sets, see Defining cardinality in the absence of choice. Injections define partial order on cardinalities by the Cantor-Bernstein theorem, also without choice, and it seems to be a lattice because we can take unions and intersections. The ladder of alephs is formed the usual way, but there can also be side branches at each aleph produced by transfinite iteration of the power set operation (and many other branches).

What can be proved about the structure of this lattice in ZF, for example does every set inject into some power set iterate of an aleph? Are there alternatives to choice that make this lattice more tractable or give it desirable properties without collapsing it into alephs? References appreciated.

Well, we can prove that this is not a lattice.

For example, there are models where there are two cardinals that have no infimum. One easy example is that if $D$ is an infinite Dedekind-finite set, then $|D|$ and $\aleph_0$ are incomparable, but every finite $n$ is smaller than both.

The same idea works just as well with any cardinal whose Hartogs is a limit $\aleph$ (this can be arranged with $2^{\aleph_0}$ and $\aleph_\omega$ for example).

Here is a possible counterexample for the existence of a supremum for two cardinals. I haven't checked all the details, but it "feels" right (although long history of these things taught me not to trust these feelings).

Suppose that $S$ and $T$ are two disjoint, and incomparable Russell sets, namely each can be written as the union of disjoint pairs $S_n$ and $T_n$, such that no infinite family of pairs has a choice function (and it is consistent that two such sets exist). We observe that this implies that both $S$ and $T$ are Dedekind-finite sets, therefore their union is Dedekind-finite, and every subset is Dedekind-finite.

We define a sequence of sets, of strictly decreasing cardinality such that $|S|$ and $|T|$ are both smaller than all of them, and all these sets are smaller than $|S|+|T|$.

Let $A_n=S\cup\bigcup_{n\leq k} T_k$. Namely we take $S$ and we add less and less pairs from $T$. First of all, $|A_n|<|A_k|$ whenever $k<n$ because $A_n$ is a proper subset of $A_k$, and $A_0=S\cup T$. Therefore all these (except $A_0$) are strictly smaller than $|S|+|T|$. On the other hand, it is obvious why $|S|<|A_n|$ for all $n$, as for $T$, we have a bijection between the first $n$ pairs of $T$ and the first $n$ pairs of $S$, so we can use this bijection to extend the partial injection from $T$ into $A_n$.

Therefore we have that $S$ and $T$ are strictly smaller than all the $A_n$'s which in turn are strictly smaller than $S\cup T$ (except $n=0$).

(I haven't checked that there's no other possible supremum, but it seems more plausible than before, that's for sure.)

Similar tricks can be done with any two Dedekind-finite sets which are incomparable (otherwise the larger is the supremum). Just replace increasingly larger chunks of one by another. If there is no largest cardinal which can be embedded into both sets, then the process cannot halt, and you have a similar situation where their disjoint union is not the supremum.

What properties can we prove? We can prove that if the axiom of choice fails, then there are antichains of any finite size. We don't know to prove if it necessarily means that there are infinite antichains, though, but all the standard models we know where the axiom of choice fails have such infinite antichains (to the best of our knowledge).

What more can we say? We can show that given a model of $\sf ZFC$, every partial order in that model, and in fact the entire model itself, can be embedded into the cardinals of a larger model. This shows that we can say very little, if anything at all, on this "lattice" (which is not a lattice at all).

As for injecting every set into the power set of an ordinal, we know that it is consistently true, and that for every $n\in\omega$ there is a model where there is a set that cannot be injected into $n$-th power set of any ordinal. What about transfinite iterations? I know of at least one counterexample which will be part of my Ph.D. thesis, but I have the feeling that this is already known, at least to some extent.

You might find the following paper interesting:

John Truss, Convex sets of cardinals, Proc. London Math. Soc. (3) 27 (1973), 577--599.

• Is there at least a sup for every pair (I am thinking of cardinality of disjoint union)? Are there notes posted somewhere about this poset, or a book? Thank you. – Conifold Jun 17 '14 at 22:27
• Which poset? I'm not 100% sure about supremum either, to be honest. But that's something I'll have to think about more carefully. It is likely true. – Asaf Karagila Jun 17 '14 at 22:35
• My bad, it's not a set, but about order properties of cardinalities in ZF and its non-choice extensions. – Conifold Jun 17 '14 at 22:38
• Again, I'm not quite sure what you mean. You can find some theorems in Jech's The Axiom of Choice in Ch. 11; and a few in Herrlich's The Axiom of Choice, although they are not always as explicitly stated as you might want them to be (so you have to deduce them from given examples, but it is usually fairly easy to make these inferences). – Asaf Karagila Jun 17 '14 at 22:41
• There is also a paper by Truss about convex sets of cardinals which may interest you. – Asaf Karagila Jun 17 '14 at 22:42