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  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   for more). In particular, the Feldman-Moore theorem described below proved useful in the study of certain Von Neumann algebras (see ). 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 . 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  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 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. 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  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 . 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 
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. 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   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 

Descriptive set theory
Binary relations