Relation of equivalence

The concept of relation of equivalence on a Ensemble makes it possible to put in relation elements which are similar by a certain property.

One will be able to thus gather these elements by “packages” of elements which resemble each other, thus defining the concept of class of equivalence , for finally building new whole in “comparing” the similar elements to a single element. One leads then to the concept of unit quotient .

Definition

Formal definition

A relation of equivalence $\backslash \; mathcal\; R\; \backslash ,$ in a $E$ unit is a binary Relation which is at the same time reflexive , symmetrical and transitive .

• It is a binary relation : it is thus a disjoined sum $(E,\; E,\; G\_\; \{\backslash \; mathcal\; R\})$, where $G\_\; \{\backslash \; mathcal\; R\}$, the graph of $\backslash \; mathcal\; R\; \backslash ,$, is part of $E^2$ characterizing the relation. In practice, except ambiguity on the unit in which the relation is placed, one can confuse this one with his graph. If $x$ and $y$ are two elements of $E$, it is said that “$y$ is image of $x$ by $\backslash \; mathcal\; R\; \backslash ,$” or that “$y$ is associated with $x$ by $\backslash \; mathcal\; R\; \backslash ,$” or that “$y$ corresponds to $x$ by $\backslash \; mathcal\; R\; \backslash ,$” if the couple $(X,\; there)$ belongs to $G\_\; \{\backslash \; mathcal\; R\}$; one notes that “$x\; \backslash \; mathcal\; R\; \backslash ,\; y$”.

• $\backslash \; mathcal\; R\; \backslash ,$ is reflexive : any element of $E$ is associated with itself:   $\backslash \; forall\; \backslash \; X\; \backslash \; in\; E,\; X\; \backslash \; mathcal\; R\; X\; \backslash ,$

• $\backslash \; mathcal\; R\; \backslash ,$ is symmetrical : any element of $E$ is image of its images:

$\backslash \; forall\; \backslash \; (X,\; there)\; \backslash \; in\; E^\; \{\backslash ,\; 2\},\; (X\; \backslash \; mathcal\; R\; there)\; \backslash \; Rightarrow\; (there\; \backslash \; mathcal\; R\; X)\; \backslash ,$

• $\backslash \; mathcal\; R\; \backslash ,$ is transitive : any image of an image of an element of $E$ is directly image of this element:

$\backslash \; forall\; \backslash \; (X,\; there,\; Z)\; \backslash \; in\; E^\; \{\backslash ,\; 3\},\; (X\; \backslash \; mathcal\; R\; there\; \backslash \; wedge\; there\; \backslash \; mathcal\; R\; Z)\; \backslash \; Rightarrow\; (X\; \backslash \; mathcal\; R\; Z)\; \backslash ,$

Equivalent definition

One can also define a relation of equivalence like a binary relation reflexive and circular .

A binary relation is circular if any image of an image of an element of $E$ is previous of this element, i.e. if:

$\backslash \; forall\; \backslash \; (X,\; there,\; Z)\; \backslash \; in\; E^\; \{\backslash ,\; 3\},\; (X\; \backslash \; mathcal\; R\; there\; \backslash \; wedge\; there\; \backslash \; mathcal\; R\; Z)\; \backslash \; Rightarrow\; (Z\; \backslash \; mathcal\; R\; X)\; \backslash ,$

Classify equivalence

Let us consider a nonempty unit $E$ provided with a relation of equivalence $\backslash \; mathcal\; R\; \backslash ,$. The class of equivalence of an element $x$ of $E$, noted “$\backslash \; mathcal\; R\; (X)$”, is then the whole of the images of $x$ by $\backslash \; mathcal\; R\; \backslash ,$:

$\backslash \; mathcal\; R\; (X)\; =\; \backslash \; \{there\; \backslash \; in\; E\; \backslash ,|\backslash \; X\; \backslash \; mathcal\; R\; there\; \backslash \}\; \backslash ,$.

• $\backslash \; mathcal\; R\; (X)$ is a subset of $E$.

