MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Return to Answer

3 added 5 characters in body; added 5 characters in body

[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|<|\mathcal |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<x\})=x 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.

2 added 1121 characters in body

[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|<|\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 $$f(\{a\in W\mid a<x\})=x for any x\in W. But then W witnesses that f is not injective.] 1 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.