$A,B$ sets without 1-1 function either way

Question

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?

Answer 1

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.