Editing Equivalence relation (section)

== Related important definitions ==

Let <math>a, b \in X</math>, and <math>\sim</math> be an equivalence relation. Some key definitions and terminology follow:

=== Equivalence class ===
{{main|Equivalence class}}

A subset <math>Y</math> of <math>X</math> such that <math>a \sim b</math> holds for all <math>a</math> and <math>b</math> in <math>Y</math>, and never for <math>a</math> in <math>Y</math> and <math>b</math> outside <math>Y</math>, is called an ''equivalence class'' of <math>X</math> by <math>\sim</math>. Let <math>[a] := \{x \in X : a \sim x\}</math> denote the equivalence class to which <math>a</math> belongs. All elements of <math>X</math> equivalent to each other are also elements of the same equivalence class.

=== Quotient set ===
{{main|Quotient set}}

The set of all equivalence classes of <math>X</math> by <math>\sim,</math> denoted <math>X / \mathord{\sim} := \{[x] : x \in X\},</math> is the ''quotient set'' of <math>X</math> by <math>\sim.</math> If <math>X</math> is a [[topological space]], there is a natural way of transforming <math>X / \sim</math> into a topological space; see ''[[Quotient space (topology)|Quotient space]]'' for the details.{{undue weight inline|date=October 2024}}

=== Projection ===
{{main|Projection (relational algebra)}}

The ''projection'' of <math>\,\sim\,</math> is the function <math>\pi : X \to X/\mathord{\sim}</math> defined by <math>\pi(x) = [x]</math> which maps elements of <math>X</math> into their respective equivalence classes by <math>\,\sim.</math>
: '''Theorem''' on [[Projection (set theory)|projection]]s:<ref>[[Garrett Birkhoff]] and [[Saunders Mac Lane]], 1999 (1967). ''Algebra'', 3rd ed. p.&nbsp;35, Th. 19. Chelsea.</ref>  Let the function <math>f : X \to B</math> be such that if <math>a \sim b</math> then <math>f(a) = f(b).</math> Then there is a unique function <math>g : X / \sim \to B</math> such that <math>f = g \pi.</math> If <math>f</math> is a [[surjection]] and <math>a \sim b \text{ if and only if } f(a) = f(b),</math> then <math>g</math> is a [[bijection]].

=== Equivalence kernel ===
The '''equivalence kernel''' of a function <math>f</math> is the equivalence relation ~ defined by <math>x \sim y \text{ if and only if } f(x) = f(y).</math> The equivalence kernel of an [[Injective function|injection]] is the [[identity relation]].

=== Partition ===
{{main|Partition of a set}}
A ''partition'' of ''X'' is a set ''P'' of nonempty subsets of ''X'', such that every element of ''X'' is an element of a single element of ''P''. Each element of ''P'' is a ''cell'' of the partition. Moreover, the elements of ''P'' are [[pairwise disjoint]] and their [[Union (set theory)|union]] is ''X''.

==== Counting partitions ====

Let ''X'' be a finite set with ''n'' elements. Since every equivalence relation over ''X'' corresponds to a partition of ''X'', and vice versa, the number of equivalence relations on ''X'' equals the number of distinct partitions of ''X'', which is the ''n''th [[Bell number]] ''B<sub>n</sub>'':
:<math display="block">B_n = \frac{1}{e} \sum_{k=0}^\infty \frac{k^n}{k!} \quad</math> ([[Dobinski's formula]]).