[이산 수학] 동치 관계와 부분 순서 관계

동치 관계와 부분 순서 관계

• 관계 `R` 이 어떤 성질을 갖느냐에 따라 관계에 의미를 부여하여 그 의미에 따라 관계의 순서쌍을 구성하는 원소들을 활용할 수 있다.
• 관계에 부여되는 의미에는 동치 관계나 부분 순서 관계가 있는데, 동치 관계의 경우 그 관계의 순서쌍을 구성하는 원소들이 같은 의미라는 것을 뜻하며, 부분 순서 관계의 경우는 그 관계의 순서쌍을 구성하는 원소들 사이에 순서가 존재한다는 것을 뜻한다.

 

동치 관계(Equivalence Relation)

반사 관계, 대칭 관계, 추이 관계가 모두 성립하는 관계

• 동치는 표현이 달라도 의미가 같아서 동등하게 사용할 수 있음을 의미한다.
• 예) 10진수 $7_{10}$ 과 2진수 $111_{2}$ 이 표현은 다르지만 같은 값으로 사용되므로 동치라고 할 수 있다.
• 관계에서 동치 관계라고 하면 관계에 포함된 어떤 순서쌍 `(a, b)` 에서 `a` 와 `b` 가 같은 의미임을 말한다.

 

예

• 집합 $A = \{ 1, 2, 3\}$ 에 대한 관계 $R = \{(1, 1), (1, 2), (2, 1), (2, 2), (3, 3) \}$ 이 동치 관계인지 살펴보자.
• 이 관계 `R` 을 관계 행렬로 표현하여 반사, 대칭, 추이 관계인지를 살펴 본다.

$$M_{R} = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

• ① 주대각 원소가 모두 1이다.
  • 관계 `R` 은 반사 관계이다.
• ② 주대각 원소를 기준으로 마주보는 원소가 같은 값이다.
  • 관계 `R` 은 대칭 관계이다.
• ③ 합성의 거듭 제곱으로 추이 관계인지 판별한다.

$$R^{2} = R \circ R = M_{R} \odot M_{R} \begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \odot \begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}  = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \\ R^{3} = R^{2} \circ R = M_{R} \odot M_{R^{2}} = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}  \odot \begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}  = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$ $∴ R^{3} ⊆ R$ 이므로 관계 `R` 은 추이 관계이다.

• 위 과정에서 관계 `R` 이 반사, 대칭, 추이 관계를 모두 만족함을 확인하였다.
  • 그러므로 `R` 은 동치 관계이다.
• 만약 어떤 관계 `R` 이 반사, 대칭, 추이 관계 중 하나라도 만족하지 못한다면 그 관계는 동치 관계가 아니다.

 

동치류(Equivalence Class : $[a]$)

집합 `A` 에 대한 관계 `R` 이 동치 관계일 때, 집합 `A` 의 각 원소 `a` 와 순서쌍을 이루는 원소들의 집합
$$[a] = \{x \; | \; (a, x) \in R \}$$

• 동치 관계에 포함되는 순서쌍 원소는 같은 의미를 갖는다. 이렇게 같은 의미인 원소를 모아 놓은 집합을 동치류라고 한다.
• 동치류는 분할(Partition)의 일부 특징을 갖는다.

 

동치류와 분할

집합 `A` 에 대한 관계 `R` 이 동치 관계일 때, 동치류 집합 $S = \{ A_{1}, A_{2}, \cdots, A_{k}\}$ 는 다음과 같은 특징을 갖는다.
① $i = 1, 2, \cdots, k$ 일 때, $A_{i} ≠ \varnothing$
② $\cup_{A_{i}} = A$ ($A_{i} ⊆ A$)
③ $i ≠ j$ 이면, $A_{i} ∩ A_{j} = \varnothing$

 

예

• 집합 $A = \{1, 2, 3\}$ 에 대한 관계 $R = \{(1, 1), (1, 2), (2, 1), (2, 2), (3, 3) \}$ 은 동치 관계임을 앞에서 증명하였다.
• 집합 `A` 의 각 원소에 대한 동치류는 다음과 같다.

$$[1] = \{1, 2\}, \; [2] = \{1, 2\}, \; [3] = \{3\}$$

