[이산수학]관계와 함수

기본 용어

관계는 보통 복수의 대상이 관련하여 이루는 특성으로 이해된다. 수학에서는 어떻게 정의할까?

수학에서 관계는 집합(곱집합)을 통해 정의된다. n개의 대상에 대해서 이들이 관련이 있다면 이를 n항 관계라 한다.

항이 2개인 이항관계의 가장 대표적인 예는 순서관계이다.

$$a<b$$

이는 $b$가 $a$보다 크다는 것을 의미한다. 구체적으로는 임의의 집합 $X$에 대해서 이항관계는 다음과 같이 정의한다.

$$R\subset X^2=X\times X$$

그리고 n항 관계는 다음과 같이 정의된다.

$$R\subset \prod_{i\in I}X_i$$

즉, 관계란 곱집합의 부분집합이다. (물론, 이항관계를 주로 다룬다.)

 

정의역은 적당한 $y\in Y$에 대하여 $(x,y)\in X\times Y$인 모든 $x\in X$의 집합을 의미하며, 다음과 같이 표기한다.

$$\mathrm{Dom}\left(R\right)$$

예를 들어 $X=\{1,2,3\}$와 $Y=\{1,2,3\}$의 관계가 다음과 같이 주어졌을 때,

$$R=\{(1,2),(2,3),(3,2)\}$$

관계 $R$의 정의역은 $(x,y)\in R$에서 $x$들을 모은 집합을 의미한다.

$$\mathrm{Dom}\left(R\right)=\{1,2,3\}$$

 

상은 적당한 $x\in X$에 대해서$(x,y)\in R$인 모든 $y\in Y$의 집합을 의미하며, 다음과 같이 표기한다.

$$\mathrm{Im}\left(R\right)$$

예를 들어 위에서 주어진 관계의 상은 $(x,y)\in R$에서 $y$들을 모은 집합을 의미하며, 다음과 같다.

$$\mathrm{Im}\left(R\right)=\{2,3\}$$

 

관계의 성질

집합 $X$에서의 관계 $R$에 대하여

다음을 만족할 때, 이 성질을 반사성이라 한다.

$$\forall x\in X,\ (x,x)\in R$$

예를 들어 집합 $X=\{1,2\}$의 관계 $R$이 반사성을 만족한다는 것은 다음과 같다는 뜻이다.

$$R=\{(1,1),(2,2)\}$$

관계가 다음과 같이 주어져도 모든 $x\in X$에 대해서 $(x,x)\in R$이기만 하면 되기 때문에 마찬가지로 반사성을 만족한다고 한다.

$$R=\{(1,1),(2,2),(2,1)\}$$

 

대칭성은 다음과 같은 성질을 말한다.

$$(x,y)\in R \implies (y,x)\in R$$

이 때, $x$와 $y$는 다를 수도 있고 같을 수도 있다.

예를 들어 집합 $X=\{1,2\}$에 대해 다음과 같은 관계를 말한다.

$$R=\{(1,2),(2,1)\}$$

대칭성 또한 마찬가지로 $(x,y)\in R$에 대해서 $(y,x)\in R$이기만 하면 되기 때문에 다음과 같은 관계 또한 대칭성을 만족한다고 한다.

$$R=\{(1,2),(2,1),(1,1)\}$$

 

반대칭성은 다음과 같은 성질을 말한다.

$$(x,y)\in R\wedge (y,x)\in R \implies x=y$$

예를 들어 집합 $X=\{1,2,3\}$에 대해 

$$R=\{(1,1),(2,2),(3,3)\}$$

은 반대칭성을 만족한다. 반면에 관계 $R$이 다음과 같이 주어졌을 때,

$$R=\{(1,1),(2,1),(1,2)\}$$

관계 $R$은 대칭적이지만 반대칭적이지는 않다. 왜냐하면 $(1,2)\in R\wedge (2,1)\in R$이지만 $1=2$는 거짓이기 때문이다.

 

추이성은 다음과 같은 성질을 말한다.

$$(x,y)\in R \wedge (y,z)\in R \implies (x,z)\in R$$

$(x,y)\in R$이고 $(y,z)\in R$일 때, $(x,z)$또한 원소로 갖는다면 이를 추이성이라고 한다. 삼단논법으로 생각하면 된다.

 

역관계

관계를 뒤집은 것을 의미하며, 다음과 같이 정의된다.

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

 

합성관계

합성관계는 합성함수로 이해하면 된다. 다음과 같이 정의된다.

관계 $G$와 $H$에 대해,

$$H\circ G=\{(x,z)| (x,y)\in G\wedge (y,z)\in H\}$$

 

여러가지 관계들

동치관계: 반사적, 대칭적, 추이적인 관계를 동치관계라 한다. 자연수, 정수, 실수에서의 "같다."를 의미하는 "="나 기하학에서의 합동 등이 동치관계에 속한다.

순서관계: 반사적, 반대칭적, 추이적인 관계를 말한다. $a<b$와 같은 부등호가 순서관계에 속한다.

 

분할

집합 $X$에 대해서 $X$의 분할은 다음과 같은 성질을 만족시키는 집합 $P$를 의미한다.

$$\forall A\in P,\ A\subset X$$

$$\varnothing \notin P$$

$$\forall A,\ B\in P,\ A\cap B = \varnothing$$

$$\bigcup P=\bigcup _{i\in I}A_i=X$$

어떤 집합을 분할해서 그 분할한 것들을 모아놓은 집합으로 이해하면 된다.

 

동치류

집합 $X$의 원소 $x\in X$와 동치관계 $R$에 대하여 다음과 같은 집합을 동치류라 한다.

$$[x]=\{y|(x,y)\in R\}$$

 

상집합

모든 동치류들의 집합이며, 다음과 같이 표기한다.

$$X/R=\{[x]| x\in X\}$$

 

함수

함수는 다음을 만족하는 $X$에서 $Y$로의 관계 $f:X\rightarrow Y,\ f\subset X\times Y$이다.

$$\forall x\in X,\ \exists! y\in Y\ s.t\ (x,y)\in f$$

$\exists!$는 유일하게 존재한다는 것을 의미한다.

$(x,y)\in f$는 $y=f(x)$로 표기하기도 한다.