관계 구성

이항 관계의 수학에서 관계의 구성은 주어진 두 개의 이항 관계 R과 S에서 새로운 이항 관계 R ; S를 형성하는 것이다. 관계의 미적분학에서는 관계의 구성을 상대적 곱셈이라고 하며,^[1] 그 결과를 상대적 곱셈이라고 한다.^{[2]: 40} 함수 구성은 관련된 모든 관계가 함수인 관계 구성의 특별한 경우다.

삼촌과 고모라는 단어는 복합적인 관계를 나타낸다: 어떤 사람이 삼촌이 되려면 그는 부모(또는 이모의 여동생)의 형제여야 한다. 대수 논리학에서는 삼촌(xUz)의 관계가 "형제" (xBy)이고 "부모"(yPz)의 관계 구성이라고 한다.

$\displaystyle U=BP\quad \equiv \quad xByPz\iff xUz.}$

아우구스투스 드 모건부터 시작하여 삼단논법에 의한 전통적인 추리의 형식은 관계적 논리적인 표현과 그 구성으로 요약되어 왔다.^[3][4]

정의

${\displaystyle R}$ ${\displaystyle \subseteq }$ ${\displaystyle X}$ ${\displaystyle \times }$ Y ${\displaystyle R\subseteq X\time$ Y$}$과 $S$ ⊆ Y ${\displaystyle \times }$ ${\displaystyle Z}$ ${\displaystyle S\subseteq Y\time Z}$이(가) 두 개의$$ 이항 관계인 경우, 구성 $R{\displaystyle ;}$ ${\displaystyle S}$ ${\displaystystyle$ R$;S}$은 관계가 된다.

$[\displaystyle R;S=\{(x,z)\in X\times Z\mid \exists y\in Y:(x,y)\in R\land (y,z)\in S\}.}$

In other words, ${\displaystyle R;S\subseteq X\times Z}$ is defined by the rule that says ${\displaystyle (x,z)\in R;S}$ if and only if there is an element ${\displaystyle y\in Y}$ such that ${\displaystyle x\,R\,y\,S\,z}$ (i.e. ${\displaystyle (x,y)\in R$$}$ 및$$${\displaystyle }$( ${\displaystyle y}$, ${\displaystyle z}$) ${\displaystyle \in }$ ${\displaystyle S}$ ${\displaystyle (y,z)\in S}$ $$^{[5]: 13} )

공칭 변주곡

관계 구성을 위한 인픽스 표기법으로서의 세미콜론은 1895년 에른스트 슈뢰더의 교과서로 거슬러 올라간다.^[6] 건터 슈미트는 세미콜론, 특히 관계 수학(2011년)의 사용을 갱신했다.^{[2]: 40 [7]} 세미콜론의 사용은 (대부분 컴퓨터 과학자들에 의해) 카테고리 이론에서 사용되는 함수 구성에 대한 표기법뿐만 아니라 언어 ^[8]동적 의미론 내에서 동적 결합에 대한 표기법과 일치한다.^[9]

