06. Relations and Functions

1. Relation

  관계(Relation)는 두 집합 사이의 연결을 나타내는 개념이다. 함수와 달리 제한이 없어서, 정의역의 하나의 원소가 공역의 여러 원소와 연결될 수 있고, 아예 연결되지 않아도 된다. 수학적으로는 두 집합의 Cartesian product의 부분집합으로 정의한다.

        R⊆A×B

 

예를 들어 학생-수강 관계는 다음과 같이 표현할 수 있다.

R={⟨Aisha, Ec10⟩, ⟨Aisha, Cs20⟩, ⟨Ben, Cs20⟩}

 

Aisha가 두 과목과 연결되어 있어도 전혀 문제없다. 이것이 Relation과 Function의 핵심적인 차이다.

 

Inverse Relation

 관계 R⊆A×B의 역관계(Inverse Relation)는 쌍의 순서를 뒤집은 것이다. 모든 관계는 역관계를 가진다.

R−1={⟨y,x⟩:⟨x,y⟩∈R}⊆B×A

 

위의 예시에서 역관계는 "어떤 과목에 누가 수강 중인가"를 나타낸다. ⟨Cs20, Aisha⟩, ⟨Cs20, Ben⟩처럼 방향이 반대가 된다.

 

---

2. Function

  함수(Function)는 Relation의 특수한 경우다. 정의역의 각 원소가 공역의 원소 중 정확히 하나에만 연결되어야 한다는 조건이 추가된다.

f:A→B⇔∀x∈A, ∃! y∈B s.t. ⟨x,y⟩∈f

 

• Domain (정의역) A : 입력값들의 집합
• Codomain (공역) B : 가능한 출력값들의 집합
• Image (치역) f[A]⊆B : 실제로 출력된 값들의 집합. 치역은 공역의 부분집합이다.

 

  치역과 공역을 혼동하기 쉽다. 예를 들어 f:Z→Z, f(n)=2n에서 공역은 Z 전체이지만, 실제로 출력되는 값은 짝수뿐이므로 치역은 짝수 전체다.

 

Partial Function

  정의역의 일부 원소에서만 정의된 관계를 부분함수(Partial Function)라고 한다.

∃A′⊆A s.t. f:A′→B

 

예를 들어 f(x) = 1 / x는 f:R→R로 정의하면 x = 0에서 값이 존재하지 않으므로 부분함수다. f:R−{0}→R 로 정의역을 좁히면 완전한 함수가 된다.

 

---

3. 함수의 종류

Injective Function (단사함수 / One-to-one)

  서로 다른 입력은 반드시 서로 다른 출력을 가지는 함수다. 공역에서 두 개 이상의 화살표가 같은 원소를 가리키는 일이 없다.

x1 !=x2 ⇒f(x1) != f(x2)

∣A∣≤∣B∣

 

치역이 공역과 같지 않아도 된다. 즉 공역 중 연결되지 않은 원소가 있어도 단사함수일 수 있다.

예) f(n) = n+1, f(n) = 2n

 

역함수의 존재 조건

 

  모든 함수는 역관계를 가지지만, 역관계가 함수가 되려면 원래 함수가 단사함수여야 한다. 단, 이때 역함수의 정의역은 공역 B 전체가 아니라 치역 f[A]로 한정해야 한다.

f^{-1}: f[A] -> A

 

예를 들어 f:Z→Z, f(n)=2n에서 f^{-1}를 Z 전체에 정의하려 하면, 홀수 y에 대해 f^{-1}(y) = y/2가 정수가 아니므로 함수가 될 수 없다. 치역인 짝수 전체로 정의역을 한정해야 비로소 역함수가 성립한다.

 

Surjective Function (전사함수 / Onto)

  치역과 공역이 같은 함수다. 공역의 모든 원소가 적어도 하나의 입력과 연결된다.

∀y∈B, ∃x∈A s.t. f(x)=y

∣A∣≥∣B∣

 

Bijective Function (전단사함수 / One-to-one Correspondence)

  단사함수이면서 동시에 전사함수인 경우다. 정의역과 공역 사이에 완전한 일대일 대응이 성립한다.

∀y∈B, ∃! x∈A s.t. f(x)=y

∣A∣=∣B∣

 

전단사함수가 존재하면 역함수 f^{-1}도 존재하며, f^{-1} 역시 전단사함수다.

 

 전단사함수는 무한 집합의 크기를 비교하는 데 쓰인다. 두 집합 사이에 전단사함수가 존재한다는 것은 정의역의 원소와 공역의 원소가 남거나 모자람 없이 정확히 일대일로 대응된다는 의미이므로, 두 집합의 크기가 같다고 정의할 수 있다.

 

예) f:R→R, f(x)=2x → Bijective ✓
예) :Z→Z, f(x)=2x → Not bijective. 홀수가 치역에 없으므로 전사함수가 아니다.

 

---

4. 한눈에 보기

종류	조건	크기 관계	역함수
Injective	다른 입력 → 다른 출력	∥A∥≤∥B∥	치역으로 한정 시 존재
Surjective	치역 = 공역	∥A∥≥∥B∥	보장 안 됨
Bijective	Injective + Surjective	∥A∥=∥B∥	존재

 

---

5. Multi-argument Function

  인자가 여러 개인 함수도 결국 튜플 하나를 입력받는 일반 함수로 볼 수 있다. 예를 들어 덧셈 add(1, 2) = 3은 정수 쌍 (1, 2)를 입력받아 정수 3을 출력하는 함수다.

add:Z×Z→Z

 

일반적으로 k개의 인자를 받는 함수는 다음과 같이 쓴다.

f:X1​×X2​×⋯×Xk​→Y

 

  표기 편의상 f(⟨a,b⟩)=c 대신 f(a,b)=c로 쓰는 것이 일반적이다. 개념적으로는 특별한 것이 없고, 도메인이 Cartesian product인 일반 함수다.