## Why is there no Borel function mapping every countable set of reals outside itself?

A choice function maps every set (in its domain) to an element of itself. This question concerns existence of an anti-choice function defined on the family of countable sets of reals. In an answer to a question about uncountability proofs it was suggested that while Cantor's diagonal method furnishes a Borel function mapping each countable sequence $S$ of real numbers to a number not in the seqence, the same is not true for countable sets of reals. This seems surprising (but believable) to me and an important insight, if true. But why is it true? Put more provocatively (if this is fair, if not explain it as stated)

Let $\mathcal{C}$ be the family of countable subsets of $\mathbb{R}$ . Is it the case that for every Borel function $f:\mathcal{C} \rightarrow \mathbb{R}$ there is an $X \in \mathcal{C}$ such that $f(X) \in X$?

-
What is the topology on $\mathcal{C}$? (A function $f:\mathcal{C}\to\mathbb{R}$ being Borel depends of course on the topology). From the suggestion that motivated your post, it seems the relevant topology comes from the space of sequences, after identifying sequences which can be obtained from each other from permutation. I guess for sequences we are looking at the product topology? – Pablo Shmerkin Nov 24 2010 at 3:20
I freely admit that part of my question is "what does that claim mean?" (but also in what sense is it true and why?). Now I am intrigued what that topology on $\mathcal{C}$ would be! But one can sidestep the issue by saying Is it the case that for every $f:\mathcal{C} \rightarrow \mathbb{R}$ whose induced (permutation invariant) map on sequences is Borel...etc. For me, "Borel" is standing in for "nice". There is a nice constructive, proof, not needing the axiom of choice that any sequence of reals omits a real. Is the same fact for countable sets of reals much less concrete? – Aaron Meyerowitz Nov 24 2010 at 4:01
I do not think you can give a standard Borel structure to the space of countable sets of reals. I'll expand this as an answer (since there may be some interest to it) hopefully tonight when I ought to find some time. – Andres Caicedo Nov 24 2010 at 17:03
This is a special case of Friedman's so-called "Borel diagonalization theorem" for Borel equivalence relations. There is a proof by Harrington that uses Borel determinacy and effective descriptive set theory which can be found in Su Gao's "Invariant Descriptive Set Theory" Theorem 8.3.5 – Robin Tucker-Drob Nov 25 2010 at 19:41
@Robin : I haven't received my copy of Su's book. How do you like it? – Andres Caicedo Dec 1 2010 at 12:54
show 1 more comment

The initial function you mention is the diagonalizing function $d:\mathbb{R}^\omega\to\mathbb{R}$, for which one ensures that $z=d(x_0,x_1,\ldots)$ is distinct from every $x_n$ simply by making the $n$-th digit of $z$ different from the $n$-th digit of $x_n$ in some regular way. Since the graph of this function is arithmetically definable (needing to look only at the individual digits of the input and output), it follows that $d$ is a Borel function.

The point of your question, however, is that this function is not well-defined on different enumerations of the same set---the resulting diagonal value will be different if you rearrange the input. What would be desired is a function $f:\mathbb{R}^\omega\to\mathbb{R}$ such that always $f(x_0,x_1,\ldots)\neq x_n$, but for which $f$ gives the same value for different enumerations of the same countable set. Unfortunately, there is no such function that is Borel.

Theorem. There is no Borel function $f:\mathbb{R}^\omega\to\mathbb{R}$ such that

• $f(x_0,x_1,\ldots)\neq x_n$ for every sequence $\vec x$ and index $n$, and
• $f(x_0,x_1,\ldots)=f(y_0,y_1,\ldots)$, whenever $\{\ x_0,x_1,\ldots\ \}=\{\ y_0,y_1,\ldots\ \}$.

Proof. The nonexistence of such a function is closely related in spirit, in the context of Borel equivalence relation theory, to the impossibility of a Borel reduction from the equivalence relation $E_{set}$ to $=$, and the argument below belongs to that subject. The argument will use set-theoretic forcing, and is an instance where forcing is used in order to make a conclusion about the ground model $V$, rather than to prove an independence result.

