Equivalence relation

In mathematics, an equivalence relation is understood to be a two-digit relation that is reflexive , symmetrical and transitive . Equivalence relations are of great importance for mathematics and logic . An equivalence relation divides a set completely into disjoint (non-element) subsets, called equivalence classes . Class formation with the help of the concept of equivalence is fundamental for many mathematical concept formations.

Definitions

equivalence

In mathematics, objects that are similar in a certain context are regarded as equivalent or equivalent .

Such a connection can always be established for all elements of a non-empty set through a function by designating two elements as "equivalent" to one another and symbolizing this relationship by if their images are the same: ${\displaystyle A}$ ${\displaystyle f\colon \,A\to B}$ ${\displaystyle a,b\in A}$ ${\displaystyle a\sim b}$

${\displaystyle a\sim b\;:\!\iff f(a)=f(b)}$.

This relationship or relation has the following three properties:

1. Each object is equivalent to himself   . ${\displaystyle a}$ ${\displaystyle a\sim a}$
2. When to equivalent , then is equivalent to :   . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle a\sim b\implies b\sim a}$
3. If is equivalent to and is equivalent to , then is also equivalent to :   and . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle a}$ ${\displaystyle c}$ ${\displaystyle a\sim b\;}$ ${\displaystyle \;b\sim c\implies a\sim c}$

Equivalence relation

Set of eight book copies with drawn equivalence relation " and have the same ISBN" as an arrow diagram ${\displaystyle a}$ ${\displaystyle b}$

An equivalence relation on a set is a two-digit relation that fulfills the following conditions: ${\displaystyle A\neq \emptyset }$ ${\displaystyle {\mathrel {\sim }}\subseteq A\times A}$

Reflexivity

${\displaystyle (a,a)\in {\mathrel {\sim }}\;\;}$for everyone . ${\displaystyle a\in A}$

symmetry

${\displaystyle (a,b)\in {\mathrel {\sim }}\implies (b,a)\in {\mathrel {\sim }}\;\;}$for everyone . ${\displaystyle a,b\in A}$

Transitivity

${\displaystyle (a,b)\in {\mathrel {\sim }}}$and for everyone . ${\displaystyle (b,c)\in {\mathrel {\sim }}\implies (a,c)\in {\mathrel {\sim }}\;\;}$ ${\displaystyle a,b,c\in A}$

As usual with two-digit relations, if you write instead of simpler , then these properties take the form mentioned above. ${\displaystyle (a,b)\in {\mathrel {\sim }}}$ ${\displaystyle a\sim b}$

In this case, the ordered pair is also called Setoid or E-set (English term: extensional set , also Bishop set ). ${\displaystyle (A,\sim )}$

Equivalence classes

Set of eight book copies with the drawn equivalence relation “ and have the same ISBN” as an arrow diagram and the equivalence classes ${\displaystyle a}$ ${\displaystyle b}$

If an equivalence relation is on a set ( class ) , then the subset (or subclass) is called ${\displaystyle \sim }$ ${\displaystyle A\neq \emptyset }$

${\displaystyle [a]_{\sim }:=\{b\in A\mid b\sim a\}}$,

of all elements to be equivalent, the -equivalence class of . ${\displaystyle a\in A}$ ${\displaystyle \sim }$ ${\displaystyle a}$

If it is clear from the context that equivalence classes are formed with respect to, the addition is omitted: ${\displaystyle \sim }$ ${\displaystyle \sim }$

${\displaystyle [a]}$,

other spellings are

${\displaystyle a/{\sim }\quad }$as well . ${\displaystyle \quad {\bar {a}}}$

Representative systems

Elements of an equivalence class are called their representatives or representatives . Each element of is contained in exactly one equivalence class. The equivalence classes for two elements are either equal or disjoint . The former if and only if the elements are equivalent: ${\displaystyle A}$ ${\displaystyle a,b\in A}$

${\displaystyle [a]=[b]\iff a\in [b]\iff a\sim b\iff b\in [a]}$.

A subset is called a (complete) representative or representative system of if there is exactly one with for each equivalence class . ${\displaystyle S\subseteq A}$ ${\displaystyle \sim }$ ${\displaystyle [a]}$ ${\displaystyle s\in S}$ ${\displaystyle s\in [a]}$

