추이적 관계

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 예시
4. 성질
- 4.1. 닫힘 성질
- 4.2. 기타 성질
5. 추이적 확장과 추이적 폐쇄
6. 추이성을 요구하는 관계
7. 추이 관계의 수
8. 관련 개념
참조

1. 개요

추이적 관계는 집합 X의 원소 a, b, c에 대해 a가 b와 관계를 맺고 b가 c와 관계를 맺으면 a가 c와 관계를 맺는 이항 관계 R을 의미한다. "보다 크다", "이상이다", "같다"와 같은 관계가 추이적 관계의 예시이며, "의 친모이다"와 같은 관계는 추이적이지 않다. 추이적 관계는 비반사적, 비대칭적, 강한 반순서 관계와 동치 관계를 가지며, 추이적 관계의 역관계와 교집합은 항상 추이적 관계이다. 추이적 확장과 추이적 폐쇄는 추이적 관계를 만드는 데 사용되며, 전순서, 부분 순서, 동치 관계 등 다양한 관계가 추이성을 요구한다. 유한 집합에 대한 추이 관계의 수를 세는 일반적인 공식은 알려져 있지 않다. 비추이적 관계, 반추이적 관계, 준추이 관계와 같은 관련 개념이 있으며, 확률적 추이성을 연구하는 분야도 존재한다.

2. 정의

집합 ''X''에 대한 동차 관계 ''R''은 다음과 같은 경우 '''추이 관계'''이다.^[1]

: 모든 $a, b, c \in X$ 에 대해, 만약 $a R b$ 이고 $b R c$ 이면, $a R c$ 이다.

또는 일계 논리로 표현하면 다음과 같다.

: $\forall a,b,c \in X: (aRb \wedge bRc) \Rightarrow aRc$

여기서 $a R b$ 는 $(a, b) \in R$ 에 대한 중위 표기법이다.

3. 예시

수학적 예시

실수 a, b, c에 대하여 다음 관계는 추이적이다.
* " $a < b$ " (보다 작다): $a < b$ 이고 $b < c$ 이면 $a < c$ 이다.
* " $a \le b$ " (이하이다): $a \le b$ 이고 $b \le c$ 이면 $a \le c$ 이다.
* " $a = b$ " (같다): $a = b$ 이고 $b = c$ 이면 $a = c$ 이다. 이는 자연수 집합에서도 마찬가지이다.
집합 A, B, C에 대하여 다음 관계는 추이적이다.
* " $A \subseteq B$ " (부분 집합이다): $A \subseteq B$ 이고 $B \subseteq C$ 이면 $A \subseteq C$ 이다.
* " $A = B$ " (같다): $A = B$ 이고 $B = C$ 이면 $A = C$ 이다.
기타 추이적 관계의 예시는 다음과 같다.
* " $x$ 는 $y$ 로 나누어 떨어진다" (자연수 간의 관계).
* " $p \implies q$ " ( $p$ 이면 $q$ 이다, 명제 간의 관계).
어떤 집합 $X$ 에 대한 공집합 관계는 추이적이다. 왜냐하면 $aRb$ 와 $bRc$ 를 만족하는 $a,b,c \in X$ 원소가 없어 추이성 조건이 공허하게 참이기 때문이다.
단 하나의 순서쌍만 포함하는 관계 *R*도 추이적이다. 만약 순서쌍이 $(x, x)$ 형태라면 $a=b=c=x$ 일 때 $aRc$ 가 성립하며, 순서쌍이 $(x, x)$ 형태가 아니라면 $aRb$ 와 $bRc$ 를 만족하는 $a,b,c$ 가 존재하지 않아 *R*은 공허하게 추이적이다.

비수학적 예시

"A는 B의 조상이다" 관계는 추이적이다. 예를 들어, 에이미가 베키의 조상이고 베키가 캐리의 조상이라면, 에이미도 캐리의 조상이다.

추이적 관계가 아닌 예시