• $\backslash \; mathcal\; R\; (X)$ is never empty, because it contains always at least $x$ itself ($\backslash \; mathcal\; R\; \backslash ,$ is reflexive).

• Conversely, any element of $E$ belongs to at least a class of equivalence: his.

• $\backslash \; mathcal\; R\; (there)\; =\; \backslash \; mathcal\; R\; (X)$ if $y$ belongs to $\backslash \; mathcal\; R\; (X)$.

• Conversely, if $y$ is an element of $E$ not belonging to $\backslash \; mathcal\; R\; (X)$, then the intersection of $\backslash \; mathcal\; R\; (X)$ and of $\backslash \; mathcal\; R\; (there)$ is empty.

One deduces from what precedes that the unit by the classes of equivalence of $E$ form a partition of $E$. Conversely, any partition of a unit defines a relation of equivalence in it. One can establish a canonical Bijection between the partitions of a unit and the relations of equivalence in this unit.

Lastly, the restriction of a relation of equivalence on the one of its classes of equivalence is a full relation.

Quotient unit

It is the together classes of equivalence of $E$ according to $\backslash \; mathcal\; R$.

Definition

The unit quotient of $E$ by the relation of equivalence $\backslash \; mathcal\; R$, noted “$E/\backslash \; mathcal\; R$”, is the whole of the classes of equivalence of $E$ according to $\backslash \; mathcal\; R$:

$E/\backslash \; mathcal\; R\; =\; \backslash \; \{\backslash \; mathcal\; R\; (X)\; \backslash ,|\backslash \; X\; \backslash \; in\; E\; \backslash \}\; \backslash ,$

The quotient unit is thus a new unit built starting from $E$ and of $\backslash \; mathcal\; R$. It is a subset of $\backslash \; mathfrak\; P$ ($E$), together of the parts of $E$.

Note: one can provide a clean class with a relation of equivalence. One can even define classes of equivalence in it, but as they can be themselves of the clean classes, that prohibits the existence of a quotient unit in this case. For example, if one considers the relation of equipotence in the class of the units, this relation is a relation of equivalence, and one can define classes of equivalence in it known as “classes of equipotence”:

• the class of equipotence of the empty set is thus the singleton formed by the empty set, since it can be put in bijection only with itself;
• let us singletons them form another class of equipotence; but it is about a clean class, which prohibits to form a whole (or a class) starting from the classes of equipotence (and, incidentally, to identify the classes of equipotence to the cardinals).

The quotient unit can also be indicated like “the unit $E$ quotienté by $\backslash \; mathcal\; R$” or “the $E$ unit considered modulo $\backslash \; mathcal\; R$”. The idea behind these names is to work as a whole quotient as in $E$, but without distinguishing between them the equivalent elements according to $\{\backslash \; mathcal\; R\}$.

Example

The whole of the relative whole can be provided with the relation “has the same sign as” (including in a strict sense). There are three classes of equivalence:

1. the unit $\backslash \; mathbb\; Z\_+^*$ of the strictly positive entireties,
2. the unit $\backslash \; mathbb\; Z\_-^*$ of the strictly negative entireties,
3. the singleton {0}.

One can note these three classes by, respectively, (+), (-) and (0).

One knows the “rule of the signs” for the product of two relative entireties: it shows that if one knows in which class of equivalence X are and there, the product xy is in a well defined class. For example, if X is in (+) and there in (0), then xy is in (0). Formally, one can note it (+). (0) = (0). In the same way (+). (-) = (-), or (+). (+) = (+), (-). (-) = (+) etc This is a simple example of law-quotient .

But with this example one cannot “make pass to the quotient” the law +: what to say sum of an element of (+) and an element of (-)? To know if the laws and the properties of structure are compatible with the passage to the quotient, it is useful to introduce the concept of surjection canonical.

Canonical Surjection

There exists a canonical surjection $s$ of $E$ as a whole quotient, which with each element of $E$ associates its class of equivalence:

$s$   :   $E\; \backslash \; longrightarrow\; E/\backslash \; mathcal\; R\; \backslash ,$

$X\; \backslash \; longmapsto\; \backslash \; has\; =\; \backslash \; mathcal\; R\; (X)\; \backslash ,$

