Functions & Mappings

1. Overview

함수 및 매핑(Functions & Mappings, FAM)은 입력 집합의 각 원소를 출력 집합의 유일한 원소에 대응시키는 논리적 장치에 대해 다룹니다.

컴퓨터 과학에서 함수는 단순한 계산 식을 넘어, 데이터 변환의 규격이자 프로그램의 가장 작은 실행 단위입니다. 학습자는 함수의 핵심 성질인 일대일 대응(Bijection), 서로 다른 함수를 연결하는 함수 합성(Composition), 그리고 유한 집합의 크기를 비교하는 **비둘기집 원리(Pigeonhole Principle)**의 수학적 역학을 배웁니다. 이를 통해 알고리즘의 복잡도를 정의하고, 함수형 프로그래밍에서의 부작용 없는 순수 함수(Pure Function) 설계를 위한 엄밀한 논리를 확보합니다.

2. Scope & Boundaries

In-Scope

• Function Types: 단사(Injective), 전사(Surjective), 전단사(Bijective) 함수의 정의 및 판별 물리
• Composition & Inverses: 합성 함수의 역학 및 역함수의 존재 조건(가역성)
• Special Mappings: 항등 함수, 상수 함수 및 바닥/천장 함수(Floor/Ceiling)의 특징
• Combinatorial Foundations: 전단사 함수를 통한 두 집합 간의 크기(Cardinality) 동등성 증명

Out-of-Scope

• 연속적인 실함수의 미분 및 적분 (해석학 영역)
• 프로그래밍 언어의 특정 '람다' 문법 (05-04 FPL 영역으로 위임)

Boundaries

• FAM vs. Calculus: 미적분학이 '연속적인 변화'를 다룬다면, FAM은 '불연속적인 원소 간의 대응 무결성'과 그로 인한 논리적 사상(Mapping)에 집중합니다.

3. Counterexample

• 단순히 "입력을 받아 출력을 내놓는 코드 블록"을 이해하는 것은 FAM 학습이 아닙니다. 왜 특정 해시 함수가 **단사 함수(Injection)**가 아니면 충돌이 물리적으로 발생할 수밖에 없는지 그 치역의 겹침을 수학적으로 설명할 수 있어야 하고, 역함수가 존재하지 않는 연산에서 데이터 복구가 왜 논리적으로 불가능한지 입증할 수 있어야 합니다.

4. Prerequisites

• 집합론 및 관계 (Basic): 집합의 정의와 데카르트 곱 개념 이해가 필수입니다. (01-01 STR)

5. Learning Map

1. Rule of Correspondence: 함수가 되기 위한 조건인 '정의역의 모든 원소가 하나의 공역 원소와 연결됨'을 이해합니다.
2. Structural Properties: 대응의 밀도와 겹침 정도에 따라 함수의 성질을 분류합니다.
3. Chain of Transformations: 여러 개의 대응 규칙을 유기적으로 결합하여 복합적인 데이터 흐름을 설계합니다.
4. Abstract Cardinality: 함수를 자로 삼아 무한하거나 방대한 집합의 크기를 논리적으로 비교합니다.

6. Learning Topics

Basic

Core: 함수의 정의와 대응 물리 (Function Foundations)

• Why to Learn: 유효하지 않은 대응으로 인한 런타임 오류(undefined 등)를 논리적으로 예방하기 위함입니다.
• What to Learn:
  • 정의역(Domain), 공역(Codomain), 치역(Range)의 물리적 구분
  • 함수가 될 수 없는 대응: '하나의 입력에 두 개의 출력' 혹은 '대응되지 않는 입력'의 모순
  • 상(Image)과 역상(Pre-image)의 개념
• How to Learn:
  • 사용자 ID 집합에서 전화번호 집합으로의 대응이 함수인지 가계(Relation)인지 판별하는 실습
  • 바닥 함수($\lfloor x \rfloor$)와 천장 함수($\lceil x \rceil$)가 소수점 데이터를 어떻게 정수 그리드에 고정(Gridding)하는지 시각화
• Implement: 데이터 유효성 검사 로직을 함수적 매핑 조건으로 정형화한 모듈

Recommended

Core: 단사, 전사, 전단사의 성질 (Transformation Types)

• Why to Learn: 데이터의 유실 없는 전달(단사)과 공간의 완전한 점유(전사) 가능성을 판단하기 위해서입니다.
• What to Learn:
  • 일대일 함수(Injection): 입력이 다르면 출력이 반드시 다른 물리적 보장
  • 위로의 함수(Surjection): 공역의 모든 원소가 입력과 연결되는 상태
  • 일대일 대응(Bijection): 역함수가 존재할 수 있는 유일한 동형 전이 체계
