이항 관계

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

1. 개요

이항 관계는 두 집합 간의 원소들 사이의 관계를 나타내는 수학적 개념이다. 집합 R이 이항 관계이면, R의 모든 원소는 순서쌍으로 구성된다. 집합 X와 Y의 데카르트 곱의 부분 집합으로 정의되며, 순서쌍 (x, y)가 R에 속할 경우 x와 y 사이에 관계 R이 성립한다고 표현한다. 이항 관계는 연산, 종류, 성질 등을 가지며, 함수, 동차 관계, 이종 관계 등 다양한 형태로 분류될 수 있다.

이항 관계

개요

정의	두 집합의 원소 간의 관계
다른 이름	이항 관계 (二項關係) 2항 관계 다이애딕 관계 (dyadic relation)

상세 정보

예시	'보다 큼' (>) '와 같다' (=) '의 약수이다'
표현	집합의 데카르트 곱의 부분집합
형식적 정의	임의의 두 집합 A와 B의 데카르트 곱 A × B의 부분집합 R ⊆ A × B
n항 관계	'n'개의 집합 A1, ..., An의 데카르트 곱 A1 × ... × An의 부분집합 R ⊆ A1 × ... × An

성질

종류	대칭적 반대칭적 연결적 정초적 합류를 가짐 교차를 가짐 반사적 비반사적 비대칭적
관련 개념	동치 관계 준순서 부분 순서 전순서 엄격한 부분 순서 약한 순서 엄격한 전순서 격자 합류 반격자 교차 반격자

📚 더 읽어볼만한 페이지

관계 (수학) - 동치 관계
동치 관계는 집합의 원소들 사이에서 반사성, 대칭성, 추이성을 만족하는 이항 관계로서, 집합을 겹치지 않는 부분집합인 동치류로 분할하여 몫집합 개념으로 이어지며 수학의 다양한 분야에서 활용된다.
관계 (수학) - 교환법칙
교환법칙은 집합 S에 정의된 이항연산 *에 대해 S의 임의의 두 원소 a, b에 대해 a * b = b * a가 성립하는 성질로, 덧셈, 곱셈, 집합의 교집합과 합집합 등이 그 예시이다.

1. 개요
2. 정의
3. 연산
4. 종류
5. 성질

2. 정의

이항 관계는 집합(또는 클래스) $X$ 와 $Y$ 의 데카르트 곱 $X \times Y$ 의 부분집합으로 정의된다. $(x, y) \in R$ 은 $x$ 가 $y$ 와 관계 $R$ 을 가짐을 의미하며, $xRy$ 로 표기하기도 한다.

$X$ 와 $Y$ 가 같은 집합일 때, 이항 관계는 동차 관계(또는 내부 관계)라고 불린다. $X$ 와 $Y$ 가 다른 집합일 때, 이항 관계는 이종 관계라고도 불린다.

이항 관계에서 원소의 순서는 중요하며, 만약 $x \neq y$ 이면, $yRx$ 는 $xRy$ 와 독립적으로 참 또는 거짓일 수 있다. 예를 들어, 3은 9를 나누지만, 9는 3을 나누지 않는다.

3. 연산

이항 관계는 집합 연산(합집합, 교집합)과 합성, 역관계 등의 연산을 할 수 있다.

만약 $R$ 과 $S$ 가 집합 $X$ 와 $Y$ 에 대한 이항 관계라면, $R \cup S = \{ (x, y) \mid xRy \text{ 또는 } xSy \}$ 는 $X$ 와 $Y$ 에 대한 $R$ 과 $S$ 의 합 관계이다. 항등원은 공집합 관계이다. 예를 들어, $\leq$ 는 <와 =의 합이고, $\geq$ 는 >와 =의 합이다.

만약 $R$ 과 $S$ 가 집합 $X$ 와 $Y$ 에 대한 이항 관계라면, $R \cap S = \{ (x, y) \mid xRy \text{ 이고 } xSy \}$ 는 $X$ 와 $Y$ 에 대한 $R$ 과 $S$ 의 교집합 관계이다. 항등원은 전체 관계이다. 예를 들어, "6으로 나누어떨어진다"라는 관계는 "3으로 나누어떨어진다"와 "2로 나누어떨어진다"라는 관계의 교집합이다.

3.1. 합성

이항 관계 $R$ 와 $S$ 의 합성 $S\circ R$ 는 다음과 같이 정의된다.

