안내
전체 조망
이산수학 코스의 개념적 뼈대 한눈에 보기
읽음 0/0
갱신 2026-08-09
이 코스는 셀 수 있는 세계의 수학을 다룬다. 연속적인 극한 대신 유한하거나 가산적인 구조 — 명제, 집합, 순열, 그래프 — 를 대상으로, 그것을 정확히 기술하고, 세고, 존재를 증명하는 방법을 16개 장에 걸쳐 쌓아 올린다. 전체 경로는 읽기 경로에, 재료의 출처는 원전 소개에 정리되어 있다.
개념적 뼈대
코스는 다섯 개의 큰 흐름으로 이어진다. 각 단계는 앞 단계가 만든 언어와 도구 위에 서 있다.
- 논리 — 증명의 문법 (명제논리 → 술어와 한정기호 → 증명 기법): 수학적 진술이 무엇이고, 참임을 보이는 정당한 방법이 무엇인지 확정한다. 진리표와 동치, $\forall$·$\exists$의 부정 규칙, 그리고 직접증명·대우·귀류·수학적 귀납법이라는 네 가지 기본 무기가 여기서 나온다.
- 집합과 관계 — 이산 구조의 재료 (집합과 함수 → 관계와 동치관계 → 집합의 크기): 이후 등장하는 모든 대상은 집합과 함수로 만들어진다. 단사·전사는 "크기 비교"의 언어가 되고, 동치관계는 분할을, 부분순서는 위계를 낳으며, 집합의 크기의 대각선 논법은 무한에도 크기의 등급이 있음을 보인다.
- 조합론 — 세는 기술 (셈의 기본 원리 → 순열과 조합 → 포함–배제의 원리 → 점화식 → 생성함수): 곱·합의 법칙에서 출발해 이항계수 $\binom{n}{k}$, 포함–배제, 점화식을 거쳐, 수열 전체를 하나의 형식적 멱급수로 압축하는 생성함수에 이른다. "얼마나 많은가"라는 질문에 답하는 도구 상자가 완성된다.
- 그래프 이론 — 점과 선의 수학 (그래프와 트리 → 평면그래프 → 그래프 채색 → 매칭과 홀의 정리): 관계를 그림으로 그리면 그래프가 된다. 트리의 특성화, 오일러 공식 $V-E+F=2$, 채색수, 홀의 결혼 정리 — 이산 구조의 기하학이자, 조합적 논증이 실제로 작동하는 무대다.
- 확률적 방법 — 무작위로 존재를 증명한다 (확률적 방법): 세기와 구조가 합류하는 종착점. 무작위 대상의 기대값을 계산해 "좋은 대상이 존재한다"를 증명하는 기법으로, 램지 수의 하계가 대표적 예다. 현대 조합론으로 건너가는 다리다.
왜 이 순서인가
배열의 원리는 단순하다 — 말하는 법을 먼저, 재료를 그다음, 기술은 그 위에. 논리와 증명법(I–II부)이 맨 앞에 오는 이유는 이후의 모든 장이 정리와 증명으로 쓰여 있기 때문이다. 귀납법을 모르면 점화식도 트리도 다룰 수 없다. 집합·관계·크기(III부)는 조합론과 그래프 이론이 공유하는 공통 재료다: 순열은 단사함수이고, 그래프는 대칭적 관계이며, "센다"는 행위 자체가 유한집합 사이의 전단사를 찾는 일이다.
조합론(IV–V부)이 그래프 이론(VI부)보다 앞서는 것은 도구의 방향 때문이다. 그래프 이론의 정리들 — 트리의 간선 수, 평면그래프의 간선 상한, 채색 논증 — 은 비둘기집 원리와 이중 세기(double counting) 같은 조합적 기법을 끊임없이 소비한다. 마지막의 확률적 방법는 두 흐름을 모두 전제한다: 세는 기술로 기대값을 계산하고, 그래프에서 존재성을 결론짓는다. 그래서 이 장은 코스의 끝이자 요약이다.