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

n항 관계 정의

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

$\prod _{i=1}^n{X}_i=X_1\times X_2\times \mathrm{...}\times X_n=\{(x_1,x_2,\mathrm{...}{x}_n)|x_1\in X_1,x_2\in X_2,\mathrm{...},x_n\in X_n\}$

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

$R\subset \prod _{i=1}^n{X}_i$

이때 $(x_1,x_2,\mathrm{...},x_n)\in R$를 보통 다음과 같이 쓴다:

$R{x}_1{x}_2\mathrm{...}{x}_n$

이는 일상어에서 ""$x_1,x_2,\mathrm{...},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)이라 하고 $\mathrm{dom}R$로 쓴다.

$\mathrm{dom}R=\{x|\mathrm{\exists }y[xRy]\}$

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

$\mathrm{ran}R=\{y|\mathrm{\exists }x[xRy]\}$

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

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

2항 관계의 특성들

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

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

예

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

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

는 관계다.

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

${\in }_A=\{(a,b)|a\in A,b\in A,a\in b\}$

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

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

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

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

이므로,

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

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

$\mathrm{\forall }x[\{x\}\in \bigcup E]$

이고 따라서

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

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