For any equivalence relation on a set can be at any of representatives of a function defined by ${\displaystyle \sim }$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle \sim }$ ${\displaystyle f_{S}\colon \,A\to A}$

${\displaystyle f_{S}(a):=s\iff a\sim s\;\;}$ for all ${\displaystyle a\in A,\,s\in S}$

puts.

Set of quotients and partition

The set of factors or quotients of an equivalence relation on the set is the set of all equivalence classes: ${\displaystyle \sim }$ ${\displaystyle A}$

${\displaystyle A/{\sim }:=\{[a]_{\sim \!}\mid a\in A\}}$.

It forms a decomposition or partition of ${\displaystyle A}$ .

Conversely , if there is a partition of , then through ${\displaystyle {\mathcal {P}}}$ ${\displaystyle A}$

${\displaystyle a\sim b\;:\!\iff \exists B\in {\mathcal {P}}\colon \;a,b\in B}$

given an equivalence relation.

The cardinality (cardinality) is sometimes called the index of the equivalence relation called. A special case is the index of a subgroup . ${\displaystyle |A/{\sim }|}$ ${\displaystyle \sim }$

Quotient mapping

The surjective function

${\displaystyle \mathrm {q} _{\sim }\colon \,A\twoheadrightarrow A/{\sim },\,a\mapsto [a]_{\sim }}$,

which assigns its equivalence class to each element is called canonical mapping or quotient mapping .

This mapping is only injective if the equivalence relation to is the identity relation . ${\displaystyle A}$ ${\displaystyle \mathrm {I} _{A}}$

Core of a function

The equivalence relation given by the function is also called the kernel of ${\displaystyle f\colon \,A\to B}$ ${\displaystyle \sim }$ ${\displaystyle f}$

${\displaystyle \ker f:=f^{-1}\circ f=\{(a,b)\in A\times A\mid f(a)=f(b)\}={\mathrel {\sim }}}$.

In particular, the equivalence class of each is the archetype of its image : ${\displaystyle a\in A}$ ${\displaystyle f(a)\in B}$

${\displaystyle [a]_{\sim }=f^{-1}(\{f(a)\})=f^{-1}(f(\{a\}))=\ker f(\{a\})}$.

${\displaystyle f}$then be in a surjective, as follows, bijective and a one function disassemble :

${\displaystyle f=\mathrm {i} _{f}\circ f^{\sim \!}\circ \mathrm {q} _{\sim }}$

with and the inclusion image . ${\displaystyle f^{\sim }\colon \,A/{\sim }\;{\!\;\twoheadrightarrow \;\!\!\!\!\!\!\!\!\!\!\;\rightarrowtail }\;f(A),\,[a]_{\sim }\mapsto f(a),}$ ${\displaystyle \mathrm {i} _{f}\colon \;f(A)\rightarrowtail B,\,f(a)\mapsto f(a)}$

Independence of the three properties

In fact, the properties of reflexivity, symmetry and transitivity are completely independent of each other and must all be checked individually. For example, a reflexive and symmetrical relation is not automatically transitive. In order to prove this, it is sufficient to give an example for each of the eight possible cases of what happens in the following with relations on the set of natural numbers. ${\displaystyle \mathbb {N} }$

None of the three properties is met

Neither reflexive nor symmetric nor transitive:

${\displaystyle \{(a,b)\in \mathbb {N} \times \mathbb {N} \mid a-b=1\}}$   ( is 1 greater than ). ${\displaystyle a}$ ${\displaystyle b}$

