수학의신이상엽/ 관계와 분할

관계

용어 정리

  • 관계
    • 곱집합 A \times B 의 부분집합
    • \mathcal{R} = (A, B, P(x, y))
    • P(x, y)는 명제함수
    • ex) A = {2, 3}, B = {4, 6} 이라 할 때,
      • A \times B = \{ (2, 4), (2, 6), (3, 4), (3, 6) \} 이 되고
      • 명제함수 P(x, y)를 ‘x는 y의 약수이다’ 라고 정의하면
      • \mathcal{R} = \{ (2, 4), (2, 6), (3, 6) \} 이 된다.
      • 이때 \mathcal{R} 의 한 원소인 (2, 4)는 (2, 4) \in \mathcal{R} 또는 _{2} \mathcal{R}_{4} 와 같이 표기가 가능하다.
  • 관계 \mathcal{R} 의 해집합
    • \{ (x, y) | x \in A, y \in B, P(x, y) 는 참 \}
  • 정의역 (Domain)
    • 적당한 y \in B 에 대하여, _{x} \mathcal{R}_{y} 인 모든 x \in A 의 집합 Dom(\mathcal{R})
    • _{x} \mathcal{R}_{y} 의 왼쪽에 오는 원소들(x). 위의 예시의 경우 Dom(\mathcal{R}) = \{ 2, 3 \}  
  • 상 (Image)
    • 적당한 x \in A 에 대하여, _{x} \mathcal{R}_{y} 인 모든 y \in B 의 집합 Im(\mathcal{R})
    • _{x} \mathcal{R}_{y} 의 오른쪽에 오는 원소들(y). 위의 예시의 경우 Im(\mathcal{R}) = \{ 4, 6 \}  

관계의 성질

집합 X에서의 관계 \mathcal{R} 에 대하여

  • 반사성: \forall x \in X, _{x} \mathcal{R}_{x}
    • ex) X = {1, 2, 3} 에서의 관계
      • \mathcal{R}_{1} = \{ (1, 1), (2, 2) \} 는 반사적이지 않다. (3, 3)이 없기 때문
      • \mathcal{R}_{2} = \{ (1, 1), (2, 2), (3, 3), (1, 3) \} 는 반사적이다. 자기 자신에 대해 반사적인 원소가 모두 있으면 추가적인 원소가 있는 것은 반사성에 영향이 없다.
      • 이때 반사성을 이루는 원소 (1, 1), (2, 2), (3, 3)을 특별히 \Delta x 라고 표기하며 대각관계 또는 항등관계라고 부른다.
      • 집합이 반사적이라는 말은 대각관계(또는 항등관계)를 포함하고 있다는 말이 된다.
  • 대칭성: _{x} \mathcal{R}_{x} \Rightarrow _{y} \mathcal{R}_{x}
    • ex) X = {1, 2, 3} 에서의 관계
      • \mathcal{R}_{3} = \{ (1, 1), (1, 2), (2, 1) \} 는 대칭적이다. (1, 2)가 있을 때 (2, 1)이 있으면 대칭적이라고 인정한다.
  • 반대칭성: _{x} \mathcal{R}_{y} \wedge _{y} \mathcal{R}_{x} \Rightarrow x = y
    • ex) X = {1, 2, 3} 에서의 관계
      • \mathcal{R}_{3} = \{ (1, 1), (1, 2), (2, 1) \} 는 반대칭적이지 않다. 대칭되는 쌍이 존재하기 때문. 만일 위 집합에서 (1, 2)나 (2, 1)이 빠지면 반대칭적이 된다.
      • 반면 반대칭성의 정의에 의해 (1, 1)은 반대칭적이다. _{1} \mathcal{R}_{1} \wedge _{1} \mathcal{R}_{1} \Rightarrow 1 = 1 이 성립하기 때문.
  • 추이성: _{x} \mathcal{R}_{y} \wedge _{y} \mathcal{R}_{z} \Rightarrow _{x} \mathcal{R}_{z}
    • ex) X = {1, 2, 3} 에서의 관계
      • \mathcal{R}_{4} = \{ (1, 1), (1, 2), (2, 3) \} 은 추이적이지 못하다. (1, 2), (2, 3)은 있지만 (1, 3)은 없기 때문. 위 집합에 (1, 3)을 추가하면 추이적이 된다. (3, 1)이 추가 되어야 하는 것이 아니므로 주의.
  • ex) X = {1, 2, 3} 에서의 관계
    • \mathcal{R}_{5} = \{ (1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2) \} 가 있을 때
    • 위 집합은 반사적이지 못하다. (3, 3)이 없기 때문.
    • 위 집합은 대칭적이다. (1, 3)에 대칭되는 (3, 1)이 존재하고 (2, 3)에 대칭되는 (3, 2)가 존재하기 때문.
    • 위 집합은 반대칭적이지 못하다. 대칭적이기 때문.
    • 위 집합은 추이적이지 못하다. (1, 3)과 (2, 3)이 존재하지만 (1, 2)가 없기 때문.

