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

Question

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$?

Answer 1

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.

Answer 2

Although the question has an accepted answer, I will post a forcing-free proof of this fact that uses the Baire category theorem.

The theorem Joel proved is originally due to Harvey Friedman and is a special case of his "Borel diagonalization theorem" that he proves in his paper On the necessary use of abstract set theory, Advances in Mathematics, 41 (1981), 209-280. The following proof is from the appendix of this paper.

Theorem. Assume that $f: {\mathbb{R}}^{\mathbb{N}} \rightarrow \mathbb{R}$ is a Borel measurable function with the property that if $x =^+ y$, then $f(x)=f(y)$, where $x =^+ y$ if and only if $\{x_n: n \in \mathbb{N}\}=\{y_n: n \in \mathbb{N}\}$ for $x,y \in {\mathbb{R}}^{\mathbb{N}}$. Then, there exists $x \in {\mathbb{R}}^{\mathbb{N}}$ such that $f(x)=x_k$ for some $k \in \mathbb{N}$.

Proof. Let $f$ be such a Borel map. In particular, $f(x)=f(y)$ whenever $g \cdot x = y$ for some $g \in \operatorname{Fin}(\mathbb{N})$ where the action is given by permuting the indices.

For each rational $q \in \mathbb{Q}$, define $A_q=\{x \in {\mathbb{R}}^{\mathbb{N}}: f(x) < q\}$. Let ${\overline{\mathbb{R}}}^{\mathbb{N}}$ denote the product space where $\overline{\mathbb{R}}$ is the space of real numbers endowed with the discrete topology.

Lemma. For any $q \in \mathbb{Q}$, either $A_q$ or $A_q^C$ is meager in ${\overline{\mathbb{R}}}^{\mathbb{N}}$.

Proof. Pick some $q \in \mathbb{Q}$. Then, $A_q$ is also Borel in ${\overline{\mathbb{R}}}^{\mathbb{N}}$ and hence has the Baire property. Let $U$ be an open set such that $A_q \triangle U$ is meager.

Each $g \in \operatorname{Fin}(\mathbb{N})$ induces a homeomorphism of ${\overline{\mathbb{R}}}^{\mathbb{N}}$. Then, since $f$ is producing the same element for sequences that are in the same orbit under the action of $\operatorname{Fin}(\mathbb{N})$, $g[A_q] \triangle g[U]=A_q \triangle g[U]$. So, each $A_q \triangle g[U]$ is meager and so is $A_q \triangle \bigcup_{g} g[U]$.

If $U=\emptyset$, then $A_q$ is meager. If $U \neq \emptyset$, then $\bigcup_{g} g[U]$ is dense and it follows that $A_q^C$ is meager since $(\bigcup_{g} g[U])^C$ and $\bigcup_{g} g[U] - A_q$ are meager. This completes the proof of the lemma. $\blacksquare$

Now, let $S$ be the set of all rationals $q$ such that $A_q$ is meager in ${\overline{\mathbb{R}}}^{\mathbb{N}}$. $S$ cannot be $\emptyset$ or $\mathbb{Q}$ by the Baire category theorem. Let $z=sup(S)$. Then, since $\bigcup_{s < z} A_q \cup \bigcup_{s > z} A_q^C$ is meager, $\{x \in {\mathbb{R}}^{\mathbb{N}}: f(x) = z\}$ is comeager, and hence dense by the BCT. But then, $\{x \in {\mathbb{R}}^{\mathbb{N}}: f(x) = z\}$ being dense implies that it has an element starting with $z$. $\blacksquare$

From the proof it can be seen that if we weaken the uniformity condition on $f$ so that it produces the same element for the sequences that are $\operatorname{Fin}(\mathbb{N})$-equivalent, we still cannot diagonalize in a Borel way.

The most general version of this theorem is the following

Theorem. Let $X$ be a standard Borel space and $E \subseteq X^2$ be a Borel equivalence relation. For any $x,y \in X^{\omega}$, define $x E^+ y$ if and only if $\{[x_n]: n \in \omega\}=\{[y_n]: n \in \omega\}$. Then, there does not exist a Borel map $f: X^{\omega} \rightarrow X$ such that $\neg f(x) E x_n$ for all $n \in \omega$ and $x E^+ y$ implies $f(x) E f(y).$

In some sense, this theorem tells you that you cannot diagonalize "against a Borel equivalence relation" in a "uniform" Borel way.

The operation $E \mapsto E^+$ is known as the Friedman-Stanley jump. For any Borel equivalence relation $E$ with more than one equivalence class on a standard Borel space, $E <_B E^+$ where $\leq_B$ denotes the Borel reducibility. Indeed, Friedman's own proof that $^+$ is a jump operator makes use of the Borel diagonalization theorem.

As a last remark, I should add that in the above paper Friedman claims that in order to prove this Borel diaganolization theorem in its full form, it is necessary to use $\omega_1$ many iterations of the power set of operation (Corollary 3.4), just like Borel determinacy theorem. Indeed, according to Lemma 3.2.5, there exists a constant $n \in \omega$ such that Borel determinacy up to Borel sets of rank $ \leq \alpha+n$ implies the Borel diagonalization theorem for Borel equivalence relations of rank $\leq \alpha$.

Answer 3

[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.

Answer 4

There is no known forcing-free proof of the following strong version. (Here $E_{cntble}$ is yet another name for the equivalence relation that others call $T_{2}$ or $=^{+}$.)

Theorem Suppose that $E$ is a countable Borel equivalence relation on the standard Borel space $Z$ and that $f: {\mathbb{R}}^{\mathbb{N}} \rightarrow Z$ is a Borel homomorphism from $E_{cntble}$ to $E$. There there exists $z \in Z$ such that for every $r \in \mathbb{R}$, there exists $x \in {\mathbb{R}}^{\mathbb{N}}$ with $r \in \{ x_{n} \mid n \in \mathbb{N}\}$ such that $f(x) \mathbin{E} z$.

On the other hand, the analogous statement is false for Borel homomorphisms from $E_{cntble}^{+}$ to $E_{cntble}$. This suggests that there does not exist an easy forcing proof of the general form of Friedman's theorem.