Equivalence relation

from Wikipedia, the free encyclopedia

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:

.

This relationship or relation has the following three properties:

  1. Each object is equivalent to himself   .
  2. When to equivalent , then is equivalent to :   .
  3. If is equivalent to and is equivalent to , then is also equivalent to :   and .

Equivalence relation

Set of eight book copies with drawn equivalence relation " and have the same ISBN" as an arrow diagram

An equivalence relation on a set is a two-digit relation that fulfills the following conditions:

Reflexivity
for everyone .
symmetry
for everyone .
Transitivity
and for everyone .

As usual with two-digit relations, if you write instead of simpler , then these properties take the form mentioned above.

In this case, the ordered pair is also called Setoid or E-set (English term: extensional set , also Bishop set ).

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

If an equivalence relation is on a set ( class ) , then the subset (or subclass) is called

,

of all elements to be equivalent, the -equivalence class of .

If it is clear from the context that equivalence classes are formed with respect to, the addition is omitted:

,

other spellings are

as well .

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:

.

A subset is called a (complete) representative or representative system of if there is exactly one with for each equivalence class .

For any equivalence relation on a set can be at any of representatives of a function defined by

for all

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:

.

It forms a decomposition or partition of .

Conversely , if there is a partition of , then through

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 .

Quotient mapping

The surjective function

,

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 .

Core of a function

The equivalence relation given by the function is also called the kernel of

.

In particular, the equivalence class of each is the archetype of its image :

.

then be in a surjective, as follows, bijective and a one function disassemble :

with and the inclusion image .

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.

None of the three properties is met

Neither reflexive nor symmetric nor transitive:

  ( is 1 greater than ).

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:

  ( is at most 1 greater than ).

Symmetrical, but neither reflexive nor transitive:

  ( and are adjacent).

Transitive, but neither reflexive nor symmetrical:

  ( is less than ).

Exactly two of the three properties are met

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

  ( is equal and not 1).

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

  ( is less than or equal to ).

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

  ( and are equal or adjacent).

All three properties are met

Reflexive, symmetric and transitive:

.

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 :

For every two farm animals and from should apply if and are animals of the same species .

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:

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).

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

.

The following applies:

  • The equivalence class of an element is the one-element set .
  • The quotient set is the set of the one-element subsets of . The mapping is bijective .
  • The following applies to the chaining with any relations on :
  ( 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

.

The following applies:

  • The equivalence class of each element is the whole set .
  • The quotient set is the one-element set . The mapping is constant .
  • For the concatenation with any reflexive relations on the following applies:
  ( 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

and are similar to each other

given on the set of all figures of the plane.

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

and are congruent

is an equivalence relation given.

Partition of a finite set of numbers

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

,
,
,
,
,
.

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

.

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.
  • The quotient amount is the alternating element amount .

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 :

.
  • The equivalence class of the pair is then the fraction or (total) quotient .
  • With the quotient set we get the set of rational numbers .

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:

with as the multiplicative group of .

  • Equivalence class of a real number is the set of numbers that can be commensurate with , which is infinite for countable .
  • 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
  • The real addition is not compatible with , because z. B. is , but so

Hilbert space of the L 2 -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

represents a positive semidefinite bilinear form , if

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 ).

The solution is to introduce an equivalence relation: You define that and give the set of equivalence classes the name .

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 .

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.

Topological equivalence of metrics

be a metric space and

open in

the associated topology . If there is another metric on and its associated topology, then they are called and topologically equivalent if and match:

.

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:

is equivalence relation on with

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

.

The symmetrical envelope denotes the converse (inverse) relation and powers of relations are formed by means of concatenation .

Special equivalences

Equality of sets

Any two sets and are equal if and only if there is a bijection . By laying down

and are equal

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

and are isomorphic.

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

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 .

In particular, all functions belonging to the structure are then also compatible.

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.

Every partial equivalence relation on a set is on the subset

a total equivalence relation. The decomposition of defined by the equivalence classes is also called the partial decomposition of .

A partial equivalence relation can be extended to a (total) equivalence relation in different ways :

  1. Each forms its own equivalence class :
  2. All form a single equivalence class :

The result is a total decomposition of .

Every partial function according to any other set produces a partial equivalence relation

for everyone .

Conversely, a partial equivalence relation always provides a surjective partial quotient mapping

for everyone .

Quasi order

A two-digit relation on a set is called a pre -order or quasi-order if it is reflexive and transitive.

A relation on is a quasi-order if and only if the following applies to all :

.

Through every quasi-order on an equivalence relation on is given by the definition

and .

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 :

.

A maximum pre-class , i.e. if everyone with at least one is not tolerant, is in turn called a compatibility or tolerance class .

The set of tolerance classes of a tolerance relation on the set is an overlap of .

Further equivalence terms

literature

Web links

Commons : equivalence relation  - collection of images, videos and audio files
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 .
  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).