이산수학 - 함수, 함수의 상등, 전사함수, 단사함수, 합성함수, 계승함수, 바닥함수, 천장함수, 나머지 함수

1. 기본사항 

집합 $X$와 $Y$가 주어졌을 때, $X$에서 $Y$로의 함수 $f$는 다음 조건을 만족하는 관계이다.

모든 $x\in X$에 대해, 오직 하나의 $y\in Y$가 존재하여 $(x,y)\in f$를 만족한다. 이를 수식으로 표현하면 다음과 같다.

$$\mathrm{\forall }x\in X,\mathrm{\exists }!y\in Y\text{such that}(x,y)\in f$$

즉, $X$의 임의의 원소 $x$에 대해, $(x,y)\in f$를 만족하는 $y$가 $Y$에 오직 하나만 존재한다.

이를 함수 $f$로 표현하면 다음과 같이 쓸 수 있다.

$$f:X\to Y$$

그리고, $f(x)=y$라는 관계를 만족한다.

 

다음은 𝑿에서 𝒀로의 함수 𝒇에 대한 설명이다.

먼저, 𝑿와 𝒀는 각각 집합이다. 𝑿에서 𝒀로의 함수 𝒇는 다음과 같은 조건을 만족한다:

모든 𝒙가 𝑿에 속할 때, 유일한 𝒚가 𝒀에 속하여 𝒇(𝒙) = 𝒚가 성립한다. 이를 수식으로 나타내면 다음과 같다:

$$\mathrm{\forall }\mathbf{x}\in \mathbf{X},\mathrm{\exists }!\mathbf{y}\in \mathbf{Y}\text{such that}(\mathbf{x},\mathbf{y})\in \mathbf{f}$$

즉, 함수 𝒇는 𝑿와 𝒀의 관계이며, 𝒇는 𝑿의 각 원소 𝒙에 대해 𝒀의 유일한 원소 𝒚를 대응시키는 관계이다. 함수 𝒇는 다음과 같이 집합 𝑿와 𝒀의 데카르트 곱의 부분 집합으로 표현될 수 있다:

$$\mathbf{f}\subseteq \mathbf{X}\times \mathbf{Y}$$

따라서, 함수 𝒇는 𝑿와 𝒀 사이의 관계로, 𝑿의 모든 원소가 𝒀의 유일한 원소에 대응되는 특징을 가진다.

 

관련 용어를 살펴보자. 

 

𝑿와 𝒀는 집합이다. 𝑿에서 𝒀로의 함수(function) 𝒇는 모든 𝒙가 𝑿에 속할 때, 유일한 𝒚가 𝒀에 속하고 𝒇는 𝒙와 𝒚의 쌍을 만족하는 𝑿에서 𝒀로의 관계이다. 

𝒇의 정의역은 𝑿이고, 공역은 𝒀이다. 𝒇에 의해 𝒙는 𝒚의 역상이며, 𝒚는 𝒙의 상이다. 𝒇(𝑿)은 𝒇의 치역으로 정의되며, 이는 다음과 같다:

$$\{y\in Y\mid \mathrm{\forall }x\in X,y=f(x)\}$$

 

 

 

 

 

(1) 상수함수 

$$f:X\to Y,\mathrm{\forall }x\in X,f(x)=c$$

여기서 $c$는 상수

 

 

(2) 항등함수 

항등함수는 주어진 집합 $X$에서 자기 자신으로 가는 함수로 정의된다. 이 함수는 모든 입력값을 그대로 출력하는 특징을 가진다. 

$$f:X\to X,\mathrm{\forall }x\in X,f(x)=x$$

이 함수는 종종 $I_X$로 표현된다. 여기서 $I_X$는 집합 $X$의 항등함수를 의미한다.

즉, 항등함수 $f$는 입력값 $x$가 무엇이든지 항상 $x$를 그대로 반환하는 함수이다. 

 

 

(3) 함수의 상등 

함수 $\mathbf{f}:X\to Y$와 $\mathbf{g}:A\to B$가 있을 때, 다음 조건을 만족하면 $\mathbf{f}$와 $\mathbf{g}$는 '상등하다' 즉, 서로 같다. 이는 $\mathbf{f}=\mathbf{g}$로 표시한다.

