[군론](15)[동치관계와 분할]

 

관계

$R \subseteq S \times S$를 집합 S에서의 이진 관계 R라고 한다

 

동치관계 (equivalent relation)

다음과 같은 성질을 만족하는 관계

• 반사 (Reflecivity): $\forall a \in S,$ a~a
• 대칭 (Symmetry): a~b $\Rightarrow$ b~c
• 추이 (Transitivity): a~b & b~c $\Rightarrow$ a~c

예) $R = {(a,b) \ | \ a \equiv b \ (mod \ n)}$
- 반사
    $a \equiv a \ (mod \ n)$
    -> aRa
- 대칭
    $a \equiv b \ (mod \ n)$라고 하자.
    a = nk + b (단, k는 정수)
    $\iff$ b = a - nk
    따라서, $b = a-nk \equiv a \ (mod \ n)$
    -> aRb => bRa
- 추이
    $a \equiv b \ (mod \ n)$, $b \equiv c \ (mod \ n)$라고 하자.
    a = np + b, b = nq + c (단, p, q는 정수)
    $\Rightarrow$ a = np + nq + c = n(p+q) + c
    따라서, $a \equiv c \ (mod \ n)$
    -> aRb & bRc => aRc
-> 따라서, R은 동치관계이다.

 

예) $R = {(a,b) \ | \ a < b}$
- 반사
    애초에 aRa가 없음
    -> 동치관계가 아님

 

동치류 (equivalence class)

$a\in S, \ [a] = {x \in S \ |\ x\sim a }$
(단, ~은 동치관계)

• 동치류의 특성
  동등성: [a] = [b] $\iff$ a~b
  상호 배제: 동치류들은 완전 동일하거나 서로소집합임
  -> 동치류는 분할을 형성한다!

 

분할 (partition)

다음을 만족하는 S의 부분집합의 모음

• non-empty
• 서로소 집합
  즉, 임의의 분할의 원소끼리는 겹치는게 없음
• 분할의 합집합 = 전체집합

 

동치관계가 주어졌다 = partition이 주어졌다

즉, 기준에 따라 분할하는 것과
두 원소를 같다고 취급하는 것이 수학적으로 동일하다!

• 예) equiv => part
  동치류의 모임의 집합이 분할을 만드는 것을 증명하바
  • non-empty?
    a~a이므로, $a \in [a]$
    따라서, $[a] \neq \emptyset$
  • disjoint set?
    만약 $[a]\bigcap [b] \neq \emptyset$이라면
    $\exists x \in [a]\bigcap [b]$
         $x \in [a] \Rightarrow x\sim a \Rightarrow a\sim x$ (대칭)
         $x \in [b] \Rightarrow x\sim b$
    따라서, 추이에 의해,
    $a\sim x, \ x\sim b \Rightarrow a\sim b$
    $\Rightarrow a \in [b]$
    즉, [a] = [b]이다.
         즉, 겹치는 원소가 있으면 동일한 집합이라는 소리
  • exhaustive union?
    $\forall a \in S$에 대해, $a \in [a]$임을 보였으므로,
         즉, S의 모든 원소가 동치류에 속함
    $\bigcup\limits_{a\in S}[a] = S$

      -> 따라서 동치류의 집합은 분할이다

• 예) part => equiv
  분할 $[a] = {x \in S \ | \ x\sim a}$에 대해,
  관계 $R = {(a, b) \ | \ a \in [b]}$라고 정의하고 이것이 동치관계임을 증명하자
  • 반사
    ~이 동치관계이므로, 반사성에 의해,
    a~a $\Rightarrow a \in [a]$
    $\Rightarrow aRa$
  • 대칭
    aRb라고 가정하자.
    $\iff a \in [b] \Rightarrow a\sim b$
    ~은 동치관계이므로, 대칭성에 의해,
    $\Rightarrow b \sim a \Rightarrow b \in [a]$
    $\Rightarrow bRa$
  • 추이
    aRb, bRc라고 가정하자.
    $\iff a\in [b], \ b \in [c]$
    $\iff a \sim b, \ b \sim c$
    ~은 동치관계이므로, 추이성에 의해,
    $\Rightarrow a\sim c \Rightarrow a \in [c]$
    $\Rightarrow aRc$

      따라서 분할로 만든 관계는 동치 관계이다