https://youtu.be/4qgSJ8KuzOw

관계

용어 정리

• 관계
  • 곱집합 $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) \text{는 참} \}$
• 정의역 (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) \}$은 순서 관계이다.