Equivalence class: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 11:05, 8 December 2024

In mathematics, when the elements of some set $S$ have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set $S$ into equivalence classes. These equivalence classes are constructed so that elements $a$ and $b$ belong to the same equivalence class if, and only if, they are equivalent.

Formally, given a set $S$ and an equivalence relation $\,\sim \,$ on $S,$ the equivalence class of an element $a$ in $S$ is denoted $[a]$ or, equivalently, $[a]_{\sim }$ to emphasize its equivalence relation $\sim .$ The definition of equivalence relations implies that the equivalence classes form a partition of $S,$ meaning, that every element of the set belongs to exactly one equivalence class. The set of the equivalence classes is sometimes called the quotient set or the quotient space of $S$ by $\,\sim \,,$ and is denoted by $S/{\sim }.$

When the set $S$ has some structure (such as a group operation or a topology) and the equivalence relation $\,\sim \,$ is compatible with this structure, the quotient set often inherits a similar structure from its parent set. Examples include quotient spaces in linear algebra, quotient spaces in topology, quotient groups, homogeneous spaces, quotient rings, quotient monoids, and quotient categories.

Definition and notation

An equivalence relation on a set $X$ is a binary relation $\,\sim \,$ on $X$ satisfying the three properties:^[1]

$a\sim a$ for all $a\in X$ (reflexivity),
$a\sim b$ implies $b\sim a$ for all $a,b\in X$ (symmetry),
if $a\sim b$ and $b\sim c$ then $a\sim c$ for all $a,b,c\in X$ (transitivity).

The equivalence class of an element $a$ is defined as^[2]

[a]=\{x\in X:a\sim x\}.

The word "class" in the term "equivalence class" may generally be considered as a synonym of "set", although some equivalence classes are not sets but proper classes. For example, "being isomorphic" is an equivalence relation on groups, and the equivalence classes, called isomorphism classes, are not sets.

The set of all equivalence classes in $X$ with respect to an equivalence relation $R$ is denoted as $X/R,$ and is called $X$ modulo $R$ (or the quotient set of $X$ by $R$ ).^[3] The surjective map $x\mapsto [x]$ from $X$ onto $X/R,$ which maps each element to its equivalence class, is called the canonical surjection, or the canonical projection.

Every element of an equivalence class characterizes the class, and may be used to represent it. When such an element is chosen, it is called a representative of the class. The choice of a representative in each class defines an injection from $X/R$ to $X$ . Since its composition with the canonical surjection is the identity of $X/R,$ such an injection is called a section, when using the terminology of category theory.

Sometimes, there is a section that is more "natural" than the other ones. In this case, the representatives are called canonical representatives. For example, in modular arithmetic, for every integer $m$ greater than $1$ , the congruence modulo $m$ is an equivalence relation on the integers, for which two integers $a$ and $b$ are equivalent—in this case, one says congruent—if $m$ divides $a-b;$ this is denoted ${\textstyle a\equiv b{\pmod {m}}.}$ Each class contains a unique non-negative integer smaller than $m,$ and these integers are the canonical representatives.

The use of representatives for representing classes allows avoiding to consider explicitly classes as sets. In this case, the canonical surjection that maps an element to its class is replaced by the function that maps an element to the representative of its class. In the preceding example, this function is denoted $a{\bmod {m}},$ and produces the remainder of the Euclidean division of $a$ by $m$ .

Properties

Every element $x$ of $X$ is a member of the equivalence class $[x].$ Every two equivalence classes $[x]$ and $[y]$ are either equal or disjoint. Therefore, the set of all equivalence classes of $X$ forms a partition of $X$ : every element of $X$ belongs to one and only one equivalence class.^[4] Conversely, every partition of $X$ comes from an equivalence relation in this way, according to which $x\sim y$ if and only if $x$ and $y$ belong to the same set of the partition.^[5]

It follows from the properties in the previous section that if $\,\sim \,$ is an equivalence relation on a set $X,$ and $x$ and $y$ are two elements of $X,$ the following statements are equivalent:

$x\sim y$
$[x]=[y]$
$[x]\cap [y]\neq \emptyset .$

