Equivalence relation

Under an equivalence relation is understood in mathematics, a relation that is reflexive, symmetric and transitive. Equivalence relations are for the logic and mathematics of great importance.

• An equivalence relation shares a lot in completely disjoint ( disjoint ) subsets, called equivalence classes.
• The class education using the concept of equivalence allows a mathematical concept formation.

Equivalence - mathematical equivalence

In mathematics you want to view in many contexts, objects that are similar in certain aspects, as equivalent. A formalization of the minimum requirements for such a concept equivalence is the notion of equivalence relation.

So is any term that can be defined as the equality of certain properties, an equivalence relation. Examples:

And ultimately includes the equality itself to do so.

Definition of an equivalence relation

The word " equivalent" stand below one of these relationships between two objects; that two objects are equivalent and, is symbolized by.

All these terms have the following three characteristics:

• Reflexivity:

• Symmetry:

• Transitivity:

Every relationship ( between objects ) that has these properties is called an equivalence relation.

Formal definition

An equivalence relation on a set is a subset that satisfies the following conditions:

Usually, one writes

And then these demands take exactly the address mentioned in the introduction form.

( Note: A relation on a set is as defined above is equal to the amount of standing in this relation is a relation on pairs Then simply a set of such pairs, that is a subset of the Cartesian product of with itself. )

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 symmetric relation rather than automatically already transitive. To prove this, it is sufficient for each of the eight possible cases provide an example of what happens in the following with relations on the set of natural numbers.

None of the three properties is satisfied:

• Neither reflexive nor symmetric nor transitive: ( is 1 greater than. )

Exactly one of the three properties is satisfied:

• Reflexive but neither symmetric nor transitive: ( is at most one greater than. )
• Symmetric, but neither reflexive nor transitive ( and are adjacent. )
• Transitive, but neither reflexive nor symmetric: ( is less than ).

Exactly two of the three properties are satisfied:

• Symmetric and transitive, but not reflexive: ( equals and not 1 )
• Reflexive and transitive, but not symmetric: ( is less than or equal to. )
• Reflexive and symmetric, but not transitive ( and are the same or adjacent. )

All three properties are satisfied:

• Reflexive, symmetric and transitive:

Illustrative example

An example from agriculture to illustrate the concepts introduced. Considering there is a set M of farm animals in a farm. We define the following binary relation on M:

For the cow and the ox shall apply to the chicken but does not apply the relation satisfies the three requirements for equivalence relations:

An equivalence class consists here of the animals of a kind, the cattle and the chickens form a another equivalence class.

No equivalence relation is the relation " is brother of " on the set of all people. This relation is indeed transitive, but not reflexive ( because I am not my own brother ) or symmetric ( because my sister is not my brother, even though I 'm her brother).

Equivalence classes

The equivalence class of an object is the class of objects that are equivalent to.

Formal: Is an equivalence relation on a set, it is called a subset

The equivalence class of. Is clear from the context that equivalence classes are formed with respect to works, omit the extension. Other spellings are

Elements of an equivalence class are called their agents or representatives. Each element of is contained in exactly one equivalence class. The equivalence classes thus form a partition of. The equivalence classes to two elements are either equal or disjoint, the former if and only if the elements are equivalent:

If one has accurate for each equivalence class with one, then it is called the subset a (complete ) representative or representatives system.

Set of equivalence classes and index

The set of equivalence classes (sometimes factor quantity or quotient set called ) is an equivalence relation on the set

In this crowd, the equivalence classes are considered as a stand- alone basis and. The set of equivalence classes arises when one " makes the same " equivalent elements by being identified by the below picture with the canonical equivalence class, in which they lie. So you mathematically formalized the cognitive process of abstraction identification (see also the concept of partial identity with Löring Hoff ).

The thickness ( cardinality) is sometimes referred to as the index of the equivalence relation. ( A special case is the index of a sub-group. )

There is a canonical surjective map

Which assigns to each element of its equivalence class. This figure is only injective if it is the equivalence relation on M by the so-called diagonal

Concerns. is then the graph of a function, namely the identity map on M.

Other examples

• Equivalence class of a student is the set of all of his classmates in the same school class - but he has himself to be included and considered his own classmates to obtain reflexivity.
• The set of equivalence classes, the set of classes.

• Equivalence class of an element is the singleton.
• The set of equivalence classes, the set of subsets of single-element; the mapping is a bijection.

• Equivalence class of an integer is called the residue class

• The set of equivalence classes is the residue class ring

• The equivalence class of a pair consisting of all pairs ( numerator, denominator ) for fraction representations of the rational number.
• The set of equivalence classes is

Universal property

When an amount, each function in any other quantity defines an equivalence relation, which is sometimes also referred to as a core by:

Conversely, every equivalence relation nucleus of a suitable imaging, such as the canonical figure, in this notation so.

Modulo

Of particular importance is equivalence relations, which are comparable with an algebraic structure on a lot. In all these cases there is a " module " (from Latin modulus measure ), that is compatible with an algebraic link in the initial amount substructure that mediates the equivalence:

You take only as the neutral element of. Is always, then we also write

And says, " ( is ) congruent modulo [ mo ː modulo ː ] " (from the Latin ablative modulo modulus to measure ). Grammatically modulo is the German used as a preposition that governs the genitive.

If the module simply produced in, for example, with one, then one notes also

This way of speaking is the almost exclusive in the ring of integers.

Even with the equivalence classes or cosets is called equivalence classes modulo and the factor set of modulo or modulo and modulo.

The factor amount can "inherit" algebraic structure of the initial amount. Based defining this modulo arithmetic on the elements of the initial amount, ie, the so-called "representatives" of the equivalence classes, even the well- definedness of this computing must always be ensured. If this is successful and is the substructure that mediates the equivalence, one speaks of the modulo arithmetic.

Be the symmetric group of degree 3 and cycles of writing one of the three subgroups of order 2 Man Namely, the three cosets

Form (in order of composition of the cycles as symmetric in the article group). However, the inherited shortcut is not on the choice of representatives of independent ( see example in the article well- definedness ).

However, would not only sub-group, but normal subgroup of, the inherited group operation could probably define the factor group.

Other equivalent terms

Examples of factor quantities:

• Factor space ( for vector spaces )
• Factor group (for groups)
• Factor ring ( for rings )
• Congruence ( for general algebraic structures)

The following equivalence terms arise from the requirement that a pair of images with certain properties exists between two objects that are " more or less" inverse to each other:

• Isomorphism
• Homeomorphism
• Homotopy equivalence
• Equivalence of categories

Other examples of equivalence relations:

• Completion by equivalence classes of Cauchy sequences