관계 (수학)

n항 관계 정의

어떤 집합 [math]\displaystyle{ X_1, X_2,..., X_n }[/math]의 곱집합(Cartesian Product)은 다음과 같이 정의될 수 있다

[math]\displaystyle{ \prod \limits_{i=1}^{n}X_i = X_1 \times X_2 \times... \times X_n = \left\{\left(x_1,x_2,... x_n\right)|x_1\in X_1, x_2\in X_2, ..., x_n\in X_n\right\} }[/math]

"[math]\displaystyle{ X_1, X_2,..., X_n }[/math] 위의 n항 관계 [math]\displaystyle{ R }[/math]"란 해당 곱집합의 부분집합으로 정의된다.

[math]\displaystyle{ R \subset \prod \limits_{i=1}^{n}X_i }[/math]

이때 [math]\displaystyle{ \left(x_1, x_2,..., x_n\right)\in R }[/math]를 보통 다음과 같이 쓴다:

[math]\displaystyle{ Rx_1 x_2... x_n }[/math]

이는 일상어에서 ""[math]\displaystyle{ x_1, x_2,..., x_n }[/math]이 관계 [math]\displaystyle{ R }[/math]을 맺는다"라고 말하는 것에 대응한다.

2항 관계 정의

집합 R의 원소 r에 대해

[math]\displaystyle{ r=(x,y) }[/math]

를 만족하는 [math]\displaystyle{ x,y }[/math]가 존재하면, R을 2항 관계(Binary relation)라고 한다. 이때 [math]\displaystyle{ (x,y)\in R }[/math]를 간단히

[math]\displaystyle{ xRy }[/math]

로 나타낸다. 이때, [math]\displaystyle{ (x,y)\in R }[/math]인 y가 존재하는 x들의 집합을 R의 정의역(domain)이라 하고 [math]\displaystyle{ \operatorname{dom} R }[/math]로 쓴다.

[math]\displaystyle{ \operatorname{dom} R=\{x\vert \exists y[xRy]\} }[/math]

고, [math]\displaystyle{ (x,y)\in R }[/math]인 x가 존재하는 y들의 집합을 R의 치역(range)이라 하고 [math]\displaystyle{ \operatorname{ran}R }[/math]로 쓴다.

[math]\displaystyle{ \operatorname{ran} R=\{y\vert \exists x [xRy]\} }[/math]

[math]\displaystyle{ \operatorname{dom}R\cup\operatorname{ran}R }[/math]을 R의 마당(field)이라 하고 [math]\displaystyle{ \operatorname{field}R }[/math]로 쓴다.

[math]\displaystyle{ \operatorname{dom} R = \operatorname{ran} R = X }[/math]인 경우, [math]\displaystyle{ R }[/math]은 "[math]\displaystyle{ X }[/math] 위의 2항 관계"라고 부르기도 한다.

2항 관계의 특성들

[math]\displaystyle{ X }[/math] 위의 2항 관계 [math]\displaystyle{ R }[/math]이 띨 수 있는 대표적인 성질들은 다음과 같다:

• 반사성(or 재귀성; reflexivity): [math]\displaystyle{ \forall x \in X: xRx }[/math]
• 대칭성(symmetricity): [math]\displaystyle{ \forall x,y \in X: xRy \to yRx }[/math]
• 비대칭성(asymmetricity): [math]\displaystyle{ \forall x,y \in X: xRy \to \neg yRx }[/math]
• 반대칭성(antisymmetricity): [math]\displaystyle{ \forall x,y \in X: (xRy \wedge yRx) \to (x=y) }[/math]
• 전이성(or 추이성, 이행성; transitivity): [math]\displaystyle{ \forall x,y,z \in X: (xRy \wedge yRz) \to (xRz) }[/math]
• 동치관계: [math]\displaystyle{ R }[/math]이 반사성, 대칭성, 전이성을 모두 만족시키는 경우.

예

집합 A,B에 대해, A와 B의 곱집합

[math]\displaystyle{ A\times B=\{(a,b)\vert a\in A \text{ and } b\in B\} }[/math]

는 관계다.

집합 A에 대해, 소속관계(membership relation)

[math]\displaystyle{ \in_A=\{(a,b)\vert a\in A, b\in A, a\in b\} }[/math]

는 잘 정의되어 있다. 그러나

[math]\displaystyle{ E=\{(a,b)\vert a\in b\} }[/math]

는 잘 정의되어 있지 않다. 왜냐 하면,

[math]\displaystyle{ \forall x[x\in \{x\}] }[/math]

이므로,

[math]\displaystyle{ \forall x[(x,\{x\})\in E] }[/math]

이다. [math]\displaystyle{ \{x\}\in (x,y) }[/math]이므로

[math]\displaystyle{ \forall x\left[ \{x\}\in \bigcup E\right] }[/math]

이고 따라서

[math]\displaystyle{ \forall x\left[ x\in \bigcup\left(\bigcup E\right)\right] }[/math]

이다. 그러므로 모든 집합의 집합이 존재하게 되어 모순이 발생한다. 따라서 E는 관계가 아니다.