Quotient by an equivalence relation

From Maths
Jump to: navigation, search
Stub grade: A
This page is a stub
This page is a stub, so it contains little or minimal information and is on a to-do list for being expanded.The message provided is:
Needs linking to other sections, more work, so forth. See what's on the equivalence relation page, make sure it's all inline with this


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.
    • 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