Another example of this is the “is a brother of” relationship on the crowd of all people. It is neither reflexive (because no one is his own brother) nor symmetrical (because a man's sister is not his brother even though he is a brother of hers) nor transitive (because a man is not a brother of himself even though he - if he is has a brother - is a brother of his brother and that brother is his brother).

Exactly one of the three properties is fulfilled

Reflexive, but neither symmetric nor transitive:

${\displaystyle \{(a,b)\in \mathbb {N} \times \mathbb {N} \mid a-b\in \{0,1\}\}}$   ( is at most 1 greater than ). ${\displaystyle a}$ ${\displaystyle b}$

Symmetrical, but neither reflexive nor transitive:

${\displaystyle \{(a,b)\in \mathbb {N} \times \mathbb {N} \mid |a-b|=1\}}$   ( and are adjacent). ${\displaystyle a}$ ${\displaystyle b}$

Transitive, but neither reflexive nor symmetrical:

${\displaystyle \{(a,b)\in \mathbb {N} \times \mathbb {N} \mid a<b\}}$   ( is less than ). ${\displaystyle a}$ ${\displaystyle b}$

Exactly two of the three properties are met

Symmetrical and transitive ( partial equivalence relation ), but not reflexive:

${\displaystyle \{(a,b)\in \mathbb {N} \times \mathbb {N} \mid b=a\neq 1\}}$   ( is equal and not 1). ${\displaystyle a}$ ${\displaystyle b}$

Reflexive and transitive ( quasi-order ), but not symmetrical:

${\displaystyle \{(a,b)\in \mathbb {N} \times \mathbb {N} \mid a\leq b\}}$   ( is less than or equal to ). ${\displaystyle a}$ ${\displaystyle b}$

Reflexive and symmetrical ( tolerance relation), but not transitive:

${\displaystyle \{(a,b)\in \mathbb {N} \times \mathbb {N} \mid |a-b|\leq 1\}}$   ( and are equal or adjacent). ${\displaystyle a}$ ${\displaystyle b}$

All three properties are met

Reflexive, symmetric and transitive:

${\displaystyle \{(a,b)\in \mathbb {N} \times \mathbb {N} \mid a=b\}}$.

Examples

Farm animals on a farm

A clear example from agriculture is intended to clarify the terms introduced. A lot of livestock on a farm is considered. We define the following binary relation to : ${\displaystyle T}$ ${\displaystyle \sim }$ ${\displaystyle T}$

For every two farm animals and from should apply if and are animals of the same species . ${\displaystyle t}$ ${\displaystyle v}$ ${\displaystyle T}$ ${\displaystyle t\sim v}$ ${\displaystyle t}$ ${\displaystyle v}$

This always applies to the cow and the ox . For the chicken , however this does not apply: . The relation fulfills the three requirements for equivalence relations: ${\displaystyle k}$ ${\displaystyle o}$ ${\displaystyle k\sim o}$ ${\displaystyle h}$ ${\displaystyle h\nsim o}$ ${\displaystyle \sim }$

Reflexivity

Every animal is of the same species as itself (in the sense of: every animal belongs to a species).

symmetry

If one animal is of the same species as a second, then the second is also of the same species as the first.

Transitivity

If and animals are of the same kind and are of the same kind, then are also and of the same kind (namely, of the kind to which each of the three animals then belongs). ${\displaystyle k}$ ${\displaystyle o}$ ${\displaystyle o}$ ${\displaystyle b}$ ${\displaystyle k}$ ${\displaystyle b}$

An equivalence class consists of the animals of one species. The cattle form one equivalence class and the chickens another. The quotient amount is the amount of animal species on the farm.

Identity relation

On any set, let two elements be equivalent if they are equal. This by the graph of the identity mapping on calls given equivalence relation to the equality or identity relation ${\displaystyle A}$ ${\displaystyle \operatorname {id} _{A}}$ ${\displaystyle A}$

${\displaystyle \mathrm {I} _{A}:=\{(a,b)\in A\times A\mid a=b\}=\{(a,a)\mid a\in A\}\!}$.

The following applies:

• The equivalence class of an element is the one-element set . ${\displaystyle a}$ ${\displaystyle \{a\}}$
• The quotient set is the set of the one-element subsets of . The mapping is bijective . ${\displaystyle A}$ ${\displaystyle A\to A/\mathrm {I} _{A}}$
• The following applies to the chaining with any relations on : ${\displaystyle \circ }$ ${\displaystyle R}$ ${\displaystyle A}$

${\displaystyle \mathrm {I} _{A}\circ R=R\circ \mathrm {I} _{A}=R}$   ( neutral element ).

All relation

Let any two elements on a set be equivalent. Also be an equivalence relation to given, called the all- or Universal relation ${\displaystyle A}$ ${\displaystyle A}$

${\displaystyle \mathrm {U} _{A}:=A\times A=\{(a,b)\mid a,b\in A\}}$.

The following applies:

• The equivalence class of each element is the whole set . ${\displaystyle a}$ ${\displaystyle A}$
• The quotient set is the one-element set . The mapping is constant . ${\displaystyle \{A\}}$ ${\displaystyle A\to A/\mathrm {U} _{A}}$
• For the concatenation with any reflexive relations on the following applies: ${\displaystyle \circ }$ ${\displaystyle R}$ ${\displaystyle A}$

${\displaystyle \mathrm {U} _{A}\circ R=R\circ \mathrm {U} _{A}=\mathrm {U} _{A}}$   ( absorbent element ).

Similarity and congruence of geometric figures

Two geometrical figures and in the Euclidean plane are exactly similar to one another if they can be converted into one another by means of a similarity mapping. Due to the similarity there is an equivalence relation ${\displaystyle F}$ ${\displaystyle G}$

${\displaystyle F\sim G\;:\!\iff F}$and are similar to each other ${\displaystyle G}$

given on the set of all figures of the plane. ${\displaystyle \mathbf {F} }$

In addition, and are congruent precisely when they can be converted into one another by means of a congruence mapping , that is to say a length-true similarity mapping . Also through ${\displaystyle F}$ ${\displaystyle G}$

${\displaystyle F\cong G\;:\!\iff F}$and are congruent ${\displaystyle G}$

is an equivalence relation given. ${\displaystyle \mathbf {F} }$

Partition of a finite set of numbers

We first define six sets of natural numbers from 1 to 23:

${\displaystyle A_{1}:=\{1,7,10,13,17\}}$,

${\displaystyle A_{2}:=\{2,5,8,16\}}$,

${\displaystyle A_{3}:=\{3,4,6,11,18,22\}}$,

${\displaystyle A_{4}:=\{9,12,14,15,23\}}$,

${\displaystyle A_{5}:=\{19\}}$,

${\displaystyle A_{6}:=\{20,21\}}$.

They have the property that every number from the range from 1 to 23 occurs in exactly one of the six sets, which thus form a decomposition or partition of the set . Like every partition of , they are the equivalence classes of an equivalence relation on , viz ${\displaystyle A=\{1,\dotsc ,23\}}$ ${\displaystyle A}$ ${\displaystyle \sim }$ ${\displaystyle A}$

${\displaystyle a\sim b\;:\!\iff \exists i\in \{1,\ldots ,6\}\colon \;a,b\in A_{i}}$.

The sets were determined by rolling the dice, that is, they were arbitrarily selected from the approximately 44 quadrillion partitions - and thus just as many equivalence relations - of this 23-element set. Equivalent numbers according to this relation have no easily describable similarities.

• The equivalence class of an element is the set that contains. ${\displaystyle a}$ ${\displaystyle A_{i}}$ ${\displaystyle a}$
• The quotient amount is the alternating element amount . ${\displaystyle \{A_{1},A_{2},A_{3},A_{4},A_{5},A_{6}\}}$

Rational numbers

Let it be the set of pairs of integers whose second entry is different from zero. The following equivalence should apply to two pairs : ${\displaystyle P:=\{(z,n)\in \mathbb {Z} ^{2}\mid n\neq 0\}}$ ${\displaystyle (z_{1},n_{1}),(z_{2},n_{2})\in P}$

${\displaystyle (z_{1},n_{1})\sim (z_{2},n_{2})\;:\!\iff z_{1}\cdot n_{2}=z_{2}\cdot n_{1}}$.

• The equivalence class of the pair is then the fraction or (total) quotient . ${\displaystyle (z,n)}$ ${\displaystyle \,{\tfrac {z}{n}}:=[(z,n)]_{\sim }}$
• With the quotient set we get the set of rational numbers . ${\displaystyle \,\mathbb {Q} :=P/{\sim }=\left\{{\tfrac {z}{n}}\;{\big |}\;(z,n)\in P\right\}}$

Commensurability of real numbers

Two real numbers and are called commensurable if they are integral multiples of a suitable third real number . Commensurability is an equivalence relation if one considers the zero separately: ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$

${\displaystyle x\sim y\;:\!\iff {\begin{cases}{\frac {x}{y}}\in \mathbb {Q} ^{\times },&{\text{falls }}\;x,y\neq 0,\\x=y=0,&{\text{falls }}\;x\cdot y=0\end{cases}}}$

with as the multiplicative group of . ${\displaystyle \mathbb {Q} ^{\times }:=\mathbb {Q} \setminus \{0\}}$ ${\displaystyle \mathbb {Q} }$

• Equivalence class of a real number is the set of numbers that can be commensurate with , which is infinite for countable . ${\displaystyle x}$ ${\displaystyle x\cdot \mathbb {Q} ^{\times }}$ ${\displaystyle x}$ ${\displaystyle x\neq 0}$
• The quotient set is uncountable . In contrast to other similarly simple equivalence relations, however, there is no system of representatives available here.
• The multiplication is compatible with , because if and , then it follows e.g. B. off ${\displaystyle \sim }$ ${\displaystyle x\sim y}$ ${\displaystyle x^{\prime }\sim y^{\prime }}$ ${\displaystyle xx^{\prime }\sim yy^{\prime }}$ ${\displaystyle {\tfrac {xx^{\prime }}{yy^{\prime }}}\in \mathbb {Q} ^{\times }.}$
• The real addition is not compatible with , because z. B. is , but so ${\displaystyle \sim }$ ${\displaystyle -1\sim 1}$ ${\displaystyle {\tfrac {{\sqrt {2}}-1}{{\sqrt {2}}+1}}=3-2{\sqrt {2}}\;\notin \mathbb {Q} ^{\times },}$ ${\displaystyle {\sqrt {2}}-1\;\not \sim {\sqrt {2}}+1.}$

Hilbert space of the L ² -integratable functions

Let be a sigma algebra on a set and a complete measure . It can easily be shown that for measurable functions the figure ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \Omega }$ ${\displaystyle \mu {\text{: }}{\mathcal {F}}\rightarrow [0,\infty ]}$ ${\displaystyle f_{1},f_{2}:\Omega \rightarrow \mathbb {R} }$