"A는 B의 어머니다" 관계는 추이적 관계가 아니다. 앨리스가 브렌다의 친모이고 브렌다가 클레어의 친모라고 해서 앨리스가 클레어의 친모가 되는 것은 아니기 때문이다. 이 관계는 반추이적 관계이다. 즉, 앨리스는 클레어의 친모가 될 수 없다.
" $x \ne y$ " ( $x$ 와 $y$ 는 같지 않다).
"의 승계자이다" (자연수 간의 관계).
"집합의 구성원이다" ( $\in$ ).
"수직이다" (유클리드 기하학의 선 간의 관계).

4. 성질

추이 관계에서는 다음 관계들이 동치이다.

비반사 관계 (irreflexivity)
비대칭 관계 (asymmetry)
강한 반순서 관계 (strict partial order)

4. 1. 닫힘 성질

추이적 관계의 역관계는 항상 추이적 관계이다. 예를 들어, "부분 집합이다"가 추이적 관계이고, "상위 집합이다"가 그 역관계라는 것을 알면, 후자 또한 추이적 관계임을 알 수 있다.
두 추이적 관계의 교집합은 항상 추이적 관계이다.^[4] 예를 들어, "전에 태어났다"와 "이름이 같다"가 추이적 관계라는 것을 알면, "전에 태어났고 이름도 같다" 역시 추이적 관계임을 알 수 있다.
두 추이적 관계의 합집합은 추이적 관계가 아닐 수도 있다. 예를 들어, "전에 태어났거나 이름이 같다"는 추이적 관계가 아닌데, 왜냐하면 예를 들어 허버트 후버는 프랭클린 D. 루스벨트와 관련이 있고, 루스벨트는 다시 프랭클린 피어스와 관련이 있지만, 후버는 프랭클린 피어스와 관련이 없기 때문이다.
추이적 관계의 여집합은 추이적 관계가 아닐 수도 있다.^[5] 예를 들어, "같다"는 추이적 관계이지만, "같지 않다"는 최대 하나의 원소를 가진 집합에서만 추이적 관계이다.

4. 2. 기타 성질

추이 관계는 비반사적일 때에만 비대칭적이다.^[6]

추이 관계는 반사적일 필요는 없다. 만약 추이 관계가 반사적이기도 하다면, 이를 전순서라고 부른다. 예를 들어, 집합 ''X'' = {1, 2, 3} 위에서의 관계를 살펴보자.

''R'' = {(1,1), (2,2), (3,3), (1,3), (3,2)}는 반사적이지만, 추이적이지는 않다. 왜냐하면 (1, 3) ∈ ''R''이고 (3, 2) ∈ ''R''이지만, (1, 2) ∉ ''R''이기 때문이다.
''R'' = {(1,1), (2,2), (3,3), (1,3)}는 반사적이면서 추이적이므로, 전순서이다.
''R'' = {(1,1), (2,2), (3,3)}는 반사적이면서 추이적이므로, 역시 전순서이다. (이는 ''X'' 위의 항등 관계이다.)

반례로, 실수 집합 위의 '<' 관계 (보다 작음)는 추이적이지만 (a < b 이고 b < c 이면 a < c), 반사적이지는 않다 (a < a는 성립하지 않음).

5. 추이적 확장과 추이적 폐쇄

집합 X에 대한 이항 관계를 R이라고 하자. R의 '''추이적 확장'''은 R₁으로 표시되며, X에 대한 가장 작은 이항 관계로서 R₁이 R을 포함하고, (a, b) ∈ R이고 (b, c) ∈ R이면 (a, c) ∈ R₁이다.^[7] 예를 들어, X가 일부가 도로로 연결된 마을의 집합이라고 가정해 보자. 관계 R을 마을 A와 마을 B를 직접 연결하는 도로가 있는 경우 (A, B) ∈ R이라고 하자. 이 관계는 추이적일 필요는 없다. 이 관계의 추이적 확장은 최대 두 개의 도로를 사용하여 마을 A와 마을 C 사이를 여행할 수 있는 경우 (A, C) ∈ R₁으로 정의할 수 있다.

관계가 추이적이면 추이적 확장은 그 자체이다. 즉, R이 추이적 관계이면 R₁ = R이다.

R₁의 추이적 확장은 R₂로 표시되고, 이런 식으로 계속 진행하면 일반적으로 R_i의 추이적 확장은 R_i+1이 된다. R의 '''추이적 폐쇄'''는 R* 또는 R^∞로 표시되며, R, R₁, R₂, ... 의 합집합이다.^[8]