• 이 동치류에 대한 동치류 집합 `S` 는 $\{\{1, 2\}, \{3\}\}$ 으로, $A_{1} = \{1, 2\}, \; A_{2} = \{3\}$ 라 할 때 다음과 같이 분할의 특징을 갖는다.

① $A_{1} \ne \varnothing, \; A_{2} \ne \varnothing$ ② $\displaystyle \bigcup_{i = 1}^{2}A_{i} = A (A_{1} ⊆ A, \; A_{2} ⊆ A)$ ③ $A_{1} \cap A_{2} = \varnothing$

 

부분 순서 관계(Partial Order Relation)

반사 관계, 반대칭 관계, 추이 관계가 성립하는 관계

• 관계의 원소인 순서쌍은 나열 순서에 의미가 있으므로 `(a, b)` 와 `(b, a)` 는 전혀 다른 순서쌍이다.
• 관계가 어떻게 정의되느냐에 따라 그 관계 안의 순서쌍을 구성하는 집합 원소가 항상 앞에만 오는 경우가 있을 수 있다.
  • 예) 어떤 관계 안에 순서쌍 `(a, b)` 는 존재하고 `(b, a)` 는 존재하지 않는다면, 이 관계에서 `a` 는 항상 `b` 보다 앞에 오는 원소라고 판단한다.
• 이러한 형태의 순서쌍을 포함하는 관계를 '순서 관계를 갖는다'고 말한다.
• 어떤 관계 `R` 이 순서 관계를 가지려면 $a \ne b$ 일 때 $(a, b) \in R$ 이면 $(b, a) \not \in R$ 이어야 한다.
  • 그러므로 관계 `R`이 반대칭 관계이여만 순서 관계가 성립한다.

 

예

• 집합 $A = \{1, 2, 3\}$ 에 대한 관계 $R = \{(1, 1), (1, 2), (1,3 ), (2, 2), (3, 3) \}$ 이 부분 순서 관계인지 살펴보자.

$$M_{R} = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

• ① 주대각 원소가 모두 1이다.
  • 관계 `R` 은 반사 관계이다.
• ② 주대각 원소를 기준으로 마주보는 원소가 서로 다른 값이다.
  • 관계 `R` 은 반대칭 관계이다.
• ③ 합성의 거듭 제곱으로 추이 관계인지 판별한다.

$$R^{2} = R \circ R = M_{R} \odot M_{R} \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \odot \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}  = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \\ R^{3} = R^{2} \circ R = M_{R} \odot M_{R^{2}} = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}  \odot \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}  = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$ $∴ R^{3} ⊆ R$ 이므로 관계 `R` 은 추이 관계이다.

• 그러므로 관계 `R` 은 반사, 반대칭, 추이 관계이므로 부분 순서 관계이다.
• 만약 관계 `R` 이 반사, 반대칭, 추이 관계 중 하나라도 만족하지 않는다면 관계 `R` 은 부분 순서 관계일 수 없다.

 

부분 순서 집합(Partial Order Set)

집합 `A` 에 대한 관계 `R` 이 부분 순서 관계일 때, 집합 `A`

• 부분 순서 관계가 성립하는 경우, 그 관계에 사용된 집합을 부분 순서 집합이라고 한다.
• 부분 순서 관계가 성립하면 부분 순서 집합의 원소 사이에 순서가 정해지는데, 이는 원소끼리 비교가 가능하기 때문이다.

 

비교 가능(Comparable)과 비교 불가능(Noncomparable)

집합 `A` 에 대한 관계 `R` 이 부분 순서 관계이고 $a, b \in A$ 이고, $(a, b) \in R$ 또는 $(b, a) \in R$ 일 때, '`a` 와 `b` 는 비교 가능'이라 하고, $a \leqslant b \; ((a, b) \in R\text{인 경우})$ 또는 $b \leqslant a \; ((b, a) \in R\text{인 경우})$ 로 표기한다.
반면, $(a, b) \not \in R$ 또는 $(b, a) \not \in R$ 일 때, '`a` 와 `b` 는 비교 불가능' 이라 하고 $a \not \leqslant b$ 또는 $b \not \leqslant a$ 로 표기한다.