• How to Learn:
  • 암호화 알고리즘이 왜 '전단사 함수'여야만 복호화가 가능한지 논리적 증명 시도
  • 해시 테이블의 크기($n$)와 데이터 개수($m$)의 관계에서 전사가 깨지는 시점 관찰
• Implement: 두 리스트 간의 전단사 여부를 확인하는 자동 매핑 검증기

Practical

Core: 함수 합성와 가역성 (Composition & Invertibility)

• Why to Learn: 복잡한 비즈니스 로직을 작은 함수의 결합으로 분해하고, 필요 시 원래 상태로 복원하기 위함입니다.
• What to Learn:
  • 합성 함수 ($f \circ g$): 중간 단계의 치역이 다음 단계의 정의역에 포함되어야 하는 물리적 제약
  • 결합법칙의 성립과 교환법칙의 불성립에 따른 데이터 처리 순서의 중요성
  • 역함수 ($f^{-1}$): 연산의 방향을 물리적으로 되돌리는 논리
• How to Learn:
  • 데이터 필터링 -> 변환 -> 집계로 이어지는 파이프라인을 함수 합성 기법으로 설계
  • 압축-해제 프로세스에서 역함수 관계가 성립하지 않을 때 발생하는 데이터 오염 사례 분석
• Implement: 고차 함수(Higher-order Function)를 활용한 재사용 가능한 로직 합성 엔진

Advanced

Core: 비둘기집 원리와 크기 비교 (Advanced Cardinality)

• Why to Learn: 시스템의 한계(용량부족 등)를 수학적으로 미리 예측하고 최악의 시나리오를 대비하기 위해서입니다.
• What to Learn:
  • 비둘기집 원리: $n$개의 공간에 $n+1$개 이상의 원소를 넣을 때 발생하는 물리적 충돌 필연성
  • 가부번 집합(Countable) vs 불기산 집합(Uncountable)의 대응 역학
  • 대각선 논법(Diagonal Argument): 실수 집합이 자연수 집합보다 왜 '더 큰지'에 대한 존재론적 함수 증명
• How to Learn:
  • $k$-bit 해시 값이 가질 수 있는 최대 유니크 개수를 넘었을 때의 충돌 확률을 비둘기집 원리로 계산
  • 무한 호텔(Hilbert's Hotel) 역설을 통해 함수의 이동(Shift)이 집합 크기에 미치는 영향 탐구
• Implement: 확률적 최적화가 필요한 대규모 중복 제거 알고리즘 프로토타입

7. Terminology

8. References

Primary References

• [P1] CS2023 - DS/Discrete Structures and Modeling — Core functions and mapping.
• [P2] SWEBOK v4.0 - Computing Foundations / Discrete Mathematics — Applied foundations.

Secondary References

• [Discrete Mathematics Tutorial] Stanford CS103 — Rigorous approach to proofs and functions.
• [Book of Proof] Richard Hammack — Step-by-step function mapping logic.

Industry References

• [Type Systems in Programming Languages] Benjamin Pierce — Function types and safety.
• [Purely Functional Data Structures] Chris Okasaki — Functional mapping in practice.

9. Final Checklist

Primary Checklist

• 특정 대응 규칙이 왜 '함수'가 될 수 없는지(혹은 왜 함수인지) 공리적 정의를 바탕으로 입증할 수 있는 가? (P1)
• 함수의 합성 ($g \circ f$) 결과가 단사/전사가 되기 위해 원래 함수 $f, g$가 갖춰야 할 최소 조건을 추론 가능한가? (P1)

Secondary Checklist

• 해시 충돌(Hash Collision) 현상을 비둘기집 원리를 이용해 수학적으로 모델링하고, 충돌 없는 해시가 존재하기 위한 공간 조건을 제시할 수 있는가?
• 바닥 함수와 천장 함수의 성질을 이용해 부동 소수점 연산에서 발생할 수 있는 오차를 정수 범위로 제한하는 논리를 설계할 수 있는가?

Industry Checklist

• API 설계 시, 입력 파라미터(Domain)와 리턴 타입(Codomain)의 일관성을 함수적 무결성 관점에서 검증하고 타입 오류를 예방할 수 있는가? (SFIA)
• 함수형 프로그래밍 아키텍처를 도입할 때, 모나드(Monad)나 파이프라인 구조가 왜 수학적 '함수 합성'의 연장선에 있는지 동료에게 설명할 수 있는 가?