Revisions - MathOverflow

Return to Answer

Improved exposition; added 19 characters in body; added 10 characters in body

view source

edited Nov 24 2010 at 14:35

You can formalize

The initial function you mention is the question as diagonalizingfunction $d:\mathbb{R}^\omega\to\mathbb{R}$, for which oneensures that $z=d(x_0,x_1,\ldots)$ is distinctfrom every $x_n$ simply by making the assertion $n$-th digit of $z$different from the $n$-th digit of $x_n$ in some regularway. Since the graph of this function is arithmeticallydefinable (needing to look only at the individual digitsof the input and output), it follows that there$d$ is no a Borelfunctiondefined .

The point of your question, however, is that this function is notwell-defined on sequences to realsdifferent 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 always $f$ gives thesame value to all for different enumerations of the same set, and which gives a value outside the given countableset. Suppose towards contradiction Unfortunately, there is no such function that isBorel.

Theorem. There is no Borel function$f:\mathbb{R}^\omega\to\mathbb{R}$ has this feature such that

$f(x_0,x_1,\ldots)\neq x_n$ for every sequence $\vec x$and is Borelindex $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.

(Such The nonexistence of such a function is closely related in spirit, in thecontext of Borel equivalence relation theory, to thepossibility impossibility of a Borel reduction of from the equivalence relation$E_{set}$ to $=$, in the context of Borel equivalence relation theory, and this the argument below belongs to thattheory.)

Continuing with the subject. The argument will use set-theoretic forcing, let$\mathbb{P}$ be the partial andis an instance where forcing is used in order consisting of all finitesequences of real numbersto make aconclusion about the ground model $V$, rather than to prove anindependence result.

To begin, ordered suppose that $f$ is a Borel function with longer sequenceslower in the ordertwoproperties. This is Let $\mathbb{P}=\text{Coll}(\omega,\mathbb{R})$be the usual forcing notion to collapse $\mathbb{R}$ to $\omega$, and the \omega$. Thatis, conditions in $\mathbb{P}$ are finite sequences ofreals, ordered by end-extension. The generic object will beground model $V$. Let $g_0$ g$ and $g_1$ h$ be mutually $V$-genericextensions $V[g_0]$, V[g]$, $V[g_1]$ V[h]$ and their common extension$V[g_0][g_1]$. V[g][h]$. Since $f$ was a Borel function, it has a Borelis a $\Sigma^1_2$ \Pi^1_1$ statement about this Borel code, and henceabsolute between $V$ and these larger universes. That is,the re-interpreted function $f$ continues to have thedesired properties in $V[g][h]$. Since $g_0$ g$ and $g_1$ h$ bothenumerate the same set $\mathbb{R}^V$, it follows that$f(g_0)=f(g_1)$ f(g)=f(h)$ in $V[g_0][g_1]$. V[g][h]$. In particular, the value$z=f(g_0)$ z=f(g)=f(h)$ is in both $V[g_0]$ V[g]$ and $V[g_1]$. V[h]$. But since $g_0$ g$and $g_1$ h$ are mutually generic, it follows that $V[g_0]\cap V[g_1]=V$V[g]\capthat $f(g_0)$ f(g)$ should be a real not listed in $g_0$, g$, since $g_0$ g$

The practitioners of Borel equivalence relation theory havea large bag of tools at their disposal---many argumentsproceed with one's choice of forcing or ergodic theory andgroup actions or something else---and I expect similarlythat there is a forcing-free proof of the theorem above(perhaps someone can post such an argument?). But to my way of thinking, theforcing proof is fairly sharp.

Lastly, let me say that if there are sufficient largecardinals, then projective truth is absolute from $V$ to$V[g][h]$, and in this case, the same argument shows thatthere can be no projective function $f$ with the twoproperties. Since the Borel functions sit merely at thedoorstep of the projective hierarchy, this would be anenormous expansion of the phenomenon.

Post Undeleted by Joel David Hamkins

occurred Nov 24 2010 at 4:31

Fixed an error; deleted 23 characters in body

view source

edited Nov 24 2010 at 4:31

Joel David Hamkins
75k●7●187●343