To begin, suppose that $f$ is a Borel function with the two properties. Let $\mathbb{P}=\text{Coll}(\omega,\mathbb{R})$ be the forcing to collapse $\mathbb{R}$ to $\omega$. That is, conditions in $\mathbb{P}$ are finite sequences of reals, ordered by end-extension. The generic object will be a countable enumeration consisting of all the reals of the ground model $V$. Let $g$ and $h$ be mutually $V$-generic for $\mathbb{P}$, and consider the corresponding forcing extensions $V[g]$, $V[h]$ and their common extension $V[g][h]$. Since $f$ was a Borel function, it has a Borel code that may be re-interpreted in any of these universes. Furthermore, the assertion that $f$ has the stated features is a $\Pi^1_1$ statement about this Borel code, and hence absolute between $V$ and these larger universes. That is, the re-interpreted function $f$ continues to have the desired properties in $V[g][h]$. Since $g$ and $h$ both enumerate the same set $\mathbb{R}^V$, it follows that $f(g)=f(h)$ in $V[g][h]$. In particular, the value $z=f(g)=f(h)$ is in both $V[g]$ and $V[h]$. But since $g$ and $h$ are mutually generic, it follows that $V[g]\cap V[h]=V$, and so $z\in V$. But this contradicts the fact that $f(g)$ should be a real not listed in $g$, since $g$ lists all the reals of $V$, including $z$. Contradiction! QED

The practitioners of Borel equivalence relation theory have a large bag of tools at their disposal---many arguments proceed with one's choice of forcing or ergodic theory and group actions or something else---and I expect similarly that there is a forcing-free proof of the theorem above (perhaps someone can post such an argument?). But to my way of thinking, the forcing proof is fairly sharp.

Lastly, let me say that if there are sufficient large cardinals, then projective truth is absolute from $V$ to $V[g][h]$, and in this case, the same argument shows that there can be no projective function $f$ with the two properties. Since the Borel functions sit merely at the doorstep of the projective hierarchy, this would be an enormous expansion of the phenomenon.

-
 Small correction: the assertion that $f$ is a total function has complexity $\Pi^1_2$ in the Borel code, and so is absolute. This is why $f(g)$ and $f(h)$ make sense. – Joel David Hamkins Nov 24 2010 at 17:37 A masterful explanation. I too would enjoy a forcing-free proof but that one is pretty incisive and a good demonstration of forcing. ---- 2 peripheral speculations (about the question not the answer) I'll replace $\mathbb{R}$ with the space of sequences $\mathbb{B}=2^{\omega}$ to avoid irrelevancies. ---- 1) I realize that "most" countable subsets of $\mathbb{B}$ are dense in $\mathbb{B}$ and can be enumerated (in uncountably many ways) to make the diagonal construction yield any possible output. So maybe in some sense there aren't nice functions on them at all. (continued) – – Aaron Meyerowitz Nov 25 2010 at 2:40 2) However, any acceptable function from $\mathbb{B}^{\omega}$ to $\mathbb{B}$ yields in an obvious way a function from $\mathbb{B}^{\omega}$ to itself with $X \subseteq f(X)$ and $|f(X) \setminus X| \le 1$. SO if it is fair to state the result as I did in the question (which I am not sure it is), then it can be rephrased as saying that any Borel function with those two properties has a fixed point. I'd love to get that by iteration but doubt it. --- I'm not going to post it as a new question, but I wonder if Borel + $X \subseteq f(X)$ alone is enough to require a fixed point. – Aaron Meyerowitz Nov 25 2010 at 2:52

