Jump to content

Countable Borel relation

From Wikipedia, the free encyclopedia

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

[edit]

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

[edit]

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 .

Examples

[edit]
  • 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 is a countable Borel relation.
  • If is a function between standard Borel spaces, the graph of the function is a countable Borel relation between and if and only if is Borel measurable (this is a consequence of the Luzin-Suslin theorem[3] and the fact that ). The converse relation of the graph, , is a countable Borel relation if and only if is Borel measurable and has countable fibers.
  • If 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 be the set of subgroups of , the Free group of rank 2, with the topology generated by basic open sets of the form and for some (this is the Product topology on ). The equivalence relation 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 or ) - this is known as the Cantor space. The equivalence relation of Turing equivalence is a countable Borel equivalence relation.[4]
  • 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.[4] Examples include:

The Luzin–Novikov theorem

[edit]

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 (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:

  • If is a Borel measurable function with countable fibers, the image of is a Borel subset of (since the image is exactly where is the converse relation of the graph of ) .
  • Assume is a Borel equivalence relation on a standard Borel space which has countable equivalence classes. Assume is a Borel subset of . Then is also a Borel subset of (since this is precisely where , and 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

[edit]

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.

Marker lemma

[edit]

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).

References

[edit]
  1. ^ Adams, Scot; Kechris, Alexander (2000). "Linear algebraic groups and countable Borel equivalence relations". Journal of the American Mathematical Society. 13 (4): 911. doi:10.1090/S0894-0347-00-00341-6. ISSN 0894-0347.
  2. ^ Feldman, Jacob; Moore, Calvin C. (1977). "Ergodic equivalence relations, cohomology, and von Neumann algebras. II". Transactions of the American Mathematical Society. 234 (2): 325–359. doi:10.1090/S0002-9947-1977-0578730-2. ISSN 0002-9947.
  3. ^ Kechris, Alexander S. (1995). Classical Descriptive Set Theory (N ed.). New York: Springer New York. Theorem 15.1. ISBN 978-1-4612-4190-4. OCLC 958524358.
  4. ^ a b Hjorth, Greg; Kechris, Alexander S. (1996-12-15). "Borel equivalence relations and classifications of countable models". Annals of Pure and Applied Logic. 82 (3). Part 4.2. doi:10.1016/S0168-0072(96)00006-1. ISSN 0168-0072.
  5. ^ Kechris, Alexander S. (1995). Classical Descriptive Set Theory (N ed.). New York: Springer New York. Theorem 18.10. ISBN 978-1-4612-4190-4. OCLC 958524358.
  6. ^ Feldman, Jacob; Moore, Calvin C. (1977). "Ergodic equivalence relations, cohomology, and von Neumann algebras. I". Transactions of the American Mathematical Society. 234 (2): 289–324. doi:10.1090/S0002-9947-1977-0578656-4. ISSN 0002-9947.
Lu, Gao (September 5, 2019), Invariant Descriptive Set Theory, Chapman & Hall, pp. 157–177, ISBN 9780367386962