Correspondence and relation

In general Algebra, the concept of correspondence , or relation , is an abstraction of concepts such as the equality, the alphabetical order, or the comparison.

In an abstract way, a relation in a unit (one also says “on a unit”) is a proposal which binds a certain number of elements. On a unit made up people, for example, one could define a relation “Alice loves Bernard”, or “Cecile knows David”… One can thus see a relation like wire connecting various elements of a unit.

This concept can be generalized by establishing bonds between elements of distinct units.

Graph and correspondence

The bond between two elements can be expressed in a more formal way by a “couple”. A couple , noted between brackets, consists of two elements put in a particular order. The correspondences , or general relations can thus be regarded in first approach as whole of couples, i.e. directed graphs . But that is not always enough:

the properties of the correspondences depend as much on the absences of bonds between elements as of their existence.

In other words, the data of the graph of a correspondence is not enough to define this one completely; it is also necessary to know which are the couples of elements which it does not bind. That amounts specifying in which Produit Cartesian fits the correspondence.

Nevertheless, it remains possible, generally, to confuse a correspondence with its graph, since there is no ambiguity on the Cartesian product in which it fits.

To illustrate these ideas, let us consider for example the unit P according to people:

$P\; =\; \backslash \; \{Alice,\; Bernard\; \backslash \}\; \backslash ,$

There let us define naively the relation likes by the only data of its graph:

$likes\; =\; \backslash \; \{(Alice,\; Bernard),\; (Alice,\; Alice),\; (Bernard,\; Bernard)\; \backslash \}\; \backslash ,$

For the relation likes , if “Alice likes Bernard”, then the couple (Alice, Bernard) belonged to the unit likes .

The unit likes is a subset of P × P . We note that:

• the relation likes is a binary Relation in P ;
• the relation likes is reflexive , since all the people considered like themselves.

Let us notice in the passing that the order in the couple has importance. If “Alice likes Bernard”, the Réciproque is not inevitably true, and besides here   ( Bernard , Alice ) does not belong to likes .

Let us add a person to P . The whole of the people becomes:

$Q\; =\; \backslash \; \{Alice,\; Bernard,\; Christian\; \backslash ,\; \backslash \}$

likes is still a subset of Q × Q , but the relation likes is not more reflexive : the simple presence of Christian modified the relation, even if no bond were added.

In fact, the relation likes in Q must be distinguished from the relation likes in P , even if they have both the same graph. For that purpose, the simplest idea is to consider that a relation comprises not only one graph, but also the Cartesian product in which it fits: if likes always indicates the graph, the relations become then:

$(P\; \backslash \; times\; P,\; likes)\; \backslash \; quad\; and\; \backslash \; quad\; (Q\; \backslash \; times\; Q,\; likes)\; \backslash ,$,

or, which returns in practice to same:

$(P,\; P,\; like)\; \backslash \; quad\; and\; \backslash \; quad\; (Q,\; Q,\; like)\; \backslash ,$.

This way of proceeding still comprises however a defect: she does not make it possible to generalize the relations with the clean classes , since the elements of tuples must be units. That poses problem with the relation of equipotence for example, which is at the base of the definition of the cardinal , and which is supposed being defined in the class of all the units.

A solution (already interview in the article “Produces Cartesian”) consists in replacing the preceding triplets by disjoined sums : the two preceding relations will be then defined like:

$\backslash \; dowry\; \backslash \; cup\; (P,\; P,\; like)\; \backslash \; quad\; and\; \backslash \; quad\; \backslash \; dowry\; \backslash \; cup\; (Q,\; Q,\; like)\; \backslash ,$,

but still noted however by abuse writing:

$(P,\; P,\; like)\; \backslash \; quad\; and\; \backslash \; quad\; (Q,\; Q,\; like)\; \backslash ,$.

; Notice

above the advance is characteristic of the step of the mathematicians when they work out a definition: they start from a first simple approach, which they then improve by complicating it to eliminate from internal contradictions or to take into account certain particular cases, then that they generalize to the maximum.

Formal definition

Preliminary notes

• to reduce the writing, we will note starting from here the disjoined sums like tuples .

• the following definitions remain thus valid if one replaces the units there by clean classes even .

Definition

a correspondence , or general relation , is the disjoined sum of three units of which the last is part of the Cartesian product of the first by the second .

