First, here are some definition:

$A$ is finite set - there exists bijective function between $[n]=\{0,\ldots,n-1\}$ and $A$

$A$ is infinite set - $A$ not finite

$A$ is Dedekind infinite - there exists bijective function between $A$ and a proper subset of $A$

$A$ is Dedekind finite - $A$ is not Dedekind infinite

I learned that without assuming choice(or some weak version of choice) the order of cardinality(exists injective function from $A$ to $B$) is not connex; exists $A,B$ such that no $|A|\le |B|$ and $|B|\le |A|$.

When I asked, I was told that such $A,B$ are sets such that $|A|\ge|\Bbb N|$ and $B$ is Dedekind finite and infinite, this made me think for example of such $A,B$, but I couldn't think on set in the form of $B$.

Is there a simple example for such $A,B$? And how to prove that there is no one to one function from either direction?

  • $\begingroup$ Well, an example would disprove the axiom of choice, so you aren't going to find any explicit example in ZF... $\endgroup$ – Eric Wofsey May 29 '18 at 7:48

There are no "simple" examples. It is consistent with $\sf ZF$ that the axiom of choice holds, and therefore there are no incomparable cardinals.

The simplest example would be either of two options:

  1. Assume the axiom of choice fails, let $A$ be a set which cannot be well-ordered, then by Hartogs' theorem there is an ordinal $B$ such that $B$ cannot be mapped injectively into $A$. Moreover, since $A$ cannot be well-ordered and $B$ is an ordinal, $A$ cannot be mapped injectively into $B$ so $A$ and $B$ are incomparable.

    It is important to note that the failure of choice is not a "constructive thing". Just assuming choice fails will tell us nothing about the nature of this failure.

  2. We can construct models using forcing and symmetric extensions where there are Dedekind-finite sets, i.e., infinite sets which are incomparable with $\Bbb N$. The canonical example is Cohen's first model, where such Dedekind-finite set can be found as a set of real numbers.

    This is a fairly involved and technical construction, though. So I am not going to go into details.

  • $\begingroup$ The second of these is a particular case of the first, of course. But interesting enough that $B$ may be $\omega$. $\endgroup$ – hmakholm left over Monica May 29 '18 at 8:11
  • $\begingroup$ Henning, indeed so. The OP talks about infinite Dedekind-finite sets, which is why I brought the example up. $\endgroup$ – Asaf Karagila May 29 '18 at 8:12
  • $\begingroup$ What do you mean in Cohen's first model? I didn't find it, can you send a link to a source to this forcing? $\endgroup$ – ℋolo May 29 '18 at 8:28
  • $\begingroup$ @Holo: It's in pretty much any introduction to forcing that has a section about the failure of the axiom of choice. In Jech's book you can find it at the end of chapter 14, for example. Or in his small book called "The Axiom of Choice" you can find it in chapter 5. $\endgroup$ – Asaf Karagila May 29 '18 at 9:15

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.