${\displaystyle \langle f_{1}|f_{2}\rangle :=\int \limits _{\Omega }f_{1}\cdot f_{2}{\text{ d}}\mu }$

represents a positive semidefinite bilinear form , if

${\displaystyle f_{1},f_{2}\in {\mathcal {L}}^{2}:=\{f:\Omega \rightarrow \mathbb {R} :\int \limits _{\Omega }f^{2}{\text{ d}}\mu <\infty \}}$

applies.

The reason is that in general no strict positive definiteness true, is that a well can be considered without the zero function is - namely if and only if (that is, if.. Only on a set equal to 0, which one - zero amount represents ). ${\displaystyle f\in {\mathcal {L}}^{2}}$ ${\displaystyle \langle f|f\rangle =0}$ ${\displaystyle f}$ ${\displaystyle \mu (\{x\in \Omega :f(x)\neq 0\})=0}$ ${\displaystyle f}$ ${\displaystyle \mu }$

The solution is to introduce an equivalence relation: You define that and give the set of equivalence classes the name . ${\displaystyle f_{1}\sim f_{2}:\Leftrightarrow \langle f_{1}-f_{2}|f_{1}-f_{2}\rangle =0}$ ${\displaystyle L^{2}}$

Then, in addition to the properties mentioned above, it is also positive definite, i.e. a scalar product and thus a norm . It is therefore a normalized space. Finally, it follows from Riesz-Fischer's theorem that this space is complete , so that it is a Banach space and in particular (since the norm is induced by a scalar product ) a Hilbert space . This finds its application z. B. in quantum mechanics , but also in probability . ${\displaystyle \langle \cdot |\cdot \rangle }$ ${\displaystyle \|\cdot \|:={\sqrt {\langle \cdot |\cdot \rangle }}}$ ${\displaystyle (L^{2},\|\cdot \|)}$