관계의 추이적 폐쇄는 추이적 관계이다.^[8]

사람들의 집합에서 "의 친생 부모이다"라는 관계는 추이적 관계가 아니다. 그러나 생물학에서는 임의의 세대에 걸쳐 친생 부모 관계를 고려해야 하는 경우가 종종 발생한다. "의 친생 조상이다"라는 관계는 추이적 관계이며, "의 친생 부모이다"라는 관계의 추이적 폐쇄이다.

위의 마을과 도로의 예에서, (A, C) ∈ R*는 여러 개의 도로를 사용하여 마을 A와 마을 C 사이를 여행할 수 있는 경우에 해당한다.

6. 추이성을 요구하는 관계

유사 순서 (Preorder): 반사성과 추이성을 만족하는 관계이다.
부분 순서 (Partial order): 반사성, 반대칭성, 추이성을 만족하는 관계이다. 즉, 반대칭적인 유사 순서이다.
전사적 유사 순서 (Total preorder): 반사성, 추이성, 완전성(totality)을 만족하는 관계이다. 즉, 완전한 유사 순서이다.
동치 관계 (Equivalence relation): 반사성, 대칭성, 추이성을 만족하는 관계이다. 즉, 대칭적인 유사 순서이다.
엄격한 부분 순서 (Strict partial order): 비반사성, 비대칭성, 추이성을 만족하는 관계이다.
엄격 약순서 (Strict weak ordering): 엄격한 부분 순서 중에서 비교 불가능성(incomparability)이 동치 관계를 이루는 관계이다.
전체 순서 (Total order): 반사성, 반대칭성, 추이성, 완전성을 만족하는 관계이다. 즉, 완전한 부분 순서이다.

추이적인 관계에서는 다음 세 가지 성질이 서로 동치이다.

비반사 관계 (irreflexivity)
비대칭 관계 (asymmetry)
강한 반순서 관계 (strict partial order)

7. 추이 관계의 수

유한 집합에 대한 추이 관계의 수를 세는 일반적인 공식은 알려져 있지 않다(OEIS A006905).^[9] 그러나 동시에 반사적이고, 대칭적이며, 추이적인 관계, 즉 동치 관계의 수를 찾는 공식(OEIS A000110)은 있다. 또한, 대칭적이고 추이적인 관계, 대칭적이고 추이적이며 반대칭적인 관계, 그리고 전체적이고 추이적이며 반대칭적인 관계의 수를 세는 방법도 알려져 있다.

Pfeiffer는 이러한 속성들의 조합으로 관계를 서로 표현하는 연구를 진행했지만, 여전히 개별 속성을 만족하는 관계의 수를 계산하는 것은 어렵다고 여겨진다.^[10]^[22] Brinkmann과 McKay (2005)의 연구도 참고할 수 있다.^[11]

모든 추이 관계의 반사화는 전순서이므로, ''n''개의 원소를 가진 집합에 대한 추이 관계의 수는 전순서의 수보다 최대 2^''n''배 많다. Kleitman과 Rothschild의 결과에 따라 이 수는 점근적으로 $2^{(1/4+o(1))n^2}$ 이다.^[12]

8. 관련 개념

Cycle diagram — 가위 바위 보 게임은 비추이적이고 반추이적인 관계 "''x''는 ''y''를 이긴다"를 기반으로 한다.

어떤 관계 ''R''이 ''xRy''이고 ''yRz''이지만, 일부 ''x'', ''y'', ''z''에 대해 ''xRz''가 성립하지 않으면 그 관계는 '''비추이적'''(intransitive)이라고 한다.

반대로, ''xRy''이고 ''yRz''일 때 항상 ''xRz''가 성립하지 않는다면, 그 관계 ''R''은 '''반추이적'''(antitransitive)이라고 한다.