More precisely, if E and F is two units, then $\backslash \; mathfrak\; \{C\}$ is a correspondence of E in F if and only if:

$\backslash \; exists\; \backslash \; G\; \backslash /\backslash \; (\backslash \; mathfrak\; \{C\}\; =\; (E,\; F,\; G))\; \backslash \; wedge\; (G\; \backslash \; subseteq\; E\; \backslash \; times\; F)$

E is the whole starting of the correspondence, F its together of arrival and G its graph .

In practice, one will confuse a correspondence with his graph if there is no ambiguity on arrival and the starting whole.

Equality of two correspondences

According to their definition, two correspondences are equal if and only if they have same arrival and starting whole and even graph.

In other words, if   $\backslash \; mathfrak\; \{C\}\; \_1$ = ( E ₁, F ₁, G ₁)   and if   $\backslash \; mathfrak\; \{C\}\; \_2$ = ( E ₂, F ₂, G ₂), then:

$(\backslash \; mathfrak\; \{C\}\; \_1\; =\; \backslash \; mathfrak\; \{C\}\; \_2)\; \backslash \; Leftrightarrow\; (E\_1\; =\; E\_2)\; \backslash \; wedge\; (F\_1\; =\; F\_2)\; \backslash \; wedge\; (G\_1\; =\; G\_2)\; \backslash ,$.

Important examples and particular cases

• Etudier which are the sports practiced by the French amounts establishing a correspondence of the whole of the French in the whole of the possible sports.

• If E = {has, B, C, D}, F = {1,2,3} and if G = {(has, 1), (B, 2), (B, 3), (C, 3)}, then (E, F, G) is a correspondence of E in F.

• a correspondence is empty if and only if its graph is equal to the empty set.

• a correspondence is full if and only if its graph is equal to the Cartesian product of entire arrival and the starting whole.

• the relation in E whose graph is the diagonal of E is called identity E , and is usually noted “$Id\_E\; \backslash ,$”.

• the starting whole of a correspondence can be the Cartesian product of two units or more: thus, the addition of the real numbers is a correspondence of $\backslash \; mathbb\; \{R\}\; \backslash \; times\; \backslash \; mathbb\; \{R\}\; \backslash ,$ in $\backslash \; mathbb\; \{R\}\; \backslash ,$. It seems obvious that the addition comprises two arguments; but in fact, the number of arguments of a correspondence depends on the adopted point of view and is thus not an intrinsic property: thus, one can consider that the addition has only one argument, the couple formed by the two added numbers!

Representation of the correspondences

There exist three types of representation of a correspondence:

• sagittal , which derives from the Venn diagrams for the units, where arrival and the starting whole is represented by two “patatoïdes” side by side, the elements by points inside the patatoïdes, and the couples of the graph by arrows connecting the first components to the seconds;
• tabular or matric , in the form of a table at two entries, with in first column the list of the elements of the starting whole and in first line that of the elements of the whole of arrival. The couples are represented by crosses in the boxes with the intersection of the line of the first component and the column of the second component;

• graphic , with a horizontal axis whose points represent the elements of the starting whole, and a vertical axis whose points represent the elements of the whole of arrival. The couples are represented by the points with the intersection of the vertical line cutting the horizontal axis with the site of the first component, and the horizontal line cutting the vertical axis with the site of the second component. Traditionally, the cloud of the points of the graph is located above and on the right axes.

Relations N - surfaces

The starting whole of a correspondence can be a Cartesian product. Thus, we saw that the addition of the real numbers has as a starting whole $\backslash \; mathbb\; \{R\}\; \backslash \; times\; \backslash \; mathbb\; \{R\}\; \backslash ,$, and that there was an ambiguity on its number of arguments. This ambiguity can be distinct by taking as reference the whole of arrival: in this case, the addition presents two arguments.

More generally, the correspondences whose starting whole is a Cartesian product where figure the whole of arrival play a big role. In fact, as any unit can be seen like a Cartesian product with only one operand, it is possible to regard any starting whole as a Cartesian product, and to classify the correspondences according to the presence or not of the whole of arrival in this Cartesian product.

Within this framework, let us start by defining the concepts of internal relations and external .

Internal and external relations

