페미위키:포크 프로젝트/리브레 위키/관계 (수학)

n항 관계 정의

어떤 집합 $X_{1},X_{2},...,X_{n}$의 곱집합(Cartesian Product)은 다음과 같이 정의될 수 있다

$\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\}$

"$X_{1},X_{2},...,X_{n}$ 위의 n항 관계 $R$"란 해당 곱집합의 부분집합으로 정의된다.

$R\subset \prod \limits _{i=1}^{n}X_{i}$

이때 $\left(x_{1},x_{2},...,x_{n}\right)\in R$를 보통 다음과 같이 쓴다:

$Rx_{1}x_{2}...x_{n}$

이는 일상어에서 ""$x_{1},x_{2},...,x_{n}$이 관계 $R$을 맺는다"라고 말하는 것에 대응한다.

2항 관계 정의

집합 R의 원소 r에 대해

$r=(x,y)$

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

$xRy$

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

$\operatorname {dom} R=\{x\vert \exists y[xRy]\}$

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

$\operatorname {ran} R=\{y\vert \exists x[xRy]\}$

$\operatorname {dom} R\cup \operatorname {ran} R$을 R의 마당(field)이라 하고 $\operatorname {field} R$로 쓴다.

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

2항 관계의 특성들

$X$ 위의 2항 관계 $R$이 띨 수 있는 대표적인 성질들은 다음과 같다:

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

예

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

$A\times B=\{(a,b)\vert a\in A{\text{ and }}b\in B\}$

는 관계다.

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

$\in _{A}=\{(a,b)\vert a\in A,b\in A,a\in b\}$

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

$E=\{(a,b)\vert a\in b\}$

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

$\forall x[x\in \{x\}]$

이므로,

$\forall x[(x,\{x\})\in E]$

이다. $\{x\}\in (x,y)$이므로

$\forall x\left[\{x\}\in \bigcup E\right]$

이고 따라서

$\forall x\left[x\in \bigcup \left(\bigcup E\right)\right]$

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