: $S\circ R=\{(x,z)|\exists y\colon(x,y)\in R\land(y,z)\in S\}$

즉, $S \circ R$ 은 $xRz$ 이고 $ySz$ 인 $y$ 가 존재할 때 $(x, z)$ 를 원소로 갖는 관계이다.

이항 관계의 합성은 결합 법칙을 만족시킨다.

: $(T\circ S)\circ R=T\circ(S\circ R)$

이에 따라, 범주 $\operatorname{Rel}$ 을 다음과 같이 정의할 수 있다.

* 대상은 집합이다.
* 두 집합 사이의 사상 $f\colon X\to Y$ 은 이항 관계 $f\subseteq X\times Y$ 이다.
* 사상의 합성은 이항 관계의 합성이다.
* 집합 $X$ 의 항등 사상은 대각선 $\operatorname{id}_X=\{(x,x)\colon x\in X\}\subseteq X\times X$ 이다.

집합과 이항 관계의 범주 $\operatorname{Rel}$ 은 모든 작은 곱과 쌍대곱을 가지며, 둘 모두 분리합집합으로 주어진다.

또한, 이항 관계 $R$ 의 거듭제곱을 다음과 같이 정의할 수 있다.

: $R^{\circ n}=\underbrace{R\circ\cdots\circ R}_n$

이에 대하여 다음 항등식들이 성립한다.

: $R^{\circ m} \circ R^{\circ n} =R^{\circ(m+n)}$
: $(R^{\circ m})^{\circ n} =R^{\circ mn}$

그 밖에도, 다음 항등식들이 성립한다.

: $\bigcup \mathcal{S} \circ R=\bigcup _{S\in \mathcal{S}}(S\circ R)$
: $S\circ \bigcup \mathcal{R} =\bigcup _{R\in \mathcal{R}}(S\circ R)$

만약 $R$ 이 집합 $X$ 와 $Y$ 에 대한 이항 관계이고, $S$ 가 집합 $Y$ 와 $Z$ 에 대한 이항 관계라면, $S \circ R = \{ (x, z) | \text{ 존재 } y \in Y \text{ 가 있어서 } xRy \text{ 이고 } ySz \}$ (또한 $R; S$ 로 표기)는 $X$ 와 $Z$ 에 대한 $R$ 과 $S$ 의 합성 관계이다.

여기서 사용된 $S \circ R$ 표기에서 $R$ 과 $S$ 의 순서는 함수의 합성에 대한 표준 표기 순서와 일치한다. 예를 들어, 합성 (부모이다) $\circ$ (어머니이다)는 (외조부모이다)를 생성하며, 반면 합성 (어머니이다) $\circ$ (부모이다)는 (할머니이다)를 생성한다. 전자의 경우, 만약 $x$ 가 $y$ 의 부모이고 $y$ 가 $z$ 의 어머니라면, $x$ 는 $z$ 의 외조부모이다.

3.2. 역관계

이항 관계 $R$ 의 역관계 $R^{-1}$ 는 $R$ 속 순서쌍의 두 성분을 뒤바꾼 이항 관계이다.

: $R^{-1}=\{(y,x)|(x,y)\in R\}$

역관계는 자명하게 대합을 이룬다.

: $(R^{-1})^{-1}=R$

역관계와 합성은 다음과 같이 호환된다.

: $(S\circ R)^{-1}=R^{-1}\circ S^{-1}$

특히,

: $(R^{\circ n})^{-1}=(R^{-1})^{\circ n}$

이다.

만약 $R$ 이 집합 $X$ 와 $Y$ 에 대한 이항 관계라면, $R^\textsf{T} = \{ (y, x) \mid xRy \}$ 는 $R$ 의 역관계이며, 이는 $Y$ 와 $X$ 에 대한 관계이다.

예를 들어, $=$ 는 자기 자신의 역관계이며, $\neq$ 도 마찬가지이다. 그리고 $<$ 와 $>$ 는 서로의 역관계이며, $\leq$ 와 $\geq$ 도 마찬가지이다. 이항 관계는 만약 대칭 관계일 때에만 역관계와 같다.

$R$ 이 $X$ 와 $Y$ 위의 이항 관계라면, 다음과 같은 $Y$ 와 $X$ 위의 이항 관계가 정해진다.