예를 들어, 두 수의 곱 ''xy''가 짝수일 때 ''xRy''라고 정의된 관계는 비추이적이지만,^[13] 반추이적이지는 않다.^[14] ''x''가 짝수이고 ''y''가 홀수일 때 ''xRy''로 정의된 관계는 추이적이면서 동시에 반추이적이다.^[15] 또한, ''x''가 ''y''의 다음 수일 때 ''xRy''로 정의된 관계는 비추이적^[16]이고 반추이적이다.^[17] 비추이성은 정치적 문제나 집단 선호도 같은 예상치 못한 상황에서도 나타날 수 있다.^[18]

추이성을 일반화한 개념 중 하나로 '''확률적 추이성'''(probabilistic transitivity)이 있으며, 이는 의사 결정 이론, 심리 측정학, 공리주의 등 다양한 분야에서 응용된다.^[19]

또 다른 일반화로는 '''준추이 관계'''(quasitransitive relation)가 있다.^[5] 이는 관계의 비대칭적인 부분에 대해서만 추이성이 요구되는 관계이며, 사회 선택 이론이나 미시 경제학 등에서 사용된다.^[20]

'''명제:''' ''R''이 단일 관계이면 R;R^T는 추이적이다.

: 증명:

x R;R^T y R;R^T z

라고 가정하자. 그러면

x R a R^T y

이고

y R b R^T z

를 만족하는 ''a''와 ''b''가 존재한다. 이는 각각

x R a

,

y R a

그리고

y R b

,

z R b

를 의미한다. ''R''이 단일 관계이므로,

y R a

와

y R b

는 ''a''=''b''임을 의미한다. 따라서

x R a

이고

z R a

이며, 이는

x R a

와

a R^T z

를 의미한다. 그러므로

x R;R^T z

가 성립하고, R;R^T는 추이적이다.

'''따름정리:''' ''R''이 단일 관계이면 R;R^T는 ''R''의 정의역(domain)에서 동치 관계이다.

: 증명: R;R^T는 그 정의역에서 대칭적이고 반사적이다. ''R''이 단일 관계라는 조건 덕분에 동치 관계에 필요한 추이성 요구 사항이 충족된다.

추이 관계와 관련하여 다음 개념들은 서로 밀접하게 연관되어 있다.

비반사 관계 (irreflexivity)
비대칭 관계 (asymmetry)
강한 반순서 관계 (strict partial order)
반순서 (partial order) - 반대칭적인 유사 순서
유사 순서 (preorder) - 추이적이면서 동시에 반사적인 관계
전사적 유사 순서 (total preorder) - 완전한(total) 유사 순서
동치 관계 (equivalence relation) - 대칭적인 유사 순서
엄격 약순서 (strict weak order) - 강한 반순서 관계에서 동치 관계를 통해 비교 불가능성을 다루는 경우
전순서 (total order) - 추이적이며 반대칭적인 완전 관계

참조

_[1] 기타
_[2] 문서
_[3] 기타
_[4] 논문 On finite solvable groups in which normality is a transitive relation https://www.degruyte[...] 2022-12-29
_[5] 논문 Groups in which normality is a transitive relation https://www.cambridg[...] 2022-12-29
_[6] 서적 Transitive Closures of Binary Relations I https://web.archive.[...] School of Mathematics - Physics Charles University
_[7] 기타
_[8] 기타
_[9] 웹사이트 "Transitive relations, topologies and partial orders" http://www.people.fa[...] Steven R. Finch 2016-03-04
_[10] 간행물 "Counting Transitive Relations" http://www.cs.uwater[...] Götz Pfeiffer 2023-02-04
_[11] 웹사이트 "Counting unlabelled topologies and transitive relations" http://cs.anu.edu.au[...] Gunnar Brinkmann and Brendan D. McKay 2005-07-20
_[12] 논문 The number of finite topologies
_[13] 문서
_[14] 문서
_[15] 문서
_[16] 문서
_[17] 문서
_[18] 뉴스 Preferences are not transitive https://www.motherjo[...] 2018-11-29
_[19] 논문 Stochastic transitivity: Axioms and models 2018-08
_[20] 논문 Quasi-transitivity, rational choice and collective decisions
_[21] 웹사이트 "Transitive relations, topologies and partial orders" http://algo.inria.fr[...] Steven R. Finch
_[22] 간행물 "Counting Transitive Relations" http://www.cs.uwater[...] Götz Pfeiffer

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com