• 비교 가능한 원소 `a, b` 에 대해 $a \leqslant b$ 는 `a` 의 값이 `b` 보다 작다는 의미가 아니라, 순서쌍에서 `a` 가 `b` 보다 앞에 옴을 의미한다.
• 예)
  • 부분 순서 관계인 $R = \{(1, 1), (2, 1), (2, 2), (3, 3), (3, 4), (4, 4)\}$ 에서 `(2, 1)` 의 경우 '2와 1은 비교 가능'이라고 하여 $2 \leqslant 1$ 로 표기한다.
  • 부분 순서 관계인 $R = \{(a, b) \in N \times N \; | \; a|b \}$ 에서 `(2, 4)` 의 경우 '2와 4는 비교 가능' 이라고 하며 $2 \leqslant 4$ 로 표기한다.
    • 반면, `(2, 5)` 는 관계 `R` 에 포함되지 않으므로 '2와 5는 비교 불가능' 이라 하고 $2 \not \leqslant 5$ 로 표기한다.
• 집합 `A` 에 대한 관계 `R` 이 있을 때, 집합 `A` 의 일부 원소끼리만 비교 가능하면 관계 `R` 을 부분 순서 관계라고 한다.
  • 예) 부분 순서 관계인 $R = \{(1, 1), (2, 1), (2, 2), (3, 3), (3, 4), (4, 4)\}$ 의 원소 중 1 과 3 또는 2와 4는 비교 불가능하다. 
• 만약 부분 순서 집합의 모든 원소가 서로 비교 가능하면 그 관계를 완전 순서 관계라고 한다.

 

완전 순서 관계(Total Order Relation)과 완전 순서 집합(Total Order Set)

집합 `A` 에 대한 관계 `R` 이 부분 순서 관계일 때, 집합 `A` 의 모든 원소가 그 관계에서 비교 가능하면 그 관계 `R` 을 완전 순서 관계라 하고, 집합 `A` 를 완전 순서 집합이라고 한다.

 

예 : $R = \{(a, b) \in N \times N \; | \; a ≤ b \}$

• 이 관계 `R` 은 반사, 반대칭, 추이 관계가 성립하는 부분 순서 관계로, 자연수 집합 `N` 에서 `a ≤ b` 인 모든 원소 `b` 가 원소 `a` 와 비교 가능하다.
• 즉, `a = 5` 일 때, 자연수 집합 `N` 의 원소 중 5보다 크거나 같은 모든 원소는 `a` 와 비교 가능하다.
• 그러므로 관계 `R` 은 부분 순서 관계이면서 완전 순서 관계이다.

 

하세 도표(Hasse Diagram)

방향 그래프에 부분 순서 관계의 특징을 적용한 부분 순서 관계 표기 방법

하세 도표의 예

• 하세 도표는 방향 그래프와 부분 순서 관계의 특징을 이용하여 도표로 나타냄으로서 관계를 표기하는 방법이다.
• 하세 도표는 독일의 수학자 헬무트 하세(Helmut Hasse)가 착안한 표기 방식으로, 다음과 같은 규칙을 따라 그린다.

 

하세 도표 그리는 규칙

[규칙 ①] 방향 그래프에서 루프를 생략한다.
[규칙 ②] $a \ne b$ 인 부분 순서 집합의 원소 $a, b \in A$ 에 대하여 $(a, b) \in R$ 이면 정점 $a$ 를 정점 $b$ 보다 아래쪽에 그린다.
[규칙 ③] $a \ne b \ne c$ 인 부분 순서 집합의 원소 $a, b, c \in A$ 에 대하여 $(a, b) \in R, \; (b, c) \in R, \; (a, c) \in R$ 일 때, 정점 `a` 에서 정점 `c` 로 가는 선만 그리고 정점 `a` 에서 정점 `b`, 정점 `b` 에서 정점 `c` 로 가는 선은 생략한다.

• 어떤 관계의 하세 도표를 그릴 수 있다는 것은 이미 그 관계가 부분 순서 관계라는 의미이다.
• 그러므로 하세 도표를 그리는 규칙은 부분 순서 관계가 성립하는 특징인 반사 관계, 반대칭 관계, 추이 관계를 그대로 적용한 것이라고 생각하면 된다.
• 하세 도표를 그리는 각 규칙에 대한 이유는 다음과 같다.

