3.1. 곱집합
“순서쌍”(Ordered Pair)은 원소들을 표현하는 방법으로, 원소들 사이에 순서를 갖는 것을 말합니다.
보통 괄호와 순서를 지켜서 표현됩니다.
예를들어 순서쌍(a, b)는 두 집합 내 각 원소를 a, b를 순서를 지켜 나타낸 것입니다.
“곱집합”(Cartesian Product)은 어떤 두 집합을 “×” 곱 한 순서쌍집합을 곱집합이라고 표현합니다.
두 집합 A, B에 대해 A × B 는 \{ ( a, b ) | a ∈ A , b ∈ B \}로 정의됩니다.
곱집합은 두 개 이상의 집합에서 모든 가능한 순서쌍 으로 정의되고,
곱집합의 크기는 | A × B | = | A | × | B | 로 정의 가능합니다.
3.2. 관계
두 집합 A, B 가 존재할 때, A에서 B로 가는 관계를 “이항관계”(Binary Relation)라고 표현합니다.
이항관계 R은 A × B의 부분집합이고, a ∈ A , b ∈ B 에 대해 ( a, b ) ∈ R 이면, “a \mathrel{R} b“으로 표현 가능 하고,
반대로 포함되지 않으면, “¬( a \mathrel{R} b )“으로 표현 가능 합니다.
관계 R의 “정의역”(Domain)은 R에 속한 순서쌍 중에서 모든 첫 번째 원소 집합이고,
R의 정의역은 “Dom(R)“로 나타낼 수 있고, 위의 예시에서 a들의 집합이 될 수 있습니다.
관계 R의 “치역”(Range)은 R에 속한 순서쌍 중에서 모든 두 번째 원소 집합이고,
R의 치역은 “Ran(R)“로 나타낼 수 있고, 위의 예시에서 b들의 집합이 될 수 있습니다.
어떤 집합 A에 대해 a ∈ A라고 정의 할 때, a \mathrel{R} a를 “항등관계”(Identity Relation)라고 표현합니다.
두 집합 A, B가 존재할 때, 집합 A의 원소의 개수 m개와 B의 원소의 개수 n개가 있을 때,
행이 m개 열이 n개 인 행렬 M에 대하여
행렬의 원소 M_{ij} = ( i \mathrel{R} j 가 있으면 1, 없으면 0 ) 으로 정의 한다면,
행렬 M을 “관계 행렬”(Relation Matrix)이라고 정의합니다.
관계 행렬은 행렬(부울 행렬)의 형태로도 표현가능하지만, 방향그래프(유향그래프)로도 표현 할 수 있습니다.
행에서 열로의 관계를 그래프에서 “정점”(Vertex)을 원소로 두고, “간선”(Edge 또는 방향 선분)을
행에서 열로의 관계로 정의하여 “방향그래프”(Directed Graph)로도 나타낼 수 있을 것입니다.
3.3. 경로
집합 A의 관계 R을 정의 할 때, 가능한 정의역 원소에서 길이가 n인 경로로 도달한 원소가 치역이라고 정의한다면,
정의역의 원소 a와 치역의 원소 b가 있다고 하면, “a \mathrel{R^n} b” 로 나타낼 수 있고, “길이가 n인 관계”라고 정의합니다.
가능한 정의역에서 가능한 경로로 모두 연결된 원소를 치역으로 정의한다면,
( 정의역 : a , 치역 : b 일 때, ) “a \mathrel{R^∞} b” 로 나타낼 수 있고, “연결관계”(Connectivity Relation)라고 정의합니다.
추가적으로 연결관계에서 연결된 두 원소간의 관계를 “도달관계”(Reachability Relation)라고 표현하고,
“\mathrel{R^*}“라고 표현 할 수 있습니다.
임의의 두 정점 사이에 도달관계가 성립하면 “강하게 연결”(Strongly Connected)되었다고 표현합니다.
길이가 n인 관계를 관계행렬의 부울 n제곱으로 나타낼 수도 있습니다.
길이가 n인 관계는 “M_{\mathrel{R^n}}“으로 구할 수 있고 M_{\mathrel{R^n}} = \underbrace{(M_{\mathrel{R}}) ⊙ \ldots ⊙ (M_{\mathrel{R}}}_{\rm n개}) = M_R^n 로 정의됩니다.
어떤 경로가 있을 때, 이 경로의 순서를 반대로 추적하면, 이를 “역경로”라고 표현합니다.
3.4. 관계의 종류(1)
관계에는 여러 가지 경우가 존재 할 수 있고, 이 중에서 특별한 관계들을 정의하여 사용하기도 합니다.
이번 장에서는 특별하게 정의한 관계에 대해 다룰 것입니다.
다음은 10가지의 특별한 관계에 대해 정의한 것입니다.
1). 집합 A에 관한 관계 R이 정의 될 때, \forall a \in A : a \mathrel{R} a ( 즉, \forall a \in A : ( a, a ) \in R ) 이면,
R을 “반사 관계”(Reflexive Relation)라고 정의합니다.
쉽게, A에 정의된 모든 원소가 자기 자신과 관계가 있으면 R은 반사 관계가 성립합니다.
2). 집합 A에 관한 관계 R이 정의 될 때, \forall a \in A : a \not\mathrel{R} a ( 즉, \forall a \in A : ( a, a ) \not\in R ) 이면,
R을 “비반사 관계”(Irreflexive Relation)라고 정의합니다.
정의를 주의 깊게 보면, 반사 관계와 비반사 관계는 역 이 아닙니다.
따라서 반사 관계 일수도, 비반사 관계 일수도, 둘 다 아닐 수도 있습니다.
3). 집합 A에 관한 관계 R이 정의 될 때, \forall (a, b) \in A : a \mathrel{R} b => b \mathrel{R} a 이면,
R을 “대칭 관계”(Symmetric Relation)라고 정의합니다.
쉽게, 관계 화살표를 나타낼 때, 어떤 두 원소 간에 서로 단 방향으로 화살표가 그려지면
이 두 단방향 화살표를 하나의 무 방향선으로 연결할 수 있습니다.
이때, 모든 화살표를 무 방향선으로 그릴 수 있으면, ( 무방향 그래프가 된다면, )
4). 집합 A에 관한 관계 R이 정의 될 때, \forall (a, b) \in A : a \mathrel{R} b => b \not\mathrel{R} a 이면,
R을 “비대칭 관계”(Asymmetric Relation)라고 정의합니다.
역시, 정의를 주의 깊게 보면, 대칭 관계와 비대칭 관계는 역 이 아닙니다.
5). 집합 A에 관한 관계 R이 정의 될 때, \forall (a, b) \in A : ( a \mathrel{R} b \wedge b \mathrel{R} a ) => a = b이면,
R을 “반대칭 관계”(Antisymmetric Relation)라고 정의합니다.
즉, 반대칭 관계는 원소 a와 b가 같을 때만 서로 관계가 있어야 하고 대우 관계에 따라
a와 b가 다를 때는 서로 관계가 있으면 안됩니다.
( 대우로 나타내면 \forall (a, b) \in A : a \neq b => a \not\mathrel{R} b \vee b \not\mathrel{R} a 가 됩니다. )
6). 집합 A에 관한 관계 R이 정의 될 때, \forall (a, b, c) \in A : ( a \mathrel{R} b \wedge b \mathrel{R} c ) => a \mathrel{R} c 이면,
R을 “추이 관계”(Transitive Relation)라고 정의합니다.
추이 관계는 직감적으로 이해가 되실 거라 믿습니다.
3.5. 관계의 종류(2)
위의 반사 관계와 대칭 관계와 추이 관계를 이해 하셨다면, 동치 관계에 대해 논할 수 있습니다.
7). 집합 A에 관한 관계 R이 정의 될 때, R := 반사 관계 \wedge R := 대칭 관계 \wedge R := 추이 관계 이면,
R을 “동치 관계”(Equivalence Relation)라고 정의합니다.
그리고, 정의된 모든 관계 R은 [ R := 반사 관계, S := 대칭 관계, T := 추이 관계 ]; 이 세 가지로 표현 가능합니다.
만약, R, S, T가 성립하지 않으면, \bar{R}, \bar{S}, \bar{T} 가 됩니다.
( 각 \bar{R}, \bar{S}, \bar{T}는 ” R, S, T가 아니다” 의 의미이므로 비반사, 비대칭, 반대칭 과는 차이가 있습니다. )
(I). 만약, 어떤 관계 R이 ( \bar{R}, \bar{S}, \bar{T} ) 이면, “트리” 형태가 되고, 트리는 단 방향, 비 순환 관계들로 이루어집니다.
(II). 만약, 어떤 관계 R이 ( \bar{R}, \bar{S}, T ) 이면, “>” (관계 순서가 있는 그래프) 형태가 되고,
단 방향, 비 순환 그래프들로 이루어집니다.
(III). 만약, 어떤 관계 R이 ( \bar{R}, S, \bar{T} ) 이면, 무 방향 직선 형태의 그래프가 되고,
서로 두 개의 원소 끼리 순환이 이루어집니다.
(IV). 만약, 어떤 관계 R이 ( R, \bar{S}, \bar{T} ) 이면, “형제 관계” 형태가 되고, 모든 원소 간의 무 방향 선과 순환이 이루어집니다.
(V). 만약, 어떤 관계 R이 ( \bar{R}, S, T ) 이면, “항등 관계”(identity) 형태가 되고,
모든 원소가 독립적으로 자신만 관계를 가지는 순환이 이루어집니다.
(VI). 만약, 어떤 관계 R이 ( R, \bar{S}, T ) 이면, “≥” 나 “부분 순서 관계”(partial ordering) 형태가 되고,
자기 자신만 순환하고 임의의 두 원소들과는 비 순환 그래프가 이루어집니다.
(VII). 만약, 어떤 관계 R이 ( R, S, \bar{T} ) 이면, “친구 관계”(compatibility) 형태가 되고,
자기 자신과 순환하는 서로 두 개의 원소끼리 순환이 이루어집니다.
(VIII). 만약, 어떤 관계 R이 ( R, S, T )이면, “동치 관계” 형태가 되고,
모든 가능한 단 방향 화살표가 그려진 그래프가 이루어집니다.
8). 집합 A에서 B로의 관계 R이 정의될 때, B에서 A로의 관계를 R^{-1} 이라고 표현하고,
이를 “역관계”(inverse relation) 라고 정의합니다.
( R^{-1} = \{(b, a) \in B \times A | (a, b) \in \mathrel{R}, a \in A, b \in B \} )
9). 집합 A, B 가 있고, R \subset A \times B 라고 정의될 때, R의 여를 \bar{R} 라고 표현하고,
이를 “여관계”(complementary relation) 라고 정의합니다.
( \bar{R} = \{(a, b) \in A \times B | (a, b) \not\in R \}, 즉 a \mathrel{\bar{R}} b <=> a \not\mathrel{R} b )
집합 A에 대해 관계 R과 S가 정의 될 때, R의 관계 행렬을 M_R, S의 관계 행렬을 M_S 라고 표현하고,
다음의 4가지를 성립합니다.
(I). M_{R \cap S} = M_R \wedge M_S
(II). M_{R \cup S} = M_R \vee M_S
(III). M_{R^{-1}} = (M_R)^T
(IV). M_{\bar{R}} = \bar{M_R}
10). 집합 A, B, C에 대해서 A에서 B로의 관계 R과 B에서 C로의 관계 S가 정의 될 때,
R 과 S의 합성 관계를 R \circ S 라고 표현하고 이를 “합성 관계”(Composite Relation)라고 정의합니다.
또한, R과 S로부터 R \circ S를 구하는 것을 “합성”(composition)이라고 표현합니다.
(R \circ S = \{(a, c) \in A \times C | (a, b) \in R 이고, \exists b \in B : (b, c) \in S \} )
합성 관계는 다음 3가지가 성립합니다.
(I). 두 합성 가능 한 관계 R과 S가 정의 될 때, 관계 행렬 M_{R \circ S} = M_R \odot M_S : ( \odot 는 부울곱 )
(II). 집합 A, B, C, D 가 존재하고 A에서 B로의 관계 R, B에서 C로의 관계 S, C에서 D로의 관계 T 가 정의 될 때,
결합법칙 ( R \circ S) \circ T = R \circ ( S \circ T ) 이 성립합니다.
(III). 집합 A, B, C가 존재하고, A에서 B로의 관계 R, B에서 C로의 관계 S 가 정의 될 때,
( R \circ S )^{-1} = S^{-1} \circ R^{-1} 가 성립합니다.