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

 A: 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.
A: 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.
A: 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$.
A: [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. 