[규칙 ①] 부분 순서 관계가 성립하는 관계 `R` 은 반사 관계가 당연히 성립하므로 굳이 표시하지 않는다. [규칙 ②] 부분 순서 관계가 성립하는 관계 `R` 은 반대칭 관계가 당연히 성립하므로 $(a, b) \in R$ 일 때 $(b, a) \not \in R$ 이고 $a \leqslant b$ 이므로 `a` 가 `b` 보다 앞에 온다는 개념으로 아래쪽에 표시한다. [규칙 ③] 부분 순서 관계가 성립하는 관계 `R` 은 추이 관계가 당연히 성립하므로 $(a, b) \in R, \; (b, c) \in R, \; (a, c) \in R$ 일 때, 정점 `a` 에서 정점 `c` 로 가는 두 종류의 경로 중 짧은 경로 하나만 표시한다.

 

예 : 하세 도표 그리기

• 집합 $A = \{1, 2, 3\}$ 에 대한 관계 $R = \{(1, 1), (1, 2), (1,3 ), (2, 2), (3, 3) \}$ 은 부분 순서 집합이다. 관계 `R` 의 하세 도표를 그려보자.

① 관계 `R` 에 포함된 순서쌍 중 `(1, 2), (1, 3)` 에서 $a \leqslant 2, \; 1 \leqslant 3$ 임을 알 수 있으므로 1을 2나 3보다 아래쪽에 표시한다. ② $(2, 3) \not \in R, \; (3, 2) \not \in R$ 이므로 2와 3은 비교 불가능한 원소이다. 이렇게 비교 불가능한 원소 사이에서는 선을 그리지 않는다. ③ $(1, 2), (2, 2), (3, 3)$ 에 대한 루프를 표시하지 않아도 된다. ④ $(1, 2), (1, 3)$ 에 대해 1과 2, 1과 3 사이에 직선을 그린다.

관계 R의 하세 도표

 

• 부분 순서 관계는 부분 순서 집합에 속한 원소 사이의 순서를 알 수 있는 관계이다.
• 그러므로 어떤 원소가 위쪽에 위치하는지, 혹은 가장 아래쪽에 위치하는지에 따른 의미를 부여할 수 있는 관계이기도 하다.

 

극대 원소(Maximal Element)

부분 순서 집합 `A` 의 원소 `a` 에 대해 $a \leqslant b$ 인 원소 `b` 가 집합 `A` 에 존재하지 않을 때 원소 `a`

 

극소 원소(Minimal Element)

부분 순서 집합 `A` 의 원소 `a` 에 대해 $b \leqslant a$ 인 원소 `b` 가 집합 `A` 에 존재하지 않을 때 원소 `a`

 

최대 원소(Greatest Element)

부분 순서 집합 `A` 의 모든 원소 `a` 에 대해 $a \leqslant b$ 인 집합 `A` 의 원소 `b` 

 

최소 원소(Least Element)

부분 순서 집합 `A` 의 모든 원소 `a` 에 대해 $b \leqslant a$ 인 집합 `A` 의 원소 `b` 

 

• 하세 도표에서 극대 원소나 최대 원소는 선으로 연결된 원소 중 가장 위에 표시된 부분 순서 집합의 원소이다.
  • 극대 원소는 가장 위에 위치한 모든 원소를 말한다.
  • 최대 원소는 가장 위에 위치한 원소가 오직 하나만 있을 때만 의미한다.
  • 그러므로 부분 순서 집합에서 극대 원소는 1개 이상이지만, 최대 원소는 1개이거나 없을 수도 있다.
• 하세 도표에서 극소 원소나 최소 원소는 선으로 연결된 원소 중 가장 아래에 표시된 부분 순서 집합의 원소이다.
  • 극소 원소는 가장 아래에 위치한 모든 원소를 말한다.
  • 최소 원소는 가장 아래에 위치한 원소가 오직 하나만 있을 때만 의미한다.
  • 그러므로 부분 순서 집합에서 극소 원소는 1개 이상이지만, 최소 원소는 1개이거나 없을 수도 있다.

 

예

극대 원소 : 1, 4 극소 원소 : 2, 3 최대 원소 : 없음 최소 원소 : 없음	극대 원소 : 6, 8, 10 극소 원소 : 2 최대 원소 : 없음 최소 원소 : 2