nLab
equivalence class

Equivalence classes

Idea

An equivalence class is an element of a quotient set.

Definitions

There are a variety of ways to make this precise.

Axiomatic

Let SS be a set, and let {\sim} be an equivalence relation on SS. Then there exists a set S/S/{\sim}, the quotient set of SS modulo \sim. Given any element xx of SS, there is an element [x] [x]_{\sim} of S/S/{\sim}, the equivalence class of xx modulo {\sim}. Every element of S/S/{\sim} is of this form. Furthermore, [x] [x]_{\sim} and [y] [y]_{\sim} are equal in S/S/{\sim} if and only if xyx \sim y in SS.

The axiom of quotients is an axiom of set theory which states that the paragraph above is true. It corresponds to the clause in the definition of a pretopos (or in Giraud's axioms for a Grothendieck topos) that every congruence has a coequaliser. In most formulations of set theory, this axiom is not needed; instead, it is a theorem when equivalence classes are defined in one of the ways below.

As subsets

Again, let SS be a set, and let {\sim} be an equivalence relation on SS. Let xx be an element of SS. Then the equivalence class of xx modulo {\sim} is the subset of SS consisting of those elements of SS that are equivalent to xx:

[x] {y:S|xy}. [x]_{\sim} \coloneqq \{ y\colon S \;|\; x \sim y \} .

Then the quotient set S/S/{\sim} is the collection of these equivalence classes.

We may construct this collection using the power set of SS; therefore, this may be done in any elementary topos as well as in such diverse set theories as ZFC, SEAR, and ETCS. This definition of equivalence class is quite natural in material set theory, since it immediately produces a set (assuming that subsets are sets).

Redefined equality

In some foundations of mathematics, sets are not fundamental, but are defined as more basic presets (sometimes called types? or, confusingly, sets). By definition, a set (sometimes called a setoid) is a preset equipped with an equivalence (pre)relation.

Once more, let SS be a set, and let {\sim} be an equivalence relation on SS. Then the quotient set S/S/{\sim} is the the underlying preset of SS equipped with \sim (in place of the original equality on SS), and the equivalence class [x] [x]_{\sim} is simply xx.

As objects of a groupoid

One can also consider sets as groupoids (or \infty-groupoids) with the property of being discrete.

So again, let SS be a set, and let {\sim} be an equivalence relation on SS. Then the quotient set S/S/{\sim} is the (higher) groupoid whose objects are the same as those of SS and with a single morphism from xx to yy iff xyx \sim y (and none otherwise); [x] [x]_{\sim} is simply xx again.

Representatives

Any element xx of SS is a representative of its equivalence class [x][x]. Every equivalence class has at least one representative, and its representatives are all equivalent. The set of representatives is the equivalence class in the material set-theoretic sense.

One usually defines properties of equivalence classes and functions on quotient sets by defining them for an arbitrary representative, then proving that the result is independent of the representative chosen. This does not require the axiom of choice.

Revised on March 29, 2011 23:19:49 by Toby Bartels (69.171.178.12)