[집합론] 9. 관계와 함수(4. 단사, 전사, 전단사, 합성함수)

[집합론] 9. 관계와 함수(4. 단사, 전사, 전단사, 합성함수)

함수 \(f:\,X\,\rightarrow\,Y\)에서의 \(x_{1},\,x_{2}\in X\)에 대하여 \(f(x_{1})=f(x_{2})\,\Rightarrow\,x_{1}=x_{2}\)일 때 이 함수를 일대일(one-to-one) 또는 단사적(injective)이라 하고, 단사적 함수를 간단히 단사(injection)라고 한다.(정의역의 원소가 공역의 서로 다른 원소에 대응)

대우를 이용하여 단사를 다음과 같이 정의할 수 있다.

함수 \(f:\,X\,\rightarrow\,Y\)에서 \(x_{1},\,x_{2}\in X\)에 대해 \(x_{1}\neq x_{2}\,\Rightarrow\,f(x_{1})\neq f(x_{2})\)일 때 이 함수는 단사이다.

함수 \(f:\,X\,\rightarrow\,Y\)에 있어서 임의의 \(y\in Y\)에 대하여 적어도 하나의 \(x\in X\)가 존재해서 \(y=f(x)\)일 때 이 함수를 위로(onto) 또는 전사적(surjective)이라고 한다. 전사적 함수를 간단히 전사(surjection)라고 부른다.(공역과 치역이 같음)   

다시 말하면 함수 \(f:\,X\,\rightarrow\,Y\)에 대하여 \(f[X]=Y\)일 때 그리고 그때에만 \(f\)는 전사이다.

함수 \(f:\,X\,\rightarrow\,Y\)가 단사적이고 전사적일 때 이 함수를 전단사적(bijection)이라 하고 이러한 함수를 간단히 전단사(bijective) 또는 일대일대응(one-to-one correspondence)이라고 한다.

예를들어 항등함수 \(I_{X}\)는 전사이고 단사이므로 전단사이다.

주어진 함수 \(f:\,X\,\rightarrow\,Y\)가 단사이면 그 정의역 \(X\)의 부분집합족 \(\{A_{\gamma}\,|\,\gamma\in\Gamma\}\)에 대하여 \(\displaystyle f\left[\bigcap_{\gamma\in\Gamma}{A_{\gamma}}\right]=\bigcap_{\gamma\in\Gamma}{f[A_{\gamma}]}\)이다. 

증명:$$\begin{align*}y\in\bigcap_{\gamma\in\Gamma}{f[A_{\gamma}]}\,&\Leftrightarrow\,\forall\gamma\in\Gamma,\,y\in f[A_{\gamma}]\\&\Leftrightarrow\,\forall\gamma\in\Gamma[\exists x_{\gamma}\in A_{\gamma},\,y=f(x_{\gamma})]\end{align*}$$이고 가정에서 \(f:\,X\,\rightarrow\,Y\)는 단사이므로 \(x_{\gamma}\)들은 모두 같다. 이것을 \(x_{0}\)라고 하면$$\begin{align*}y\in\bigcap_{\gamma\in\Gamma}{f[A_{\gamma}]}\,&\Leftrightarrow\,\forall\gamma\in\Gamma[\exists x_{0}\in A_{\gamma},\,y=f(x_{0})]\\&\Leftrightarrow\,\exists x_{0}\in\bigcap_{\gamma\in\Gamma}{A_{\gamma}},\,y=f(x_{0})\\&\Leftrightarrow\,y\in f\left[\bigcap_{\gamma\in\Gamma}{A_{\gamma}}\right]\end{align*}$$그러므로 \(\displaystyle y\in\bigcap_{\gamma\in\Gamma}{f[A_{\gamma}]}\,\Leftrightarrow\,y\in f\left[\bigcap_{\gamma\in\Gamma}{A_{\gamma}}\right]\)이고 따라서 \(\displaystyle f\left[\bigcap_{\gamma\in\Gamma}{A_{\gamma}}\right]=\bigcap_{\gamma\in\Gamma}{f[A_{\gamma}]}\)이다. 

집합 \(X\)에서 집합 \(Y\)로의 관계 \(\mathcal{R}\)에 대한 역관계 \(\mathcal{R}^{-1}=\{(y,\,x)\,|\,(x,\,y)\in\mathcal{R}\}\)는 \(Y\)에서 \(X\)로의 관계이다. 함수 \(f:\,X\,\rightarrow\,Y\)는 집합 \(X\)에서 집합 \(Y\)로의 관계이므로 역함수 \(f^{-1}\)는 집합 \(Y\)에서 \(X\)로의 관계이다.

전단사 \(f:\,X\,\rightarrow\,Y\)에 대하여 \(f^{-1}:\,Y\,\rightarrow\,X\)도 전단사이다.(증명생략)

전단사 \(f:\,X\,\rightarrow\,Y\)에 대하여 \(f^{-1}:\,Y\,\rightarrow\,X\)를 \(f\)의 역함수(inverse function)라고 한다. 함수 \(f:\,X\,\rightarrow\,Y\)가 전단사일 때 이 \(f\)를 \(X\)와 \(Y\) 사이의 일대일대응 이라고 한다.