Examples

Let $X$ be the set of all rectangles in a plane, and $\,\sim \,$ the equivalence relation "has the same area as", then for each positive real number $A,$ there will be an equivalence class of all the rectangles that have area $A.$ ^[6]
Consider the modulo 2 equivalence relation on the set of integers, $\mathbb {Z} ,$ such that $x\sim y$ if and only if their difference $x-y$ is an even number. This relation gives rise to exactly two equivalence classes: one class consists of all even numbers, and the other class consists of all odd numbers. Using square brackets around one member of the class to denote an equivalence class under this relation, $[7],[9],$ and $[1]$ all represent the same element of $\mathbb {Z} /{\sim }.$ ^[2]
Let $X$ be the set of ordered pairs of integers $(a,b)$ with non-zero $b,$ and define an equivalence relation $\,\sim \,$ on $X$ such that $(a,b)\sim (c,d)$ if and only if $ad=bc,$ then the equivalence class of the pair $(a,b)$ can be identified with the rational number $a/b,$ and this equivalence relation and its equivalence classes can be used to give a formal definition of the set of rational numbers.^[7] The same construction can be generalized to the field of fractions of any integral domain.
If $X$ consists of all the lines in, say, the Euclidean plane, and $L\sim M$ means that $L$ and $M$ are parallel lines, then the set of lines that are parallel to each other form an equivalence class, as long as a line is considered parallel to itself. In this situation, each equivalence class determines a point at infinity.

Graphical representation

Graph of an example equivalence with 7 classes

An undirected graph may be associated to any symmetric relation on a set $X,$ where the vertices are the elements of $X,$ and two vertices $s$ and $t$ are joined if and only if $s\sim t.$ Among these graphs are the graphs of equivalence relations. These graphs, called cluster graphs, are characterized as the graphs such that the connected components are cliques.^[2]

Invariants

If $\,\sim \,$ is an equivalence relation on $X,$ and $P(x)$ is a property of elements of $X$ such that whenever $x\sim y,$ $P(x)$ is true if $P(y)$ is true, then the property $P$ is said to be an invariant of $\,\sim \,,$ or well-defined under the relation $\,\sim .$

A frequent particular case occurs when $f$ is a function from $X$ to another set $Y$ ; if $f\left(x_{1}\right)=f\left(x_{2}\right)$ whenever $x_{1}\sim x_{2},$ then $f$ is said to be class invariant under $\,\sim \,,$ or simply invariant under $\,\sim .$ This occurs, for example, in the character theory of finite groups. Some authors use "compatible with $\,\sim \,$ " or just "respects $\,\sim \,$ " instead of "invariant under $\,\sim \,$ ".

Any function $f:X\to Y$ is class invariant under $\,\sim \,,$ according to which $x_{1}\sim x_{2}$ if and only if $f\left(x_{1}\right)=f\left(x_{2}\right).$ The equivalence class of $x$ is the set of all elements in $X$ which get mapped to $f(x),$ that is, the class $[x]$ is the inverse image of $f(x).$ This equivalence relation is known as the kernel of $f.$

More generally, a function may map equivalent arguments (under an equivalence relation $\sim _{X}$ on $X$ ) to equivalent values (under an equivalence relation $\sim _{Y}$ on $Y$ ). Such a function is a morphism of sets equipped with an equivalence relation.

Quotient space in topology

In topology, a quotient space is a topological space formed on the set of equivalence classes of an equivalence relation on a topological space, using the original space's topology to create the topology on the set of equivalence classes.

In abstract algebra, congruence relations on the underlying set of an algebra allow the algebra to induce an algebra on the equivalence classes of the relation, called a quotient algebra. In linear algebra, a quotient space is a vector space formed by taking a quotient group, where the quotient homomorphism is a linear map. By extension, in abstract algebra, the term quotient space may be used for quotient modules, quotient rings, quotient groups, or any quotient algebra. However, the use of the term for the more general cases can as often be by analogy with the orbits of a group action.

