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](https://mathoverflow.net/questions/46970/proofs-of-the-uncountability-of-the-reals) 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$?
> 
> 
> 



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


