- This article is about equivalency in mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
; for equivalency in musicMusic is an art form whose medium is sound and silence. Its common elements are pitch , rhythm , dynamics, and the sonic qualities of timbre and texture...
see equivalence class (music)In music theory, equivalence class is an equality or equivalence between sets or twelve-tone rows. A relation rather than an operation, it may be contrasted with derivation. "It is not surprising that music theorists have different concepts of equivalence [from each other]..." "Indeed, an informal...
.
In
mathematicsMathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, given a set
X and an
equivalence relationIn mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
~ on
X, the
equivalence class of an element
a in
X is the
subsetIn mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of all elements in
X which are equivalent to
a:
The notion of equivalence classes is useful for constructing sets out of already constructed ones. The set of all equivalence classes in
X given an equivalence relation ~ is usually denoted as
X / ~ and called the
quotient set of
X by ~. This operation can be thought of (very informally) as the act of "dividing" the input set by the equivalence relation, hence both the name "quotient", and the notation, which are both reminiscent of division. One way in which the quotient set resembles division is that if
X is finite and the equivalence classes are all equinumerous, then the order of
X/~ is the quotient of the order of
X by the order of an equivalence class. The quotient set is to be thought of as the set
X with all the equivalent points identified.
For any equivalence relation, there is a
canonical projection map from
X to
X/~ given by (
x) = [
x]. This map is always surjective. In cases where
X has some additional structure, one considers equivalence relations which preserve that structure. Then one says that that structure is
well-definedIn mathematics, well-definition is a mathematical or logical definition of a certain concept or object which uses a set of base axioms in an entirely unambiguous way and satisfies the properties it is required to satisfy. Usually definitions are stated unambiguously, and it is clear they satisfy...
, and the quotient set inherits the structure to become an object of the same
categoryIn mathematics, a category is an algebraic structure that comprises "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose...
in a natural fashion; the
mapIn most of mathematics and in some related technical fields, the term mapping, usually shortened to map, is either a synonym for function, or denotes a particular kind of function which is important in that branch, or denotes something conceptually similar to a function.In graph theory, a map is a...
that sends
a to [
a] is then an
epimorphismIn category theory, an epimorphism is a morphism f : X → Y which is right-cancellative in the sense that, for all morphisms ,...
in that category. See
congruence relationIn abstract algebra, a congruence relation is an equivalence relation on an algebraic structure that is compatible with the structure...
.
The alternative notation [
a]
R can be used to denote that we mean the equivalence class of the element
a specifically with respect to the equivalence relation
R. This is said to be the
R-equivalence class of
a.
Examples
- If X is the set of all cars, and ~ is the equivalence relation "has the same color as", then one particular equivalence class consists of all green cars. X / ~ could be naturally identified with the set of all car colors.
- Consider the "modulo
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
2" equivalence relation on the set Z of integerThe integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s: x~y if and only if x-y is evenIn mathematics, the parity of an object states whether it is even or odd.This concept begins with integers. An even number is an integer that is "evenly divisible" by 2, i.e., divisible by 2 without remainder; an odd number is an integer that is not evenly divisible by 2...
. This relation gives rise to exactly two equivalence classes: one class consisting of all even numbers, and the other consisting of all odd numbers. Under this relation [7] [9] and [1] all represent the same element of Z / ~.
- The rational number
In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
s can be constructed as the set of equivalence classes of ordered pairs of integers (a,b) with b not zero, where the equivalence relation is defined by
-
- (a,b) ~ (c,d) if and only if ad = bc.
- Here the equivalence class of the pair (a,b) can be identified with rational number a/b. This construction can be generalized to the field of fractions
In abstract algebra, the field of fractions or field of quotients of an integral domain is the smallest field in which it can be embedded. The elements of the field of fractions of the integral domain R have the form a/b with a and b in R and b ≠ 0...
of an integral domain.
- Any function
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
f : X → Y defines an equivalence relation on X by x1 ~ x2 if and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
f(x1) = f(x2). The equivalence class of x is the set of all elements in X which get mapped to f(x), i.e. the class [x] is the inverse image of f(x). This equivalence relation is known as the kernelIn set theory, the kernel of a function f may be taken to be either*the equivalence relation on the function's domain that roughly expresses the idea of "equivalent as far as the function f can tell", or*the corresponding partition of the domain....
of f.
- Given a group
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
G and a subgroupIn group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
H, we can define an equivalence relation on G by x ~ y if and only if xy -1 ∈ H. The equivalence classes are known as right cosetIn mathematics, if G is a group, and H is a subgroup of G, and g is an element of G, thenA coset is a left or right coset of some subgroup in G...
s of H in G; one of them is H itself. They all have the same number of elements (or cardinality in the case of an infinite H). If H is a normal subgroupIn abstract algebra, a normal subgroup is a subgroup which is invariant under conjugation by members of the group. Normal subgroups can be used to construct quotient groups from a given group....
, then the set of all cosets is itself a group in a natural way.
- Every group can be partitioned into equivalence classes called conjugacy class
In mathematics, especially group theory, the elements of any group may be partitioned into conjugacy classes; members of the same conjugacy class share many properties, and study of conjugacy classes of non-abelian groups reveals many important features of their structure...
es.
- The homotopy
In topology, two continuous functions from one topological space to another are called homotopic if one can be "continuously deformed" into the other, such a deformation being called a homotopy between the two functions...
class of a continuousIn mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...
map f is the equivalence class of all maps homotopic to f.
- In natural language processing
Natural language processing is a field of computer science and linguistics concerned with the interactions between computers and human languages; it began as a branch of artificial intelligence....
, an equivalence class is a set of all references to a single person, place, thing, or event, either real or conceptual. For example, in the sentence "GE shareholders will vote for a successor to the company's outgoing CEO Jack Welch", GE and the company are synonymous, and thus constitute one equivalence class. There are separate equivalence classes for GE shareholders and Jack Welch.
- In an equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
's matrix, the equivalence classes appear as blocks. In this example these equivalence blocks are marked in different colors, to be easily recognized.
Properties
Because of the properties of an equivalence relation it holds that
a is in [
a] and that any two equivalence classes are either equal or
disjoint. It follows that the set of all equivalence classes of
X forms a
partitionIn mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
of
X: every element of
X belongs to one and only one equivalence class. Conversely every partition of
X also defines an equivalence relation over
X.
It also follows from the properties of an equivalence relation that
-
- a ~ b if and only if [a] = [b].
If ~ is an equivalence relation on
X, and
P(
x) is a property of elements of
x, such that whenever
x ~
y,
P(
x) is true if
P(
y) is true, then the property
P is said to be
well-definedIn mathematics, well-definition is a mathematical or logical definition of a certain concept or object which uses a set of base axioms in an entirely unambiguous way and satisfies the properties it is required to satisfy. Usually definitions are stated unambiguously, and it is clear they satisfy...
or a
class invariant under the relation ~.
A frequent particular case occurs when
f is a function from
X to another set
Y; if
x1 ~
x2 implies
f(
x1) =
f(
x2) then
f is said to be a
morphism for ~, a
class invariant under ~, or simply
invariant under ~. This occurs, e.g. in the character theory of finite groups. The latter case with the function
f can be expressed by a commutative triangle. See also
invariantIn mathematics, an invariant is a property of a class of mathematical objects that remains unchanged when transformations of a certain type are applied to the objects. The particular class of objects and type of transformations are usually indicated by the context in which the term is used...
. Some authors use "compatible with ~" or just "respects ~" instead of "invariant under ~".
More generally, a function may map equivalent arguments (under an equivalence relation ~
A) to equivalent values (under an equivalence relation ~
B). Such a function is known as a morphism from ~
A to ~
B.
In other words, if ~ is an equivalence relation on a set
A and
a and
b are two elements, then these statements are equivalent:
- a ~ b
-
-
See also
- First Isomorphism Theorem
- In computing a form of testing is based on equivalence partitions
Equivalence partitioning is a software testing technique that divides the input data of a software unit into partitions of data from which test cases can be derived. In principle, test cases are designed to cover each partition at least once...
, which are based on equivalence classes.