A relation interns or relation in a unit or relation on a unit is a correspondence whose starting whole is a Cartesian power of the whole of arrival.

A external relation is a correspondence whose starting whole is the Cartesian product of a whole known as of scalar or of operators by a Cartesian power of the whole of arrival.

More precisely, if E and S is two units:

- $\backslash \; mathfrak\; \{R\}$ is a relation in E , therefore intern if:

$\backslash \; exists\; \backslash \; G\; \backslash ,\; \backslash \; exists\; \backslash \; N\; \backslash \; in\; \backslash \; mathbb\; \{NR\}\; \backslash /\backslash \; (N\; \backslash \; geq\; 2)\; \backslash \; wedge\; (\backslash \; mathfrak\; \{R\}\; =\; (E^\; \{\backslash ,\; n-1\},\; E,\; G\; \backslash ,))\; \backslash \; wedge\; (G\; \backslash \; subseteq\; E^\; \{\backslash ,\; N\}\; \backslash ,)$

- $\backslash \; mathfrak\; \{R\}$ is a relation on the left on E with operators in S , therefore external on the left if:

$\backslash \; exists\; \backslash \; G\; \backslash ,\; \backslash \; exists\; \backslash \; N\; \backslash \; in\; \backslash \; mathbb\; \{NR\}\; \backslash /\backslash \; (N\; \backslash \; geq\; 3)\; \backslash \; wedge\; (\backslash \; mathfrak\; \{R\}\; =\; (S\; \backslash \; times\; E^\; \{\backslash ,\; N2\},\; E,\; G\; \backslash ,))\; \backslash \; wedge\; (G\; \backslash \; subseteq\; S\; \backslash \; times\; E^\; \{\backslash ,\; n-1\}\; \backslash ,)$

- $\backslash \; mathfrak\; \{R\}$ is a relation on the right on E with operators in S , therefore external on the right if:

$\backslash \; exists\; \backslash \; G\; \backslash ,\; \backslash \; exists\; \backslash \; N\; \backslash \; in\; \backslash \; mathbb\; \{NR\}\; \backslash /\backslash \; (N\; \backslash \; geq\; 3)\; \backslash \; wedge\; (\backslash \; mathfrak\; \{R\}\; =\; (E^\; \{\backslash ,\; N2\}\; \backslash \; times\; S,\; E,\; G\; \backslash ,))\; \backslash \; wedge\; (G\; \backslash \; subseteq\; E^\; \{\backslash ,\; N2\}\; \backslash \; times\; S\; \backslash \; times\; E\; \backslash ,)$

So that these definitions are coherent, S should not be a Cartesian product where E figure (the case S = E however is tolerated by abuse language: an internal relation is then seen like an external relation in E with operators in E itself).

The correspondences of S in E where S is neither E , nor a Cartesian product comprising E do not raise of these definitions, but can be seen like external relations in E with the borderline case where N = 2. S is then the whole of the operators (without specifying on the left or on the right, both merging).

Besides this case, if it is not specified if an external relation is on the left or on the right , and if the context does not make it possible to raise ambiguity, then it is on the left . In the same way, if it is not specified if a relation is internal , external or general , and if the context does not make it possible to raise ambiguity, then it is internal . To speak about the relations to the general direction of the term, it will be to better specify general relation , or to employ the term of correspondence .

Arite of a relation

The number N intervening in the preceding definitions is called arite relation. This one is known as N - surface; as follows:

• a binary Relation intern , of arite 2, is a correspondence whose arrival and starting whole is the same ones. In other words, if E is a unit, $\backslash \; mathfrak\; \{R\}$ is a binary relation in E if it is a correspondence of E in E , i.e. if:

$\backslash \; exists\; \backslash \; G\; \backslash /\backslash \; (\backslash \; mathfrak\; \{R\}\; =\; (E,\; E,\; G\; \backslash ,))\; \backslash \; wedge\; (G\; \backslash \; subseteq\; E\; \backslash \; times\; E\; \backslash ,)\; \backslash ,$

• a external binary relation , still of arite 2, is a correspondence of a unit S in a unit E , where S is not a Cartesian product whose E is a component; in other words, if E and S is two units, $\backslash \; mathfrak\; \{R\}$ is a external binary relation of S in E if:

