Correspondence

relation

A generalization of the notion of a binary relation (usually) between two sets or mathematical structures of the same type. Correspondences are widely used in mathematics and also in various applied disciplines, such as theoretical programming, graph theory, systems theory, and mathematical linguistics.

A correspondence between two sets $ A $ and $ B $ is any subset $ R $ of the Cartesian product $ A \times B $. In other words, a correspondence between $ A $ and $ B $ consists of certain ordered pairs $ ( a , b ) $, where $ a \in A $ and $ b \in B $. As a rule, a correspondence is denoted by a triple $ ( R , A , B ) $ and one may write $ a R b $ or $ R ( a , b ) $ in place of $ ( a , b ) \in R $. Instead of "correspondence" the term "binary relation" , or "relation between setsrelation" is sometimes used (in the general case where $ A $ and $ B $ need not coincide).

For finite sets, the matrix and graphical representations of a correspondence are commonly used. Suppose that $ A $ and $ B $ have $ n $ and $ m $ elements, respectively, and let $ ( R , A , B ) $ be some correspondence. One can describe this by using an $ n \times m $ matrix the rows and columns of which are labelled with the elements of $ A $ and $ B $, respectively, and the intersection of the $ a $- th row with the $ b $- th column contains 1 if $ ( a , b ) \in R $, and $ 0 $ otherwise. Conversely, every $ ( n \times m ) $- matrix consisting of zeros and ones describes a unique correspondence between $ A $ and $ B $. In the graphical representation, the elements of $ A $ and $ B $ are represented by points in the plane. These points are usually denoted by the same symbols as the corresponding elements. Then $ a $ and $ b $ are connected by an arrow (arc) from $ a $ to $ b $ if $ ( a , b ) \in R $. Thus, the correspondence is represented by an oriented graph.

The set of all correspondences between two sets $ A $ and $ B $ forms a complete Boolean algebra the zero of which is the empty correspondence and the identity of which is the so-called complete correspondence, consisting of all pairs $ ( a , b ) $, $ a \in A $, $ b \in B $. Let $ R \subseteq A \times B $. The set

$$ \mathop{\rm Dom} R = \ \{ {a \in A } : {\exists b ( a , b ) \in R } \} $$

is called the domain of definition of $ R $, and the set

$$ \mathop{\rm Ran} R = \ \{ {b \in B } : {\exists a ( a , b ) \in R } \} $$

is called the range, or image, of $ R $. The correspondence $ R $ is everywhere defined if $ \mathop{\rm Dom} R = A $, and surjective if $ \mathop{\rm Ran} R = B $. For every $ a \in A $ the set

$$ \mathop{\rm Im} _ {R} a = \ \{ {b \in B } : {( a , b ) \in R } \} $$

is called the image of $ a $ with respect to $ R $, and for every $ b \in B $, the set

$$ \mathop{\rm Coim} _ {R} b = \ \{ {a \in A } : {( a , b ) \in R } \} $$

is called the co-image (or pre-image) of $ b $ with respect to $ R $. Then

$$ \mathop{\rm Dom} R = \ \cup _ {b \in B } \mathop{\rm Coim} _ {R} b ,\ \ \mathop{\rm Ran} R = \ \cup _ {a \in A } \mathop{\rm Im} _ {R} a . $$

Any correspondence $ R $ establishes a Galois correspondence between the subsets of $ A $ and those of $ B $. Namely, to any subset $ X \subseteq A $, one assigns the subset $ X ^ { \prime } = \cup _ {a \in X } \mathop{\rm Im} _ {R} a \subseteq B $. Together with the dual correspondence $ S $, which assigns to every $ Y \subseteq B $ the set $ Y ^ { \prime } = \cup _ {b \in Y } \mathop{\rm Coim} _ {R} b $, the Galois correspondence defines a closure operator on both $ A $ and $ B $.

The inverse or involution $ R ^ {*} $, or $ R ^ {-} 1 $, of a correspondence $ ( R , A , B ) $ is defined by the equation

