[Discrete Mathematics] 함수(function)의 정의와 성질을 통한 분류

---

함수의 정의

 

함수는 어떤 집합의 각 원소를 다른 어떤 집합의 각 원소에 유일하게 대응시키는 관계를 말한다. 예를 들어 $ X $ 와 $ Y $ 가 집합일 때 $ X $ 에서 $ Y $ 로의 함수 $ f $ 는 $ f : X \to Y $ 로 나타낸다. 이는 카테시안 곱 $ X \times Y $ 의 부분집합으로 정의되며 카테시안 곱은 $ \{ (x,y) \mid x \in X, y \in Y \} $ 이다. 각 $ x \in X $ 에 대해 정확히 하나의 $ y \in Y $ 가 존재하여 $ (x,y) \in f $ 를 만족하는 성질을 가진다. 이를 $ f(x) = y $ 라 표기한다.

이때 집합 $ X $ 를 정의역(domain)이라 하고, 집합 $ Y $ 를 공역(codomain)이라 한다. $ f $ 의 치역(range)은 $ \{y \mid (x, y) \in f \} $ 로 정의된다.

만약 정의역의 원소가 공역에 대응되지 않거나, 두 개 이상의 공역에 대응된다면, 함수가 아니다.

이러한 함수를 그래프로 나타낼 때에는 일반적으로 가로축에 정의역을, 세로축에 공역을 놓고 그린다. 

 

---

단사 함수 (Injection; Injective Function)

 

출처: https://ko.wikipedia.org/wiki/

일대일 함수(one-to-one function)라고도 한다. $ f : X \to Y $ 가 $ \forall x_1, x_2 \in X $ 에 대해 $ f(x_1) = f(x_2) $ 일 때 $ x_1 = x_2 $ 이 성립하면 함수 $ f $ 를 단사 함수라 한다. 함수 그림으로 확인한다면 공역의 각 요소를 최대 하나의 화살표만 가리킬 수 있는 함수인 것이다.

예를 들어 $ f = \{ (1, b), (2, a), (3, c) \} $ 는 단사 함수이고, $ f = \{ (1, b), (2, b), (3, c) \} $ 는 단사 함수가 아니다.

 

---

전사 함수 (Subjection; Subjective Function)

 

출처: https://ko.wikipedia.org/wiki/

위로의 함수(onto function)라고도 한다. 치역과 공역이 같은 함수를 전사 함수라 한다. 함수 그림으로 확인한다면 화살표가 가리키지 않는 값이 없는 함수인 것이다.

예를 들어 $ X = \{ 1, 2, 3 \} $ 이고 $ Y = \{a, b, c\} $ 일 때, $ f = \{ (1, a), (2, b), (3, c) \} $ 는 전사 함수이지만, $ f = \{ (1, a), (2, a), (3, c) \} $ 는 전사 함수가 아니다.

 

---

전단사 함수 (Bijection; Bijective Function)

 

출처: https://ko.wikipedia.org/wiki/

일대일 대응(one-to-one correspondence)이라고도 한다. 단사 함수이면서 전사 함수인 함수를 말한다. 즉 치역과 공역이 동일하면서 입력값이 다르다면 출력값이 항상 다른 함수를 말한다. 이때문에 어떤 전단사 함수의 정의역과 치역이 유한 집합이라면 $ | X | = | Y | $ 이다. 즉 두 집합은 같은 원소 개수(same cadinality)를 가진다.

예를 들어 $ X = \{ 1, 2, 3 \} $ 이고 $ Y = \{a, b, c, d\} $ 인 함수  $ f $ 는 전단사 함수일 수 없다.

 

---

역함수 (Inverse Function)

 

정의역과 치역을 서로 뒤바꾸어 얻는 함수이다. 즉 원래의 입력값이 출력값이 되고, 원래의 출력값이 입력값이 된다. 이는 기호로 $ f^{-1} $ 이라 표시한다.

역함수를 가질 필요충분조건은 전단사 함수이다. 생각해보면 만약 단사 함수가 아니라면 정의역과 치역이 바뀌었을 때 하나의 입력값에서 두 개 이상의 출력값이 나올 수 있어 함수가 아니다. 또 전사 함수가 아니라면 정의역과 치역이 바뀌었을 때 출력값이 없는 입력값이 존재할 수 있어 함수가 아니다. 따라서 정의역과 치역이 바뀌었을 때 하나의 입력값에 하나의 출력값을 보장하고, 모든 입력값에 출력값을 보장하기 위해서는 해당 함수가 전단사 함수여야 한다.

함수 그림으로 표현하면 화살표 방향이 반대가 되면 된다.

 

---

합성 함수 (Composite Function)

 

출처: https://ko.wikipedia.org/wiki/

함수 $ g : X \to Y $ 와 함수 $ f : Y \to Z $ 가 존재할 때, $ f \circ g $ 는 $ f $ 와 $ g $ 의 합성을 나타내며 이는 $ f \circ g = f \left( g (x) \right) $ 로 정의된다.

 

---

이항 연산자와 단항 연산자

 

연산자를 함수의 특수한 경우로 생각해볼 수 있다.

$ X \times X $ 에서 $ X $ 로 가는 함수를 집합 $ X $ 에 대한 이항 연산자(binary operator)라 한다. 이항 연산자가 아니라 이진 연산자라고도 한다.

예를 들어 $ X = \{ 1, 2, \dots \} $ 일 때, $ x, y \in X $ 에 대해 $ f(x, y) = x + y $ 로 정의하면 $ f $ 는 $ X $ 에 대한 이항 연산자다.

반면 $ X $ 에서 $ X $ 로 가는 함수를 집합 $ X $ 에 대한 단항 연산자(unary operator)라 한다.

예를 들어 $ U $ 가 전체 집합일 때, $ X \in \mathcal{P}(U) $ 에 대해 $ f (X) = \bar{X} $ 로 정의하면, $ f $ 는 $ \mathcal{P}(U) $ 에 대한 단항 연산자이다.