$\backslash \; exists\; \backslash \; G\; \backslash /\backslash \; (\backslash \; mathfrak\; \{R\}\; =\; (S,\; E,\; G\; \backslash ,))\; \backslash \; wedge\; (G\; \backslash \; subseteq\; S\; \backslash \; times\; E\; \backslash ,)\; \backslash ,$

• a ternary Relation interns , of arite 3, is a correspondence whose starting whole is the Cartesian square of the whole of arrival; in other words, if E is a unit, $\backslash \; mathfrak\; \{R\}$ is a ternary relation interns in E if:

$\backslash \; exists\; \backslash \; G\; \backslash /\backslash \; (\backslash \; mathfrak\; \{R\}\; =\; (E\; \backslash \; times\; E,\; E,\; G\; \backslash ,))\; \backslash \; wedge\; (G\; \backslash \; subseteq\; E^\; \{\backslash ,\; 3\}\; \backslash ,)\; \backslash ,$

• a external ternary Relation on the left (resp. on the right ) is a correspondence whose starting whole is the Cartesian product of a unit S of scalar by the whole of arrival (resp. of the whole of arrival by a unit S of scalars); in other words, if E and S is two units: , $\backslash \; mathfrak\; \{R\}$ is a external ternary relation in E with operators in S :

- on the left if:   $\backslash \; exists\; \backslash \; G\; \backslash /\backslash \; (\backslash \; mathfrak\; \{R\}\; =\; (S\; \backslash \; times\; E,\; E,\; G\; \backslash ,))\; \backslash \; wedge\; (G\; \backslash \; subseteq\; S\; \backslash \; times\; E^\; \{\backslash ,\; 2\}\; \backslash ,)\; \backslash ,$

- on the right if:   $\backslash \; exists\; \backslash \; G\; \backslash /\backslash \; (\backslash \; mathfrak\; \{R\}\; =\; (E\; \backslash \; times\; S,\; E,\; G\; \backslash ,))\; \backslash \; wedge\; (G\; \backslash \; subseteq\; E\; \backslash \; times\; S\; \backslash \; times\; E\; \backslash ,)\; \backslash ,$

Once again, the unit S above should not be a Cartesian product whose whole of arrival E is a component.

In practice, one seldom considers higher arite relations, because they can always break up into binary or ternary relations.

Examples

• the equality and inclusion are binary relations in the class of the units.

• the meeting, the intersection, the difference and the symmetrical difference are internal ternary relations in the class of the units.

• If has , B and C is three disjoined units two to two:

* any relation of has in has is binary internal ;

* any relation of has in B is binary external ;

* any relation of has X has in has is ternary internal ;

* any relation of has X has in B is scalar (see following paragraph);

* any relation of has X B in has is on the right ternary external ;

* any relation of has X B in B is on the left ternary external ;

* and finally, any relation of has X B in C is binary external (for arite, the reference is the whole of arrival! );

Scalar relations

A scalar Relation is a correspondence of a unit E ² in a unit S , where S is not a Cartesian product whose whole E is a component; it is thus a external binary relation whose starting whole is a Cartesian square.

The scalar name of relation can be wide if the starting whole is not a Cartesian square, but a Cartesian power of a nature N higher than 2. The value n+1 is sometimes called scalar arite of the relation, not to confuse with arite defined previously (always equalizes to 2 for a scalar relation).

Functions

Images and antecedents

If $\backslash \; mathfrak\; \{C\}$ is a correspondence, with $\backslash \; mathfrak\; \{C\}\; =\; (E,\; F,\; G)$, then the following assertions are equivalent:

- corresponds there to X by $\backslash \; mathfrak\; \{C\}$;

- ( X , there ) belongs to G ;

- is there image of X by $\backslash \; mathfrak\; \{C\}$;

- X is previous of there by $\backslash \; mathfrak\; \{C\}$.

The term of “préimage” is sometimes employed in the place of that of “antecedent”.

“ corresponds there to X by $\backslash \; mathfrak\; \{C\}$” can be noted:

• “( X , there ) ∈ G ($\backslash \; mathfrak\; \{C\}$)”   (notation ensemblist )
• “( X , there ) $\backslash \; mathfrak\; \{C\}$”   (relational notation postfixée )
• “$\backslash \; mathfrak\; \{C\}$ ( X , there )”   (relational notation prefixed )
• “ X $\backslash \; mathfrak\; \{C\}$ there ”   (relational notation infix )