; 역관계 inverse^영어, converse^영어
: 어떤 집합 위의 이항 관계가 그 역관계와 일치하는 것은, 그 관계가 대칭적인 것과 동치이다.

3.3. 정의역과 치역

이항 관계 R의 정의역(dom R)은 R에 속하는 순서쌍의 첫 번째 원소들의 집합이다. 이항 관계 R의 치역(ran R)은 R에 속하는 순서쌍의 두 번째 원소들의 집합이다.

정의역과 치역은 다음과 같이 표현된다.

* 정의역:
*:math>\operatorname{dom}R=R^{-1}(V)=\{x|\exists y\colon(x,y)\in R\}
* 치역:
*:math>\operatorname{ran}R=R(V)=\{y|\exists x\colon(x,y)\in R\}

여기서,
* $R^{-1}(V)$ 는 모든 집합의 고유 모임의 원상이다.
* $R(V)$ 는 모든 집합의 고유 모임의 상이다.

상(image)과 원상(preimage)은 정의역과 치역 개념의 확장이다.

* 집합 또는 모임 $A$ 의 상은 $A$ 의 원소와 관계를 이루는 원소들의 집합이다.
*: $R(A)=\{y|\exists x\in A\colon(x,y)\in R\}$
* 집합 또는 모임 $B$ 의 원상은 역관계에 대한 상이다.
*: $R^{-1}(B)=\{x|\exists y\in B\colon (x,y)\in R\}$

임의의 이항 관계 $R$ 에 대하여 다음이 성립한다.
: $\operatorname{dom}R^{-1}=\operatorname{ran}R$
: $\operatorname{ran}R^{-1}=\operatorname{dom}R$
: $\operatorname{dom}R\cup\operatorname{ran}R=\bigcup\bigcup R$
: $\operatorname{dom}(S\circ R)\subseteq\operatorname{dom}R$
: $\operatorname{ran}(S\circ R)\subseteq\operatorname{ran}S$

4. 종류

이항 관계는 다양한 종류가 있으며, 크게 동차 관계와 이종 관계로 나눌 수 있다.

* 동차 관계: 반사 관계, 비반사 관계, 대칭 관계, 반대칭 관계, 비대칭 관계, 추이 관계, 연결 관계, 강한 연결 관계, 조밀 관계 등이 있다.
* 이종 관계: 단사, 함수 관계, 일대일, 일대다, 다대일, 다대다, 전체 관계, 전사 함수 등이 있다.

함수는 이항 관계의 중요한 유형 중 하나이지만, 모든 이항 관계가 함수는 아니다. 예를 들어, 약수 관계에서 5로 나누어지는 정수는 유일하지 않다.

실수에 대한 네 가지 유형의 이항 관계: 일대일(녹색), 일대다(파란색), 다대일(빨간색), 다대다(검은색).

4.1. 함수

함수는 이항 관계의 중요한 유형이다. 이항 관계 $F\subseteq X\times Y$ 가 함수 $F\colon X\to Y$ 일 필요충분조건은 다음 두 조건을 만족시키는 것이다.
* $\forall x\in X\exists y\in Y\colon xFy$
* $\forall x\in X\forall y,z\in Y\colon xFy\land xFz\implies y=z$

이항 관계는 일반적으로 함수가 아니다. 예를 들어 약수 관계에서, 5로 나누어지는 정수는 유일하지 않다.

집합

X

와

Y

에 대한 몇 가지 중요한 유형의 이항 관계

R

은 다음과 같다.

고유성 속성:
* 함수 관계 (오른쪽 고유 또는 단가): 모든

x \in X

와 모든

y, z \in Y

에 대해,

xRy

이고

xRz

이면

y = z

이다. 즉, 정의역의 모든 요소는 최대 하나의 상 요소를 갖는다. 이러한 이항 관계를 부분 함수 또는 부분 매핑이라고 한다. 이러한 관계에 대해

\{ X \}

는

R

의 기본 키라고 한다. 예를 들어, 그림의 빨간색과 녹색 이항 관계는 함수 관계이지만, 파란색 관계는 (

1

을

1

과

-1

에 모두 연결하므로) 그렇지 않으며, 검은색 관계도 (

0

을

-1

과

1

에 모두 연결하므로) 그렇지 않다.

전체성 속성 (정의역

X

와 공역

Y

가 지정된 경우에만 정의 가능):
* 전체 (왼쪽 전체): 모든

x \in X

에 대해,

