무한의 구조 (2) - 집합의 무한성과 유한성
집합의 유한성과 무한성은 수학의 기초 개념 중 하나로, 직관적으로는 "셀 수 있는가?"에 대한 문제처럼 보이지만, 이를 정확히 다루기 위해서는 수학적으로 엄밀한 정의가 필요합니다. 이 글에서는 이전글과 이어지는 주제로 유한 집합과 무한 집합에 관련된 정리들과 그 증명들을 살펴보며, 유한성에 대한 수학적 기반을 탄탄히 정리해보고자 합니다.
보조 정리
- 무한 집합에서 원소를 하나 제거해도 여전히 무한합니다.
- 즉, 무한 집합 X와 그 안의 어떤 원소 x₀∈X에 대해, X−{x₀} 역시 무한 집합입니다.
증명
무한 집합의 정의에 따라, 무한 집합 X에는 f(X)⊂X인 단사 함수 f: X→X가 존재합니다.
여기서 아래처럼 두 가지 경우로 나눠서 증명할 필요가 있습니다.
(1) x₀∈f(X)
이 경우 f(x₁)=x₀ 되는 어떤 x₁∈X가 존재하게 됩니다.
이제 g: X−{x₀} → X−{x₀}를 다음과 같이 정의합니다:
| g(x) = | f(x) | if x≠x₁ |
| x₂ | if x=x₁ |
여기서 x₂는 X-f(X)의 원소로 f(X)⊂X임에 따라 항상 고를 수 있습니다.
이렇게 정의된 g는
- 단사 함수이며
- g(X - {x₀}) = f(X - {x₀,x₁})∪{x₂} 인데
- f(x₁)=x₀이고 g(x₁)=x₂ 이므로 f(x₀)는 또다른 x₃∈X-{x₀} 여야 하는데
- f(X - {x₀,x₁})∪{x₂}는 x₃를 포함하지 않으므로 ≠ X - {x₀}가 되어
무한 집합의 정의를 만족합니다.
(2) x₀∈X - f(X)
이 경우는 더 간단합니다.
- g(x) = f(x)로 정의하면 f가 단사이므로 g도 단사가 됩니다.
- 또한 g(X-{x₀}) = f(X) - {f(x₀)} ≠ X - {x₀} 이므로 X - {x₀}는 무한합니다.
자연수의 초기 구간
먼저 앞으로 자주 사용될 집합 하나를 정의해보도록 하겠습니다.
ℕ_k = {1, 2, 3, …, k} (단, k∈ℕ)
이 집합은 명백히 유한하다고 생각할 수 있지만 이를 수학적 귀납법으로 아래와 같이 증명할 수 있습니다.
- (기초) k=1일 때, ℕ₁={1}은 유한 집합입니다. (무한 집합의 예제로부터)
- (귀납 가정) 어떤 k∈ℕ에 대해 ℕ_k가 유한하다고 가정합시다.
- (귀납 단계)
ℕ_(k+1) = ℕ_k ∪ {k+1} 인데, 만약 이것이 무한 집합이라면, 위의 보조 정리에 따라 원소 k+1을 제거한 집합 ℕ_k도 무한이어야 합니다. 이는 귀납 가정에 위배되므로, ℕ_(k+1 유한 집합입니다.
따라서 모든 k∈ℕ에 대해 ℕ_k는 유한합니다.
유한 집합의 대안적 정의를 위한 정리
- 집합 X는 유한 ⇔ X=∅ 또는 X가 어떤 ℕ_k와 일대일 대응 관계
- 즉, 집합 X가 유한하다는 것은 X가 공집합이거나 어떤 ℕ_k와 전단사 함수를 만들 수 있다는 말과 동치입니다.
증명
- ⇐ 방향: "X=∅ 이거나 X가 어떤 ℕ_k와 일대일 대응 관계를 만들 수 있으면 집합 X는 유한 집합"입니다.
- 만약 X가 공집합이면 무한 집합의 예제에 의해 유한 집합입니다.
- 만약 X가 어떤 ℕ_k와 전단사 함수를 만들 수 있다면 일대일 대응과 무한성의 전이 정리와 위의 자연수의 초기 구간 정리에 따라 유한 집합입니다.
- ⇒ 방향: 대우명제인 "X≠∅ 이고 X가 어떤 ℕ_k와도 일대일 대응 관계가 아니면 X는 무한 집합"임을 증명합니다.
- X는 공집합이 아니므로 어떤 x₁∈X를 선택할 수 있습니다.
- 여기서 X-{x₁}이 공집합이라면 X={x₁}이 되어 ℕ₁과 일대일 대응 관계가 생겨서 가정에 모순이 되므로 X-{x₁}은 공집합이 아닙니다.
- 마찬가지로 x₂∈X-{x₁}을 선택할 수 있고 계속해서 x₁, x₂, x₃, ..., x_k를 선택할 수 있습니다.
- 이는 X-{x₁, x₂, x₃, ..., x_k}가 공집합이라면 X가 ℕ_k와 일대일 대응 관계가 생겨서 가정에 모순이 되므로 다음 원소인 x_(k+1)을 반드시 선택할 수 있기 때문입니다.
- 즉, 임의의 자연수 n에 대해 집합 {x₁, x₂, x₃, ..., x_n}은 X의 진부분집합으로 존재합니다.
- 이제 모든 자연수에 대해 선택된 집합을 Y라 하고 함수 f: Y → Y-{x₁}를 f(x_k) = x_(k+1), for all k∈ℕ으로 정의할 수 있으며 이는 Y와 그의 진부분집합 Y-{x₁} 사이의 일대일 대응을 정의하게 되므로 집합 Y는 무한 집합입니다.
- 이는 무한성과 유한성의 보존 정리에 따라 X도 무한 집합이 됩니다.
위의 정리를 통해 우리는 유한 집합과 무한 집합을 다음과 같이 다시 정의할 수 있습니다:
- 유한 집합: 공집합이거나 어떤 ℕ_k와 일대일 대응되는 집합.
- 무한 집합: 유한 집합이 아닌 집합.
이는 무한성에 대한 정의(진부분집합과 일대일 대응되는 경우)을 증명 가능한 정리로 만들 수 있다는 뜻입니다.
다만, 실제로 그렇게 정리와 정의의 순서를 바꾸어 구성하더라도 증명의 복잡도는 거의 동일합니다.