This last notation, except the particular case, most practical and consequently is used.

The unit formed by the images of all the elements of the starting whole of a correspondence is called together-image this correspondence. It is usually noted “$Im\; \backslash \; mathfrak\; \{C\}$”. An abuse current language consists in calling this unit “image” of the correspondence, but that can involve a confusion if the correspondence is itself element of a unit from which another correspondence is built.

Symmetrically, the unit formed by the antecedents of all the elements of the whole of arrival of a correspondence is called together-antecedent this correspondence. It is usually noted “$Ant\; \backslash \; mathfrak\; \{C\}$”. The together-antecedent is also named “field of definition” of the correspondence, and then noted “$Dom\; \backslash \; mathfrak\; \{C\}$” or “$D\; \backslash \; mathfrak\; \{C\}$”, but this last name is rather reserved for the functions (below).

Functions, applications and bijections

Basic properties

A correspondence can have four basic properties independent from/to each other. It can be:

• functional : any element of the starting whole has with more the one image :

$\backslash \; forall\; \backslash ,\; (X,\; y\_1,\; y\_2)\; \backslash \; in\; E\; \backslash \; times\; F^\; \{\backslash ,\; 2\},\; (X\; \backslash ,\; \backslash \; mathfrak\; \{C\}\; \backslash ,\; y\_1\; \backslash \; wedge\; X\; \backslash ,\; \backslash \; mathfrak\; \{C\}\; \backslash ,\; y\_2)\; \backslash \; Rightarrow\; (y\_1\; =\; y\_2)$

• applicative : any element of the starting whole has at least an image :

$\backslash \; forall\; \backslash ,\; X\; \backslash \; in\; E,\; \backslash \; exists\; \backslash ,\; there\; \backslash \; in\; F\; \backslash /\backslash \; X\; \backslash ,\; \backslash \; mathfrak\; \{C\}\; \backslash ,\; there\; \backslash ,$

• injective : any element of the whole of arrival has with more the one antecedent :

$\backslash \; forall\; \backslash ,\; (x\_1,\; x\_2,\; there)\; \backslash \; in\; E^\; \{\backslash ,\; 2\}\; \backslash \; times\; F,\; (x\_1\; \backslash ,\; \backslash \; mathfrak\; \{C\}\; \backslash ,\; there\; \backslash \; wedge\; x\_2\; \backslash ,\; \backslash \; mathfrak\; \{C\}\; \backslash ,\; there)\; \backslash \; Rightarrow\; (x\_1\; =\; x\_2)\; \backslash ,$

• surjective : any element of the whole of arrival has at least an antecedent :

$\backslash \; forall\; \backslash ,\; there\; \backslash \; in\; F,\; \backslash \; exists\; \backslash ,\; X\; \backslash \; in\; E\; \backslash /\backslash \; X\; \backslash ,\; \backslash \; mathfrak\; \{C\}\; \backslash ,\; there\; \backslash ,$.

; Equivalent definitions

a correspondence is applicative if and only if its together-antecedent merges with its starting whole, i.e. if: $\backslash \; Ant\; \backslash \; mathfrak\; \{C\}\; =\; E$.

a correspondence is surjective if and only if its together-image merges with its whole of arrival, i.e. if: $\backslash \; Im\; \backslash \; mathfrak\; \{C\}\; =\; F$.

Derived properties

By combining these four basic properties, we obtain a priori 16 kinds of correspondences, but only 9 of them have a qualifier. It is possible to summarize these properties and their definition in the following table:

Some of the combinations of the four basic properties received a name, because of their practical importance:

• a function is a functional correspondence . Each starting element has with more the one image. One can thus speak about his image without ambiguity, and indicate it by a symbol, usually “R ( X )” if the function is noted “R”. That makes it possible to replace the relational notation “ X R there ” by the functional notation “ there = R ( X )” more practical;

• a application is a applicative function . It is thus also a functional correspondence and applicative , i.e. a univocal correspondence . As it is applicative , its field of definition merges with its starting whole;

• a injection is a injective mapping . It is thus a functional correspondence , applicative and injective , i.e. a applicative correspondence and bifunctional ;

