Equivalence relation

In set theory and algebra, the notion of equivalence relation on a set allows us to establish a relationship between the elements of the set that share a certain characteristic or property. This makes it possible to regroup these elements into equivalence classes, that is, "packages" of similar elements. This makes it possible to build new sets "joining" all the elements of the same class as a single element that will represent them and that defines the notion of quotient set.

Definition

Sea K{displaystyle K} a given non-empty set R{displaystyle {mathcal {R}}} a defined binary relationship K{displaystyle K}. It's said that R{displaystyle {mathcal {R}}} is an equivalence ratio if it fulfills the following properties:

• Reflectivity: All element of K{displaystyle K} He's connected to himself. I mean,

Русский Русский x한 한 K:xRx{displaystyle forall xin K;:quad x{mathcal {R}x}.

• Symmetry: If an element of K{displaystyle K} is related to another, then that other element also relates to the first. I mean,

Русский Русский x,and한 한 K:xRand⇒ ⇒ andRx{displaystyle forall x,yin K;:quad x{mathcal {R}y};Rightarrow ;y{mathcal {R}x}.

• Transitivity: If an element of K{displaystyle K} is related to another, and that other in turn relates to a third party, then the first will also be related to the latter. I mean,

Русский Русский x,and,z한 한 K:xRand∧ ∧ andRz⇒ ⇒ xRz{displaystyle forall x,y,zin K;:quad x{mathcal {R}}yland and{mathcal {R}zquad Rightarrow quad x{mathcal {R}z}.

Notation:

In modular arithmetic the equivalence ratio between two elements x{displaystyle x} e and{displaystyle and} denotes x≡ ≡ and(mordR){displaystyle xequiv y(modR)} read «x{displaystyle x} equivalent to and{displaystyle and} module R{displaystyle R}».

An equivalence ratio ♥ ♥ {displaystyle sim } on a body K{displaystyle K} can denote with the pair (K,♥ ♥ ){displaystyle (K,sim),}.

Equivalence class or equivalence relation

In class logic and mathematical analysis, the relation of equivalence R{displaystyle {mathcal {R}}} defines disjunct subsets in K{displaystyle K} called equivalence classes:

Given an element a한 한 K{displaystyle ain K}, the set given by all elements related to a{displaystyle a} define the class:

[chuckles]a]={b한 한 K日本語aRb!{displaystyle [a]={bin K, structured, a{mathcal {R}b}}}}

is called the equivalence class associated with the element a{displaystyle a}.

The element a{displaystyle a} He's called a class representative.

The number of classes generated by an equivalence relation is called order; if this is finite, the relation is said to be of finite order.

The concept of equivalence class is important in science, given a set of objects or abstract entities (potentially infinite), equivalence relations can be established based on some criteria, the resulting classes are the "types& #3. 4; into which the entire range of objects can be classified.^{[citation needed]}

Quotient set

The set of all equivalence classes is called the quotient set and is denoted as:

K/R{displaystyle K/{mathcal {R}}}

K/♥ ♥ {displaystyle K/sim }

Partition

An equivalence relation on a set induces a partition of the set, that is, a set in which an equivalence relation has been defined can be divided into several subsets of elements equivalent to each other and such that the union of these subsets matches the entire set. The following theorem expresses this same idea in more formal terms:

ProposedOne equivalence ratio in the non-empty set K determines a partition of this, and all partition K determines a equivalence ratio in this one.

Demonstration

Give a equivalence ratio R{displaystyle {mathcal {R}}} in K: To see that the intersection is empty, suppose that it is not, that is, given [a] and [b] two different classes and c한 한 [chuckles]a] [chuckles]b]{displaystyle cin [a]cap [b]} Then you have: By symmetry cRb⇒ ⇒ bRc.{displaystyle c{mathcal {R}bRightarrow b{mathcal {R}c. ! By transitivity bRc{displaystyle b{mathcal {R}c} and cRa⇒ ⇒ bRa.{displaystyle c{mathcal {R}aRightarrow b{mathcal {R}a. ! Therefore [a]=[b] which is a contradiction, therefore two different classes do not have elements in common, as well as any element of K belongs to a class, it is well defined a partition. Given a K partition, {Ai!i한 한 I{displaystyle {A_{i}{iin}}}, we can define the following class of equivalence: Given two elements a and b of K are related if they belong to the same set Ai.{displaystyle A_{i}. !

The partition has equivalence classes as elements. These are disjoint two by two and the union of them is equal to the set K.

• for any two ai,aj{displaystyle a_{i},a_{j}}} non-related we have: [chuckles]ai] [chuckles]aj]=∅ ∅ {displaystyle [a_{i}]cap [a_{j}]=emptyset };
• the union of all integrates to the total: s[chuckles]as]=K{displaystyle bigcup _{s}[a_{s}]=K}

Examples

• Be N= {0,1,2, 3...}. An equivalence ratio is defined in NxN, as follows: (a;b)~ (c;d) yes and only if a+d = b +c. This is an equivalence ratio in NxN and each equivalence class is an integer. [(2;0)]= { (x;y)/ 2+y = 0 + x } to (2;0) is called Canon representative and denotes, simplifiedly, 2.

• Mathematical equality

• The M module congruence ratio in the whole numbers (i.e. M한 한 Z{displaystyle Min mathbb {Z} }), where it is defined: a♥ ♥ b{displaystyle asim b} Yes and only if a− − b{displaystyle a-b,} It's multiple of M.

This relationship is of equivalence because:

• It is reflective: a - a = 0, which is multiple of M.
• It is symmetrical: if a - b is multiple of M, then b - a = -(a - b) is also multiple of M.
• It is transient: be k and l integers such that a - b = M k and b - c = M l. Then, a - c = (a - b) + (b - c) = M k + M l = M(k + l) and therefore a multiple of M. In particular, if M = 2 we have the traditional classification of integers in pairs and odds.

• Sea H a subgroup of a group G. Defining for group elements a♥ ♥ b{displaystyle asim b} Yes and only if ab− − 1한 한 H{displaystyle ab^{-1}in H}, will have the equivalence ratio called module congruence H.

• Defining, for group elements, a♥ ♥ b{displaystyle asim b} Yes and only if it exists g in G such as gag− − 1=b{displaystyle gag^{-1}=b}, it is called conjugation ratio. His classes are called conjugation classes. The equivalence classes receive the name of orbit or class of conjugation.^{[chuckles]required]}

• Be the real numbers to and b, we'll say a♥ ♥ b{displaystyle asim b} Yes and only if their entire maximums are equal. The equivalence class is the intervals [n; n+1) where n is an integer. Thus 3,56 and 3,875 are equivalents because they have the same whole maximum = 3.

Fundamental Theorem of Equivalence Relations

A key result links equivalence relations and partitions:

• An equivalence ratio ~ on a set X divide a X.
• Conversely, corresponding to any partition X, there is an equivalence ratio ~ about X.

In both cases, the partition cells of X are the equivalence classes of X by ~. Since each element of X belongs to a unique cell of any partition of X, and since each cell of the partition is identical to an equivalence class of X by ~, each element of ' 'X belongs to a unique equivalence class of X times ~. Thus, there is a natural bijection between the set of all equivalence relations on X and the set of all partitions on X.

Comparing Equivalence Relations

Yeah. ♥ ♥ {displaystyle sim } and ≈ ≈ {displaystyle approx } are two equivalence relationships in the same set S{displaystyle S}and a♥ ♥ b{displaystyle asim b} implies that a≈ ≈ b{displaystyle aapprox b} for all a,b한 한 S,{displaystyle a,bin S,} then. ≈ ≈ {displaystyle approx } is said to be a relationship thicker that ♥ ♥ {displaystyle sim }and ♥ ♥ {displaystyle sim } It's a relationship. more thin that ≈ ≈ {displaystyle approx }. Equivalently,

• ♥ ♥ {displaystyle sim } It's finer than ≈ ≈ {displaystyle approx } if every kind of equivalence ♥ ♥ {displaystyle sim } is a subset of a class of equivalence ≈ ≈ {displaystyle approx }and therefore every kind of equivalence of ≈ ≈ {displaystyle approx } is a union of equivalence classes ♥ ♥ {displaystyle sim }.
• ♥ ♥ {displaystyle sim } It's finer than ≈ ≈ {displaystyle approx } if the partition created by ♥ ♥ {displaystyle sim } is a refinement of the partition created by ≈ ≈ {displaystyle approx }.

The equivalence relation of equality is the finest equivalence relation of any set, while the universal relation, which relates all pairs of elements, is the coarsest.

The relationship "♥ ♥ {displaystyle sim } It's finer than ≈ ≈ {displaystyle approx }"on the collection of all equivalence relationships in a fixed set is itself a partial order relationship, which makes the collection a geometric network.