同値関係

要素が等しい(合同)であるという関係の一般化

• 二項関係で、以下の3つの性質を満たす関係

  • 反射律: すべての元$a\in A$に対して、$a\equiv a$
    • 反射関係
  • 対称律: すべての元$a,b\in A$に対して、$a\equiv b$なら$b\equiv a$
    • 対称関係
  • 推移律: すべての元$a,b,c\in A$に対して、$a\equiv b$かつ$b\equiv c$なら$a\equiv c$
    • 推移関係

• 同値類

  • $R$を集合$A$上の同値関係とする。$x\in A$となる$x$に対して、$x$の同値類$[x]$とは以下の集合のことである
    • $[x]=\{y|y\in A\wedge xRy\}$

• 商集合

  • 集合$A$上の同値関係$R$に対して、商集合$A/R$は、同値類をすべて集めた集合である
    • $A/R=\{[x]|x\in A\}$

• 例: $aRb\iff (a\mathrm{mod}5=b\mathrm{mod}5)$としたときの$N/R$は…($N$は自然数)

  • $N/R=\{[0],[1],...,[4]\}=\{\{0,5,10,...\},\{1,6,11,...\},...\}$