Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
What is the topology on $\mathcal{C}$? (A function $f:\mathcal{C}\to\mathbb{R}$ being Borel depends of course on the topology). From the suggestion that motivated your post, it seems the relevant topology comes from the space of sequences, after identifying sequences which can be obtained from each other from permutation. I guess for sequences we are looking at the product topology? –  Pablo Shmerkin Nov 24 '10 at 3:20
    
I freely admit that part of my question is "what does that claim mean?" (but also in what sense is it true and why?). Now I am intrigued what that topology on $\mathcal{C}$ would be! But one can sidestep the issue by saying Is it the case that for every $f:\mathcal{C} \rightarrow \mathbb{R}$ whose induced (permutation invariant) map on sequences is Borel...etc. For me, "Borel" is standing in for "nice". There is a nice constructive, proof, not needing the axiom of choice that any sequence of reals omits a real. Is the same fact for countable sets of reals much less concrete? –  Aaron Meyerowitz Nov 24 '10 at 4:01
1  
I do not think you can give a standard Borel structure to the space of countable sets of reals. I'll expand this as an answer (since there may be some interest to it) hopefully tonight when I ought to find some time. –  Andres Caicedo Nov 24 '10 at 17:03
    
This is a special case of Friedman's so-called "Borel diagonalization theorem" for Borel equivalence relations. There is a proof by Harrington that uses Borel determinacy and effective descriptive set theory which can be found in Su Gao's "Invariant Descriptive Set Theory" Theorem 8.3.5 –  Robin Tucker-Drob Nov 25 '10 at 19:41
    
@Robin : I haven't received my copy of Su's book. How do you like it? –  Andres Caicedo Dec 1 '10 at 12:54

3 Answers 3

up vote 22 down vote accepted

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.

share|improve this answer
    
Small correction: the assertion that $f$ is a total function has complexity $\Pi^1_2$ in the Borel code, and so is absolute. This is why $f(g)$ and $f(h)$ make sense. –  Joel David Hamkins Nov 24 '10 at 17:37
    
A masterful explanation. I too would enjoy a forcing-free proof but that one is pretty incisive and a good demonstration of forcing. ---- 2 peripheral speculations (about the question not the answer) I'll replace $\mathbb{R}$ with the space of sequences $\mathbb{B}=2^{\omega}$ to avoid irrelevancies. ---- 1) I realize that "most" countable subsets of $\mathbb{B}$ are dense in $\mathbb{B}$ and can be enumerated (in uncountably many ways) to make the diagonal construction yield any possible output. So maybe in some sense there aren't nice functions on them at all. (continued) – –  Aaron Meyerowitz Nov 25 '10 at 2:40
    
2) However, any acceptable function from $\mathbb{B}^{\omega}$ to $\mathbb{B}$ yields in an obvious way a function from $\mathbb{B}^{\omega}$ to itself with $X \subseteq f(X)$ and $|f(X) \setminus X| \le 1$. SO if it is fair to state the result as I did in the question (which I am not sure it is), then it can be rephrased as saying that any Borel function with those two properties has a fixed point. I'd love to get that by iteration but doubt it. --- I'm not going to post it as a new question, but I wonder if Borel + $X \subseteq f(X)$ alone is enough to require a fixed point. –  Aaron Meyerowitz Nov 25 '10 at 2:52

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

share|improve this answer
4  
Tangential remark about the non-existence in determinacy models of $f:[\mathbb R]^{\leq\omega}\to\mathbb R$ mapping every set to a non-member. Such an $f$ would let us inductively define a one-to-one map $\omega_1\to\mathbb R$. So it is prohibited by far weaker assumptions than determinacy; for example, by a result of Shelah, there's no such $f$ if all sets of reals are Lebesgue measurable. –  Andreas Blass Nov 25 '10 at 16:02
    
@Andreas: Oh, this is nice. $\omega_1\le|{\mathbb R}|$ also implies that there is an uncountable set of reals without a perfect subset. –  Andres Caicedo Nov 25 '10 at 16:27
2  
In fact, the existence of a map $f:[\mathbb{R}]^{\leq\omega}\to\mathbb{R}$ mapping every set to a non-member is equivalent to $\aleph_1 \leq |\mathbb{R}|$. –  François G. Dorais Sep 22 '12 at 18:19
1  
Existence of non-measurables is equivalent to $\aleph_1 \leq |\mathbb {R}|$ –  Ostap Chervak Dec 4 '12 at 6:39
1  
@Ostap Chervak: Could you give some more information about the forward direction of the equivalence in your comment? In particular, suppose we take a Solovay model or a model of AD+DC and generically adjoin a nonprincipal ultrafilter by forcing with (P(omega)/Fin)-{0}. The ultrafilter is a non-measurable set in the extension, but I don't see any embedding of omega_1 into the reals. –  Andreas Blass Jan 2 '13 at 14:29

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

share|improve this answer
    
About the last paragraph... I'll be honest, I haven't read the proofs of these claims and have no idea what the connection between determinacy and diagonalization theorem is. But I thought I should point these out. –  Burak Sep 12 at 20:55
    
Also, I left out some details and am in a hurry now. If there turn out to be any mistakes, someone with enough privileges is welcome to correct it. –  Burak Sep 12 at 21:02
    
Very nice. Does this proof generalize (as with the forcing argument) to show that there is no projective diagonalizing function, when there are sufficient large cardinals (so that projective absoluteness holds)? –  Joel David Hamkins Sep 13 at 0:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.