It is easy to form in ZF, for each real $a$, a "canonical" Cauchy sequence that converges to $a$. For example, one can take the sequence of finite initial segments of the decimal expansion of $a$, being careful when $a$ is a base-10 rational to pick one of the two decimal expansions explicitly.

But what if we are given a set of Cauchy sequences of rationals, all converging to the same real. The set might not contain all the Cauchy sequences for that real. How hard is it to pick a "canonical" representative from the sequences that are in the set?

To make this question precise: consider a family of sets $C$ so that each $X \in C$ is a set of Cauchy sequences of rationals that all converge to the same real $a(X)$. Note that $X$ is not required to have the entire set of Cauchy sequences for $a(X)$. Does ZF prove the existence of a choice function for each family $C$ of this kind?

There are two aspects of Cauchy sequences that make this problem interesting. First, every infinite subsequence of a Cauchy sequence is again a Cauchy sequence converging to the same real. So we cannot hope for a "minimal" sequence. Also, we may prepend any finite sequence to a Cauchy sequence to yield a new Cauchy sequence converging to the same real. So we cannot hope for a "maximal" sequence. Cauchy sequences are very slippery in this way.

Dedekind cuts behave differently: once we specify whether cuts for rationals can have a maximum element, we have a unique Dedekind cut for each real, whereas we always have infinitely many Cauchy sequences.

I have a vague memory of encountering something similar to this question in the past, but I cannot remember any details. It also seems to have a flavor related to Borel equivalence relations, although this question is not written in that way.


Let me take Lord_Farin's answer, and crank it all the way to $2^{\aleph_0}$.

Suppose that we could have chosen from any family of Cauchy sequences. Fix for each real number a canonical Cauchy sequence of rationals $r_n$ which is strictly increasing. This is of course doable without choice.

Now suppose that $A_r\subseteq 2^\omega\setminus 2^{<\omega}$ is non-empty for each $r\in\Bbb R$, then consider $C_r=\{\langle r_n\mid a_n\neq 0\rangle\mid\langle a_n\rangle\in A_r\}$. Namely we encode each $a\in A_r$ as a subsequence of $r_n$, with the assumption that $a$ is not eventually $0$.

By the assumption there will be a choice from each $C_r$, and then we can easily decode this into a choice from $A_r$. So we have proved the axiom of choice for families of size $\leq2^{\aleph_0}$ of sets of reals. And of course we cannot even prove choice for countable families of sets of reals in $\sf ZF$ itself.

| cite | improve this answer | |
  • $\begingroup$ There might be some minor corrections to this idea, but I need to write an exercise, and it's getting late. So I'll address them once that part of the evening is over! $\endgroup$ – Asaf Karagila May 4 '15 at 18:25
  • 2
    $\begingroup$ I don't follow yet; does this give back a Cauchy sequence that was in the original set of Cauchy sequences, which may not be the full equivalence class? $\endgroup$ – Carl Mummert May 4 '15 at 18:38
  • $\begingroup$ Oh. I sort of missed that "subsets of equivalence classes" part. No, I don't see at all why there can be canonical choices for subsets of equivalence classes. I answered indeed for "choice for the equivalence classes". Should I delete this answer? $\endgroup$ – Asaf Karagila May 4 '15 at 18:44
  • 1
    $\begingroup$ All better. I hope. Now I can finally quell my mind and write that exercise about definable truth predicates in $\Bbb N$. :-) $\endgroup$ – Asaf Karagila May 4 '15 at 19:05
  • 1
    $\begingroup$ No, this won't work. Suppose $C=\{f_1,f_2,f_3,\ldots\}$ where $$f_k(m)=\begin{cases} 0 & m<k \\ 1 & \text{otherwise}\end{cases}$$ and use an enumeration of $\mathbb Q$ where $0$ comes before $1$. Then your $\bigcap C_n$ is empty! $\endgroup$ – hmakholm left over Monica May 4 '15 at 19:22

Such a choice mechanism would translate to a canonical choice for a function $\Bbb N \to \Bbb N_{>0}$ from a given set $S$ of such functions. If I'm not mistaken, this is some nontrivial choice principle (and if I am, please do correct me).

Given $f: \Bbb N \to \Bbb N_{>0}$, define: $$b_f (n) = \begin{cases}2^{-k} &: n = \sum\limits_{i=0}^k f(i) \\0&: \text{otherwise}\end{cases}$$

Now define $s_f(n) = \sum\limits_{i=0}^n b_f(i)$. Then for all $f$: $$\lim_{n\to\infty} s_f(n) = 2$$ and $f \leftrightarrow s_f$ is a bijective correspondence. Hence a choice function for each set $\{s_f: f \in S\}$ amounts to a choice function for each $S \subseteq (\Bbb N_{>0})^{\Bbb N}$.

By defining, for $f: \Bbb N \to 2$: $$b_f(n) = \begin{cases}2^{-k} &: n = k + \sum\limits_{i=0}^k f(i) \\0&: \text{otherwise}\end{cases}$$ the argument seems to carry over to $2^{\Bbb N}$.

| cite | improve this answer | |
  • $\begingroup$ I believe the correspondence here is correct (and $\mathbb{N} \to \mathbb{N}_{>0}$ is in effective bijection with $\mathbb{N} \to \mathbb{N}$ via the math $T(f)(x) = f(x) - 1$. So the argument carries over to $\mathbb{N}^\mathbb{N}$. But then the argument in Asaf's answer seems to apply equally well, which leads to a fact I had not realized, which is that ZF proves choice for families of subsets of $\mathbb{N}^\mathbb{N}$. (I think this answer is very relevant, by the way; +1) $\endgroup$ – Carl Mummert May 4 '15 at 19:11
  • $\begingroup$ @Carl I was also straining my mind to see the possible flaw in Asaf's answer, but it seems fine. Thus, we seem to have proven choice for subsets of $\Bbb N^{\Bbb N}$ :). $\endgroup$ – Lord_Farin May 4 '15 at 19:15
  • $\begingroup$ So you translate a set functions into Cauchy sequences approaching $2$. I'm not sure this would be an issue. But I do agree that given a countable collection of sets of functions, translating each to a set of Cauchy sequences approaching $n$; then being able to choose would prove at least countable choice for sets of reals, which we know is impossible to prove in $\sf ZF$. $\endgroup$ – Asaf Karagila May 4 '15 at 20:35
  • $\begingroup$ @Carl: I originally had a hunch that this would be unprovable. But I managed to convince myself that it can be done. I blame the time stress that I needed to write an exercise! :-) $\endgroup$ – Asaf Karagila May 4 '15 at 20:37

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.