The Direction of Borel Reducibility

58 Views Asked by At

Given that $X$ and $Y$ are Polish spaces and $E$ and $F$ are Borel equivalence relations on $X$ and $Y$, respectively, we say that $E$ is Borel reducible to $F$ if there exists a Borel function $f:X\to Y$ such that for all $x, x'\in X$, we have $xEx'$ if and only if $f(x)Ff(x')$. The idea is to express a certain fact that "$E$ is no more complicated than $F$". (See this Wikipedia article for instance.) But why is $f$ from $X$ into $Y$ and not the other way around?

There are countless notions of reducibility in mathematics. Many of the notions invoke the existence of a function from one set to another, such as this one here. Other examples of such notions include Turing reducibility and so on. The "direction" of Turing reducibility is easy to grasp, but I am not sure why for Borel reducibility.

1

There are 1 best solutions below

0
On BEST ANSWER

Perhaps the following naive idea might help you. When a function $f:X\to Y$ is Borel? Whenever $f^{-1}(B)$ is Borel (in $X$) if $B$ is Borel (in $Y$). (Note that this does not preclude “uglier” (non Borel) sets have “nice” preimages.) So the rough conclusion is that

(*) preimages of sets are nicer that the sets themselves.

The same goes for continuous, computable… So, no matter what you are reducing, if reductions are done through functions with a behavior like (*), the simpler side is on the domain.

To illustrate the point, you can work through the following exercise: If $E$ is Borel-reducible to $F$ and $F$ has Borel equivalence classes, then so does $E$.

The proof depends exactly on the assumption (*) (namely, Borel-measurability).