What is an example of two sets which cannot be compared?

In set theory, if we do not assume the Axiom of Choice, we cannot prove the Trichotomy Law between cardinals. That is, we cannot prove that for any two sets, there exists an injection from one to the other. But this raises the question: what is an example of a pair of sets between which there does not exist an injection?

Solution 1:

If we could give an explicit example of sets for which we could prove the non-existence of such injections, the axiom of choice would be false. However, there are models of $\mathsf{ZF}$ without the axiom of choice in which there are Dedekind finite sets that are not finite. If $X$ is such a set, there is no injection from $X$ to $\Bbb N$ or from $\Bbb N$ to $X$.

Specifically, $X$ has the property that there is no injection from $X$ properly into $X$. This is easily shown to be equivalent to the property that there is no injection from $\Bbb N$ to $X$. If there were an injection $f:X\to\Bbb N$, the fact that $X$ is not finite means that $f[X]$ would be an infinite subset of $\Bbb N$, and it would then be a straightforward matter recursively to construct a bijection from $\Bbb N$ to $X$. Since $X$ is Dedekind finite, no such bijection exists.

Solution 2:

Brian's answer addresses the "strong" version of your question: asking for an explicit counterexample. If, on the other hand, all you want is an example of a pair of sets which might form a counterexample to Trichotomy, it turns out we can do this! The easiest is probably the following: it is undecidable in ZF whether there is an injection in either direction between $\mathbb{R}$ and $\omega_1$ (the set of countable ordinals).

It is provable in ZF that $\mathbb{R}$ surjects onto $\omega_1$ (every countable ordinal can be coded by a real in a natural way), but this surjection cannot (in ZF) be given a right inverse (there is no easy way to pick a canonical code for a given ordinal).

Maybe a more interesting answer can be given by considering larger ordinals: in ZF, we cannot prove the existence of a surjection or injection in either direction between $\omega_2$ and $\mathbb{R}$.

EDIT: Technically, that last sentence is true in ZFC as well. What I should really say is, "It is consistent with ZF that there are no injections or surjections between $\omega_2$ and $\mathbb{R}$."

Solution 3:

There is no example in any good and reasonable sense of the word.

Given any two sets $A$ and $B$, there is an extension of the universe, to a larger universe of $\sf ZF$, in which both $A$ and $B$ are countable, and therefore can be compared.

You might want to talk about "definitions" rather than concrete sets. But even that can be difficult. Any reasonable definition for a set which involves bounding the rank of that set (so you can't say something like "the least $V_\alpha$ that cannot be well-ordered" in your definition), is going to fail. The axiom of choice consistently holds up to whatever level you want, and fails in however way you want it to fail afterwards.

The negation of the axiom of choice teaches us nothing about where the axiom of choice fails, or how it fails.

If you want a "concrete" example for two sets, then you can say the following, we know that the axiom of choice fails if and only if there exists some ordinal $\alpha$ such that $\mathcal P(\alpha)$ cannot be well-ordered. Take that power set of $\alpha$, and let $\kappa$ be the least ordinal that cannot be injected into $\mathcal P(\alpha)$. Then $\mathcal P(\alpha)$ and $\kappa$ cannot be compared.

But is this example really helpful? Did you learn anything meaningful from it? No. I haven't told you what is $\alpha$ or what is $\kappa$. And I can't tell you that. Because all you've told me is that the axiom of choice fails. You haven't told me how it fails. Does countable choice holds? Perhaps Dependent Choice holds up to the least measurable cardinal holds? We don't know. We can't know. Unless we assume more about this failure.