The orbits of a group action on a set may be called the quotient space of the action on the set, particularly when the orbits of the group action are the right cosets of a subgroup of a group, which arise from the action of the subgroup on the group by left translations, or respectively the left cosets as orbits under right translation.

A normal subgroup of a topological group, acting on the group by translation action, is a quotient space in the senses of topology, abstract algebra, and group actions simultaneously.

Although the term can be used for any equivalence relation's set of equivalence classes, possibly with further structure, the intent of using the term is generally to compare that type of equivalence relation on a set $X,$ either to an equivalence relation that induces some structure on the set of equivalence classes from a structure of the same kind on $X,$ or to the orbits of a group action. Both the sense of a structure preserved by an equivalence relation, and the study of invariants under group actions, lead to the definition of invariants of equivalence relations given above.

Notes

^ Devlin 2004, p. 122.
^ ^a ^b ^c Devlin 2004, p. 123.
^ Wolf 1998, p. 178
^ Maddox 2002, p. 74, Thm. 2.5.15
^ Avelsgaard 1989, p. 132, Thm. 3.16
^ Avelsgaard 1989, p. 127
^ Maddox 2002, pp. 77–78

References

Avelsgaard, Carol (1989), Foundations for Advanced Mathematics, Scott Foresman, ISBN 0-673-38152-8
Devlin, Keith (2004), Sets, Functions, and Logic: An Introduction to Abstract Mathematics (3rd ed.), Chapman & Hall/ CRC Press, ISBN 978-1-58488-449-1
Maddox, Randall B. (2002), Mathematical Thinking and Writing, Harcourt/ Academic Press, ISBN 0-12-464976-9
Stein, Elias M.; Shakarchi, Rami (2012). Functional Analysis: Introduction to Further Topics in Analysis. Princeton University Press. doi:10.1515/9781400840557. ISBN 978-1-4008-4055-7.
Wolf, Robert S. (1998), Proof, Logic and Conjecture: A Mathematician's Toolbox, Freeman, ISBN 978-0-7167-3050-7

External links

Media related to Equivalence classes at Wikimedia Commons

[FOOTNOTEDevlin2004122-1] Devlin 2004, p. 122.

[FOOTNOTEDevlin2004123-2] Devlin 2004, p. 123.

[3] Wolf 1998, p. 178

[4] Maddox 2002, p. 74, Thm. 2.5.15

[5] Avelsgaard 1989, p. 132, Thm. 3.16

[6] Avelsgaard 1989, p. 127

