이항 관계(binary relation)의 수학(mathematics)에서, 관계의 합성(composition of relations)은 두 주어진 이항 관계 R과 S로부터 새로운 이항 관계 R ; S를 형성하는 것입니다. 관계의 계산(calculus of relations)에서, 관계의 합성은 관계적 곱셈(relative multiplication)이라고 불리고, 그것의 결과는 관계적 곱(relative product)이라고 불립니다. 함수 합성(Function composition)은 관계의 합성의 특수한 경우이며 여기서 관련된 모든 관계는 함수(function)입니다.
단어 삼촌과 이모는 혼합 관계입니다: 삼촌인 사람에 대해, 그는 부모의 형제 (또는 고모에 대해 자매)여야 합니다. 대수적 논리(algebraic logic)에서, 삼촌의 관계 (xUz)는 관계 "...의 형제입니다" (xBy)와 "...의 부모입니다" (yPz)의 합성이라고 말합니다.
\(\quad U = BP \quad \equiv \quad xByPz \iff xUz.\)
오거스터스 드 모르간(Augustus De Morgan)을 시작으로, 삼단논법(syllogism)에 의한 추론의 전통적인 형식은 관계 논리적 표현과 그 합성에 의해 포함되어 왔습니다.
Definition
만약 \(R \subseteq X \times Y\)과 \(S \subseteq Y \times Z\)가 두 이항 관계이면, 그것들의 합성 \(R;S\)는 다음 관계입니다:
\(\quad R;S = \{ (x,z)\in X\times Z\mid \exists y\in Y: (x,y)\in R\land (y,z)\in S \}.\)
다시 말해서, \(R;S \subseteq X\times Z\)가 \((x,z)\in R;S\)인 것과 \(x\,R\,y\,S\,z\) (즉, \((x,y)\in R\)와 \((y,z)\in S\))를 만족하는 원소 \(y\in Y\)가 있는 것이 필요충분 조건이라고 말하는 규칙에 의해 정의됩니다.
Notational variations
관계의 합성에 대해 중위 표기법(infix notation)으로 세미콜론은 1895년 에른스트 슈뢰더(Ernst Schroder)의 교과서로 거슬러 올라갑니다. 군터 슈미트(Gunther Schmidt)는 특히 Relational Mathematics (2011)에서 세미콜론의 사용을 새롭게 했습니다. 세미콜론의 사용은 카테고리 이론(category theory)에서 (대부분 컴퓨터 과학자들에 의해) 함수 합성에 대한 표기법과 일치(coincides)하고, 마찬가지로 언어적 동적 의미론(dynamic semantics) 내에 동적 논리곱에 대한 표기법과 일치합니다.
작은 원 \((R \circ S)\)은 존 하위(Jon Howie)에 의해 관계의 반그룹(semigroup)을 고려하는 그의 책에서 관계의 합성의 중위 표기법에 대해 사용되어 왔습니다. 어쨌든, 작은 원은 연산 순서로부터 텍스트 순서를 거꾸로 하는 함수의 합성(composition of functions) \(g(f(x)) = (g \circ f)(x)\)을 나타내기 위해 널리 사용됩니다. 작은 원은 그것이 (중위 표기법 없는) 병치에 찬성으로 버려질 때까지 ''Graphs and Relations''의 소개 페이지에서 사용되었습니다. 병치(Juxtaposition) \((RS)\)는 역시 곱셈을 의미하기 위해 대수학에서 공통적으로 사용되므로, 그것은 관계있는 곱셈을 의미할 수도 있습니다.
나아가서 원 표기법과 함께, 아래 첨자가 사용될 수 있습니다. 일부 저자는 필요에 따라 왼쪽 또는 오른쪽 관계가 첫 번째로 적용되는지 여부에 의존하여 명시적으로 \(\circ_l\)와 \(\circ_r\)를 쓰는 것을 선호합니다. 컴퓨터 과학에서 볼 수 있는 또 다른 변형은 Z 표기법(Z notation)입니다: \(\circ\)는 전통적인 (오른쪽) 합성을 나타내기 위해 사용되지만, ⨾ (U+2A3E ⨾ FAT OPEN SEMICOLON)은 왼쪽 합성을 나타냅니다.
이항 관계 \(R\subseteq X\times Y\)는 때때로 집합을 대상으로 가지는 카테고리(category) Rel에서 사상 \(R\colon X\to Y\)으로 여겨집니다. Rel에서 , 사상의 합성은 위에서 정의된 것처럼 정확하게 관계의 합성입니다. 집합의 카테고리 집합(Set)은 같은 대상이지만 더 적은 사상을 가지는 Rel의 부분카테고리입니다.
Properties
- 관계의 합성은 결합적(associative)입니다: \(R;(S;T) = (R;S);T .\)
- R ; S의 전환 관계(converse relation)는 \(R\,;\,S)^\textsf{T} = S^\textsf{T}\,;\,R^\textsf{T}\)입니다. 이 속성은 집합에서 모든 이항 관계의 집합을 인볼루션을 갖는 반그룹(semigroup with involution)으로 만듭니다.
- (부분) functions (즉, 함수형 관계)의 합성은 다시 (부분) 함수입니다.
- 만약 R과 S가 단사(injective)이면, R ; S는 반대로 R의 오직 단사성을 의미하는 단사입니다.
- 만약 R과 S가 전사(surjective)이면, R ; S는 반대로 S의 오직 전사성을 의미하는 전사입니다.
- (왼쪽 또는 오른쪽) 관계 합성과 함께 집합 X에서 이항 관계 (즉, X에서 X로의 관계)의 집합은 영을 갖는 모노이드(monoid)를 형성하며, 여기서 X에서 항등 맵은 중립 원소(neutral element)이고 빈 집합은 영 원소(zero element)입니다.
Composition in terms of matrices
유한 이항 관계는 논리적 행렬(logical matrices)에 의해 표현됩니다. 이들 행렬의 엔트리는 영 또는 일이고, 표현된 그 관계가 비교 대상에 해당하는 행과 열에 대해 거짓 또는 참인지 여부에 의존합니다. 그러한 행렬로 작업하는 것은 1 + 1 = 1 및 1 × 1 = 1인 부울 산술과 관련시킵니다. 두 논리적 행렬의 행렬 곱(matrix product)에서 엔트리는 1이 곱해진 행과 열이 해당하는 1을 가지면 오직 1이 될 것입니다. 따라서 관계의 합성의 논리적 행렬은 구성 요소의 인수를 나타내는 행렬의 행렬 곱을 계산함으로써 구해질 수 있습니다. "행렬은 전통적으로 가설적 삼단논법과 다-삼단논법을 수단으로 도출된 결론을 계산하는 방법을 구성합니다."
Heterogeneous relations
이종 관계 R ⊆ A × B를 생각해 보십시오; 즉, 여기서 A와 B는 별개의 집합입니다. 그런-다음 그것의 전환(converse) \(R^\textsf{T}\)와 관계 R의 합성을 사용하여, 동종 관계 (A에서) \(RR^\textsf{T}\)와 (B에서) \(R^\textsf{T}R\)이 있습니다.
만약 ∀x ∈ A ∃y ∈ B xRy이면 (즉, R이 (왼쪽-)전체 관계이면), \(RR^\textsf{T}\)가 반사 관계(reflexive relation) 또는 \(\operatorname{I} \subseteq RR^\textsf{T} \forall x\)가 되도록 \(xRR^\textsf{T}x\)이며, 여기서 I는 항등 관계 {xIx : x ∈ A}입니다. 유사하게, 만약 R이 전사 관계(surjective relation)이면 다음입니다:
- \(R^\textsf{T}R \supseteq \operatorname{I}\) = {xIx : x ∈ B}. 이 경우에서 \(R \subseteq RR^\textsf{T}R\)입니다. 반대 포함은 이-함수형(difunctional) 관계에 대해 발생합니다.
합성 \(\bar{R}^\textsf{T} R \)은 \(R \bar{R}^\textsf{T} R = R\)을 만족시키는 페레르의 유형의 관계를 구별하기 위해 사용됩니다.
Example
b가 a의 국가 언어(national language)일 때 aRb에 의해 주어진 관계 R을 갖는 A = { France, Germany, Italy, Switzerland }와 B = { French, German, Italian }를 놓습니다. A와 B 둘 다는 유한하므로, R은 행 (꼭대기에서 바닥)과 열 (왼쪽에서 오른쪽)이 알파벳순으로 순서화됨을 가정하여 논리적 행렬(logical matrix)에 의해 표현될 수 있습니다:
\(\quad \begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 1 & 1
\end{pmatrix} .\)
전환 관계(logical matrix) \(R^\textsf{T}\)은 전치된 행렬(transposed matrix)에 해당하고, 관계 합성 \(R^\textsf{T}; R\)은 합계가 논리적 서로소(logical disjunction)에 의해 구현될 때 행렬 곱(matrix product)에 해당합니다. 그것은 3×3 행렬 \(R^\textsf{T} R\)이 모든 각 위치에 1을 포함하고, 반면에 뒤집힌 행렬 곱은 다음으로 계산됨이 밝혀졌습니다:
\(\quad R R^\textsf{T} = \begin{pmatrix}
1 & 0 & 0 & 1 \\
0 & 1 & 0 & 1 \\
0 & 0 & 1 & 1 \\
1 & 1 & 1 & 1
\end{pmatrix}.\)
이 행렬은 대칭적이고, A에 대한 동종 관계를 나타냅니다.
상응하게, \(R^\textsf{T}; R\)은 B에 대한 보편적 관계(universal relation)이고, 따라서 임의의 두 언어가 그것들 둘 다가 말하는 국가를 공유합니다 (사실: 스위스). 그 반대에 대해, 주어진 두 국가가 언어를 공유하는지 여부에 대한 질문은 \(R; R^\textsf{T}\)을 사용하여 답할 수 있습니다.
Schröder rules
주어진 집합 V에 대해, V에 대한 모든 이항 관계(binary relation)의 모음은 포함(inclusion) (⊆)에 의해 순서화된 부울 격자(Boolean lattice)를 형성합니다. 여집합(complementation) 뒤집힌 포함: \(A \subset B \implies B^{\complement} \subset A^{\complement}\)을 기억해 내십시오. 관계의 계산(calculus of relations)에서, 위쪽-막대에 의해 집합의 여집합을 포함하는 것이 공통적입니다: \(\bar{A} = A^{\complement} .\)
만약 S가 이항 관계이면, \(S^\textsf{T}\)가 전환 관계를 나타내는 것으로 놓고, 역시 전치라고 불립니다. 그런-다음 슈뢰더 규칙은 다음입니다:
\(\quad QR \subseteq S \quad \equiv \quad Q^\textsf{T} \bar{S} \subseteq \bar{R} \quad \equiv \quad \bar{S} R^\textsf{T} \subseteq \bar{Q} .\)
말로 하자면, 하나의 동등물은 또 다른 것에서 얻어질 수 있습니다: 첫 번째 또는 두 번째 인수를 선택하고 그것을 전치합니다; 그런-다음 다른 두 관계를 여하고 그것들을 순열합니다.
비록 관계 합성의 포함의 이러한 변형이 에른스트 슈뢰더(Ernst Schröder)에 의해 자세히 설명되었지만, 사실 오거스터스 드 모르간(Augustus De Morgan)은 1860년에 처음으로 변형을 정리 K로 명확히 했습니다. 그는 다음과 같이 썼습니다:
\(\quad L M \subseteq N \implies \bar{N} M^\textsf{T} \subseteq \bar{L}.\)
슈뢰더 규칙과 여(complementation)와 함께, 우리는 다음과 같은 관계 포함에서 미지수 관계 X에 대해 풀 수 있습니다:
\(\quad R X \subseteq S \quad \text{and} \quad XR \subseteq S .\)
예를 들어, 슈뢰더 규칙 \(RX \subseteq S \implies R^\textsf{T} \bar{S} \subseteq \bar{X}\)과 여에 의해 \(X \subseteq \overline{R^\textsf{T} \bar{S}}\)를 제공하며, 이것은 R에 의한 S의 왼쪽 잔여(left residual of S by R)라고 불립니다.
Quotients
관계의 합성이 곱의 결과로 곱셈의 한 유형인 것처럼, 일부 연산(operations)은 나눗셈과 비교하고 몫을 생성합니다. 세 가지 몫이 여기서: 왼쪽 잔여, 오른쪽 잔여, 및 대칭 몫으로 제시됩니다. 두 관계의 왼쪽 잔여는 그것들이 같은 도메인 (원천)을 가진다고 가정하고, 오른쪽 잔여는 같은 코도메인 (치역, 목표)을 가정하여 정의됩니다. 대칭 몫은 두 관계가 도메인과 코도메인을 공유한다고 가정합니다.
정의:
- 왼쪽 잔여: \(A\backslash B \mathrel{:=} \overline{A^\textsf{T} \bar{B} } \)
- 오른쪽 잔여: \(D/C \mathrel{:=} \overline{\bar{D} C^\textsf{T}} \)
- 대칭 몫: \(\operatorname{syq} (E, F) \mathrel{:=} \overline{E^\textsf{T} \bar{F} } \cap \overline{\bar{E}^\textsf{T} F}\)
슈뢰더의 규칙을 사용하여, AX ⊆ B는 X ⊆ A ∖ B와 동등합니다. 따라서 왼쪽 잔여는 AX ⊆ B를 만족시키는 가장 큰 관계입니다. 유사하게, 포함 YC ⊆ D은 Y ⊆ D/C와 동등하고, 오른쪽 잔여는 YC ⊆ D를 만족시키는 가장 큰 관계입니다.
우리는 스도쿠(Sudoku)로 잔여의 논리를 연습할 수 있습니다.
Join: another form of composition
포크 연산자 (<)는 두 관계 c: H → A와 d: H → B를 c(<)d: H → A × B로 융합하기 위해 도입되었습니다. 구성은 투영 a: A × B → A and b: A × B → B에 의존하고, 관계로 이해하며, 전환 관계 \(a^\textsf{T}\)와 \(b^\textsf{T}\)가 있음을 의미합니다. 그런-다음 c와 d의 포크(fork)는 다음에 의해 주어집니다:
\(\quad c(<)d \mathrel{:=} c ;a^\textsf{T} \cap\ d ;b^\textsf{T} .\)
n ≥ 2에 대해 일반적인 n-장소 관계에 적용하는 또 다른 형식의 관계의 합성은 관계적 대수(relational algebra)의 접합(join) 연산입니다. 여기에 정의된 것처럼 두 이항 관계의 보통 합성은 그것들의 접합을 취함으로써 얻어질 수 있으며, 중간 구성요소를 제거하는 투영에 뒤이어 삼항 연산으로 이어집니다. 예를 들어, 질의 언어 SQL에서 Join (SQL) 연산이 있습니다.
References
- M. Kilp, U. Knauer, A.V. Mikhalev (2000) Monoids, Acts and Categories with Applications to Wreath Products and Graphs, De Gruyter Expositions in Mathematics vol. 29, Walter de Gruyter,ISBN 3-11-015248-7.