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?


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}$."

| cite | improve this answer | |
  • $\begingroup$ Is there something like R and R/Q that does not use big ordinals but no size-comparing map (injection or surjection in either direction) is definable in ZF? $\endgroup$ – zyx May 12 '16 at 22:54
  • $\begingroup$ @zyx To the best of my knowledge, no. And note that of course $\mathbb{R}$ surjects onto and (surprisingly!) injects into $\mathbb{R}/\mathbb{Q}$, provably in ZF. $\endgroup$ – Noah Schweber May 12 '16 at 23:02
  • $\begingroup$ thanks. For R/Q the other direction has no map in ZF, which gives some hope for a bidirectional concrete example. $\endgroup$ – zyx May 13 '16 at 0:24

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.

| cite | improve this answer | |
  • $\begingroup$ isn't $f(x)=x$ always an injection $X\to X$? $\endgroup$ – Ittay Weiss May 8 '16 at 23:17
  • $\begingroup$ @Ittay: Yep. I forgot to add the important qualification: it has to be properly into $X$. Fixed now; thanks. $\endgroup$ – Brian M. Scott May 8 '16 at 23:19
  • $\begingroup$ Is it not possible to construct an example, using some steps that assume the axiom of choice is false? $\endgroup$ – user253751 May 9 '16 at 5:01
  • $\begingroup$ @immibis No, not really. Just knowing that AC fails tells you nothing about where it fails - for example, given a model $V\models ZFC$ and a cardinal $\kappa\in Card^V$, we can get a (symmetric submodel of a forcing) extension $W$ with the same ordinals and cardinals as $V$, where the first failure of choice has rank $>\kappa$. So there's no "canary in the mineshaft" we might hope for. $\endgroup$ – Noah Schweber May 9 '16 at 5:52
  • $\begingroup$ @NoahSchweber Are you saying there's no known simple model that has a counter-example of C, or that we can't find a counter-example for all such models? $\endgroup$ – user253751 May 9 '16 at 6:23

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.

| cite | improve this answer | |

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.