It should be noted here that an element from is not a function, but an equivalence class of functions with regard to the above equivalence relation. However, since the representatives of this class only differ on a -zero set, this is irrelevant for practical purposes. ${\displaystyle L^{2}}$ ${\displaystyle \mu }$

Topological equivalence of metrics

${\displaystyle (X,d)}$be a metric space and

${\displaystyle {\mathcal {T}}_{d}:=\{O\subseteq X\mid O}$ open in ${\displaystyle (X,d)\}}$

the associated topology . If there is another metric on and its associated topology, then they are called and topologically equivalent if and match: ${\displaystyle d}$ ${\displaystyle d^{\prime }}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {T}}_{d^{\prime }}}$ ${\displaystyle d}$ ${\displaystyle d^{\prime }}$ ${\displaystyle {\mathcal {T}}_{d}}$ ${\displaystyle {\mathcal {T}}_{d^{\prime }}}$

${\displaystyle d\sim d^{\prime }\;:\!\iff {\mathcal {T}}_{d}={\mathcal {T}}_{d^{\prime }}}$.

Generation of equivalence relations

Describing an equivalence relation explicitly is sometimes not easy. Often one would like to construct an equivalence relation which identifies certain given elements with one another and at the same time contains certain properties, for example is a congruence relation (see below).

