관계

• 두 집합 X와 Y에 대하여 곱집합 $X \times Y$의 부분집합 R을 X에서 Y로의 관계라고 한다.
  • 만약 x와 y가 각각 X와 Y의 원소이고 $(x, y) \in R$이면 $xRy$로 표기하며, x는 y와 R의 관계가 있다고 한다.
  • 만약 $(x, y) \notin R$이면 $x \not\! R y$ 로 표기하며, x는 y와 R의 관계가 없다고 한다.
• 예제) 집합 $A = \{2, 3, 4, 5\}, B = \{1, 2\}$일 때, A에서 B로 가는 관계 R은 다음과 같을 때 물음에 답하라.
  • $R = \{(a,b)|a+b = 4\}$
  • 관계 R을 순서쌍으로 나타내시오
    • $R = \{(2,2), (3,1)\}$
  • 4R1은 성립하는가?
    • 성립하지 않음

관계의 표현

화살표 도표

집합 $A = \{2, 3, 4, 5\}, B = \{0, 1, 2, 3\}$

1. $(a,b) \in R$이기 위한 필요충분조건은 $a \leq b$

부울행렬

• 관계를 행렬로 나타냈을 때 이점: 대수연산자를 이용하여 관계에 관련된 문제를 편리하게 계산 가능 $X = \{1, 2, 3, 4\}$ 에서의 관계 R이 다음과 같이 정의되었을 때 R을 부울행렬로 나타내시오
• $R = \{(x,y)|y = x + 1, x \in X, y \in X\}$
  • $M_R = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}$

관계의 성질

반사적(reflexive)

• 집합 A에서의 관계 R에 대해 모든 $a \in A$에 대해 $(a,a) \in R$이면 R은 반사적이라고 한다.
• 집합 A에서의 관계 R이 반사적이 되려면 A의 모든 원소가 자기 자신과 관계를 가져야 한다.
  • 예를 들어, 집합 $A = \{1, 2, 3\}$에서의 관계 R이 반사적이려면 (1, 1), (2, 2), (3, 3)이 모두 R에 포함되어야 한다.
• 관계를 부울 행렬로 나타냈을 때 반사적이려면 대각 원소들이 모두 1이어야 한다.

대칭적(symmetric)

• 집합 A에서의 관계 R에 대해 모든 $a, b \in A$에 대해 $(a,b) \in R$일 때 $(b, a) \in R$이면 R은 대칭적이라고 한다.
• 집합 A에서의 관계 R이 대칭적이 되려면, R에 포함된 모든 원소가 대칭되는 관계를 가져야 한다.
  • 예를 들어, 집합 $A = \{1, 2, 3\}$에서의 관계 R이 대칭적이려면 (1, 2)가 R에 포함되어 있다면 (2, 1)도 R에 포함되어야 한다.

추이적(transitive)

• 집합 A에서의 관계 R에 대해 모든 $a, b, c \in A$에 대해 $(a, b) \in R$이고 $(b, c) \in R$일 때, $(a, c) \in R$이면 R은 추이적이라고 한다.
• 집합 A에서의 관계 R이 추이적이 되려면, R에 포함된 모든 원소들에 대해서 $(a, b) \in R$이고, $(b, c) \in R$이면 $(a, c) \in R$이어야 한다.
• 부울 행렬에서는 행렬의 곱을 통해 추이적 여부를 판단할 수 있다.
  • $M_R \cdot M_R = M_R^2$
  • $M_R^2 = M_R$이면 R은 추이적이다.
  • 행렬 제곱 했을 때 새로 생기는 1 이 없으면 추이적!

• R 관계
  • (1,1), (2,2), (3,3)모두 R에 포함되어 있으므로 반사적이다.
  • (1,2)일 때 (2,1)은 포함되어 있지 않으므로 대칭적이지 않다.
  • (1,3)이 관계에 포함되어 있고, (3,2)가 포함되어 있지만, (1,2)는 포함되어 있지 않으므로 추이적이지 않다.
• S 관계
  • 반사적이다.
  • (1,3)이 관계에 포함되어 있을 때 (3,1)도 포함되어 있으므로 대칭적이다.
  • 추이적 조건에도 만족하지 못함
• T 관계
  • (2,2)와 (3,3) 은 관계에 포함하지 않으므로 반사적이지 않다.
  • (2,1)이 관계에 포함되어 있을 때 (1,2)는 포함되어 있지 않으므로 대칭적이지 않다.
  • (2,1)과 (1,3)이 관계에 포함되어 있고, (2,3)도 포함되어 있으므로 추이적이다.
    • 추이적 관계의 필요조건을 만족시키는 원소들이 존재하므로 추이적이다.

관계의 종류

주어진 관계를 이용하여 새로운 관계를 만들어 낼 수 있다.

역관계(inverse relation)

• 집합 X에서 집합 Y로의 관계 R이 있을 때, 관계를 구성하는 각 순서쌍의 원소 순서를 바꾸면 Y에서 X로의 관계가 되며, 이를 역관계라고 한다.
• $R^{-1}$라고 표기함
• $R^{-1} = \{(y, x)|(x, y) \in R\}$

합성관계(composition relation)

• 집합 A에서 집합 B로의 관계 R이 있고, 집합 B에서 집합 C로의 관계 S가 있을 때, $S \cdot R$은 집합 A에서 집합 C로의 관계를 나타낸다.
• $S \cdot R = \{(a, c) \in A \times C|a \in A, b \in B, c \in C, (a, b) \in R, (b, c) \in S\}$

• 집합 A에서 집합 B로의 관계가 R이고, 집합 B에서 C로의 관계가 S일 때, A에서 C로의 관계는 $R \cdot S$로 표기하는 것이 아니라 $S \cdot R$로 표기한다. 주의할 것

동치관계(equivalence relation)

• 집합 A에서의 관계 R이 반사적이고, 대칭적이고, 추이적이면 R은 동치관계라고 한다.
• 나머지함수: 하나의 식을 다른 값으로 나눈 뒤 나머지를 구하는 함수
  • 8 mod 5 = 3이고 13 mod 5 = 3이다. 두 정수 m, n에 대해 양의 정수 d로 나머지 연산을 하였을 때 같은 값이 나오는 경우가 있는데 이때의 m과 n은 d에 관한 모듈로 합동이라 하고 m = n(mod d)로 표기한다.
    • m = n(mod d)는 m mod d와 n mod d가 같다는 의미이다.

동치류

• 집합 A에서의 관계 R이 동치관계일 때, A의 각 원소 a에 대하여 a의 동치류는 a와 R의 관계를 가지는 A의 원소들의 집합이며, $[a]$로 표기한다.
• $[a] = \{x|x \in A, (a,x) \in R\}$

집합 A = 3 에서의 관계 R이 다음과 같을 때 R이 동치관계임을 보인 후 서로 다른 동치류를 모두 찾으시오 R = 3

[0] = 3 [1] = 3 [2] = 2 [3] = 3