[7] Maddox 2002, pp. 77–78

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
+{{Short description|Mathematical concept}}
-In [[mathematics]], given a [[set]] ''X'' and an [[equivalence relation]] ~ on ''X'', the '''equivalence class''' of an element ''a'' in ''X'' is the [[subset]] of all elements in ''X'' which are equivalent to ''a'':
+{{About|equivalency in mathematics|equivalency in music|equivalence class (music)}}
-:[a] = { ''x'' in ''X'' | ''x'' ~ ''a'' }
+{{Redirect|Quotient map|Quotient map in topology|Quotient map (topology)}}
+[[File:Congruent non-congruent triangles.svg|thumb|370px|[[Congruence (geometry)|Congruence]] is an example of an equivalence relation. The leftmost two triangles are congruent, while the third and fourth triangles are not congruent to any other triangle shown here. Thus, the first two triangles are in the same equivalence class, while the third and fourth triangles are each in their own equivalence class.]]
-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 indeed) 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.
+In [[mathematics]], when the elements of some [[Set (mathematics)|set]] <math>S</math> have a notion of equivalence (formalized as an [[equivalence relation]]), then one may naturally split the set <math>S</math> into '''equivalence classes'''. These equivalence classes are constructed so that elements <math>a</math> and <math>b</math> belong to the same '''equivalence class''' [[if, and only if]], they are equivalent.
-In cases where ''X'' has some additional structure preserved under ~, the quotient becomes an object of the same type in a natural fashion; the [[map (mathematics)|map]] that sends ''a'' to [''a''] is then an [[epimorphism]]. See [[congruence relation]].
+Formally, given a set <math>S</math> and an equivalence relation <math>\,\sim\,</math> on <math>S,</math> the {{em|equivalence class}} of an element <math>a</math> in <math>S</math> is denoted <math>[a]</math> or, equivalently, <math>[a]_{\sim}</math> to emphasize its equivalence relation <math>\sim.</math> The definition of equivalence relations implies that the equivalence classes form a [[Partition of a set|partition]] of <math>S,
-== Examples ==
+</math>  meaning, that every element of the set belongs to exactly one equivalence class.
-* If ''X'' is the set of all cars, and ~ is the equivalence relation of "having the same color", then one particular equivalence class consists of all green cars. ''X'' / ~ could be naturally identified with the set of all car colors.
+The set of the equivalence classes is sometimes called the '''quotient set''' or the '''quotient space''' of <math>S</math> by <math>\,\sim\,,</math> and is denoted by <math>S /{\sim}.</math>
-* Consider the "[[modular arithmetic|modulo]] 2" equivalence relation on the set of [[integer]]s: ''x''~''y'' if and only if ''x''-''y'' is [[even and odd numbers|even]]. This relation gives rise to exactly two equivalence classes: [0] consisting of all even numbers, and [1] consisting of all odd numbers.
-* The [[rational number]]s can be constructed as the set of equivalence classes of 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''. ''Is this the origin of the term quotient set?''
-* Any [[function (mathematics)|function]] ''f'' : ''X'' &rarr; ''Y'' defines an equivalence relation an ''X'' by ''x'' ~ ''y'' [[iff]] ''f''(''x'') = ''f''(''y''). 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 [[kernel of a function|kernel]] of ''f''.
-* Given a [[group (mathematics)|group]] ''G'' and a [[subgroup]] ''H'', we can define an equivalence relation on ''G'' by ''x'' ~ ''y'' iff ''xy''<sup>&nbsp;-1</sup> &isin; ''H''. The equivalence classes are known as right [[coset]]s of ''H'' in ''G''. If ''H'' is a [[normal subgroup]], 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]]es.
-* The [[homotopy]] class of a [[continuous function|continuous]] map ''f'' is the equivalence class of all maps homotopic to ''f''.
-* In [[natural language processing]], 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 synonomous, and thus constitute one equivalence class. There are separate equivalence classes for ''GE shareholders'' and ''Jack Welch''.
+When the set <math>S</math> has some structure (such as a [[group (mathematics)|group operation]] or a [[topological space|topology]]) and the equivalence relation <math>\,\sim\,</math> is compatible with this structure, the quotient set often inherits a similar structure from its parent set. Examples include [[quotient space (linear algebra)|quotient spaces in linear algebra]], [[quotient space (topology)|quotient spaces in topology]], [[quotient group]]s, [[homogeneous space]]s, [[quotient ring]]s, [[quotient monoid]]s, and [[quotient category|quotient categories]].
-== Properties ==
+==Definition and notation==
-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 sets|disjoint]]. It follows that the set of all equivalence classes of ''X'' forms a [[partition of a set|partition]] 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''.
+An [[equivalence relation]] on a set <math>X</math> is a [[binary relation]] <math>\,\sim\,</math> on <math>X</math> satisfying the three properties:{{sfn|Devlin|2004|p=122}}
-It also follows from the properties of an equivalence relation that
+* <math>a \sim a</math> for all <math>a \in X</math> ([[Reflexive relation|reflexivity]]),
-:: ''a'' ~ ''b'' if and only if [''a''] = [''b''].
+* <math>a \sim b</math> implies <math>b \sim a</math> for all <math>a, b \in X</math> ([[Symmetric relation|symmetry]]),
+* if <math>a \sim b</math> and <math>b \sim c</math> then <math>a \sim c</math> for all <math>a, b, c \in X</math> ([[Transitive relation|transitivity]]).
+{{anchor|Notation and formal definition}}The equivalence class of an element <math>a</math> is defined as{{sfn|Devlin|2004|p=123}}
-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 iff ''P''(''y'') is true, then the property ''P'' is said to be a ''class invariant'' under the relation ~. A frequent particular case occurs when ''f'' is a function from ''X'' to another set ''Y''; if ''x'' ~ ''y'' implies ''f''(''x'') = ''f''(''y'') then ''f'' is said to be 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 [[invariant (mathematics)|invariant]].
+:<math>[a] = \{ x \in X : a \sim x \}.</math>
+The word "class" in the term "equivalence class" may generally be considered as a synonym of "[[set (mathematics)|set]]", although some equivalence classes are not sets but [[proper class]]es. For example, "being [[group isomorphism|isomorphic]]" is an equivalence relation on [[group (mathematics)|groups]], and the equivalence classes, called [[isomorphism class]]es, are not sets.
+The set of all equivalence classes in <math>X</math> with respect to an equivalence relation <math>R</math> is denoted as <math>X / R,</math> and is called <math>X</math> [[Modulo (mathematics)|modulo]] <math>R</math> (or the '''{{vanchor|quotient set}}''' of <math>X</math> by <math>R</math>).<ref>{{harvnb|Wolf|1998|loc=p. 178}}</ref> The [[surjective map]] <math>x \mapsto [x]</math> from <math>X</math> onto <math>X / R,</math> which maps each element to its equivalence class, is called the '''{{vanchor|canonical surjection}}''', or the '''canonical projection'''.
+{{anchor|representative}}Every element of an equivalence class characterizes the class, and may be used to ''represent'' it. When such an element is chosen, it is called a '''representative''' of the class. The choice of a representative in each class defines an [[injective function|injection]] from <math>X / R</math> to {{mvar|X}}. Since its [[function composition|composition]] with the canonical surjection is the identity of <math>X / R,</math> such an injection is called a [[Section (category theory)|section]], when using the terminology of [[category theory]].
+Sometimes, there is a section that is more "natural" than the other ones. In this case, the representatives are called {{em|[[Canonical form|canonical]] representatives}}. For example, in [[modular arithmetic]], for every [[integer]] {{mvar|m}} greater than {{math|1}}, the [[congruence modulo m|congruence modulo {{mvar|m}}]] is an equivalence relation on the integers, for which two integers {{mvar|a}} and {{mvar|b}} are equivalent—in this case, one says ''congruent''—if {{mvar|m}} divides <math>a-b;</math> this is denoted <math DISPLAY=inline>a\equiv b \pmod m.</math> Each class contains a unique non-negative integer smaller than <math>m,</math> and these integers are the canonical representatives.
+The use of representatives for representing classes allows avoiding to consider explicitly classes as sets. In this case, the canonical surjection that maps an element to its class is replaced by the function that maps an element to the representative of its class. In the preceding example, this function is denoted <math>a \bmod m,</math> and produces the remainder of the [[Euclidean division]] of {{mvar|a}} by {{mvar|m}}.
+==Properties==
+Every element <math>x</math> of <math>X</math> is a member of the equivalence class <math>[x].</math> Every two equivalence classes <math>[x]</math> and <math>[y]</math> are either equal or [[disjoint sets|disjoint]]. Therefore, the set of all equivalence classes of <math>X</math> forms a [[partition of a set|partition]] of <math>X</math>: every element of <math>X</math> belongs to one and only one equivalence class.<ref>{{harvnb|Maddox|2002|loc=p. 74, Thm. 2.5.15}}</ref> Conversely, every partition of <math>X</math> comes from an equivalence relation in this way, according to which <math>x \sim y</math> if and only if <math>x</math> and <math>y</math> belong to the same set of the partition.<ref>{{harvnb|Avelsgaard|1989|loc=p. 132, Thm. 3.16}}</ref>
+It follows from the properties in the previous section that if <math>\,\sim\,</math> is an equivalence relation on a set <math>X,</math> and <math>x</math> and <math>y</math> are two elements of <math>X,</math> the following statements are equivalent:
+* <math>x \sim y</math>
+* <math>[x] = [y]</math>
+* <math>[x] \cap [y] \ne \emptyset.</math>
+==Examples==
+* Let <math>X</math> be the set of all rectangles in a plane, and <math>\,\sim\,</math> the equivalence relation "has the same area as", then for each positive real number <math>A,</math> there will be an equivalence class of all the rectangles that have area <math>A.</math><ref>{{harvnb|Avelsgaard|1989|loc=p. 127}}</ref>
+* Consider the [[Modular arithmetic|modulo]] 2 equivalence relation on the set of [[integer]]s, <math>\Z,</math> such that <math>x \sim y</math> if and only if their difference <math>x - y</math> is an [[even number]]. This relation gives rise to exactly two equivalence classes: one class consists of all even numbers, and the other class consists of all odd numbers. Using square brackets around one member of the class to denote an equivalence class under this relation, <math>[7], [9],</math> and <math>[1]</math> all represent the same element of <math>\Z /{\sim}.</math>{{sfn|Devlin|2004|p=123}}
+* Let <math>X</math> be the set of [[ordered pair]]s of integers <math>(a, b)</math> with non-zero <math>b,</math> and define an equivalence relation <math>\,\sim\,</math> on <math>X</math> such that <math>(a, b) \sim (c, d)</math> if and only if <math>a d = b c,</math> then the equivalence class of the pair <math>(a, b)</math> can be identified with the [[rational number]] <math>a / b,</math> and this equivalence relation and its equivalence classes can be used to give a formal definition of the set of rational numbers.<ref>{{harvnb|Maddox|2002|loc=pp. 77–78}}</ref> The same construction can be generalized to the [[field of fractions]] of any [[integral domain]].
+* If <math>X</math> consists of all the lines in, say, the [[Euclidean plane]], and <math>L \sim M</math> means that <math>L</math> and <math>M</math> are [[parallel lines]], then the set of lines that are parallel to each other form an equivalence class, as long as a [[parallel (geometry)#Reflexive variant|line is considered parallel to itself]]. In this situation, each equivalence class determines a [[point at infinity]].
+==Graphical representation==
+{{main|Cluster graph}}
+[[File:Equivalentie.svg|thumb|160px|Graph of an example equivalence with 7 classes]]
+An [[undirected graph]] may be associated to any [[symmetric relation]] on a set <math>X,</math> where the vertices are the elements of <math>X,</math> and two vertices <math>s</math> and <math>t</math> are joined if and only if <math>s \sim t.</math> Among these graphs are the graphs of equivalence relations. These graphs, called [[cluster graph]]s, are characterized as the graphs such that the [[Connected component (graph theory)|connected components]] are [[Clique (graph theory)|cliques]].{{sfn|Devlin|2004|p=123}}
+==Invariants==
+If <math>\,\sim\,</math> is an equivalence relation on <math>X,</math> and <math>P(x)</math> is a property of elements of <math>X</math> such that whenever <math>x \sim y,</math> <math>P(x)</math> is true if <math>P(y)</math> is true, then the property <math>P</math> is said to be an [[Invariant (mathematics)|invariant]] of <math>\,\sim\,,</math> or [[well-defined]] under the relation <math>\,\sim.</math>
+A frequent particular case occurs when <math>f</math> is a function from <math>X</math> to another set <math>Y</math>; if  <math>f\left(x_1\right) = f\left(x_2\right)</math> whenever <math>x_1 \sim x_2,</math> then <math>f</math> is said to be {{em|class invariant under}} <math>\,\sim\,,</math> or simply {{em|invariant under}} <math>\,\sim.</math> This occurs, for example, in the [[character theory]] of finite groups. Some authors use "compatible with <math>\,\sim\,</math>" or just "respects <math>\,\sim\,</math>" instead of "invariant under <math>\,\sim\,</math>".
+Any [[Function (mathematics)|function]] <math>f : X \to Y</math> is ''class invariant under'' <math>\,\sim\,,</math> according to which <math>x_1 \sim x_2</math> if and only if <math>f\left(x_1\right) = f\left(x_2\right).</math> The equivalence class of <math>x</math> is the set of all elements in <math>X</math> which get mapped to <math>f(x),</math> that is, the class <math>[x]</math> is the [[inverse image]] of <math>f(x).</math> This equivalence relation is known as the [[Kernel of a function|kernel]] of <math>f.</math>
+More generally, a function may map equivalent arguments (under an equivalence relation <math>\sim_X</math> on <math>X</math>) to equivalent values (under an equivalence relation <math>\sim_Y</math> on <math>Y</math>). Such a function is a [[morphism]] of sets equipped with an equivalence relation.
+==Quotient space in topology==
+In [[topology]], a [[Quotient space (topology)|quotient space]] is a [[topological space]] formed on the set of equivalence classes of an equivalence relation on a topological space, using the original space's topology to create the topology on the set of equivalence classes.
+In [[abstract algebra]], [[congruence relation]]s on the underlying set of an algebra allow the algebra to induce an algebra on the equivalence classes of the relation, called a [[Quotient (universal algebra)|quotient algebra]]. In [[linear algebra]], a [[Quotient space (linear algebra)|quotient space]] is a vector space formed by taking a [[quotient group]], where the quotient homomorphism is a [[linear map]]. By extension, in abstract algebra, the term quotient space may be used for [[quotient module]]s, [[quotient ring]]s, [[quotient group]]s, or any quotient algebra. However, the use of the term for the more general cases can as often be by analogy with the orbits of a group action.
+The orbits of a [[Group action (mathematics)|group action]] on a set may be called the quotient space of the action on the set, particularly when the orbits of the group action are the right [[coset]]s of a subgroup of a group, which arise from the action of the subgroup on the group by left translations, or respectively the left cosets as orbits under right translation.
+A normal subgroup of a topological group, acting on the group by translation action, is a quotient space in the senses of topology, abstract algebra, and group actions simultaneously.
+Although the term can be used for any equivalence relation's set of equivalence classes, possibly with further structure, the intent of using the term is generally to compare that type of equivalence relation on a set <math>X,</math> either to an equivalence relation that induces some structure on the set of equivalence classes from a structure of the same kind on <math>X,</math> or to the orbits of a group action. Both the sense of a structure preserved by an equivalence relation, and the study of [[Invariant (mathematics)|invariants]] under group actions, lead to the definition of [[#Invariants|invariants]] of equivalence relations given above.
 ==See also==
-*first [[isomorphism theorem]]
-*[[up to]]
+* [[Equivalence partitioning]], a method for devising test sets in [[software testing]] based on dividing the possible program inputs into equivalence classes according to the behavior of the program on those inputs
-----
+* [[Homogeneous space]], the quotient space of [[Lie group]]s
-In [[music]] see [[octave equivalency]], [[transpositional equivalency]], [[inversional equivalency]], [[enharmonic equivalency]]. [[Musical set theory]] takes advantage of all of these, to varying degrees, while other theories take more or less advantage of a selection.
+* {{annotated link|Partial equivalence relation}}
+* {{annotated link|Quotient by an equivalence relation}}
+* {{annotated link|Setoid}}
+* {{annotated link|Transversal (combinatorics)}}
+==Notes==
-[[Category:Set theory]]
+{{reflist|30em}}
-[[de:Äquivalenzklasse]]
-[[pl:Klasa abstrakcji]]
+==References==
+* {{citation|first=Carol|last=Avelsgaard|title=Foundations for Advanced Mathematics|publisher=Scott Foresman|year=1989|isbn=0-673-38152-8}}
+* {{citation|last=Devlin|first=Keith|title=Sets, Functions, and Logic: An Introduction to Abstract Mathematics|year=2004|publisher=Chapman & Hall/ CRC Press|edition=3rd|isbn=978-1-58488-449-1}}
+* {{citation|last=Maddox|first=Randall B.|title=Mathematical Thinking and Writing|year=2002|publisher=Harcourt/ Academic Press|isbn=0-12-464976-9}}
+* {{cite book | last=Stein | first=Elias M. | last2=Shakarchi | first2=Rami | title=Functional Analysis: Introduction to Further Topics in Analysis | publisher=Princeton University Press | date=2012 | isbn=978-1-4008-4055-7 | doi=10.1515/9781400840557}}
+* {{citation|last=Wolf|first=Robert S.|title=Proof, Logic and Conjecture: A Mathematician's Toolbox|year=1998|publisher=Freeman|isbn=978-0-7167-3050-7}}
+==Further reading==
+* {{citation|last=Sundstrom|title=Mathematical Reasoning: Writing and Proof|year=2003|publisher=Prentice-Hall}}
+* {{citation|last1=Smith|last2=Eggen|last3=St.Andre|title=A Transition to Advanced Mathematics |edition=6th |year=2006|publisher=Thomson (Brooks/Cole)}}
+* {{citation|last=Schumacher|first=Carol|author-link= Carol Schumacher |title=Chapter Zero: Fundamental Notions of Abstract Mathematics|year=1996|publisher=Addison-Wesley|isbn=0-201-82653-4}}
+* {{citation|last=O'Leary|title=The Structure of Proof: With Logic and Set Theory|year=2003|publisher=Prentice-Hall}}
+* {{citation|last=Lay|title=Analysis with an introduction to proof|year=2001|publisher=Prentice Hall}}
+* {{citation|last=Morash|first=Ronald P.|title=Bridge to Abstract Mathematics|publisher=Random House|year=1987|isbn=0-394-35429-X}}
+* {{citation|last1=Gilbert|last2=Vanstone|title=An Introduction to Mathematical Thinking|year=2005|publisher=Pearson Prentice-Hall}}
+* {{citation|last1=Fletcher|last2=Patty|title=Foundations of Higher Mathematics|publisher=PWS-Kent}}
+* {{citation|last1=Iglewicz|last2=Stoyle|title=An Introduction to Mathematical Reasoning|publisher=MacMillan}}
+* {{citation|last1=D'Angelo|last2=West|title=Mathematical Thinking: Problem Solving and Proofs|year=2000|publisher=Prentice Hall}}
+* {{citation|last=Cupillari|author-link= Antonella Cupillari |title=The Nuts and Bolts of Proofs|publisher=Wadsworth}}
+* {{citation|last=Bond|title=Introduction to Abstract Mathematics|publisher=Brooks/Cole}}
+* {{citation|last1=Barnier|last2=Feldman|title=Introduction to Advanced Mathematics|year=2000|publisher=Prentice Hall}}
+* {{citation|last=Ash|title=A Primer of Abstract Mathematics|publisher=MAA}}
+==External links==
+*{{Commons category-inline|Equivalence classes}}
+{{Set theory}}
+{{Authority control}}
+[[Category:Algebra]]
+[[Category:Binary relations]]
+[[Category:Equivalence (mathematics)]]
+[[Category:Set theory]]

v t e Set theory
Overview	Set (mathematics)
Axioms	Adjunction Choice countable dependent global Constructibility (V=L) Determinacy projective Extensionality Infinity Limitation of size Pairing Power set Regularity Union Martin's axiom Axiom schema replacement specification
Operations	Cartesian product Complement (i.e. set difference) De Morgan's laws Disjoint union Identities Intersection Power set Symmetric difference Union
Concepts Methods	Almost Cardinality Cardinal number (large) Class Constructible universe Continuum hypothesis Diagonal argument Element ordered pair tuple Family Forcing One-to-one correspondence Ordinal number Set-builder notation Transfinite induction Venn diagram
Set types	Amorphous Countable Empty Finite (hereditarily) Filter base subbase Ultrafilter Fuzzy Infinite (Dedekind-infinite) Recursive Singleton Subset · Superset Transitive Uncountable Universal
Theories	Alternative Axiomatic Naive Cantor's theorem Zermelo General Principia Mathematica New Foundations Zermelo–Fraenkel von Neumann–Bernays–Gödel Morse–Kelley Kripke–Platek Tarski–Grothendieck
Paradoxes Problems	Russell's paradox Suslin's problem Burali-Forti paradox
Set theorists	Paul Bernays Georg Cantor Paul Cohen Richard Dedekind Abraham Fraenkel Kurt Gödel Thomas Jech John von Neumann Willard Quine Bertrand Russell Thoralf Skolem Ernst Zermelo