5
$\begingroup$

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.

$\endgroup$

2 Answers 2

4
$\begingroup$

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}$.

$\endgroup$
4
  • $\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$ Commented May 4, 2015 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
    Commented May 4, 2015 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
    Commented May 4, 2015 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
    Commented May 4, 2015 at 20:37
3
$\begingroup$

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.

$\endgroup$
11
  • $\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
    Commented May 4, 2015 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$ Commented May 4, 2015 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
    Commented May 4, 2015 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
    Commented May 4, 2015 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$ Commented May 4, 2015 at 19:22

You must log in to answer this question.

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