동치 관계

동치 관계(equivalence relation)는 반사적, 추이적, 대칭적인 이항 관계를 말한다. 즉, 집합 \(X\)위의 이항 관계 \(\sim\)이 다음의 조건을 만족 시킨다면 \(\sim\)을 동치 관계라고 한다.

• (반사성) 임의의 \(x \in X\)에 대해 \(x \sim x\)
• (대칭성) 임의의 \(x, y \in X\)에 대해 \(x \sim y\)이면 \(y \sim x\)
• (추이성) 임의의 \(x, y, z \in X\)에 대해 \(x \sim y\)이고 \(y \sim z\) 라면 \(x \sim z\)

동치 관계가 주어진 집합을 준집합(setoid)이라고 한다.

동치류

준집합 \(\langle X , \sim \rangle\)이 주여졌을 때, \(x \in X\)와 관계된 원소들의 모임을 \([x]\)를 동치류(equivalence class)라고 한다. 즉, \[ [x] = \{y \in X \mid x \sim y\}\]

이때 다음이 성립한다. \[ \forall x, y \in X. x \sim y \leftrightarrow [x] = [y] \]

몫 집합

몫 집합(quotient set)은 동치류들의 집합을 의미한다.

\[ X/{\sim} = \{[x] \mid x \in X\} \]