08. Structural Induction

왜 구조적 귀납법이 필요한가?

  우리가 이미 배운 수학적 귀납법은 자연수에 대한 거였다.
 
  P(0)이 참이고, P(k) → P(k+1)이면, 모든 자연수 n에 대해 P(n)이 참이다.
 
  근데 컴퓨터는 숫자만 다루지 않는다. 문자열, 트리, 프로그램 같은 것들도 다룬다. 그럼 이런 것들에 대해서도 "모든 문자열에 대해 성질 P가 성립한다" 같은 걸 증명하고 싶을 때는 어떻게 할까?
 
  이때 쓰는 게 구조적 귀납법(Structural Induction)이다. 자연수 귀납법을 일반화한 버전이라고 보면 된다.

---

귀납적 정의란?

  구조적 귀납법을 쓰려면 먼저 대상이 귀납적으로 정의되어 있어야 한다.

귀납적 정의는 두 가지로 이루어진다.

• Base case: 가장 단순한 객체를 정의한다.

• Constructor: 이미 있는 객체로 더 큰 객체를 만드는 규칙이다.
   
  예를 들어 비트 문자열(Σ* where Σ = {0, 1})은 이렇게 정의된다.

• (Base case) 빈 문자열 λ는 Σ*의 원소다.

• (Constructor) s ∈ Σ_이고 a ∈ Σ이면, ⟨a, s⟩ ∈ Σ_다.
   
  그러면 10은 ⟨1, ⟨0, λ⟩⟩로 표현된다. 이 규칙 두 개만으로 무한히 많은 비트 문자열을 전부 표현할 수 있다.

---

구조적 귀납법의 구조

  집합 S가 귀납적으로 정의되어 있을 때, 모든 x ∈ S에 대해 P(x)가 성립함을 증명하려면:

• (Base case) 각 base 객체 x₀에 대해 P(x₀)가 성립함을 보인다.
• (Inductive step) x보다 먼저 만들어진 더 작은 객체 y에 대해 P(y)가 성립한다고 가정하고, P(x)가 성립함을 보인다.

자연수 귀납법이랑 구조가 완전히 같다. 대상이 숫자에서 구조적으로 정의된 객체로 바뀐 것뿐이다.

---

연산도 귀납적으로 정의한다

귀납적으로 정의된 객체 위의 연산도 귀납적으로 정의할 수 있다.

길이 |s|:

• |λ| = 0
• |⟨a, s⟩| = 1 + |s|

연결(concatenation) s · t:

• λ · t = t
• ⟨a, s⟩ · t = ⟨a, s · t⟩
   
  예를 들어 00 · 111을 계산하면:
  ⟨0, ⟨0, λ⟩⟩ · 111
  = ⟨0, ⟨0, λ⟩ · 111⟩
  = ⟨0, ⟨0, λ · 111⟩⟩
  = ⟨0, ⟨0, 111⟩⟩
  = 00111

---

예제: 균형 잡힌 괄호 문자열 (BSP)

BSP(Balanced Strings of Parentheses)는 이렇게 귀납적으로 정의된다.

• (Base case) 빈 문자열 λ는 BSP다.
• (C1) x가 BSP면 (x)도 BSP다.
• (C2) x, y가 BSP면 xy도 BSP다.

그리고 counting rule이라는 게 있다.

왼쪽부터 시작해서 ( 를 만나면 +1, ) 를 만나면 -1을 하면서 읽어나갈 때, 도중에 절대 음수가 되지 않고, 끝에서 정확히 0이 되는 것.

오늘 증명한 건 이거다.

BSP ↔ counting rule을 만족한다

---

Direction 1: BSP이면 counting rule을 만족한다

구조적 귀납법으로 BSP 정의를 그대로 따라간다.

• (Base case) λ는 아무 글자도 없으니까 카운트 변화가 없다. 0으로 끝나고 음수도 없다. ✅
• (C1) x가 counting rule을 만족한다고 가정하면, (x)는 (로 +1 시작, x 부분은 가정에 의해 0으로 끝나며 음수 없음, )로 -1 마무리. 전체적으로 0으로 끝나고 도중에 음수 없음. ✅
• (C2) x, y 둘 다 counting rule을 만족한다고 가정하면, xy는 x가 0으로 끝난 뒤 y가 이어지므로 전체도 0으로 끝나고 도중에 음수 없음. ✅

---

Direction 2: counting rule을 만족하면 BSP다

이 방향이 까다롭다. BSP 구조를 모르는 상태에서 시작하기 때문이다.

핵심 아이디어는, counting rule을 만족하는 문자열을 그래프로 그려보면 반드시 두 가지 모양 중 하나라는 것이다.

• Case 1: 그래프가 시작과 끝에서만 0을 찍는다 → (x) 형태 → C1 적용
• Case 2: 그래프가 중간에도 0을 찍는다 → xy로 쪼갤 수 있다 → C2 적용

왜 케이스를 두 개로 나누냐고 처음엔 헷갈렸는데, 생각해보면 당연하다. BSP의 constructor가 두 개(C1, C2)니까, 주어진 문자열이 어떤 constructor로 분해되는지를 기준으로 나누는 것이다. counting rule을 만족하는 문자열은 반드시 이 둘 중 하나에 해당하기 때문에 모든 경우가 커버된다.

각 케이스에서 더 작은 부분(x 또는 x, y)이 counting rule을 만족하므로 귀납 가정에 의해 BSP이고, 따라서 C1 또는 C2에 의해 전체도 BSP가 된다.

---

정리

• 문자열, 트리 같은 객체는 귀납적으로 정의된다 (base case + constructor).
• 이런 객체에 대한 증명은 구조적 귀납법으로 한다.
• 구조는 자연수 귀납법이랑 같다. base case 증명하고, 작은 것에서 큰 것으로 올라가면 된다.
• 연산도 귀납적으로 정의되고, 증명도 그 구조를 그대로 따라가면 된다.