• a Surjection is a surjective mapping . It is thus a functional correspondence , applicative and surjective , i.e. a biapplicative function . As it is surjective , its image is not other than the whole of entire arrival;

• a Bijection is a bijective mapping . It is thus a functional correspondence , applicative , injective and surjective , i.e. a bi-univocal correspondence .

; Caution!

a applicative correspondence (respectively injective, surjective, bijective) is not in general an application (respectively an injection, a surjection, a bijection).

In the same way, a injective function (respectively surjective, bijective) is not in general an injection (respectively a surjection, a bijection).

Reciprocal correspondence

The concepts of image and previous are dual. To exchange their role amounts exchanging between them the components of each couple of the graph, therefore to replace each couple ( X , there ) by its reciprocal couple ( there , X ).

The reciprocal graph of a graph $G$, noted “$G^\; \{-\; 1\}$”, is the graph resulting from such an exchange:

$G^\; \{-\; 1\}\; =\; \backslash \; \{(there,\; X)\; |\; (X,\; there)\; \backslash \; in\; G\; \backslash \}$

The reciprocal correspondence of a correspondence is the correspondence obtained by exchanging arrival and the starting whole and replacing the graph by its reciprocal graph.

In other words, if $\backslash \; mathfrak\; \{C\}\; =\; (E,\; F,\; G)$, then: $\backslash \; mathfrak\; \{C\}\; ^\; \{-\; 1\}\; =\; \backslash \; left\; (F,\; E,\; G^\; \{-\; 1\}\; \backslash \; right)$

The reciprocal one of reciprocal of a correspondence is not other than this correspondence:

$\backslash \; left\; (\backslash \; mathfrak\; \{C\}\; ^\; \{-\; 1\}\; \backslash \; right)\; ^\; \{-\; 1\}\; =\; \backslash \; mathfrak\; \{C\}$

It is enough to read the table of the combinations of the basic properties of the correspondences (see higher), by exchanging the role of the images and the antecedents, to obtain the properties of the reciprocal ones. As follows:

• the reciprocal of a ''''' function ''''' is an injective correspondence . Conversely, so that the reciprocal one of a correspondence is a function, it is necessary and it is enough that this correspondence is injective;
• the reciprocal one of a applicative correspondence is surjective , and vice versa ;
• the reciprocal of a ''''' application ''''', i.e. of a univocal correspondence , is a bijective correspondence . Conversely, so that the reciprocal one of a correspondence is an application, it is necessary and it is enough that this correspondence is bijective;
• the reciprocal one of a bifunctional correspondence , i.e. of an injective function, is a bifunctional correspondence , i.e. an injective function;
• the reciprocal one of a biapplicative correspondence is itself biapplicative ;
• Lastly, the reciprocal one of a bijection , i.e. of a bi-univocal correspondence , is a bijection .

Classification of the correspondences

; Remarks

(*) on the left or on the right.

• ) the internal ternary relations can be bijections only if the cardinal of their whole of arrival is infinite or equal to 0 or to 1.

We find in this table the two families of concepts defined higher, relations and functions , and their combinations:

• a transformation in a unit is a application of this whole in itself, therefore a binary relation in this unit;

• a permutation in a unit is a bijection of a whole in itself, therefore a binary relation in this unit. It is thus a particular case of transformation ;
• a operation is a correspondence which is at the same time a ternary relation and a function ;
• a law of composition (name often shortened in law ) is a correspondence which is at the same time a ternary relation and a application. The laws are thus particular operations .

Thus, the four operations of our childhood (+, −, ×, ÷) are indeed internal operations in $\backslash \; mathbb\; \{NR\}$. But only the addition and the multiplication are there laws of composition .

See too

• Set theory

• overall Notion
• Sous-ensemble
• Opérations on the units
• Produit Cartesian
• Opération on binary Welshman correspondences
• Correspondance
• Relation
• Fonction
• Relation of ternary Chasles
• Relation interns
• external ternary Relation
• scalar Relation
• Law of composition
• Relation of order
• relational Databases

Random links:

Afonso III de Portugal | Universal declaration of the human rights | Bayindir | Bonnie Turner | Marías islands | Sea of Hébrides | Liste_de_massacres

© 2007-2008 speedlook.com; article text available under the terms of GFDL, from fr.wikipedia.org