Namespaces
Variants
Actions

Difference between revisions of "Correspondence"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (MR/ZBL numbers added)
Line 3: Line 3:
 
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 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).
+
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.
 
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.
Line 48: Line 48:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> A.G. Kurosh,   "Lectures on general algebra" , Chelsea (1963) (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> A.I. Mal'tsev,   "Algebraic systems" , Springer (1973) (Translated from Russian)</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>
+
<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>
  
  
Line 56: Line 56:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> D. Mumford,   "Algebraic geometry" , '''1. Complex projective varieties''' , Springer (1976)</TD></TR></table>
+
<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>

Revision as of 21:51, 30 March 2012

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 and is any subset of the Cartesian product . In other words, a correspondence between and consists of certain ordered pairs , where and . As a rule, a correspondence is denoted by a triple and one may write or in place of . Instead of "correspondence" the term "binary relation" , or "relation between setsrelation" is sometimes used (in the general case where and need not coincide).

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

The set of all correspondences between two sets and 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 , , . Let . The set

is called the domain of definition of , and the set

is called the range, or image, of . The correspondence is everywhere defined if , and surjective if . For every the set

is called the image of with respect to , and for every , the set

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

Any correspondence establishes a Galois correspondence between the subsets of and those of . Namely, to any subset , one assigns the subset . Together with the dual correspondence , which assigns to every the set , the Galois correspondence defines a closure operator on both and .

The inverse or involution , or , of a correspondence is defined by the equation

This establishes a bijection between the correspondence and , which is an isomorphism of Boolean algebras. Given two correspondences and , their product or composite is given by

Multiplication of correspondences is associative, and its identities are the diagonal binary relations. Moreover, , and implies that . 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 is everywhere defined if ( is the diagonal of ), and is functional, that is, it is the graph of a function from into , if and .

For any correspondence , there are functional correspondences and such that . Moreover, . 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 be a class of mathematical structures of the same type that is closed under finite Cartesian products. By a correspondence between two structures , one means a substructure of . Thus one has group correspondences, module correspondences, ring correspondences, and others. Such correspondences often have useful descriptions of their structure. For example, let and be groups and let be a subgroup of the direct product . The sets

are called the kernel and the indeterminacy of , respectively. is a normal subgroup of , is a normal subgroup of , and the quotient groups and 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 between two (projective) varieties and is defined by a closed algebraic subset . It is said to be a rational mapping if is irreducible and there exists a Zariski-open subset such that each is related by to one and only one point of (i.e. ). The correspondence is said to be a birational mapping if both and are rational mappings.

References

[a1] D. Mumford, "Algebraic geometry" , 1. Complex projective varieties , Springer (1976) MR0453732 Zbl 0356.14002
How to Cite This Entry:
Correspondence. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Correspondence&oldid=23799
This article was adapted from an original article by M.Sh. Tsalenko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article