Let be any relation on the set . As equivalence envelope from one calls the smallest equivalence relation that contains as part relation in sign: ${\displaystyle R}$ ${\displaystyle A}$ ${\displaystyle R}$ ${\displaystyle R}$

${\displaystyle R^{\text{äq}}:=\bigcap \{{\mathrel {\sim }}\subseteq A\times A\mid {\mathrel {\sim }}}$is equivalence relation on with ${\displaystyle A}$ ${\displaystyle R\subseteq {\mathrel {\sim }}\}}$

The following applies: The equivalent envelope is the reflexive-transitive envelope of the symmetrical envelope , formally:

${\displaystyle R^{\text{äq}}=(R^{\leftrightarrow })^{*}=(R\cup R^{-1})^{*}=\bigcup _{n\in \mathbb {N} _{0}}(R\cup R^{-1})^{n}}$.

The symmetrical envelope denotes the converse (inverse) relation and powers of relations are formed by means of concatenation . ${\displaystyle R^{\leftrightarrow }}$ ${\displaystyle R^{-1}}$

Special equivalences

Equality of sets

Any two sets and are equal if and only if there is a bijection . By laying down ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle f\colon \,A\;{\!\;\twoheadrightarrow \;\!\!\!\!\!\!\!\!\!\!\;\rightarrowtail }\;B}$

${\displaystyle A\sim B\;:\!\iff A}$and are equal ${\displaystyle B}$

an equivalence is given on the class of all sets.

Isomorphism of structures

Structures and are called isomorphic if and only if there is a structurally compatible bijection for which is also structurally compatible. The isomorphism of structures is an equivalence ${\displaystyle \mathbf {A} }$ ${\displaystyle \mathbf {B} }$ ${\displaystyle \varphi \colon \,\mathbf {A} \;{\!\;\twoheadrightarrow \;\!\!\!\!\!\!\!\!\!\!\;\rightarrowtail }\;\mathbf {B} }$ ${\displaystyle \varphi ^{-1}}$

${\displaystyle \mathbf {A} \cong \mathbf {B} \;:\!\iff \mathbf {A} }$and are isomorphic. ${\displaystyle \mathbf {B} }$

Congruence relation

→ Main article : Congruence relation

An equivalence relation on a set does not necessarily have anything to do with the structure that is defined on it. Of particular interest, however, are those equivalence relations , their quotient mapping ${\displaystyle A}$ ${\displaystyle \equiv }$

${\displaystyle \mathrm {q} _{\equiv }\colon \,A\to A/{\equiv },\,a\mapsto [a]_{\equiv },}$

is compatible with the structure or a homomorphism , because then the structure generated by on the quotient set is of the same type as that of . Such an equivalence relation is called a congruence relation on the structured set . ${\displaystyle A}$ ${\displaystyle \mathrm {q} _{\equiv }}$ ${\displaystyle A/{\equiv }}$ ${\displaystyle A}$ ${\displaystyle \equiv }$ ${\displaystyle A}$

In particular, all functions belonging to the structure are then also compatible. ${\displaystyle \equiv }$

Generalizations