$$ R ^ {\#} = \{ {( b , a ) } : {( a , b ) \in R } \} . $$

This establishes a bijection between the correspondence $ ( R , A , B ) $ and $ ( R ^ {\#} , B , A ) $, which is an isomorphism of Boolean algebras. Given two correspondences $ ( R , A , B ) $ and $ ( S , B , C ) $, their product or composite is given by

$$ ( R S , A , C ) = \ \{ {( a , c ) } : {\exists b ( a , b ) \in R \wedge ( b , c ) \in S } \} . $$

Multiplication of correspondences is associative, and its identities are the diagonal binary relations. Moreover, $ ( R S ) ^ {\#} = S ^ {\#} R ^ {\#} $, and $ R _ {1} \subseteq R _ {2} $ implies that $ R _ {1} ^ {\#} \subseteq R _ {2} ^ {\#} $. Therefore the correspondences between a family of sets form an ordered category with involution. Multiplication and involution enable one to express the properties of correspondences in terms of algebraic relations. For example, a correspondence $ ( R , A , B ) $ is everywhere defined if $ R R ^ {\#} \supseteq E _ {A} $( $ E _ {A} $ is the diagonal of $ A $), and $ R $ is functional, that is, it is the graph of a function from $ A $ into $ B $, if $ R R ^ {\#} \supseteq E _ {A} $ and $ R ^ {\#} R \subseteq E _ {B} $.

For any correspondence $ R $, there are functional correspondences $ F $ and $ G $ such that $ R = F ^ {\#} G $. Moreover, $ R \subseteq R R ^ {\#} R $. Any difunctional correspondence induces equivalence relations on the domain and on the image whose quotient sets have the same cardinality. This only holds for difunctional correspondences.

Let $ \mathfrak A $ be a class of mathematical structures of the same type that is closed under finite Cartesian products. By a correspondence between two structures $ A , B \in \mathfrak A $, one means a substructure $ R $ of $ A \times B $. Thus one has group correspondences, module correspondences, ring correspondences, and others. Such correspondences often have useful descriptions of their structure. For example, let $ A $ and $ B $ be groups and let $ R $ be a subgroup of the direct product $ A \times B $. The sets

$$ \mathop{\rm Ker} R = \ \{ {a \in A } : {( a , b ) \in R } \} ,\ I _ {R} = \ \{ {b \in B } : {( 1 , b ) \in R } \} $$

are called the kernel and the indeterminacy of $ R $, respectively. $ \mathop{\rm Ker} R $ is a normal subgroup of $ \mathop{\rm Dom} R $, $ I _ {R} $ is a normal subgroup of $ \mathop{\rm Ran} R $, and the quotient groups $ ( \mathop{\rm Dom} R ) / \mathop{\rm Ker} R $ and $ ( \mathop{\rm Ran} R) / I _ {R} $ are isomorphic. It follows, in particular that all group correspondences are difunctional.

References

[1]	A.G. Kurosh, "Lectures on general algebra" , Chelsea (1963) (Translated from Russian) MR0158000 Zbl 0121.25901
[2]	A.I. Mal'tsev, "Algebraic systems" , Springer (1973) (Translated from Russian) Zbl 0266.08001
[3]	M.Š. [M.Sh. Tsalenko] Calenko, "Classification of correspondence categories and types of regularities for categories" Trans. Moscow Math. Soc. , 1 (1982) pp. 239–282 Trudy Moskov. Mat. Obshch. , 41 (1980) pp. 241–285

Comments

In algebraic geometry correspondences are used widely, [a1], Chapt. 2, 3. They are defined as the following slightly more technical concept. A correspondence $ Z $ between two (projective) varieties $ X $ and $ Y $ is defined by a closed algebraic subset $ Z \subset X \times Y $. It is said to be a rational mapping if $ Z $ is irreducible and there exists a Zariski-open subset $ X _ {0} \subset X $ such that each $ x \in X _ {0} $ is related by $ Z $ to one and only one point of $ Y $( i.e. $ \mathop{\rm card} \mathop{\rm Im} _ {Z} ( x) = 1 $). The correspondence $ Z $ is said to be a birational mapping if both $ Z $ and $ Z ^ {\#} $ are rational mappings.

References

[a1]	D. Mumford, "Algebraic geometry" , 1. Complex projective varieties , Springer (1976) MR0453732 Zbl 0356.14002