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} 가 성립합니다.