xRy

인

y \in Y

가 존재한다. 즉, 정의역의 모든 요소는 최소 하나의 상 요소를 갖는다. 즉,

R

의 정의역은

X

와 같다. 이 속성은 연결 관계의 정의와는 다르다(일부 저자는 전체라고도 함). 이러한 이항 관계를 다중 값 함수라고 한다. 예를 들어, 그림의 빨간색과 녹색 이항 관계는 전체이지만, 파란색 관계는 (

-1

을 어떤 실수에도 연결하지 않으므로) 그렇지 않으며, 검은색 관계도 (

2

를 어떤 실수에도 연결하지 않으므로) 그렇지 않다. 또 다른 예로,

>

는 정수에 대한 전체 관계이다. 그러나 양의 정수에는

1 > y

인

y

가 없으므로, 양의 정수에 대한 전체 관계는 아니다.

고유성 및 전체성 속성 (정의역

X

와 공역

Y

가 지정된 경우에만 정의 가능):
* 함수 (매핑): 함수 관계이고 전체적인 이항 관계이다. 즉, 정의역의 모든 요소는 정확히 하나의 상 요소를 갖는다. 예를 들어, 그림의 빨간색과 녹색 이항 관계는 함수이지만, 파란색과 검은색 관계는 그렇지 않다.

4.2. 동차 관계의 종류

* 반사적 관계: 모든 $x \in X$ 에 대해 $xRx$ 인 관계이다. 예를 들어, $\geq$ 는 반사 관계이지만, >는 그렇지 않다.
* 비반사적 관계: 모든 $x \in X$ 에 대해 $xRx$ 가 성립하지 않는 관계이다. 예를 들어, $>$ 는 비반사 관계이지만, $\geq$ 는 그렇지 않다.
* 대칭적 관계: 모든 $x, y \in X$ 에 대해, $xRy$ 이면 $yRx$ 인 관계이다. 예를 들어, "는 의 혈족이다"는 대칭 관계이다.
* 반대칭적 관계: 모든 $x, y \in X$ 에 대해, $xRy$ 이고 $yRx$ 이면 $x = y$ 인 관계이다. 예를 들어, $\geq$ 는 반대칭 관계이다.
* 비대칭적 관계: 모든 $x, y \in X$ 에 대해, $xRy$ 이면 $yRx$ 가 성립하지 않는 관계이다. 관계가 비대칭적일 필요충분조건은 반대칭적이면서 비반사적이어야 한다. 예를 들어, >는 비대칭 관계이지만, $\geq$ 는 그렇지 않다.
* 추이적 관계: 모든 $x, y, z \in X$ 에 대해, $xRy$ 이고 $yRz$ 이면 $xRz$ 인 관계이다. 추이 관계가 비반사적일 필요충분조건은 비대칭적이어야 한다. 예를 들어, "는 의 조상이다"는 추이 관계인 반면, "는 의 부모이다"는 그렇지 않다.
* 연결적 관계: 모든 $x, y \in X$ 에 대해, $x \neq y$ 이면 $xRy$ 또는 $yRx$ 인 관계이다.
* 강하게 연결적 관계: 모든 $x, y \in X$ 에 대해, $xRy$ 또는 $yRx$ 인 관계이다.
* 조밀한 관계: 모든 $x, y \in X$ 에 대해, $xRy$ 이면, $xRz$ 이고 $zRy$ 인 $z \in X$ 가 존재하는 관계이다.

4.3. 이종 관계의 종류

집합 $X$ 와 $Y$ 에 대한 이항 관계 $R$ 은 다음과 같은 고유성 속성을 가질 수 있다.

* 단사(왼쪽 고유라고도 함): $X$ 의 임의의 원소 $x$ , $y$ 와 $Y$ 의 임의의 원소 $z$ 에 대해, $xRz$ 이고 $yRz$ 이면 $x = y$ 이다. 즉, 공역의 모든 요소는 최대 하나의 원상 요소를 갖는다. 이러한 관계에 대해 $Y$ 는 $R$ 의 기본 키라고 한다.
* 함수 관계(오른쪽 고유 또는 단가라고도 함): $X$ 의 임의의 원소 $x$ 와 $Y$ 의 임의의 원소 $y$ , $z$ 에 대해, $xRy$ 이고 $xRz$ 이면 $y = z$ 이다. 즉, 정의역의 모든 요소는 최대 하나의 상 요소를 갖는다. 이러한 이항 관계를 부분 함수라고도 한다. 이러한 관계에 대해 $\{ X \}$ 는 $R$ 의 기본 키라고 한다.
* 일대일: 단사이고 함수 관계이다.
* 일대다: 단사이지만 함수 관계는 아니다.
* 다대일: 함수 관계이지만 단사는 아니다.
* 다대다: 단사도 아니고 함수 관계도 아니다.