1. $X=A$, $Y=B$
2. $\mathrm{\forall }x\in X$, $\mathbf{f}(x)=\mathbf{g}(x)$

이와 같은 조건을 만족할 때, 함수 $\mathbf{f}$와 $\mathbf{g}$는 '상등하다' = 서로 같다. 

 

 

 

📌 예제: 다음 관계 중 함수를 고르시오.

𝑨 = {𝟎,𝟏,𝟐} 𝑩 = {𝟑,𝟒,𝟓}

(1)𝑹 = { (𝟎,𝟑), (𝟎,𝟒),(𝟏,𝟓) }
(2)𝑺 = { (𝟏,𝟓), (𝟐,𝟒) }
(3)𝑻 = { (𝟎,𝟒), (𝟏,𝟒), (𝟐,𝟓) }

 

1. $R=\{(0,3),(0,4),(1,5)\}$:

   $R$에서는 $0$이 $3$과 $4$로 대응되므로 함수가 아니다.

2. $S=\{(1,5),(2,4)\}$:

   $S$에서는 $0$이 대응되지 않으므로 함수가 아니다.

3. $T=\{(0,4),(1,4),(2,5)\}$:

   $T$는 $0$이 $4$로, $1$이 $4$로, $2$가 $5$로 각각 단 하나의 원소에 대응되므로 함수이다.

 

📌 예제: 두 함수 𝒇와 𝒈의 정의역이 𝑿이고, 𝒇(𝒙) = 𝒙^𝟐, 𝒈(𝒙) = 𝟏일 때, 𝒇=𝒈가 되는 공집합이 아닌 𝑿를 찾으시오.

 

$f(x)=g(x)$이므로, $x^2=1$이다.

따라서, $x=\pm 1$이다.

정의역 $X$는 $\{1\}$, $\{-1\}$, $\{-1,1\}$ 중 하나이다.

 

 

2. 전사함수, 단사함수, 역함수 

 

전사함수 

 

 

함수 $f:X\to Y$가 전사함수(surjective function)라는 것은 다음과 같다,

$$\mathrm{\forall }y\in Y,\mathrm{\exists }x\in X\text{ such that }f(x)=y$$

즉, 함수 $f$는 $Y$의 모든 원소 $y$에 대해 $X$의 어떤 원소 $x$가 존재하여 $f(x)=y$가 성립함을 의미한다.

 

전사함수: 공역과 치역이 일치하는 함수

 

 

 

 

 

📌 예시: 함수 $f:\mathbb{R}\to \mathbb{R}$은 임의의 실수 $x$에 대하여 $f(x)=2x-1$이고, $g:\mathbb{R}\to \mathbb{R}$은 임의의 실수 $x$에 대하여 $g(x)=x^2$이라고 할 때,

1) 함수 $f$는 전사함수인가? 전사함수가 아니라면 반례로써 반증하시오.

2) 함수 $g$는 전사함수인가? 전사함수가 아니라면 반례로써 반증하시오.

 

✘ 풀이: 

1) 함수 $f$가 전사함수인지 확인하기 위해서는 모든 $y\in \mathbb{R}$에 대해 $y=f(x)$인 $x\in \mathbb{R}$가 존재하는지를 검토해야 한다. 

함수 $f(x)=2x-1$에 대하여,

$$y=2x-1$$

이 방정식을 $x$에 대해 풀어보면,

$$x=\frac{y+1}{2}$$

이므로, 임의의 $y\in \mathbb{R}$에 대해 $x$가 항상 존재한다. 따라서 함수 $f$는 전사함수이다.

2) 함수 $g$가 전사함수인지 확인하기 위해서는 모든 $y\in \mathbb{R}$에 대해 $y=g(x)$인 $x\in \mathbb{R}$가 존재하는지를 검토해야 한다.

함수 $g(x)=x^2$에 대하여,

$$y=x^2$$

이 방정식을 $x$에 대해 풀어보면,

$$x=\pm \sqrt{y}$$

여기서 $y$는 반드시 0 이상의 실수여야 하므로, $y\ge 0$인 경우에만 $x$가 존재한다. 따라서, $y$가 음수일 때는 $g(x)=y$인 $x$가 존재하지 않으므로 함수 $g$는 전사함수가 아니다.