두 함수 \(f:\,X\,\rightarrow\,Y\), \(g:\,Y\,\rightarrow\,Z\)가 주어졌을 때 각 \(x\in X\)에 대하여 \((g\circ f)(x)=g(f(x))\)로 정의된 함수 \(g\circ f:\,X\,\rightarrow\,Z\)를 \(f\)와 \(g\)의 합성함수라고 한다. 이 합성함수를 순서쌍을 이용하여 다음과 같이 나타낼 수 있다.$$g\circ f=\{(x,\,z)\in X\times Z\,|\,\exists y\in Y\,[(x,\,y)\in f\wedge(y,\,z)\in g]\}$$합성함수에 대한 결합법칙이 성립한다. 즉, \(f:\,X\,\rightarrow\,Y\), \(g:\,Y\,\rightarrow\,Z\), \(h:\,Z\,\rightarrow\,W\)에 대하여 \((h\circ g)\circ f=h\circ(g\circ f)\)             

증명: \((h\circ g)\circ f,\,h\circ(g\circ f)\)는 각각 \(X\)에서 \(W\)로의 함수이다. 그러므로 서로 같음을 보이려면 \(((h\circ g)\circ f)(x)=(h\circ(g\circ f))(x)\)임을 보이면 된다.

모든 \(x\in X\)에 대하여$$\begin{align*}((h\circ g)\circ f)(x)&=h\circ g(f(x))=h(g(f(x)))\\(h\circ(g\circ f))(x)&=h((g\circ f)(x))=h(g(f(x)))\end{align*}$$이므로 모든 \(x\in X\)에 대하여 \(((h\circ g)\circ f)(x)=(h\circ(g\circ f))(x)\)이고 따라서 \((h\circ g)\circ f=h\circ(g\circ f)\)이다.

함수 \(f:\,X\,\rightarrow\,Y\)에 대하여 

(a) 함수 \(g:\,Y\,\rightarrow\,X\)가 존재해서 \(g\circ f=I_{X}\)이면 \(f:\,X\,\rightarrow\,Y\)는 단사이다. 

(b) 함수 \(h:\,Y\,\rightarrow\,X\)가 존재해서 \(f\circ h=I_{Y}\)이면 \(f:\,X\,\rightarrow\,Y\)는 전사이다.  

증명:

(a): 임의의 \(x_{1},\,x_{2}\in X\)에 대하여 \(f(x_{1})=f(x_{2})\)라고 가정하면$$x_{1}=I_{X}(x_{1})=(g\circ f)(x_{1})=g(f(x_{1}))=g(f(x_{2}))=(g\circ f)(x_{2})=I_{X}(x_{2})=x_{2}$$이므로 \(x_{1}=x_{2}\)이고 따라서 \(f:\,X\,\rightarrow\,Y\)는 단사이다. 

(b): 가정에 따라 모든 \(y\in Y\)에 대해 \(x\in X\)가 존재해서 \(x=h(y)\)이므로$$f(x)=f(h(y))=(f\circ h)(y)=I_{Y}(y)=y$$이고 따라서 \(y=f(x)\)이므로 \(f:\,X\,\rightarrow\,Y\)는 전사이다.

집합 \(X\)에서 집합 \(Y\)로의 관계 \(\mathcal{R}\), 집합 \(Y\)에서 집합 \(Z\)로의 관계 \(\mathcal{P}\)에 대해 이 두 관계의 합성(composition), 즉 \(X\)에서 \(Z\)로의 관계를 다음과 같이 정의한다.$$\mathcal{P}\circ\mathcal{R}=\{(x,\,z)\in X\times Z\,|\,\exists y\,[(x,\,y)\in\mathcal{R}\wedge(y,\,z)\in\mathcal{P}]\}$$이때 \((\mathcal{P}\circ\mathcal{R})^{-1}=\mathcal{R}^{-1}\circ\mathcal{P}^{-1}\)이고, 집합 \(Z\)에서 집합 \(W\)로의 관계 \(\mathcal{T}\)에 대하여 \(\mathcal{T}\circ(\mathcal{P}\circ\mathcal{R})=(\mathcal{T}\circ\mathcal{P})\circ\mathcal{R}\)이다.

두 전단사 \(f:\,X\,\rightarrow\,Y\), \(g:\,Y\,\rightarrow\,Z\)에 대하여 합성함수 \(g\circ f:\,X\,\rightarrow\,Z\)는 전단사이다. 한편 합성함수의 역함수 \((g\circ f)^{-1}:\,Z\,\rightarrow\,X\)는 역함수 \(g^{-1}:\,Z\,\rightarrow\,Y\), \(f^{-1}:\,Y\,\rightarrow\,X\)의 합성함수 \(f^{-1}\circ g^{-1}:\,Z\,\rightarrow\,X\)와 같다. 즉 \((g\circ f)^{-1}=f^{-1}\circ g^{-1}\)

참고자료:

집합론, You-Feng Lin, Shwu-Yeng T. Lin 저, 이흥천 옮김, 경문사