Countable Borel relation

In descriptive set theory, specifically invariant descriptive set theory, countable Borel relations are a class of relations between standard Borel space which are particularly well behaved. This concept encapsulates various more specific concepts, such as that of a hyperfinite equivalence relation, but is of interest in and of itself.

Motivation

A main area of study in invariant descriptive set theory is the relative complexity of equivalence relations. An equivalence relation $E$ on a set $X$ is considered more complex than an equivalence relation $F$ on a set $Y$ if one can "compute $F$ using $E$" - formally, if there is a function $f:Y\to X$ which is well behaved in some sense (for example, one often requires that $f$ is Borel measurable) such that $\mathrm{\forall }x,y\in Y:xFy⟺f(x)Ef(y)$. Such a function If this holds in both directions, that one can both "compute $F$ using $E$" and "compute $E$ using $F$", then $E$ and $F$ have a similar level of complexity. When one talks about Borel equivalence relations and requires $f$ to be Borel measurable, this is often denoted by $E{\sim }_{B}F$.

Countable Borel equivalence relations, and relations of similar complexity in the sense described above, appear in various places in mathematics (see examples below, and see for more). In particular, the Feldman-Moore theorem described below proved useful in the study of certain Von Neumann algebras (see ).

Definition

Let $X$ and $Y$ be standard Borel spaces. A countable Borel relation between $X$ and $Y$ is a subset $R$ of the cartesian product $X\times Y$ which is a Borel set (as a subset in the Product topology) and satisfies that for any $x\in X$, the set $\{y\in Y|(x,y)\in R\}$ is countable.

Note that this definition is not symmetric in $X$ and $Y$, and thus it is possible that a relation $R$ is a countable Borel relation between $X$ and $Y$ but the converse relation is not a countable Borel relation between $Y$ and $X$.

Examples

• A countable union of countable Borel relations is also a countable Borel relation.
• The intersection of a countable Borel relation with any Borel subset of $X\times Y$ is a countable Borel relation.
• If $f:X\to Y$ is a function between standard Borel spaces, the graph $\mathrm{\Gamma }(f)$ of the function is a countable Borel relation between $X$ and $Y$ if and only if $f$ is Borel measurable (this is a consequence of the Luzin-Suslin theorem and the fact that $\{y\in Y|(x,y)\in \mathrm{\Gamma }(f)\}=\{f(x)\}$ ). The converse relation of the graph, $\{(f(x),x)|x\in X\}$, is a countable Borel relation if and only if $f$ is Borel measurable and has countable fibers.
• If $E$ is an equivalence relation, it is a countable Borel relation if and only if it is a Borel set and all equivalence classes are countable. In particular hyperfinite equivalence relations are countable Borel relations.
• The equivalence relation induced by the continuous action of a countable group is a countable Borel relation. As a concrete example, let $X$ be the set of subgroups of $F_2$, the Free group of rank 2, with the topology generated by basic open sets of the form $\{G\in X|a\in G\}$ and $\{G\in X|a\notin G\}$ for some $a\in F_2$ (this is the Product topology on $2^{F_2}$). The equivalence relation $G\sim H⟺\mathrm{\exists }a\in F_2:G=a^{-1}Ha$ is then a countable Borel relation.
• Let $𝒞$ be the space of subsets of the naturals, again with the product topology (a basic open set is of the form $\{X\in 𝒞|n\in X\}$ or $\{X\in 𝒞|n\notin X\}$) - this is known as the Cantor space. The equivalence relation of Turing equivalence is a countable Borel equivalence relation.
• The isomorphism equivalence relation between various classes of models, while not being countable Borel equivalence relations, are of similar complexity to a Borel equivalence relation in the sense described above. Examples include:
  • The class of countable graphs where the degree of each vertex is finite.
  • The class field extensions of finite transcendence degree over the rationals.

The Luzin–Novikov theorem

This theorem, named after Nikolai Luzin and his doctoral student Pyotr Novikov, is an important result used is many proofs about countable Borel relations.

Theorem. Suppose $X$ and $Y$ are standard Borel spaces and $R$ is a countable Borel relation between $X$ and $Y$. Then the set $Pro{j}_X(R)=\{x\in X|\mathrm{\exists }y\in Y:(x,y)\in R\}$ is a Borel subset of $Y$. Furthermore, there is a Borel function $f:Pro{j}_X(R)\to Y$ (known as a Borel uniformization) such that the graph of $f$ is a subset of $R$. Finally, there exist Borel subsets $\{A_n{\}}_{n=1}^{\mathrm{\infty }}$ of $X$ and Borel functions $f_n:A_n\to Y$ such that $R$ is the union of the graphs of the $f_n$, that is $R=\{(x,y)\in X\times Y|\mathrm{\exists }n\in \mathbb{N}:x\in A_n\wedge y=f_n(x)\}$.

This has a couple of easy consequences:

• If $f:X\to Y$ is a Borel measurable function with countable fibers, the image of $f$ is a Borel subset of $Y$ (since the image is exactly $Pro{j}_Y(R)$ where $R$ is the converse relation of the graph of $f$) .
• Assume $E$ is a Borel equivalence relation on a standard Borel space $X$ which has countable equivalence classes. Assume $A$ is a Borel subset of $X$. Then $[A{]}_E=\{x\in X|\mathrm{\exists }{x}^{\prime }\in A:xE{x}^{\prime }\}$ is also a Borel subset of $X$ (since this is precisely $Pro{j}_X(R)$ where $R=E\cap (X\times A)$, and $X\times A$ is a Borel set).

Below are two more results which can be proven using the Luzin-Novikov Novikov theorem, concerning countable Borel equivalence relations:

Feldman–Moore theorem

The Feldman–Moore theorem, named after Jacob Feldman and Calvin C. Moore, states:

Theorem. Suppose $E$ is a Borel equivalence relation on a standard Borel space $X$ which has countable equivalence classes. Then there exists a countable group $G$ and action of $G$ on $X$ such that for every $g\in G$ the function $x\mapsto g.x$ is Borel measurable, and for any $x\in X$, the equivalence class of $x$ with respect to $E$ is exactly the orbit of $x$ under the action.

That is to say, countable Borel equivalence relations are exactly those generated by Borel actions by countable groups.

Marker lemma

This lemma is due to Theodore Slaman and John R. Steel, and can be proven using the Feldman–Moore theorem:

Lemma. Suppose $E$ is a Borel equivalence relation on a standard Borel space $X$ which has countable equivalence classes. Let $B=\{x\in X||[x{]}_E|={\mathrm{\aleph }}_0\}$. Then there is a decreasing sequence $B\supseteq S_1\supseteq S_2\supseteq ...$ such that $[S_n{]}_E=B$ for all $S_n$ and $\bigcap _{n=1}^{\mathrm{\infty }}{S}_n=\mathrm{\varnothing }$.

Less formally, the lemma says that the infinite equivalence classes can be approximated by "arbitrarily small" set (for instance, if we have a Borel probability measure $\mu$ on $X$ the lemma implies that $\underset{n\to \mathrm{\infty }}{\lim }\mu (S_n)=0$ by the continuity of the measure).