$s$ is a application since any element of $E$ belongs to one and only one class of equivalence; $s$ is surjective since no class of equivalence is empty.

$s$ is not in general injective , but one a:

$\backslash \; forall\; X\; \backslash \; in\; E,\; \backslash \; forall\; there\; \backslash \; in\; E,\; \backslash ,\; S\; (X)\; =\; S\; (there)\; \backslash \; Leftrightarrow\; \backslash \; mathcal\; R\; (X)\; =\; \backslash \; mathcal\; R\; (there)\; \backslash \; Leftrightarrow\; X\; \backslash \; mathcal\; R\; there\; \backslash ,$

This surjection is thus a bijection if the relation of equivalence concerned is not other than the relation of equality.

Structure quotient

Thanks to the surjection $s$, if $E$ is provided with a structure, it is possible to transfer the latter to the quotient unit, provided the structure is compatible with the relation of equivalence, i.e. two elements of $E$ behave same manner with respect to the structure if they belong to the same class of equivalence. The quotient unit is then provided with the structure quotient of the initial structure by the relation of equivalence.

For example, if $E$ is provided with a structure of group, it is possible, in certain cases, of speaking about the Groupe quotient $E/\backslash \; mathcal\; R$.

Examples

• the equality on an unspecified whole of numbers (whole, rational, real, complex) is a relation of equivalence.

• the parallelism on a whole of right-hand sides (in a plan) is a relation of equivalence.
• If $f\; \backslash ,$ is an application of a unit E in a unit F , then the relation $\backslash \; mathcal\; R$ defined by:

$\backslash \; forall\; \backslash \; (X,\; there)\; \backslash \; in\; E^\; \{\backslash ,\; 2\},\; X\; \backslash \; mathcal\; R\; there\; \backslash \; Leftrightarrow\; F\; (X)\; =\; F\; (there)\; \backslash ,$

is a relation of equivalence on E . Thus any application induces a relation of equivalence on its starting whole.

$f\; \backslash ,$ is an injection if the relation induced in the starting whole is the relation of equality. We have then:

$\backslash \; forall\; \backslash \; (X,\; there)\; \backslash \; in\; E^\; \{\backslash ,\; 2\},\; F\; (X)\; =\; F\; (there)\; \backslash \; Leftrightarrow\; X\; =\; there\; \backslash ,$

• the fact of being everywhere equal Presque for functions on a space measured is a relation of equivalence which plays a big role in the theory of the integration of Lebesgue. Indeed two equal functions almost everywhere have the same behavior in this Théorie.

; Counterexamples Several relations exhibent reflexivity, symmetry and transitivity, but not all:

• Reflexive and transitive : $\backslash \; forall\; \backslash \; (X,\; there)\; \backslash \; in\; \backslash \; mathbb\; NR,\; X\; \backslash \; mathcal\; R\; there\; \backslash \; Leftrightarrow\; X\; \backslash \; Leq\; there\; \backslash ,$
• Symmetrical and transitive : $\backslash \; forall\; \backslash \; (X,\; there)\; \backslash \; in\; \backslash \; mathbb\; NR,\; X\; \backslash \; mathcal\; R\; there\; \backslash \; Leftrightarrow\; X\; there\; \backslash \; neq\; 0\; \backslash ,$
• Reflexive and symmetrical : $\backslash \; forall\; \backslash \; (X,\; there)\; \backslash \; in\; \backslash \; mathbb\; Z,\; X\; \backslash \; mathcal\; R\; there\; \backslash \; Leftrightarrow\; (2\; \backslash \; mid\; (X\; -\; there))\; \backslash \; vee\; (3\; \backslash \; mid\; (X\; -\; there))\; \backslash ,$ (“$x$-$y$ is divisible by 2 or 3”)

See too

• binary Relation
• Relation of order
• Function and algebraic application
• Structure

Zh-classical: 等價

Random links:

Geocentrism | Sofía of Greece | Guy Berryman | Moses Gunn | Players, Masters of the play | Produit_d'affaiblissement

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