전사 함수

전사 함수(surjection)는 함수의 일종으로, 공역과 치역이 같은 함수를 일컫는 단어이다. 다음은 수식으로 나타낸 정의다.

함수 [math]\displaystyle{ f:X\to Y }[/math]에 대해,

1. [math]\displaystyle{ \forall y\in Y,\,\exists x\in X\text{ s.t. }f\left(x\right)=y }[/math]
2. [math]\displaystyle{ f\left(X\right)=Y }[/math]

이중 하나를 만족하면 전사 함수가 된다. 1번 정의와 2번 정의는 동치이므로 어느 쪽을 보여도 상관없다.

성질

두 함수 [math]\displaystyle{ f:X\to Y,\,g:Y\to Z }[/math]가 주어졌다 하자.

1. [math]\displaystyle{ f }[/math]와 [math]\displaystyle{ g }[/math]가 둘 다 전사라면 [math]\displaystyle{ g\circ f }[/math]도 전사 함수이다.
   • [math]\displaystyle{ \left(g\circ f\right)\left(X\right)=g\left(f\left(X\right)\right)=g\left(Y\right)=Z }[/math].
2. 역으로, [math]\displaystyle{ g\circ f }[/math]가 전사 함수라면, [math]\displaystyle{ g }[/math]는 전사 함수이다. [math]\displaystyle{ f }[/math]는 전사 함수일 필요는 없다.
   • [math]\displaystyle{ g }[/math]가 전사 함수가 아니라 가정하자. 그럼 [math]\displaystyle{ \left(g\circ f\right)\left(X\right)=g\left(f\left(X\right)\right) }[/math]이고, [math]\displaystyle{ f\left(X\right)\subseteq Y,\,g\left(Y\right)\subsetneq Z }[/math]이므로, [math]\displaystyle{ g\left(f\left(X\right)\right)\subsetneq Z }[/math]가 된다. 따라서, [math]\displaystyle{ g\circ f }[/math]는 전사 함수가 아니다.
3. [math]\displaystyle{ f }[/math]가 전사 함수이면, [math]\displaystyle{ \left|X\right|\geq\left|Y\right| }[/math]이다 (집합의 크기가 무한일 수도 있음에 주의).
   • [math]\displaystyle{ \left|X\right|\lt \left|Y\right| }[/math]라 가정하면 [math]\displaystyle{ f }[/math]가 전사 함수가 될 수 없음을 쉽게 보일 수 있다.
4. [math]\displaystyle{ f }[/math]가 전사 함수이고 [math]\displaystyle{ \left|X\right|=\left|Y\right|\lt \infty }[/math]라 가정하자. 그럼 [math]\displaystyle{ f }[/math]는 단사 함수이다.
   • [math]\displaystyle{ f }[/math]가 단사 함수가 아니라고 가정하자. 그럼, 적당한 [math]\displaystyle{ x_i,\,x_j\in X,\,y\in Y }[/math]에 대해 [math]\displaystyle{ f\left(x_i\right)=f\left(x_j\right)=y }[/math]이다. 그러면 [math]\displaystyle{ \left|f\left(X\right)\right|\leq\left|X\right|-1\lt \left|X\right| }[/math]이 되어 [math]\displaystyle{ f }[/math]가 전사 함수라는 사실에 모순이다. 따라서, [math]\displaystyle{ f }[/math]는 단사 함수이고, 곧 일대일 대응 함수이다.

예시

• [math]\displaystyle{ f:\mathbb{R}\to\mathbb{R},\,f\left(x\right)=x }[/math]는 전사 함수이다.
• [math]\displaystyle{ f:\mathbb{R}\to\mathbb{R},\,f\left(x\right)=x^2 }[/math]는 음의 값을 가질 수 없으므로 전사 함수가 아니다. 하지만, 공역을 [math]\displaystyle{ \mathbb{R}^+\cup\left\{0\right\} }[/math]로 제한하면 전사 함수가 된다.

같이 보기

• 단사 함수
• 전단사 함수