Subset

In set theory, an equivalence class is a set of all objects that are related to a specific object by some equivalence relation.

For example, if R is an equivalence relation on a set S, and a ∈ S, then the equivalence class [a] is the set of all elements of S that are R-related to a.

[a] = { x|Rxa }

The notation for equivalence classes varies among logic texts. On this site, the notation [a] is used to denote an equivalence class of the element a. If there are multiple relations being considered, a subscript of the specific relation may be added: [a]R. Some texts will place a line over the element name instead, using the notation a to indicate an equivalence class.

Examples

Suppose that S is a set and R is an equivalence class on that set, such that:

  • S = { a, b, c, d, e }
  • R = { <a, a>, <b, b>, <c, c>, <d, d>, <e, e>, <b, c>, <c, b>, <b, e>, <c, e> }

Then the following are true:

  1. [a] = { a }
  2. [b] = { b, c }
  3. [c] = { b, c }
  4. [e] = { b, c, e }

(1) is true because the only element R-related to a (that is, the only x such that <x, a> ∈ R) is a itself. (2) and (3) are true because b and c are both R-related to themselves, and to each other, but nothing else is related to them. Similarly, in (4), b and c are both R-related to e, and e is R-related to itself.

With an equivalence relation on a set S, for every x ∈ S, x ∈ [x]. This is because equivalence relations are reflexive — that is, every element is related to itself, and is therefore a member of its own equivalence class.