In Descriptive set theory, specifically invariant descriptive set theory, countable Borel relations are a class of relations between Standard Borel spaces which are particularily 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.
A main area of study in invariant descriptive set theory is the relative complexity of equivalence relations. An equivalence relation on a set is considered more complex than an equivalence relation on a set if one can "compute using " - formally, if there is a function which is well behaved in some sense (for example, one often requires that is Borel measurable) such that . Such a function If this holds in both directions, that one can both "compute using " and "compute using ", then and have a similar level of complexity. When one talks about Borel equivalence relations and requires to be Borel measurable, this is often denoted by .
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 [1] for more). In particular, the Feldman-Moore theorem described below proved useful in the study of certain Von Neumann algebras (see [2]).
Definition. Let and be Standard Borel spaces. A countable Borel relation between and is a subset of the cartesian product which is a Borel set (as a subset in the Product topology) and satisfies that for any , the set is countable.
Note that this definition is not symmetric in and , and thus it is possible that a relation is a countable Borel relation between and but the converse relation is not a countable Borel relation between and .
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 and are Standard Borel spaces and is a countable Borel relation between and . Then the set is a Borel subset of . Furthermore, there is a Borel function such that (known as a Borel uniformization) such that the graph of is a subset of . Finally, there exist Borel subsets of and Borel functions such that is the union of the graphs of the , that is . [5]
This has a couple of easy consequences:
Below are two more results which can be proven using the Luzin-Novikov Novikov theorem, concerning countable Borel equivalence relations:
The Feldman-Moore theorem, named after Jacob Feldman and Calvin C. Moore, states:
Theorem. Suppose is a Borel equivalence relation on a standard Borel space which has countable equivalence classes. Then there exists a countable group and action of on such that for every the function is Borel measurable, and for any , the equivalence class of with respect to is exactly the orbit of under the action. [6]
That is to say, countable Borel equivalence relations are exactly those generated by Borel actions by countable groups.
This lemma is due to Theodore Slaman and John R. Steel, and can be proven using the Feldman-Moore theorem:
Lemma. Suppose is a Borel equivalence relation on a standard Borel space which has countable equivalence classes. Let . Then there is a decreasing sequence such that for all and .
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 on the lemma implies that by the continuity of the measure).
In Descriptive set theory, specifically invariant descriptive set theory, countable Borel relations are a class of relations between Standard Borel spaces which are particularily 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.
A main area of study in invariant descriptive set theory is the relative complexity of equivalence relations. An equivalence relation on a set is considered more complex than an equivalence relation on a set if one can "compute using " - formally, if there is a function which is well behaved in some sense (for example, one often requires that is Borel measurable) such that . Such a function If this holds in both directions, that one can both "compute using " and "compute using ", then and have a similar level of complexity. When one talks about Borel equivalence relations and requires to be Borel measurable, this is often denoted by .
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 [1] for more). In particular, the Feldman-Moore theorem described below proved useful in the study of certain Von Neumann algebras (see [2]).
Definition. Let and be Standard Borel spaces. A countable Borel relation between and is a subset of the cartesian product which is a Borel set (as a subset in the Product topology) and satisfies that for any , the set is countable.
Note that this definition is not symmetric in and , and thus it is possible that a relation is a countable Borel relation between and but the converse relation is not a countable Borel relation between and .
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 and are Standard Borel spaces and is a countable Borel relation between and . Then the set is a Borel subset of . Furthermore, there is a Borel function such that (known as a Borel uniformization) such that the graph of is a subset of . Finally, there exist Borel subsets of and Borel functions such that is the union of the graphs of the , that is . [5]
This has a couple of easy consequences:
Below are two more results which can be proven using the Luzin-Novikov Novikov theorem, concerning countable Borel equivalence relations:
The Feldman-Moore theorem, named after Jacob Feldman and Calvin C. Moore, states:
Theorem. Suppose is a Borel equivalence relation on a standard Borel space which has countable equivalence classes. Then there exists a countable group and action of on such that for every the function is Borel measurable, and for any , the equivalence class of with respect to is exactly the orbit of under the action. [6]
That is to say, countable Borel equivalence relations are exactly those generated by Borel actions by countable groups.
This lemma is due to Theodore Slaman and John R. Steel, and can be proven using the Feldman-Moore theorem:
Lemma. Suppose is a Borel equivalence relation on a standard Borel space which has countable equivalence classes. Let . Then there is a decreasing sequence such that for all and .
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 on the lemma implies that by the continuity of the measure).