예를 들어, $y=-1$인 경우,

$$-1=x^2$$

이 방정식은 실수 $x$에 대해 해를 가지지 않는다. 따라서 $g$는 전사함수가 아니다.

 

 

 

 

 

단사함수 

 

함수 $f:X\to Y$가 단사함수(injective function)임을 다음과 같이 정의할 수 있다.

$$\mathrm{\forall }{x}_1,\mathrm{\forall }{x}_2\in X,f(x_1)=f(x_2)\Rightarrow x_1=x_2$$

이는 다음과 같이도 표현할 수 있다.

$$\mathrm{\forall }{x}_1,\mathrm{\forall }{x}_2\in X,x_1\ne x_2\Rightarrow f(x_1)\ne f(x_2)$$

즉, 함수 $f$가 단사함수이기 위한 필요충분조건은 서로 다른 입력이 서로 다른 출력을 갖는다는 것이다.

 

 

 

 

 

 

 

 

전단사함수

 

함수 $\mathcal{f}:X\to Y$가 전단사 함수(bijective function)라는 것은 다음과 같다:

$$\mathcal{f}\text{가 전사함수}\wedge \mathcal{f}\text{가 단사함수}$$

즉, 어떤 함수 $\mathcal{f}$가 전단사 함수인지 확인하기 위해서는 그 함수가 전사함수(surjective function)이며 동시에 단사함수(injective function)이어야 한다. 전사함수란 함수 $\mathcal{f}$의 공역 $Y$의 모든 원소가 정의역 $X$의 원소들과 연결되는 것을 의미한다. 단사함수란 서로 다른 정의역 $X$의 원소들이 서로 다른 공역 $Y$의 원소들과 연결되는 것을 의미한다.

정리하면, $\mathcal{f}$가 전단사 함수임을 보이기 위해서는 다음 두 조건을 만족해야 한다:
1. $\mathrm{\forall }y\in Y,\mathrm{\exists }x\in X\text{ such that }\mathcal{f}(x)=y$
2. $\mathrm{\forall }{x}_1,x_2\in X,\mathcal{f}(x_1)=\mathcal{f}(x_2)⟹x_1=x_2$

 

 

 

📌 예제: 다음 함수의 종류를 말하시오. 

 

 

 

 

 

✘ 풀이: 

1. 첫번째 함수 :
   - 함수 $f:X\to Y$에서 $X=\{1,2,3\}$와 $Y=\{a,b,c,d\}$이다.
   - 이 함수는 정의역의 원소 $1,2,3$ 각각이 공역의 원소 $a,b$와 연결되어 있다.
   - $f(1)=a$, $f(2)=b$, $f(3)=c$로 주어져 있다.
   - 공역 $Y$의 모든 원소가 정의역 $X$의 원소와 대응되지 않으므로 전사함수는 아니다.
   - 또한, 정의역 $X$의 서로 다른 원소가 공역 $Y$의 서로 다른 원소와 대응되므로 단사함수이다.
   - 결론적으로, 이 함수는 단사함수(injective function)이다.

2. 두 번째 함수:
   - 함수 $f:X\to Y$에서 $X=\{1,2,3\}$와 $Y=\{a,b\}$이다.
   - 이 함수는 정의역의 원소 $1,2,3$ 각각이 공역의 원소 $a,b$와 연결되어 있다.
   - $f(1)=a$, $f(2)=a$, $f(3)=b$로 주어져 있다.
   - 공역 $Y$의 모든 원소가 정의역 $X$의 원소와 대응되므로 전사함수이다.
   - 그러나 정의역 $X$의 서로 다른 원소 $1$과 $2$가 동일한 공역 $Y$의 원소 $a$와 대응되므로 단사함수는 아니다.
   - 결론적으로, 이 함수는 전사함수(surjective function)이다.

3. 세 번째 함수:
   - 함수 $f:X\to Y$에서 $X=\{1,2,3\}$와 $Y=\{a,b,c\}$이다.
   - 이 함수는 정의역의 원소 $1,2,3$ 각각이 공역의 원소 $a,b,c$와 연결되어 있다.
   - $f(1)=a$, $f(2)=b$, $f(3)=c$로 주어져 있다.
   - 공역 $Y$의 모든 원소가 정의역 $X$의 원소와 대응되므로 전사함수이다.
   - 또한 정의역 $X$의 서로 다른 원소가 공역 $Y$의 서로 다른 원소와 대응되므로 단사함수이다.
   - 결론적으로, 이 함수는 전단사함수(bijective function)이다.

