同値関係
集合 S の上に同値関係 ∼ が定義されているときには、S の各元 a に対して a に同値である元を全て集めた集合を考えることができる。この S の部分集合を、a を代表あるいは代表元 (representative) とする同値類 (equivalence class) または単に a の(属する)類と呼び、普通 [a], a, C(a) などと書く:
[ a ] := { x ∈ S ∣ a ∼ x } . {\displaystyle [a]:=\{x\in S\mid a\sim x\}.}
また、1つの同値類 X に対して、[x] = X となる S の元 x を1つ定めることを、X の代表元として x をとるという。1つの同値類は、それに含まれている元を任意に選んでそれを代表元とする同値類を作ってもそれはもとと同じ同値類になる(同値類は代表元の取替えによって不変である):
X = [ x ] , y ∈ X ⟺ y ∈ [ x ] ⟺ x ∼ y ⟺ x ∈ [ y ] ⟺ [ y ] = X , x ∈ X . {\displaystyle X=[x],\ y\in X\iff y\in [x]\iff x\sim y\iff x\in [y]\iff [y]=X,\,x\in X.}
ゆえに同値類に関する性質を代表元の性質のみによって記述することは、一般には適当ではない。
与えられた左(または右)ユークリッド関係が反射的ならば、その関係は対称的かつ推移的となる。
証明は以下のようにすればよい。
左ユークリッド関係の性質 [(aRc かつ bRc) ならば aRb] において a = c ととれば、[(aRa かつ bRa) ならば aRb] を得る。いま仮定により R は反射的だから恒真となる aRa を除去すれば対称性 [bRa ならば aRb] を得る。
対称性が示されたから、左ユークリッド関係の性質 [(aRc かつ bRc) ならば aRb] において bRc を cRb で置き換えて推移性 [(aRc かつ cRb) ならば aRb] を得る。
右ユークリッド関係についても同様。ゆえに、同値関係は反射的かつユークリッド的な二項関係として特徴づけられる。
集合 S に対して、S の空集合を含まない部分集合族 M であって、M に属するどの2つの相異なる集合は交わりを持たず、M の和集合が S 全体に一致するときに、集合族 M のことを集合 S の類別または分類 (classification) あるいは分割 (partition) であるという。