[Edit, Sep. 22, 2012: I am leaving the original answer below, but Andreas's comment is the right approach, so I am incorporating it into the answer, adding a bit of context. We want to argue that there is no definable bijection between $[\mathbb R]^{\le\aleph_0}$ and $\mathbb R$. It suffices to show that there is no such bijection in Solovay's model, or under determinacy. In fact, there is no such bijection in any model where $\omega_1\not\le|\mathbb R|$.

A very general reason showing this is an old observation of Tarski, that follows from Zermelo's work on the well-ordering theorem: In $\mathsf{ZF}$, for any set $X$ we have $|X|\lt |\mathcal W(X)|$, where $\mathcal W(X)$ denotes the collection of well-orderable subsets of $X$. If $\omega_1\not\le|\mathbb R|$, then $\mathcal W(\mathbb R)$ is $[\mathbb R]^{\le\aleph_0}$.

To see the inequality, simply note that any $f:\mathcal W(X)\to X$ gives rise ("by recursion") to a unique $W$ with a well-ordering $\lt$ such that $f(W)\in W$ and $$f(\{a\in W\mid a\lt x\})=x$$ for any $x\in W$. But then $W$ witnesses that $f$ is not injective.]

Joel's answer shows that there is no Borel $f:{\mathbb R}^\omega\to{\mathbb R}$ that is invariant under the equivalence relation that identifies sequences if they have the same range and such that $f(\vec x)$ is not in the range of $\vec x$.

What remains to address is whether we can replace ${\mathbb R}^\omega$ with ${}[{\mathbb R}]^{\le\aleph_0}$, the collection of countable subsets of ${\mathbb R}$. The issue is really whether we can give the space ${}[{\mathbb R}]^{\le\aleph_0}$ a standard Borel structure in a definable manner.

I believe this is not possible: Unless I'm mistaken, the relation $E$ of having the same range is a Borel equivalence relation (on ${\mathbb R}^\omega$) bi-reducible with the equivalence relation commonly known as $T_2$, see Vladimir Kanovei, "Varia: Ideals and Equivalence Relations, beta-version", arXiv:math/0610988. Of course, ${}[{\mathbb R}]^{\le\aleph_0}$ coincides in anatural way with the quotient ${\mathbb R}^\omega/E$.

But the relation $T_2$ is very high in the reducibility hierarchy; in particular, it is above $E_0$, which means that $2^{\mathbb N}/E_0$ injects into ${\mathbb R}^\omega/E$ in a definable fashion. Recall that $xE_0y$ (for $x,y\in2^{\mathbb N}$) iff $x(n)=y(n)$ for all but finitely many $n$.

But it is known that $2^{\mathbb N}/E_0$ does not admit a Borel structure in any reasonable fashion, since in fact it is not even linearly orderable in any reasonably definable manner, see this answer.

As usual, this lack of Borel structure translates under, say, determinacy, to strong answers to Aaron's question, so in determinacy models we have that there is no function $f:[{\mathbb R}]^{\le\aleph_0}\to{\mathbb R}$ mapping each $A$ outside itself.

(Please let me know if I've misidentified $T_2$ and I'll edit accordingly.)

By the way, I learned (essentially) Joel's argument from Alekos Kechris a few years ago, and if I remember correctly, he termed this a classical result. I cannot remember at the moment whether it was attributed to anybody specifically (and I would be curious to know).

Let me close with a curious remark: In light of the answer to Aaron's question, it is natural to wonder whether we can even have a "definable" pairing function, or even a definable "countable pairing" function: A (definable) function that given a countable set ${\mathcal A}$ of sets of reals returns a set $C$ from which each $A$ in ${\mathcal A}$ can be recovered (so $C$ is essentially a definable version of a listing of ${\mathcal A}$).

Surprisingly, this is the case, as pointed out by Steve Jackson. For example, there is (definably) an $F:{\mathcal P}({\mathbb R})\times{\mathcal P}({\mathbb R})\to{\mathcal P}({\mathbb R})$ such that $F(A,B)=F(B,A)$ for all $A,B$, and both $A,B$ are Wadge reducible to $f(A,B)$. If we assume the very weak choice axiom $AC_\omega({\mathbb R})$, then the corresponding result for countable sequences of sets of reals holds as well. The details can be seen in my paper with Ketchersid, "A trichotomy theorem in natural models of AD${}^+$", to appear in the Proceedings of the BEST conference.

