# [FOM] Cardinality in the absence of AC

Noah Schweber schweber at berkeley.edu
Wed Jun 5 23:49:50 EDT 2019

```Hello Tim,

Unless I'm missing something the answer is no, that situation is not
possible - and this is provable in (much less than) ZF alone.

Let f: B->C be injective and g: A->C be surjective, fix b in B and consider
the map h from A to B given by:

- If g(a) is in the range of f, then h(a) is f^{-1}(g(a)) (which is
well-defined since f is injective).

- Otherwise h(a)=b.

This seems to be a surjection from A to B (since f is defined on all of B).

- Noah

On Wed, Jun 5, 2019 at 10:18 PM Timothy Y. Chow <tchow at math.princeton.edu>
wrote:

> Let us work in ZF + "all subsets of reals are Lebesgue measurable" (or
> ZF+LM for short).
>
> Is the following situation possible?
>
> We have three sets, A, B, and C.  There exists an injection from A to B,
> and an injection from B to C.  There *does not exist* a surjection from A
> to B, and there *does not exist* a surjection from B to C.  Nevertheless,
> there exists a surjection from A to C.
>
> ---
>
> I was led to ask this question after reading an expository article by Alan
> Taylor and Stan Wagon in the April 2019 issue of the American Mathematical
> Monthly, about the fact that in ZF one can prove the existence of an
> injection from R to R/Q and in ZF+LM one can prove the nonexistence of an
> injection from R/Q to R.  They interpret this fact as saying that in ZF+LM
> one can prove that there are "more" elements in R/Q than in R or that R/Q
> "outnumbers" R.
>
> It occurred to me that another interpretation could be that what is wrong
> is the definition of "|A| < |B|" as "there is an injection from A to B but
> no bijection from A to B."  Perhaps it is better to define "|A| < |B|" as
> "there is an injection from A to B but no surjection from A to B."  I
> believe that in the absence of choice, these two definitions are not
> equivalent.
>
> What is not immediately clear to me is whether the "<" relation as I have
> proposed it is transitive.  Hence my question.
>
> Tim
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> https://cs.nyu.edu/mailman/listinfo/fom
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20190605/decec916/attachment.html>
```