따라서, 각 함수의 종류는 다음과 같다:
1. 단사함수 (injective function)
2. 전사함수 (surjective function)
3. 전단사함수 (bijective function)

 

 

 

📌 예제: 함수 $f$의 종류를 말하시오. 함수 $f:\mathbb{Z}\to \mathbb{Z}$ ($\mathbb{Z}$: 정수집합) ∀ $x\in \mathbb{Z}$, $f(x)=2x$

✘ 풀이:

$f(x)=2x$

$x\in \mathbb{Z}=\{\dots ,-4,-2,0,2,4,\dots \}\ne \mathbb{Z}$

∴ $f$는 전사함수가 아님

만약 $x_1,x_2$가 서로 다른 정수 ($x_1\ne x_2$)이면,

$f(x_1)=2x_1\ne 2x_2=f(x_2)$

∴ $f$는 단사함수임

 

 

역함수 

 

함수 $f:X\to Y$가 전단사 함수일 때, $f$의 역관계 $f^{-1}$를 $f$의 역함수(inverse function)라 한다. $f$가 전단사 함수이기 때문에 $f$는 일대일 대응 관계를 가지며, 모든 $y\in Y$에 대해 유일한 $x\in X$가 존재하여 $f(x)=y$를 만족한다. 따라서 $f^{-1}(y)=x$를 정의할 수 있다.

이를 식으로 표현하면 다음과 같다:

$$f(x)=y\text{이면}{f}^{-1}(y)=x$$

즉, $f$가 $X$의 각 원소를 $Y$의 원소에 대응시키는 함수라면, $f^{-1}$는 $Y$의 각 원소를 $X$의 원소에 대응시키는 함수이다.

행렬의 경우에도 유사한 개념이 적용된다. $A$가 정사각행렬이고 가역 행렬일 때, $A$의 역행렬 $A^{-1}$은 $A$를 곱했을 때 단위행렬을 생성하는 행렬이다.

즉,

$$A\cdot A^{-1}=I\text{및}{A}^{-1}\cdot A=I$$

여기서 $I$는 단위행렬이다.

행렬 $A$가 다음과 같은 경우를 생각해보자:

$$A=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$$

$A$의 역행렬 $A^{-1}$는 다음과 같이 계산된다:

$$A^{-1}=\frac{1}{ad-bc}\left(\begin{array}{cc}d& -b\\ -c& a\end{array}\right)$$

단, $ad-bc\ne 0$인 경우에만 $A^{-1}$가 존재한다. 이를 행렬의 행렬식(determinant)이라 하며, $|A|=ad-bc$로 나타낸다. 행렬식이 0이 아닌 경우에만 역행렬이 존재하게 된다.

결론적으로, 함수의 역함수와 행렬의 역행렬은 모두 원래의 관계를 되돌릴 수 있는 함수 또는 행렬로 정의된다.

 

 

 

📌 예제:  함수 $f:\mathbb{R}\to \mathbb{R},f(x)=x+3$ 일 때 $f^{-1}$를 구하시오.

✘ 풀이: 

(1) 전단사 함수 확인:

함수 $f$의 치역은 다음과 같다:
$$f(\mathbb{R})=f(x)=x+3=\mathbb{R}$$

$x_1\ne x_2$ 일 때,
$$x_1+3\ne x_2+3$$
따라서,
$$f(x_1)\ne f(x_2)$$

(2) 역함수 $f^{-1}$ 구하기:

역함수 $f^{-1}:\mathbb{R}\to \mathbb{R}$ 에서, $x=f(y)=y+3$ 이다. 

따라서,
$$y=x-3$$
결론적으로,
$$f^{-1}(x)=x-3$$

 

 

합성함수 

 

 