여러가지 관계

  • 역관계 \mathcal{R}^{-1}
    • _{x} \mathcal{R}_{y} 이면 오직 그 때에만 _{y} \mathcal{R}_{x}^{-1} 즉, \mathcal{R}^{-1} = \{ (y, x) | (x, y) \in \mathcal{R} \}
    • ex) \mathcal{R} = \{ (1, 1), (1, 2) \} 의 역관계는 \mathcal{R}^{-1} = \{ (1, 1), (2, 1) \} 가 된다.
  • 합성관계
    • 집합 X에서의 관계 G와 H에 대하여 합성관계 H \circ G = \{ (x, y) | \exists z (x, z) \in G \wedge (z, y) \in H \}
      • 합성 관계의 순서는 오른쪽에서 왼쪽으로 진행되기 때문에 위 합성관계에서 G를 먼저 쓰고 그 후에 H를 쓰면 된다.
    • ex) (1, 2) \in G \wedge (2, 3) \in H \Rightarrow H \circ G \ni (1, 3) 
  • 역관계와 합성관계에 관한 정리
    • 집합 X에서의 관계 F, G, H에 대하여 다음이 모두 성립한다.
      • (F^{-1})^{-1} = F
      • (H \circ G) \circ F = H \circ (G \circ F)
      • (G \circ F)^{-1} = F^{-1} \circ G^{-1}
  •  동치관계
    • 반사적, 대칭적, 추이적인 관계
    • ex) “=” 는 반사적이고 대칭적이고 추이적이므로 동치 관계가 된다.
      • 반사적: a = b
      • 대칭적: a = b \Rightarrow b = a
      • 추이적: a = b \wedge b = c \Rightarrow a = c
    • 집합 X 에 대하여 가장 작은 동치관계는X 의 대각관계가 되고, 가장 큰 동치관계는 X^{2} 가 된다.
    • 동치관계는 E라고 표기하기도 한다.
  • 순서관계
    • 반사적, 반대칭적, 추이적인 관계
    • ex) \mathcal{R} = \{ (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3) \} 은 순서 관계이다.

동치관계와 분할

용어 정리

  • 분할: 집합 X에 대하여 다음 세 조건을 만족하는 집합족
    • 공집합을 원소로 하지 않는다.
    • X를 덮는다.
    • 서로소 집합족이다.
    • ex) X = {1, 2, 3, 4, 5} 에서의 분할 P를 다음과 같이 구성 P = { {1, 2}, {3, 4}, {5} }
  • 동치류: 집합 X 상의 하나의 동치 관계를 E라 할 때
    • E_{x} = \{ y \in X | _{x} E_{y} \}
    • ex) X = {1, 2, 3, 4, 5} 일 때
      • E = { (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 3), (3, 1), (2, 4), (4, 2) } 라 하면
      • E_{1} = \{ 1, 3 \}
        • 1의 동치류라는 것은 왼쪽에 1이 나오는 순서쌍의 오른쪽 것을 의미한다.
      • E_{2} = \{ 2, 4 \}
      • E_{3} = \{ 1, 3 \} = E_{1}
      • E_{4} = \{ 2, 4 \} = E_{2}
      • E_{5} = \{ 5 \}
  • 상집합: 집합 X에서의 모든 동치류의 집합
    • X / E = \{ E_{x} | x \in X \}
    • ex) 앞선 예와 같이 동치류들이 구성되었을 때
      • 상집합 X / E 는 모든 동치류들을 합한 것이므로 다음과 같다. X / E = \{ \{ 1, 3 \}, \{ 2, 4 \}, {\ 5\ } \}
      • 이 상집합은 집합의 분할과 동일하다. 이는 다시 말해 동치관계를 알면 그 동치관계를 이용해서 분할을 끌어낼 수 있다는 뜻이 된다.
      • 물론 그 역도 성립하므로 분할을 알면 동치 관계를 이끌어낼 수 있다.
  • \mathcal{R}_{p} (= X / P) (분할 P에 의한 관계)
    • \{ (x, y) | \exists A \in P, x, y \in A \}
    • ex) X = {1, 2, 3, 4, 5}, P = { {1, 2}, {3, 4}, {5} } 일 때, P의 부분집합을 각각 A_{1}, A_{2}, A_{3} 이라하면
      • A_{1} \Rightarrow (1, 1), (1, 2), (2, 1), (2, 2)
      • A_{2} \Rightarrow (3, 3), (3, 4), (4, 3), (4, 4)
      • A_{3} \Rightarrow (5, 5)
      • A_{1}, A_{2}, A_{3} 를 모두 모으면 \mathcal{R}_{p} 이 된다. 

여러가지 정리

  • 공집합이 아닌 집합 X 위의 동치관계 E에 대하여 다음이 모두 성립한다.
    • E_{x} \neq \emptyset
    • E_{x} = E_{y} \Leftrightarrow _{x} E_{y}
    • E_{x} \cap E_{y} \neq \emptyset \Leftrightarrow _{x} E_{y}
    • X / E X  의 분할이다.
  • 공집합이 아닌 집합 X의 분할 P에 대하여 다음이 모두 성립한다.
    • R_{p} X 상의 동치관계다.
    • X / R_{p} = P
[ssba]

The author

지성을 추구하는 사람/ suyeongpark@abyne.com

댓글 남기기

This site uses Akismet to reduce spam. Learn how your comment data is processed.