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:
- .
This relationship or relation has the following three properties:
- Each object is equivalent to himself .
- When to equivalent , then is equivalent to : .
- If is equivalent to and is equivalent to , then is also equivalent to : and .
Equivalence relation
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
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 :
- Each forms its own equivalence class :
- 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
- 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
References and comments
- ↑ 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 .
- ↑ One differentiates the concept of the kernel of a set : kernel as image of a kernel operator .
- ↑ here denotes the chaining of relations .
- ↑ Follow A000110 in OEIS
- ↑ 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).
- ↑ Notation as in Symmetric Closure , on: ProofWiki from September 12, 2016
- ↑ A distinction is made between the concept of mapping compatible with relations : homomorphism as a structure compatible mapping.
- ^ ^{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).
- ↑ 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 .
- ↑ These can be formed for every symmetrical relation (= partial tolerance relation).