완전 관계

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

1. 개요

완전 관계는 집합 X 위의 이항 관계 R이 임의의 두 원소 x, y에 대해 (x, y) ∈ R이거나 (y, x) ∈ R을 만족하는 경우를 말한다. 이는 X × X = R ∪ R⁻¹과 동치이다. 완전 관계는 연결 관계, 강하게 연결된 관계와 관련되며, 전순서와 원전순서를 포함한다.

완전 관계

관계 속성

유형	이항 관계
집합	집합론

정의

설명	집합 X에 대한 관계 R이 X의 모든 구별되는 x와 y에 대해 xRy 또는 yRx를 만족하면 연결 관계이다.
수학적 표현	∀x, y ∈ X, x ≠ y → (xRy ∨ yRx)
동치 조건	∀x, y ∈ X, ¬(xRy) → yRx

예시

일반적인 예시	집합 X에 대한 전순서 관계는 연결 관계이다. X의 모든 x, y에 대해 xRy인 관계 R은 연결 관계이다.
특수한 예시	두 사람이 같은 키가 아니면 한 사람은 다른 사람보다 키가 큰 관계는 연결 관계이다. X가 집합 {1, 2, 3}이고 R이 X에 대한 관계 {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3)}이면, R은 연결 관계가 아니다.

관련 관계	전순서 관계 반사 관계 대칭 관계 추이 관계

2. 정의

집합 X 위의 이항 관계 R⊆ X×X가 다음 조건을 만족시키면, 완전 관계라고 한다.

* 임의의 x,y∈X에 대하여, (x,y)∈R이거나, (y,x)∈R이다.

이는

:X×X=R∪R^-1

와 동치이다. 여기서

:R^-1={(y,x)ː(x,y)∈R}

집합 X에 대한 관계 R이 모든 x, y ∈ X에 대해 다음 조건 중 하나를 만족하면 연결 관계라고 한다.

* $x \neq y$ 이면 $x \mathrel{R} y$ 또는 $y \mathrel{R} x$
* $x \mathrel{R} y$ 또는 $y \mathrel{R} x$ 또는 $x = y$

모든 $x, y \in X$ 에 대해 $x \mathrel{R} y$ 또는 $y \mathrel{R} x$ 를 만족하는 관계는 강하게 연결된 관계라고 한다.

2.1. 용어

집합 X 위의 이항 관계 R⊆ X×X가 다음 조건을 만족시키면, 완전 관계라고 한다.

* 임의의 x,y∈X에 대하여, (x,y)∈R이거나, (y,x)∈R이다.

이는

:X×X=R∪R^-1

와 동치이다. 여기서

:R^-1={(y,x)ː(x,y)∈R}

연결된 관계 개념은 주로 순서와 관련하여 전체 순서 또는 선형 순서를 정의하는 데 사용된다. 이 맥락에서 이 속성은 종종 특별히 명명되지 않는다. 오히려 전체 순서는 임의의 두 요소가 비교 가능한 부분 순서로 정의된다.

따라서 전체 관계는 연결되거나 강하게 연결된 관계에 대해 보다 일반적으로 사용되는 용어이다. 그러나 이 "전체 관계" 개념은 전체라고도 하는 직렬 속성과는 구별되어야 한다. 유사하게, 연결된 관계는 때때로 완전 관계라고도 불리지만, 이 역시 혼란을 야기할 수 있다. 전체 관계는 완전이라고도 불리며, "완전성"은 순서 이론에서 여러 다른 의미를 갖는다.

연결된 관계는 결합 관계라고도 하며, 삼분법을 만족한다고 한다.

순서 관계가 아닌 경우, 연결됨과 강하게 연결됨은 중요한 차이점이 있는 속성이다. 이 둘을 정의하는 자료에서는 약하게 연결된 관계와 연결됨, 완전과 강하게 완전, 전체와 완전, 반결합 관계와 결합 관계, 또는 결합 관계와 엄격히 결합된 관계를 각각 위에서 정의된 연결됨과 강하게 연결됨 개념의 대체 이름으로 사용한다.

3. 성질

완전 관계의 정의에서 $x=y$ 를 취하면, $(x,x)\in R$ 임을 알 수 있다. 따라서, 모든 완전 관계는 반사 관계이다. 강하게 연결된 관계가 대칭적이면, 그것은 전체 관계이다. 관계가 강하게 연결되기 위한 필요충분 조건은 연결적이고 반사적인 것이다. 집합 $X$ 에 대한 연결된 관계는 $X$ 에 적어도 4개의 원소가 있다면 반추이 관계일 수 없다. 예를 들어, 3개의 원소 집합 $\{ a, b, c \}$ 에서 관계 $\{ (a, b), (b, c), (c, a) \}$ 는 두 속성을 모두 갖는다. 만약 $R$ 이 $X$ 에 대한 연결된 관계라면, $X$ 의 모든 원소 또는 한 개를 제외한 모든 원소는 $R$ 의 상에 있다. 마찬가지로, $X$ 의 모든 원소 또는 한 개를 제외한 모든 원소는 $R$ 의 정의역에 있다.

3.1. 동치 조건

집합 $X$ 위의 이항 관계 $R\subseteq X\times X$ 가 다음 조건을 만족시키면, 완전 관계라고 한다.
* 임의의 $x,y\in X$ 에 대하여, $(x,y)\in R$ 이거나, $(y,x)\in R$ 이다.
이는
: $X\times X=R\cup R^{-1}$
와 동치이다. 여기서
: $R^{-1}=\{(y,x)\colon(x,y)\in R\}$
$R$ 을 동차 관계라고 할 때, 다음은 서로 동치이다.
* $R$ 은 강하게 연결되어 있다.
* $U \subseteq R \cup R^\top$
* $\overline{R} \subseteq R^\top$
* $\overline{R}$ 은 비대칭 관계이다.
여기서 $U$ 는 전체 관계이고 $R^\top$ 는 $R$ 의 역 관계이다.

다음은 서로 동치이다.
* $R$ 은 연결되어 있다.
* $\overline{I} \subseteq R \cup R^\top$
* $\overline{R} \subseteq R^\top \cup I$
* $\overline{R}$ 은 반대칭 관계이다.
여기서 $\overline{I}$ 는 항등 관계 $I$ 의 여집합 관계이고 $R^\top$ 는 $R$ 의 역 관계이다.

4. 예

모든 전순서는 완전 관계이다. 보다 일반적으로, 모든 원전순서는 완전 관계이다.

집합 $\{a,b,c\}$ 위의 순환적인 관계

: $a\preceq b\preceq c\preceq a$

: $a\preceq a$

: $b\preceq b$

: $c\preceq c$

는 완전 관계이다. 그러나 이는 전순서가 아니다.

5. 버트런드 러셀의 인용

Bertrand Russell은 진행을 도입하면서 연결의 공리를 언급했다.

: 일련의 관계가 전이적이고 비대칭적인 관계에 의해 원래 주어질 때마다, 우리는 일련의 임의의 두 항이 생성 관계를 갖는다는 조건으로 연결을 표현할 수 있다.