3
$\begingroup$

Let $f:\mathbb{R}\to\mathbb{N}$ be onto. In ZF, no $g:\mathbb{N}\to\mathbb{R}$ s.t. $f(g(b))=b$ for all $b\in\mathbb{N}$ exists.

The above statement is from Goldrei, Classical Set Theory, p.104, exercise 5.2. The author states: "it can be shown that there is no way of constructing such a $g$ using the ZF axioms". More specifically, the author specifies that $f$ is an arbitrary function. Unfortunately, the author doesn't discuss this proof since it isn't exactly related to the material.

Would anyone have a reference on how one could do this proof, i.e., determine the difference of using choice and not using choice for this particular problem? Thank you very much!

EDIT: copy/paste of the statement following requests for clarification enter image description here

$\endgroup$
12
  • 4
    $\begingroup$ Does this answer your question? Right Inverse for Surjective Function $\endgroup$ Commented Aug 20, 2021 at 22:38
  • 1
    $\begingroup$ @José unfortunately I'm looking for a reference for the proof that one needs AC! Thank you very much for the reference however $\endgroup$
    – shintuku
    Commented Aug 20, 2021 at 22:41
  • 2
    $\begingroup$ For certain choices of $f$, such a $g$ can be constructed without AC. What exactly is Goldrei's statement? $\endgroup$
    – TonyK
    Commented Aug 20, 2021 at 22:41
  • 1
    $\begingroup$ (as an example of @TonyK's comment, let $f$ be the function which takes $r\in\mathbb{R}$ to $0$ if $r\in\mathbb{R}\setminus\mathbb{N}$ and takes $r$ to itself if $r\in\mathbb{N}$. then $f$ is onto, and the natural inclusion $g:\mathbb{N}\to\mathbb{R}$ satisfies $f\circ g=\operatorname{id}_\mathbb{N}$) $\endgroup$ Commented Aug 20, 2021 at 22:46
  • 1
    $\begingroup$ no problem! :) but the question as stated is still a bit imprecise; I think what you want to say is that it is consistent with ZF for there to exist a surjection $f:\mathbb{R}\to\mathbb{N}$ such that $f\circ g\neq\operatorname{id}_\mathbb{N}$ for any $g:\mathbb{N}\to\mathbb{R}$. this is different than the statement you've written, the wording of which seems to state that ZF proves that no such $g$ exists for any surjection $f:\mathbb{R}\to\mathbb{N}$, which is definitely not correct. $\endgroup$ Commented Aug 20, 2021 at 22:59

1 Answer 1

3
$\begingroup$

What you are asking can be phrased as "Suppose that we are given a countable family of subsets of the real line, does it admit a choice function?"

To see that this is equivalent, note that if $\{A_i\mid i\in\Bbb N\}$ is a family of sets, we can define $B_i = A_i\setminus\bigcup_{j<i}A_j$, discard the empty sets and reenumerate (so just as well assume none is empty), and define $f(r)=n+1$ if $r\in B_n$, and $f(r)=0$ if $r\notin\bigcup B_n$. Now, if $g$ is an inverse function, then $g\restriction\Bbb N\setminus\{0\}$ is a choice function from the $B_n$s which let us choose from the $A_n$s.

The other direction is simpler, I leave it to you as an exercise.

Now, you can't blame Goldrei for omitting this proof. It is complicated and requires both forcing and basic understanding of inner models and relative constructibility, or alternatively a deep dive into the inner working of forcing in the form of symmetric extensions.

Nevertheless, the very first proof that $\sf AC$ is not a theorem of $\sf ZF$, given by Cohen, shows that it is consistent that there is a subset, $A$, of $\Bbb R$ which is infinite but Dedekind-finite, that is to say, it has no countable subset. It is not hard to show that such subset must be densely ordered, so by scaling we may assume that it is dense in $\Bbb R$. Now simply consider $A_n=A\cap(-\infty,n)$.

If you are looking for a good reference, this is known as Cohen's first model; the Halpern–Levy model; the Cohen–Halpern–Levy model; the Cohen model; and more. Introductions to it exist in Jech's "The Axiom of Choice" and "Set Theory" books, as are in virtually any other book which contains a proof that $\sf ZF$ does not prove $\sf AC$.

$\endgroup$
6
  • $\begingroup$ Thank you very much for the extensive answer! $\endgroup$
    – shintuku
    Commented Aug 20, 2021 at 23:55
  • $\begingroup$ You're welcome. If you want to take a short overview, you can find it in my paper with Philipp Schlicht (which is also open access), dx.doi.org/10.1098/rspa.2019.0782, but you'd need to know forcing in order to follow it, which presumably is going beyond your current knowledge. $\endgroup$
    – Asaf Karagila
    Commented Aug 20, 2021 at 23:57
  • $\begingroup$ I'm slowly heading in that direction, so I will keep that reference saved! $\endgroup$
    – shintuku
    Commented Aug 21, 2021 at 0:01
  • $\begingroup$ This is a duplicate post, @Asaf. If you know that already, sorry, just trying to keep site protocols consistent for all users. $\endgroup$
    – amWhy
    Commented Aug 24, 2021 at 15:30
  • $\begingroup$ @amWhy: It's not a duplicate per se. It's not asking just why choice is needed and in what sense, but also for a reference. The suggested duplicate is a different question, and if you follow my activity (especially on the AC tag) you'd know that I'm the first to search and close as duplicates. $\endgroup$
    – Asaf Karagila
    Commented Aug 24, 2021 at 16:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .