Difference between revisions of "Quotient by an equivalence relation"

Latest revision as of 14:16, 13 November 2016

Definition

Let [ilmath]X[/ilmath] be a set and let [ilmath]\sim\subseteq X\times X[/ilmath] be an equivalence relation on [ilmath]X[/ilmath]. Then the quotient of [ilmath]X[/ilmath] by [ilmath]\sim[/ilmath], denoted [ilmath]X/\sim[/ilmath] or [ilmath]\frac{X}{\sim} [/ilmath] is defined as follows:

• [ilmath]\frac{X}{\sim}:\eq\{[x]\ \vert\ x\in X\} [/ilmath] where [ilmath][x][/ilmath] denotes the equivalence class of [ilmath]x[/ilmath].

Yes, [ilmath]\frac{X}{\sim} [/ilmath] is the set of equivalence classes, it is that simple.

Canonical projection

With [ilmath]X[/ilmath], [ilmath]\sim[/ilmath] and [ilmath]\frac{X}{\sim} [/ilmath] we also get a map:

• [ilmath]\pi:X\rightarrow\frac{X}{\sim} [/ilmath] given by [ilmath]\pi:x\mapsto [x][/ilmath]
  • Other commonly used letters include: [ilmath]p[/ilmath] and [ilmath]\rho[/ilmath]

Claim 1: this map is a surjection

Proof of claims

Claim 1: [ilmath]\pi:X\rightarrow\frac{X}{\sim} [/ilmath] is a surjection

We wish to show: [ilmath]\forall y\in\frac{X}{\sim}\exists x\in X[\pi(x)\eq y][/ilmath]

• Let [ilmath]y\in\frac{X}{\sim} [/ilmath] be given
  • Choose [ilmath]a\in y[/ilmath] (so now we may write [ilmath][a]\eq y[/ilmath]. Any [ilmath]a[/ilmath] will do.
    • Note that the equivalence classes are either equal or disjoint, suppose [ilmath]b\in y[/ilmath], this means [ilmath]a\sim b[/ilmath], so [ilmath][a]\eq [b][/ilmath]
  • Choose [ilmath]x:\eq a[/ilmath]
    • Then [ilmath]\pi(x)\eq [x]:\eq[a]\eq y[/ilmath]
• Since [ilmath]y[/ilmath] was arbitrary we have shown this for all [ilmath]y\in\frac{X}{\sim} [/ilmath]

See also

• Axiom of choice

Notes

References