Here is the argument for pairs: Identify reals with infinite sequences of naturals. If $A = B$, simply set $F (A, B) = A$. If $A\subseteq B$ or $B\subseteq A$, set $F (A, B) = (0 ∗ S ) \cup (1 ∗ T )$ where $S$ is the smaller of $A, B$, and $T$ is the larger. Here, $0 ∗ S =\{0{}^\frown a \mid a \in S \}$ and similarly for $1 ∗ T$.

If $A\setminus B$ and $B\setminus A$ are both non-empty, we proceed as follows: Let $X (A, B)\subseteq{\mathbb R}^{\mathbb Z}$ be defined by saying that, if $f : {\mathbb Z}\to{\mathbb R}$, then $f \in X (A, B)$ iff there is an $i$ such that $f (i) \in A \setminus B$ (or $B \setminus A$) and, for each $j$, $f (j ) \in A$ if ${}|j − i|$ is even, and $f (j ) \in B$ if ${}|j − i|$ is odd (and reverse the roles of $A, B$ here if $f (i) \in B \setminus A$).

The set $X (A, B)$ is an invariant set (with respect to the shift action of ${\mathbb Z}$ on ${\mathbb R}^{\mathbb Z}$), and $X (A, B) = X (B, A)$. (The points of $A \setminus B$ and $B \setminus A$ have to occur at places of different parity; while points of $A \cap B$ can occur anywhere.)

Given $X (A, B)$, we can compute $A$ (and also $B$) as follows: Fix $z \in A \setminus B$. Then $x \in A$ iff $$\exists f \in X (A, B) \exists i \exists j (f (i) = z \mbox{ and }f (j ) = x \mbox{ and }|j − i|\mbox{ is even}).$$ This shows that $A$ is (boldface) $\Sigma^1_1 (X (A, B))$. If we replace $X (A, B)$ with $X' (A, B)$, the *$\Sigma^1_1$-jump* of $X (A, B)$, then $A$ is Wadge reducible to $X (A, B)$.

Finally, we use that there is a Borel bijection between ${\mathbb R}^{\mathbb Z}$ and ${\mathbb R}$, and define $F (A, B)$ as the image of $X'(A, B)$ under this map.

-
Tangential remark about the non-existence in determinacy models of $f:[\mathbb R]^{\leq\omega}\to\mathbb R$ mapping every set to a non-member. Such an $f$ would let us inductively define a one-to-one map $\omega_1\to\mathbb R$. So it is prohibited by far weaker assumptions than determinacy; for example, by a result of Shelah, there's no such $f$ if all sets of reals are Lebesgue measurable. – Andreas Blass Nov 25 2010 at 16:02
@Andreas: Oh, this is nice. $\omega_1\le|{\mathbb R}|$ also implies that there is an uncountable set of reals without a perfect subset. – Andres Caicedo Nov 25 2010 at 16:27
In fact, the existence of a map $f:[\mathbb{R}]^{\leq\omega}\to\mathbb{R}$ mapping every set to a non-member is equivalent to $\aleph_1 \leq |\mathbb{R}|$. – François G. Dorais Sep 22 at 18:19
Existence of non-measurables is equivalent to $\aleph_1 \leq |\mathbb {R}|$ – Ostap Chervak Dec 4 at 6:39
@Ostap Chervak: Could you give some more information about the forward direction of the equivalence in your comment? In particular, suppose we take a Solovay model or a model of AD+DC and generically adjoin a nonprincipal ultrafilter by forcing with (P(omega)/Fin)-{0}. The ultrafilter is a non-measurable set in the extension, but I don't see any embedding of omega_1 into the reals. – Andreas Blass Jan 2 at 14:29