Denumerable and Countable Sets
Definition 1. A set $X$ is said to be denumerable if $X \sim \mathbb{N}$. A countable set is a set which is either finite or denumerable.
Countable set은 말 그대로 대상들을 하나하나 '셀 수 있는', 가산집합을 의미한다. 유한집합은 직관적으로도 당연히 셀 수 있다. 말 그대로 대상이 유한 개니까 시간은 좀 걸리더라도 언젠가 끝이 있기 때문이다. 그러나 무한집합의 경우는 어떻게 가능할까? 비록 세아려야 할 대상이 무한하지만, 각 대상이 모두 번호가 붙어 있어서 우리에게 그 번호의 규칙이 주어진다면 다른 의미에서 셀 수 있다고 말할 수 있다. 규칙, 다시 말해 패턴을 알고 있다면 어떤 원소를 우리에게 주더라도 그 패턴을 가지고 그 원소의 번호를 말할 수 있기 때문이다. 이와 같이 '셀 수 있다'는 개념과는 조금 다른, 번호를 붙일 수 있고 그 번호의 패턴을 알 수 있다는 개념을 denumerable set, 가부번집합이라고 말한다. 정의상 denumerable set은 항상 무한집합이다.
Theorem 1
Theorem 1. Every infinite subset of a denumerable set is denumerable.
일종의 subsequence를 잡아낸다고 이해해도 좋다. 그 subsequnce의 index set과 $\mathbb{N}$ 사이에 bijection을 항상 잡아낼 수 있기 때문이다.
Corollary
Corollary. Every subset of a countable set is countable.
Theorem 2
Theorem 2. For each $k \in \mathbb{N}$, let $A_k$ be a denumerable set. Then $$\bigcup_{k \in \mathbb{N}} A_k$$ is denumerable.
Theorem 3
Theorem 3. Every infinite set contains a denumerable subset.
다시 말해 denumerable set은 무한집합 중에서도 가장 '크기'가 작은 집합이다.