존 M의 관계 구성의 infix 표기법에는 작은 원$({\displaystyle R}$ ${\displaystyle \circ }$ ${\displaystyle S}$) ${\displaystyle(R\circ S)}$이 사용되어 왔다$$. Howie는 그의 책에서 관계의 sem그룹을 고려했다.^[10] 그러나 작은 원은 작동 순서에서 텍스트 순서를 반대로 하는 함수 $g{\displaystyle }$( f${\displaystyle }$(${\displaystyle }$)${\displaystyle }$=${\displaystyle }$( ${\displaystyle g}$ ${\displaystyle \circ }$ f${\displaystyle }$) = ( g ∘ ${\displaystyle f}$ )${\displaystyle }$( ${\displaystyle x}$) ${\displaystyle g(f(x)=(g\circle f)(x)})$의 구성을 나타내기 위해 널리 사용된다. 작은 원은 그래프와 관계^{[5]: 18} 소개 페이지에 사용되어 대칭(infix 표기법 없음)에 찬성하여 삭제되었다. 대수학에서는 대칭$({\displaystyle R}$ $){\displaystyle(RS)}$이 곱셈을 나타내는 데 흔히 사용되므로$$, 상대 곱셈을 나타낼 수도 있다.

원 표기법과 함께 첨자를 사용할 수 있다. 일부 저자는^[11] 왼쪽 또는 오른쪽 관계가 처음 적용되는 관계인지에 따라 필요할 때 명시적으로 ${\displaystyle {explicitly}_{}}$${\displaystyle {}_l}$ ${\$와 r${\$를 쓰는 것을 선호한다. 컴퓨터 공학에서 접하는 또 다른 변화는 Z 표기법이다$:{\displaystyle }$ { ${\displaystyle \circle$}은$$ 전통적인 (우측) 구성을 나타내기 위해 사용되지만, ( (U+2A3E fat FAT OPEN SEMVOON)은 왼쪽 구성을 나타낸다.^[12][13]

이진관계 $R{\displaystyle }$ ${\displaystyle \subseteq }$ ${\displaystyle X}$ ${\displaystyle \times }$ ${\displaystyle Y}$ ${\displaystyle R\subseteq X\time Y}$은(는) 집합이 객체로 있는 Rel 범주에서$$ 때때로 $형태{\displaystyle }$R :${\displaystyle X}$ → $[\displaystyle R\colon$X\$to$Y}로 간주된다$$. 렐에서 형태론의 구성은 위에서 정의한 것과 정확히 같은 관계의 구성이다. Set of set 범주는 Rel의 하위 범주로, 객체는 같지만 형태는 적다.

특성.

• 관계의 구성은 $연관성$이 있다: R${\displaystyle }$;${\displaystyle }$( ${\displaystyle S}$; ${\displaystyle T}$)${\displaystyle }$=${\displaystyle }$( ${\displaystyle R}$; ${\displaystyle S);}$ ${\displaystyle T}$. ${\displaystyle$ R$;(S;T)=(R;S);T.$$}$
• R ; S의 역관계는 (R ; S)^T = S ; R이다^TT. 이 속성은 비자발적인 세미그룹에 모든 이진관계를 설정한다.
• (부분)함수의 구성(즉, 기능적 관계)은 다시 (부분적)함수가 된다.
• R과 S가 주입식이라면 R ; S는 주입식이며, 이는 반대로 R의 주입성만을 의미한다.
• R과 S가 허탈적이라면, R ; S는 허탈적인데, 이는 거꾸로 S의 허탈성만을 내포한다.
• 세트 X의 이진 관계 집합(즉, X에서 X까지의 관계)과 (좌 또는 우) 관계 구성과 함께 0을 갖는 단노이드(monoid)를 형성하며, 여기서 X의 ID 맵은 중립 요소, 빈 집합은 0 요소다.

행렬의 측면에서 구성

유한 이항 관계는 논리 행렬로 표현된다. 이러한 행렬의 항목은 비교 객체에 해당하는 행과 열에 대해 표시된 관계가 거짓인지 참인지에 따라 0 또는 1이다. 그러한 행렬로 작업하는 것은 1 + 1 = 1 및 1 × 1 = 1의 부울 산수를 포함한다. 두 논리 행렬의 행렬 곱에 해당하는 행과 열이 있는 경우에만 1이 된다. 따라서 관계 구성의 논리적 행렬은 구성 요소를 나타내는 행렬의 행렬 산출물을 계산함으로써 찾을 수 있다. "매트릭스는 가상의 삼단논법과 소리에 의해 전통적으로 도출된 결론을 계산하는 방법을 구성한다."^[14]

이질적인 관계

이질적인 관계 R ⊆ A × B를 고려한다. 즉, A와 B는 구별되는 집합이다. 그 다음, R 관계와 R 관계 구성을 사용하여 R R^T (A에 대한)과^T R^T (B에 대한) 동질 관계가 있다.

만약 xx ∈ A yy b B xRy^T (즉, R은 (좌-)전체 관계인 경우, R R이^T 반사적 관계인지 아니면 I ⊆ R R^T R 여기서 나는 ID 관계 {xIx : x ∈ A}인지. 마찬가지로, R이 허탈적 관계라면,

R^T R ⊇ I = {xIx : x ∈ B}. 이 경우 R ⊆ R R^T R. 이차 관계에 대해 정반대의 포함이 발생한다.

${\displaystyle R^{}}$ $}'T$ R {\displaystyle ${\R}^{\textsf{T}R}$을(를) 사용하여 R $R{\displaystyle }$ ${\displaystyle R^{}}$= ${\displaystyle R.}$ ${\displaystyle R{\bar$}^{{R$}{\textsf{T}}}을(를)$ 만족하는 페러 유형의 관계를 구분한다.

예

렛 A = {프랑스, 독일, 이탈리아, 스위스 }, B = {프랑스, 독일, 이탈리아어 }, b = a의 국어일 때 aRb가 주는 R 관계. A와 B는 모두 유한하므로 R은 행(위에서 아래로)과 열(왼쪽에서 오른쪽으로)을 알파벳순으로 배열한다고 가정하면 논리 행렬로 나타낼 수 있다.

${\displaystyle {\pmatrix}1&0&0\\0&0&0\\\0&1\1&1\end{pmatrix}.}$

역관계 R은^T 전치된 매트릭스에 해당하며, 관계 $구성{\displaystyle {}^{}}$ R${\displaystyle {}^{}{T}^{}}$ ; ${\displaystyle R}$ ${\displaystyle R^{\textsf{T};R}$은 합계가 논리적 분리에 의해 구현될$$ 때 매트릭스 제품 R $T{\displaystyle {}^{}}$ ${\displaystyle R^{}}$ R ${\displaystyle$ R$^{\textsf {T}R}$에 해당한다$$. 3×3 매트릭스 $R{\displaystyle {}^{}}$ T ${\displaystyle R^{}}$ ${\displaystyle$ R$^{\textsf{T}R}$은(는) 모든 위치에서$$ 1을 포함하며, 반대로 매트릭스 제품은 다음과 같이 계산한다.

${\displaystyle RR^{\textsf{T}={\begin{pmatrix}1&0&1\\0&0&1\0&1\1&1\nd{pmatrix}}.}$

이 행렬은 대칭이며 A에 대한 동종 관계를 나타낸다.

이에 상응하여, $R{\displaystyle {}^{}{T}^{}}$ ; ${\displaystyle R}$ ${\displaystyle$ R$^{\textsf{T};R}$는 B의 보편적 관계이므로, 어떤 두 언어도 둘 다 사용되는 국가(사실: 스위스)를 공유한다. 반대로, 주어진 두 국가가 언어를 공유하는지 여부는 $R{\displaystyle }$; ${\displaystyle {}^{}}$; ${\displaystyle T^{}}$ ${\$를 사용하여 답할 수 있다$.$

슈뢰더 규칙

주어진 집합 V의 경우, V의 모든 이진 관계 집합은 포함(포함)에 의해 정렬된 부울 격자를 형성한다. 보완으로 인해 포함이 역전된다는 점을 상기하십시오. ${\displaystyle A}$ ${\displaystyle \subset }$ ${\displaystyle B}$ ${\displaystyle {⟹}^{}}$ ${\displaystyle B{}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle A\subset B^{\complement }\subset A^{\completion }}}$관계의^[15] 미적분학에서 다음과 같은 오버바에 의한 집합의 보어를 나타내는 것은 일반적이다. ${\displaystyle {\bar{A}=$$A^{\완료 }}$

S가 2진수 관계인 경우 ${\displaystyle S^{}}$ T ${\$S^{\$textsf{T}}$가 역수 관계를 나타내도록 하며, 전치라고도 한다. 그렇다면 슈뢰더 법칙은

${\displaystyle QR\subseteq S\quad \quad \quad Q^{\textsf{T}{\bar {S}}\subseteq {\c}\quad \quad \quad \quad \quad {\\s}R^{T}}\subseteq {Q}}.}$

구두로, 한 가지 등가성을 다른 요소로부터 얻을 수 있다: 첫 번째 또는 두 번째 요소를 선택하여 전치시킨 다음, 나머지 두 가지 관계를 보완하고 허용한다.^{[5]: 15–19}

관계 구성의 포함에 대한 이러한 변형은 에른스트 슈뢰더에 의해 상세하게 설명되었지만, 사실 아우구스투스 드 모건은 1860년 처음으로 그 변형을 정리 K로 표현했다.^[4] 그는 썼다.

${\displaystyle LM\subseteq N\implies {\bar {N}M^{\textsf {T}\subseteq {\bar {L}.}$^[16]

슈뢰더 규칙과 보완을 통해 다음과 같은 관련성 X에 대해 해결할 수 있다.

${\displaystyle RX\subseteq S\quad {\text{and}}\quad XR\subseteq S.}$

For instance, by Schröder rule ${\displaystyle RX\subseteq S\implies R^{\textsf {T}}{\bar {S}}\subseteq {\bar {X}},}$ and complementation gives ${\displaystyle X\subseteq {\overline {R^{\textsf {T}}{\bar {S}}}},}$ which is called the left residual of S by R .

인용구

관계의 구성이 곱셈의 한 종류로 결과물이 나오듯이, 어떤 구성들은 나누기와 비교해서 인용구를 만들어 낸다. 여기에는 왼쪽 잔차, 오른쪽 잔차, 대칭 몫의 세 가지 인수가 표시된다. 두 관계의 왼쪽 잔차는 동일한 도메인(출처)을 가지고 있다고 가정하여 정의되며, 오른쪽 잔차는 동일한 코도메인(범위, 표적)을 상정한다. 대칭 지수는 두 관계가 하나의 영역과 하나의 코도메인을 공유한다고 가정한다.

정의:

• 왼쪽 잔차: ${\$
• 오른쪽 잔차: $D{\displaystyle }$/ ${\displaystyle C}$ ${\displaystyle :=}$ ${\displaystyle D\stackrel{}{\stackrel{}{}}}$ ${\displaystyle \stackrel{}{\stackrel{}{¯}}}$의 C ${\displaystyle \stackrel{}{{\{}^{}}}$의 ${\$^{\$textsf{$T}}}
• Symmetric quotient: ${\displaystyle \operatorname {syq} (E,F)\mathrel {:=} {\overline {E^{\textsf {T}}{\bar {F}}}}\cap {\overline {{\bar {E}}^{\textsf {T}}F}}}$

슈뢰더의 규칙을 사용하는 AX ⊆ B는 X ⊆ A ${\displaystyle \mathrm{}}$ ${\displaystyle \backslash }$에 해당한다. 따라서 왼쪽 잔차는 AX ⊆ B를 만족하는 최대 관계다. 마찬가지로 포함 YC ⊆ D는 Y ⊆ D/C와 동등하며, 오른쪽 잔차는 YC ⊆ D를 만족하는 최대 관계다.^{[2]: 43–6}

On은 스도쿠와 잔차의 논리를 연습할 수 있다.

조인: 다른 형식의 구성

포크 오퍼레이터(<)가 도입되어 두 가지 관계 c: H → A와 d: H → B를 c(<<)d: H → A × B로 융합시켰다. 건설은 A × B → A 및 B, 관계로 이해되는 A × B 예상에 따라 달라지는데, 이는 역 관계가^T 있다는^T 것을 의미한다. 그러면 c와 d의 포크는 다음에 의해 주어진다.

${\d(<)d\mathrel {:=} c;a^{\textsf {T}\cap \d;b^{\textsf {T}.}$^[17]

n ≥ 2의 일반적인 n-place 관계에 적용되는 관계의 또 다른 형태는 관계 대수학의 가입 운용이다. 여기서 정의한 두 개의 이항 관계의 통상적인 구성은 이들의 결합을 통해 얻을 수 있으며, 3차적 관계로 이어 중간 요소를 제거하는 투영으로 이어진다. 예를 들어 쿼리 언어 SQL에는 조인(SQL) 작업이 있다.

참고 항목

• 악마적 구성
• 친구의 친구

메모들

참조

• M. Kilp, U. Knauer, A.V. Mikhalev(2000) 모노이드, 화환 제품 및 그래프에 응용한 법 및 범주, 수학의 De Gruyter Expositions 29권, Walter de Gruyter,ISBN 3-11-015248-7