View source for Correspondence

''relation''

A generalization of the notion of a [[Binary relation|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c0266001.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c0266002.png" /> is any subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c0266003.png" /> of the Cartesian product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c0266004.png" />. In other words, a correspondence between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c0266005.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c0266006.png" /> consists of certain ordered pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c0266007.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c0266008.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c0266009.png" />. As a rule, a correspondence is denoted by a triple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660010.png" /> and one may write <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660011.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660012.png" /> in place of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660013.png" />. Instead of "correspondence" the term "binary relation" , or "relation between setsrelation" is sometimes used (in the general case where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660015.png" /> need not coincide).

For finite sets, the matrix and graphical representations of a correspondence are commonly used. Suppose that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660016.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660017.png" /> have <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660019.png" /> elements, respectively, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660020.png" /> be some correspondence. One can describe this by using an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660021.png" /> matrix the rows and columns of which are labelled with the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660022.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660023.png" />, respectively, and the intersection of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660024.png" />-th row with the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660025.png" />-th column contains 1 if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660026.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660027.png" /> otherwise. Conversely, every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660028.png" />-matrix consisting of zeros and ones describes a unique correspondence between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660029.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660030.png" />. In the graphical representation, the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660031.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660032.png" /> are represented by points in the plane. These points are usually denoted by the same symbols as the corresponding elements. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660033.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660034.png" /> are connected by an arrow (arc) from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660035.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660036.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660037.png" />. Thus, the correspondence is represented by an oriented graph.

The set of all correspondences between two sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660039.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660040.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660041.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660042.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660043.png" />. The set

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660044.png" /></td> </tr></table>

is called the domain of definition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660045.png" />, and the set

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660046.png" /></td> </tr></table>

is called the range, or image, of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660047.png" />. The correspondence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660048.png" /> is everywhere defined if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660049.png" />, and surjective if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660050.png" />. For every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660051.png" /> the set

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660052.png" /></td> </tr></table>

is called the image of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660053.png" /> with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660054.png" />, and for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660055.png" />, the set

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660056.png" /></td> </tr></table>

is called the co-image (or pre-image) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660057.png" /> with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660058.png" />. Then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660059.png" /></td> </tr></table>

Any correspondence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660060.png" /> establishes a [[Galois correspondence|Galois correspondence]] between the subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660061.png" /> and those of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660062.png" />. Namely, to any subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660063.png" />, one assigns the subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660064.png" />. Together with the dual correspondence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660065.png" />, which assigns to every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660066.png" /> the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660067.png" />, the Galois correspondence defines a closure operator on both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660068.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660069.png" />.

The inverse or involution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660070.png" />, or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660071.png" />, of a correspondence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660072.png" /> is defined by the equation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660073.png" /></td> </tr></table>

This establishes a bijection between the correspondence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660074.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660075.png" />, which is an isomorphism of Boolean algebras. Given two correspondences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660076.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660077.png" />, their product or composite is given by

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660078.png" /></td> </tr></table>

Multiplication of correspondences is associative, and its identities are the diagonal binary relations. Moreover, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660079.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660080.png" /> implies that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660081.png" />. Therefore the correspondences between a family of sets form an ordered [[Category with involution|category with involution]]. Multiplication and involution enable one to express the properties of correspondences in terms of algebraic relations. For example, a correspondence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660082.png" /> is everywhere defined if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660083.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660084.png" /> is the diagonal of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660085.png" />), and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660086.png" /> is functional, that is, it is the graph of a function from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660087.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660088.png" />, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660089.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660090.png" />.

For any correspondence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660091.png" />, there are functional correspondences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660092.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660093.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660094.png" />. Moreover, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660095.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660096.png" /> be a class of mathematical structures of the same type that is closed under finite Cartesian products. By a correspondence between two structures <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660097.png" />, one means a substructure <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660098.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c02660099.png" />. Thus one has group correspondences, module correspondences, ring correspondences, and others. Such correspondences often have useful descriptions of their structure. For example, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600100.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600101.png" /> be groups and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600102.png" /> be a subgroup of the direct product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600103.png" />. The sets

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600104.png" /></td> </tr></table>

are called the kernel and the indeterminacy of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600105.png" />, respectively. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600106.png" /> is a normal subgroup of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600107.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600108.png" /> is a normal subgroup of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600109.png" />, and the quotient groups <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600110.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600111.png" /> are isomorphic. It follows, in particular that all group correspondences are difunctional.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> A.G. Kurosh, "Lectures on general algebra" , Chelsea (1963) (Translated from Russian) {{MR|0158000}} {{ZBL|0121.25901}} </TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> A.I. Mal'tsev, "Algebraic systems" , Springer (1973) (Translated from Russian) {{MR|}} {{ZBL|0266.08001}} </TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> 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</TD></TR></table>



====Comments====
In algebraic geometry correspondences are used widely, [[#References|[a1]]], Chapt. 2, 3. They are defined as the following slightly more technical concept. A correspondence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600112.png" /> between two (projective) varieties <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600113.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600114.png" /> is defined by a closed algebraic subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600115.png" />. It is said to be a rational mapping if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600116.png" /> is irreducible and there exists a Zariski-open subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600117.png" /> such that each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600118.png" /> is related by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600119.png" /> to one and only one point of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600120.png" /> (i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600121.png" />). The correspondence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600122.png" /> is said to be a birational mapping if both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600123.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026600/c026600124.png" /> are rational mappings.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> D. Mumford, "Algebraic geometry" , '''1. Complex projective varieties''' , Springer (1976) {{MR|0453732}} {{ZBL|0356.14002}} </TD></TR></table>