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

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

2010-11-24T02:49:54Z

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 by Joel David Hamkins for Why is there no Borel function mapping every countable set of reals outside itself?

2010-11-24T04:10:41Z

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 by Andres Caicedo for Why is there no Borel function mapping every countable set of reals outside itself?

2010-11-25T07:51:49Z

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