You can formalize the question as the assertion that there is no Borel function defined on sequences to reals, which always gives the same value to all enumerations of the same set, and which gives a value outside the given set. Suppose towards contradiction that $f:\mathbb{R}^\omega\to\mathbb{R}$ has this feature and is Borel.

(Such a function can also be viewed as is closely related in spirit to the possibility of a Borel reduction of the equivalence relation $E_{set}$ to $=$, in the context of Borel equivalence relation theory, and this argument belongs to that theory.

But there is no such reduction. To see thistheory.)

Continuing with the argument, let $\mathbb{P}$ be the partial order consisting of all finite sequences of real numbers, ordered with longer sequences lower in the order. This is the usual forcing notion to collapse $\mathbb{R}$ to $\omega$, and the generic object will be a countable enumeration consisting of all the reals of the ground model $V$. Let $g_0$ and $g_1$ be mutually $V$-generic for $\mathbb{P}$, and consider the corresponding forcing extensions $V[g_0]$, $V[g_1]$ and their common extension $V[g_0][g_1]$. 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$ reduces $E_{set}$ to $=$ has the stated features is a $\Sigma^1_2$ statement, and hence absolute between $V$ and these larger universes. Since $g_0$ and $g_1$ both enumerate $\mathbb{R}^V$, it follows that $f(g_0)=f(g_1)$ in $V[g_0][g_1]$. In particular, the value $z=f(g_0)$ is in both $V[g_0]$ and $V[g_1]$. But since $g_0$ and $g_1$ are mutually generic, it follows that $V[g_0]\cap V[g_1]=V$, and so $z\in V$. Now, But this contradicts the assertion fact that $z\in\ran(f)$ is f(g_0)$ should be a $\Sigma^1_1$ assertion, true in the extension $V[g_0][g_1]$ and hence also true real not listed in $V$. Thus, there is some sequence $s\in V$ with $f(s)=z$. But this implies that $f(s)=f(g_0)$, and so g_0$, since $s$ must list g_0$ lists all the reals of $V$, contrary to the fact that the reals of $V$ are uncountable in including $V$, a contradiction.z$. Contradiction!

Post Deleted by Joel David Hamkins

occurred Nov 24 2010 at 4:26

view source

answered Nov 24 2010 at 4:10

Joel David Hamkins
75k●7●187●343

You can formalize the question as the assertion that there is no Borel function defined on sequences to reals, which always gives the same value to all enumerations of the same set. Suppose towards contradiction that $f:\mathbb{R}^\omega\to\mathbb{R}$ has this feature and is Borel. Such a function can also be viewed as a Borel reduction of the equivalence relation $E_{set}$ to $=$, in the context of Borel equivalence relation theory, and this argument belongs to that theory.

But there is no such reduction. To see this, let $\mathbb{P}$ be the partial order consisting of all finite sequences of real numbers, ordered with longer sequences lower in the order. This is the usual forcing notion to collapse $\mathbb{R}$ to $\omega$, and the generic object will be a countable enumeration consisting of all the reals of the ground model $V$. Let $g_0$ and $g_1$ be mutually $V$-generic for $\mathbb{P}$, and consider the corresponding forcing extensions $V[g_0]$, $V[g_1]$ and their common extension $V[g_0][g_1]$. 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$ reduces $E_{set}$ to $=$ is a $\Sigma^1_2$ statement, and hence absolute between $V$ and these larger universes. Since $g_0$ and $g_1$ both enumerate $\mathbb{R}^V$, it follows that $f(g_0)=f(g_1)$ in $V[g_0][g_1]$. In particular, the value $z=f(g_0)$ is in both $V[g_0]$ and $V[g_1]$. But since $g_0$ and $g_1$ are mutually generic, it follows that $V[g_0]\cap V[g_1]=V$, and so $z\in V$. Now, the assertion that $z\in\ran(f)$ is a $\Sigma^1_1$ assertion, true in the extension $V[g_0][g_1]$ and hence also true in $V$. Thus, there is some sequence $s\in V$ with $f(s)=z$. But this implies that $f(s)=f(g_0)$, and so $s$ must list all the reals of $V$, contrary to the fact that the reals of $V$ are uncountable in $V$, a contradiction.