$X,Y,Y^{\prime },Z$는 집합이고, $Y^{\prime }$는 $Y$의 부분집합 $Y^{\prime }\subset Y$이다. 두 함수 $f:X\to Y^{\prime }$와 $g:Y\to Z$에 대해 다음과 같이 정의되는 함수 $g\circ f:X\to Z$를 $f$와 $g$의 합성함수(composition function)라고 한다.

모든 $x\in X$에 대해, $(g\circ f)(x)\equiv g(f(x))$이다.

 

 

 

 

전사함수의 합성함수 

두 함수 $f:X\to Y$, $g:Y\to Z$가 전사함수  
⇒ $g\circ f:X\to Z$도 전사함수

 

단사함수의 합성함수 

두 함수 $f:X\to Y$, $g:Y\to Z$가 단사함수  
⇒ $g\circ f:X\to Z$도 단사함수

 

 

합성함수의 성질 

1. $f\circ g\ne g\circ f$
2. $(f\circ g)\circ h=f\circ (g\circ h)$

 

항등함수와 합성함수 

함수 $f:X\to Y$

항등함수 $I_X:X\to X$  
항등함수 $I_Y:Y\to Y$

$$\begin{array}{rl}& f=f\circ I_X\\ & =I_Y\circ f\end{array}$$

 

역함수와 합성함수 

전단사함수 $f:X\to Y$  
전단사함수 $g:Y\to Z$

1. $f^{-1}\circ f=I_X$, $f\circ f^{-1}=I_Y$
2. $(g\circ f{)}^{-1}=f^{-1}\circ g^{-1}$

 



 

3. 함수의 종류 

 

(1) 계승함수 

$n$ : 음이 아닌 정수

$$n!=\{\begin{array}{ll}1& (n=0)\\ \prod _{k=1}^{n}k& (n\ge 1)\end{array}$$

$$=1\times 2\times \cdots \times n$$

$$=n\times (n-1)!$$

 

 

(2) 바닥함수와 천장함수 

 

(1) 바닥함수 (floor function)

실수 $x$에 대해, $x$보다 작거나 같으면서 가장 큰 정수를 구하는 함수

$$\lfloor x\rfloor =max\{m\in \mathbb{Z}\mid m\le x\}$$

[예]

1. $\lfloor 2.6\rfloor =2$
2. $\lfloor -2.6\rfloor =-3$

 

 

(2) 천장함수 (ceiling function)

실수 $x$에 대해, $x$보다 크거나 같으면서 가장 작은 정수를 구하는 함수

$$\lceil x\rceil =min\{n\in \mathbb{Z}\mid x\le n\}$$

[예]

1. $\lceil 2.6\rceil =3$
2. $\lceil -2.6\rceil =-2$

 

 

 

(3) 나머지 함수 

 

정수 $n$과 양의 정수 $m$에 대해 $n$을 $m$으로 나누었을 때의 나머지를 구하는 함수를 나머지 함수(modulo function) [모듈로 함수/mod 함수] $n\mathrm{mod}m$으로 표기함 

※ 두 정수 $n$, $m(m\ne 0)$에 대해

$$n\mathrm{mod}m=n-m\lfloor \frac{n}{m}\rfloor$$

 

 

📌 예제: 다음 함수의 값을 구하시오

(1) 𝟓𝒎𝒐𝒅𝟑
(2) 𝟓𝒎𝒐𝒅(−𝟑)

(3) −𝟓𝒎𝒐𝒅 −𝟑

 

✘ 풀이: 

 

 

1. $5\mathrm{mod}3$

$$5\mathrm{mod}3=5-3\lfloor \frac{5}{3}\rfloor =5-3\times 1=2$$

2. $5\mathrm{mod}(-3)$

$$5\mathrm{mod}(-3)=5-(-3)\lfloor \frac{5}{-3}\rfloor =5-(-3)\times (-2)=5-6=-1$$

3. $-5\mathrm{mod}(-3)$

$$-5\mathrm{mod}(-3)=-5-(-3)\lfloor \frac{-5}{-3}\rfloor =-5-(-3)\times 1=-5+3=-2$$

따라서,

(1) $5\mathrm{mod}3=2$

(2) $5\mathrm{mod}(-3)=-1$

(3) $-5\mathrm{mod}(-3)=-2$

 

 

 

---

 

참고자료: 이산수학 | 손진곤 (지은이) 한국방송통신대학교출판문화원