또한, 다음과 같은 전체성 속성을 가질 수 있다. (정의역 $X$ 와 공역 $Y$ 가 지정된 경우에만 정의 가능)

* 전체(왼쪽 전체라고도 함): $X$ 의 모든 원소 $x$ 에 대해, $xRy$ 인 $y$ 가 $Y$ 에 존재한다. 즉, 정의역의 모든 요소는 최소 하나의 상 요소를 갖는다. 이러한 이항 관계를 다중 값 함수라고 한다.
* 전사(오른쪽 전체라고도 함): $Y$ 의 모든 원소 $y$ 에 대해, $xRy$ 인 $x$ 가 $X$ 에 존재한다. 즉, 공역의 모든 요소는 최소 하나의 원상 요소를 갖는다.

고유성과 전체성 속성을 조합하여 다음과 같은 관계를 정의할 수 있다.

* 함수: 함수 관계이고 전체인 이항 관계이다. 즉, 정의역의 모든 요소는 정확히 하나의 상 요소를 갖는다.
* 단사 함수: 단사인 함수이다.
* 전사 함수: 전사인 함수이다.
* 전단사 함수: 단사이고 전사인 함수이다. 즉, 정의역의 모든 요소는 정확히 하나의 상 요소를 가지며, 공역의 모든 요소는 정확히 하나의 원상 요소를 갖는다.

실수에 대한 네 가지 유형의 이항 관계의 예: 일대일(녹색), 일대다(파란색), 다대일(빨간색), 다대다(검은색).

5. 성질

집합론적 관점에서 특정 관계(같음, 부분집합, 원소)는 이항 관계로 정의될 수 없는 경우가 있다. 왜냐하면 그들의 정의역과 공역이 일반적인 공리적 집합론 체계에서 집합으로 간주될 수 없기 때문이다. 예를 들어, 일반적인 "같음"의 개념을 이항 관계 $=$ 로 모델링하려면, 정의역과 공역을 "모든 집합의 클래스"로 설정해야 하는데, 이것은 일반적인 집합론에서는 집합이 아니다. 이 문제에 대한 일반적인 해결책은 "충분히 큰" 집합 $A$ 를 선택하고, $=$ 대신 제한된 $=_A$ 를 사용하는 것이다.

동차 관계는 유향 그래프로 표현될 수 있다.

관계 미적분은 이항 관계의 연산을 다루는 수학 분야이다. 관계의 합성과 역관계의 사용으로 확장된다.

유도된 개념 격자는 이항 관계를 분석하는 데 사용된다. 주어진 관계 $R \subseteq X \times Y$ 에 대해, 조인과 만남에 의해 확장된 개념 집합은 "유도된 개념 격자"를 형성하며, 포함 $\sqsubseteq$ 은 전순서를 형성한다.

디펑셔널 관계, 페레 타입 관계, 접촉 관계 등 특수한 관계들이 존재한다.

* 디펑셔널 관계: 동치 관계의 일반화로서, 구별되는 속성으로 객체를 분할한다. 자크 리게는 이 관계들을 디펑셔널이라고 명명했다.
* 페레 타입 관계: 자크 리고는 일반적인 이진 관계로 순서를 확장하기 위해 페르 다이어그램이라고 하는 정수 분할의 순서를 채택했다.
* 접촉 관계: 게오르그 아우만에 의해 도입되었다.

이항 관계의 종류와 그 성질은 다음 표와 같다.

👆

좌우로 밀어서 보기

이항 관계와 그 성질
이항 관계	자주 사용되는 기호	예
유향 그래프	→
무향 그래프
토너먼트		상하 관계 (찌르기 순서)
dependency relation^영어
weak order^영어	≤
전순서	≤	선호 순서 (선호 관계의 일종)
반순서	≤	포함 관계
partial equivalence relation^영어
동치 관계	∼, ≅, ≈, ≡	항등 관계
strict partial order^영어	<	진 부분 집합 관계