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) \}$가 있을 때