Partial equivalence relation

A two-digit relation on a set is called a bounded or partial equivalence relation if it is symmetric and transitive. ${\displaystyle \smallfrown }$ ${\displaystyle A}$

Every partial equivalence relation on a set is on the subset ${\displaystyle \smallfrown }$ ${\displaystyle A}$

${\displaystyle D_{\smallfrown }:=\{a\in A\mid a\smallfrown a\}\subseteq A}$

a total equivalence relation. The decomposition of defined by the equivalence classes is also called the partial decomposition of . ${\displaystyle [a]_{\smallfrown }}$ ${\displaystyle D_{\smallfrown }}$ ${\displaystyle A}$

A partial equivalence relation can be extended to a (total) equivalence relation in different ways : ${\displaystyle \smallfrown }$ ${\displaystyle \sim }$

1. Each forms its own equivalence class : ${\displaystyle a\in A\setminus D_{\smallfrown }}$ ${\displaystyle \{a\}}$ ${\displaystyle \quad \,\quad a\sim b\;:\!\iff {\begin{cases}a\smallfrown b,&{\text{falls }}\;a,b\in D_{\smallfrown },\\a=b,&{\text{sonst}}.\end{cases}}}$
2. All form a single equivalence class : ${\displaystyle a\in A\setminus D_{\smallfrown }}$ ${\displaystyle A\setminus D_{\smallfrown }}$ ${\displaystyle \quad a\sim b\;:\!\iff {\begin{cases}a\smallfrown b,&{\text{falls }}\;a,b\in D_{\smallfrown },\\a,b\in A\setminus D_{\smallfrown },&{\text{sonst}}.\end{cases}}}$

The result is a total decomposition of . ${\displaystyle A}$

Every partial function according to any other set produces a partial equivalence relation ${\displaystyle f\colon \,A\rightharpoonup B}$ ${\displaystyle B}$

${\displaystyle a_{1}\smallfrown a_{2}\;:\!\iff \exists b\in B\colon \;f(a_{1})=f(a_{2})=b\;\;}$for everyone . ${\displaystyle a_{1},a_{2}\in A}$

Conversely, a partial equivalence relation always provides a surjective partial quotient mapping ${\displaystyle A}$

${\displaystyle \mathrm {q} _{\smallfrown }\colon \,A\rightharpoonup D_{\smallfrown }/{\smallfrown },\,a\mapsto [a]_{\smallfrown }}$for everyone . ${\displaystyle a\in D_{\smallfrown }}$

Quasi order

→ Main article : quasi-order

A two-digit relation on a set is called a pre -order or quasi-order if it is reflexive and transitive. ${\displaystyle \lesssim }$ ${\displaystyle A}$

A relation on is a quasi-order if and only if the following applies to all : ${\displaystyle \lesssim }$ ${\displaystyle A}$ ${\displaystyle a,b\in A}$

${\displaystyle \!a\lesssim b\iff \forall c\in A\colon \,(c\lesssim a\implies c\lesssim b)\!}$.

Through every quasi-order on an equivalence relation on is given by the definition ${\displaystyle \lesssim }$ ${\displaystyle A}$ ${\displaystyle \sim }$ ${\displaystyle A}$

${\displaystyle a\sim b\;:\!\iff a\lesssim b\,}$and . ${\displaystyle \!\;b\lesssim a}$

So two elements are equivalent if they are mutually comparable.

Tolerance relation

A two-digit reflexive and symmetrical relation is called a compatibility or tolerance relation (in the finite case also a dependency relation ). Since a tolerance relation does not have to be transitive, tolerance is a weaker requirement than equivalence. It plays a role in biomathematics and model theory , and in fuzzy logic it is further generalized.

Designate a tolerance relation on the set (or class) . A subset (or class) is called a compatibility or tolerance pre-class if they are all tolerant of each other : ${\displaystyle \smallsmile }$ ${\displaystyle A}$ ${\displaystyle P\subseteq A}$ ${\displaystyle a,b\in P}$

${\displaystyle a\smallsmile b}$.

A maximum pre-class , i.e. if everyone with at least one is not tolerant, is in turn called a compatibility or tolerance class . ${\displaystyle K\subseteq A}$ ${\displaystyle a\in A\setminus K}$ ${\displaystyle k\in K}$

