가산집합

집합 $S$가 유한집합이거나 $S$와 $\mathbb {N}$ 사이에 일대일 대응이 존재하면 $S$를 가산집합(countable set)이라 한다. 가산집합이 아닌 집합은 비가산집합이라 한다.

공집합이 아닌 집합 $S$에 대해 다음은 서로 동등하다.

• $S$는 가산집합이다.
• 일대일 함수 $f:S\to \mathbb {N}$가 존재한다.
• 위로의 함수 $g:\mathbb {N} \to S$가 존재한다.

예시

• 모든 자연수의 집합 $\mathbb {N}$, 모든 정수의 집합 $\mathbb {Z}$, 모든 유리수의 집합 $\mathbb {Q}$는 모두 가산집합이다.

성질

$S,T$가 가산집합일 때,

• $S\cup T$는 가산집합이다.
• $S\times T$는 가산집합이다.