Uniformization in Descriptive Set Theory

Question

I'm a beginner in descriptive set theory.

There is a series of connected exercises (1C.6, 1C.7, 1C.8) in Moschovakis' classic text (new edition) on uniformization. They are simple case uniformization, reduction (by uniformization), and separation of sets (via reduction).

It seems like with such layout, the point of uniformization is to give us a way to separate sets.

My question is, why are we interested in uniformization and reduction? What I can see is that uniformization can always be carried out with AC, pretty obvious. So, has it anything to do with Choice?

What about reduction?

Answer 1

Uniformization is indeed related to the Axiom of Choice. Indeed, the Axiom of Choice is equivalent to the statement that every binary relation (on arbitrary sets) has a uniformizer. Unfortunately, the Axiom of Choice gives no bound on the complexity of the uniformizer. The Uniformization Theorems of Kondô, Lusin–Novikov, Kuratowski–Ryll-Nardzewski, and others, remedy this problem by giving complexity bounds on the uniformizing function in terms of the complexity of the relation. In addition, these unformization theorems are provable in ZF, so they also provide a way to eliminate the use of choice for certain types of constructions that are very common in mathematics, particularly in analysis.

Answer 2

One reason to be interested in uniformization is a very nice application of the Lusin–Novikov Uniformization Theorem to the theory of countable Borel equivalence relations. Here an equivalence relation $E$ on a Polish space is said to be Borel if $E$ is a Borel subset of $X \times X$ and $E$ is said to be countable if every $E$-class is countable. For example, if a countable discrete group $G$ has a Borel action $(g,x) \mapsto g \cdot x$ on a Polish space $X$, then the corresponding orbit equivalence relation $E_{G}^{X}$ is countable Borel. Using the Lusin–Novikov Uniformization Theorem, Feldman-Moore proved that every countable Borel equivalence relation arises in this manner; namely, if $E$ is a countable Borel equivalence relation on the Polish space $X$, then there exists a countable group $G$ with a Borel action on $X$ such that $E = E^{X}_{G}$.

Of course, if $E$ is an arbitrary equivalence relation on $\mathbb{R}$ with countable classes, then the Axiom of Choice implies that there is an action of $\mathbb{Z}$ on $\mathbb{R}$ which realizes $E$ as its orbit equivalence relation. The point of the Feldman-Moore Theorem is that if $E$ is Borel, then $E$ can be realized by a Borel action. It is interesting to note that there are countable Borel equivalence relations which cannot be realized by Borel actions of $\mathbb{Z}$.

Answer 3

How do we measure the complexity? Is it in terms of the Borel/Luzin Hierarchies?