이산수학 8. 함수

1. 함수의 개념

• 함수(function, \(f : A \rightarrow B\)): 집합 \(A\)에서 집합 \(B\)로 가는 관계가 성립할 때, 집합 \(A\)의 원소 \(a\)에 대하여 집합 \(B\)의 원소 \(b\) 하나가 대응되는 관계
  • 원상(preimage): \(b\)와 대응하는 \(a\)
  • 상(image): \(a\)와 대응하는 \(b\)
  • 정의역(domain, \(\text{dom}(f)\)): 원상의 집합, \(A\)
  • 공역(codomain, \(\text{codom}(f)\)): 상이 포함된 집합, \(B\)
  • 치역(range, \(\text{ran}(f)\)): 상의 집합, \(B\)의 부분집합, \(\text{ran}(f) = \{f(a) \mid a \in A\}\)
  • 관계 vs 함수
    • 관계: 정의역의 어떤 원소는 공역의 원소와 전혀 대응하지 않거나 둘 이상의 원소와 대응 가능
    • 함수: 정의역의 모든 원소는 공역의 원소 하나와 반드시 대응

2. 함수의 성질

• 단사 함수(injective function): \(f: X \rightarrow Y\)일 때, \(x_1, x_2 \in X\)에 대하여 \(x_1 \neq x_2\)이면 \(f(x_1) \neq f(x_2)\)
  • \(\vert \text{dom}(f) \vert \le \vert \text{codom}f(x)\vert\), \(\vert \text{ran}(f) \vert \le \vert \text{codom}f(x)\vert\), \(\vert \text{dom}(f) \vert = \vert \text{ran}f(x)\vert\)
• 전사 함수(surjective function): \(f: X \rightarrow Y\)일 때, 모든 공역 원소 \(y \in Y\)에 대하여 \(f(x) = y\)인 정의역 원소 \(x \in X\)가 적어도 하나 이상 존재
  • \(\vert \text{dom}(f) \vert \ge \vert \text{codom}f(x)\vert\), \(\vert \text{ran}(f) \vert = \vert \text{codom}f(x)\vert\)
• 전단사 함수(bijective function): 단사 함수이면서 전사 함수인 함수
  • \(\vert \text{dom}(f) \vert = \vert \text{codom}f(x)\vert\), \(\vert \text{ran}(f) \vert = \vert \text{codom}f(x)\vert\)

3. 합성 함수

• 함성 함수(composite function, \(g \circ f\)): \(f: A \rightarrow B\)와 \(g: B \rightarrow C\)가 있을 때, \(g \circ f = g(f(x))\)
  • 결합법칙은 성립하나 교환법칙은 성립하지 않음
• 합성 함수의 성질
  • \(f\)와 \(g\)가 단사 함수면 \(g \circ f\)​도 단사 함수
  • \(f\)와 \(g\)가 전사 함수면 \(g \circ f\)도 전사 함수
  • \(f\)와 \(g\)가 전단사 함수면 \(g \circ f\)도 전단사 함수
  • \(g \circ f\)가 단사 함수이면 \(f\)도 단사 함수
  • \(g \circ f\)가 전사 함수이면 \(f\)도 전사 함수
  • \(g \circ f\)가 전단사 함수이면 \(f\)는 단사 함수, \(g\)는 전사 함수

4. 함수의 종류

• 항등 함수(identity function, \(I_A\)): \(f: A \rightarrow A\)가 \(f(a) = a\)

  • 단사, 전사, 전단사 함수
  • \[f \circ I_A = I_B \circ f = f\]

• 역 함수(inverse function, \(f^{-1}\)): 전단사 함수 \(f: A \rightarrow B\)에 대해 \(B \rightarrow A\)로 대응되는 함수

  • 가역함수(invertible function): 전단사 함수로 역 함수가 존재하는 함수

• 항등 함수와 역 함수의 관계

  • \(f^{-1} \circ f = I_A\), \(f \circ f^{-1} = I_B\)

• 합성 함수의 역함수: \((g \circ f)^{-1} = f^{-1} \circ g^{-1}\)

• 상수 함수(constant function): 정의역의 모든 원소가 공역의 원소 하나에만 대응하는 함수

• 특성 함수(characteristic function, \(f_A\)): 전체집합의 부분집합인 \(A\)에 대해 다음을 만족하는 함수

  \[f_A(x) = \begin{cases} 1, &x \in A\\ 0, &x \notin A\\ \end{cases}\]
• 바닥 함수(floor function, \(\lfloor x \rfloor\)), 최대 정수 함수: \(x\)보다 작거나 같은 정수 중 가장 큰 정수를 구하는 함수
  • 내림
• 천정 함수(ceiling function, \(\lceil x \rceil\)), 최소 정수 함수: \(x\)보다 크거나 같은 정수 중 가장 작은 정수를 구하는 함수