The set of tolerance classes of a tolerance relation on the set is an overlap of . ${\displaystyle A}$ ${\displaystyle A}$

Further equivalence terms

• Equivalence of categories
• Logical equivalence of statements

literature

• Marcel Erné: Introduction to Order Theory . Bibliographic Institute, Mannheim / Vienna / Zurich 1982, ISBN 3-411-01638-8 .
• Gerd Fischer : Linear Algebra . An introduction for first-year students. 14th revised edition. Vieweg, Wiesbaden 2003, ISBN 3-528-03217-0 .
• Udo Hebisch , Hanns Joachim Weinert: Half rings. Algebraic Theory and Applications in Computer Science . Teubner, Stuttgart 1993, ISBN 3-519-02091-2 .
• Thomas Ihringer : General Algebra. With an appendix on Universal Coalgebra by H. P. Gumm (=  Berlin study series on mathematics . Volume 10 ). Heldermann, Lemgo 2003, ISBN 3-88538-110-9 .
• Boto von Querenburg : Set theoretical topology . 3., rework. and exp. Edition. Springer, Berlin / Heidelberg / New York 2001, ISBN 978-3-540-67790-1 , doi : 10.1007 / 978-3-642-56860-2 .
• Fritz Reinhardt, Heinrich Soeder: dtv atlas for mathematics. Boards and texts . Volumes 1 and 2. 9th and 8th editions. Deutscher Taschenbuch Verlag, Munich 1991 and 1992, ISBN 3-423-03007-0 and ISBN 3-423-03008-9 .
• Matthias Schubert: Mathematics for Computer Scientists. Explained in detail with many program examples and tasks . 2nd Edition. Vieweg + Teubner, Wiesbaden 2012, ISBN 978-3-8348-1848-5 , doi : 10.1007 / 978-3-8348-1995-6 .
• Siegfried Wendt: Non-physical basics of information technology. Interpreted formalisms . 2nd Edition. Springer, Berlin / Heidelberg 1991, ISBN 978-3-540-54452-4 ( compatibility ratio in the Google book search).

Web links

Commons : equivalence relation  - collection of images, videos and audio files

Wikiversity: Equivalence relations as part of a lecture on linear algebra  course materials

Wikibooks: Math for Non-Freaks: Equivalence Relation  - Learning and Teaching Materials

References and comments

1. ↑ Alexandre Buisse, Peter Dybjer: The Interpretation of Intuitionistic Type Theory in Locally Cartesian Closed Categories - an Intuitionistic Perspective . In: Electronic Notes in Theoretical Computer Science . tape 218 , October 22, 2008, p. 21–32 , here p.  24 , doi : 10.1016 / j.entcs.2008.10.003 .
2. ↑ One differentiates the concept of the kernel of a set : kernel as image of a kernel operator .
3. ↑ here denotes the chaining of relations . ${\displaystyle \circ }$
4. ↑ Follow A000110 in OEIS
5. ↑ Johannes Köbler: Introduction to Theoretical Computer Science . Humboldt University of Berlin, p. 38 ( WS 2011/12 [PDF; accessed on December 10, 2018] lecture notes).
6. ↑ Notation as in Symmetric Closure , on: ProofWiki from September 12, 2016
7. ↑ A distinction is made between the concept of mapping compatible with relations : homomorphism as a structure compatible mapping.
8. ^ ^{A b c} Vladimir Borschev, Barbara H. Partee: Linguistics 726: Mathematical Linguistics . Fall semester 2006. University of Massachusetts Amherst, S. 16 ( Lectures 1-3. Basic Concepts of Set Theory, Functions and Relations; and Trees [PDF; accessed December 10, 2018] Course script).
9. ↑ M. Das, M. K. Chakraborty, T. K. Ghoshal: Fuzzy tolerance relation, fuzzy tolerance space and basis . In: Fuzzy Sets and Systems . tape 97 , no. 3 , August 1, 1998, pp. 361-369 , doi : 10.1016 / S0165-0114 (97) 00253-4 .
10. ↑ These can be formed for every symmetrical relation (= partial tolerance relation).