만약 어떤 관계 `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) \}$ 은 동치 관계임을 앞에서 증명하였다.
만약 관계 `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개이거나 없을 수도 있다.
Microsoft Student (2023)
