由定义，如果存在从 S {\displaystyle S}  到自然数集合 N = { 0 , 1 , 2 , 3 , … } {\displaystyle \mathbb {N} =\left\{0,1,2,3,\ldots \right\}}  存在单射函数 f : S → N {\displaystyle f:S\rightarrow \mathbb {N} }  ，则 S {\displaystyle S}  称为可数集。

这似乎自然地把集合划分为不同类别：把所有包含一个元素的集合放在一起；包含两个元素的集合在一起......最后，把所有无限集合放在一起，并认为它们具有相同的大小。然而，在大小的自然定义下，这种观点是不确切的。

为了阐述这一点，我们需要一个双射的概念。虽然双射看起来比数更加高深，但原本数学发展中集论定义函数要先于数字。因为它们都是基于更简单的集合。这就引出了双射的概念：

由于 { a , b , c } {\displaystyle \left\{a,b,c\right\}}  的每个元素都可以和 { 1 , 2 , 3 } {\displaystyle \left\{1,2,3\right\}}  中准确的一个配对，并且反过来也同样，这就定义了一个双射。

我们将这个情境一般化，定义当且仅当它们之间存在双射，两个集合的大小相同。对于有限集，这里给出了“大小相同”的常用定义。那么对于无限集呢？

考虑集合 A = { 1 , 2 , 3 , … } {\displaystyle A=\left\{1,2,3,\ldots \right\}}  （正整数集），和 B = { 2 , 4 , 6 , … } {\displaystyle B=\left\{2,4,6,\ldots \right\}}  （正偶数集）。我们说，在我们的定义下，这些集合有相同的大小，并且因此B是无限可数集。我们需要证明它们之间存在双射。但这是很简单的，运用 n ↔ 2 n {\displaystyle n\leftrightarrow 2n}  ，那么

正如前面的例子， A {\displaystyle A}  的每个元素都已和 B {\displaystyle B}  中准确的一个配对，并且反过来也同样。因而它们大小相同。这给出了一个集合与其一个合适的子集大小相同的例子，这种情形在有限集中是不可能的。

同样，自然数的有序对的集合，也就是自然数集合的笛卡尔积 N × N {\displaystyle \mathbb {N} \times \mathbb {N} }  ，是无限可数集，可以沿着图中的一种路径：

配对结果就像这样：

显然这个映射可以覆盖所有这些有序对。另一个证明方法是可以定义一个从自然数集合的笛卡尔积 N × N {\displaystyle \mathbb {N} \times \mathbb {N} }  到自然数集合 N {\displaystyle \mathbb {N} }  的单射函数 f ( p , q ) = 2 p 3 q {\displaystyle f(p,q)=2^{p}3^{q}}  。

利用数学归纳法，可知在n是个有限的自然数时，自然数集合的n-元笛卡尔积 ∏ i = 1 n N = { ( x 1 , … , x n )   |   x 1 ∧ … ∧ x n ∈ N } {\displaystyle \prod _{i=1}^{n}\mathbb {N} =\{(x_{1},\ldots ,x_{n})\ |\ x_{1}\land \;\ldots \;\land \;x_{n}\in \mathbb {N} \}}  是可数的。利用自然数集的笛卡尔积是可数的这点，可以证明整数集和有理数集是可数集，这是因为整数可以视为自然数的有序对（可将正整数 n {\displaystyle n}  给视为 ( n , 0 ) {\displaystyle (n,0)}  ，将负整数 − n {\displaystyle -n}  给视为 ( 0 , n ) {\displaystyle (0,n)}  ），而以最简分数形式表示的有理数 p / q {\displaystyle p/q}  也可视为整数的有序对 ( p , q ) {\displaystyle (p,q)}  所致。

另外，可数无限多个可数集的联集是可数的，这是因为可以定义一个单射函数，将可数无限多个可数集的联集给映至自然数集合的笛卡尔积 N × N {\displaystyle \mathbb {N} \times \mathbb {N} }  之故。

不过可数无限多个自然数集合的笛卡尔积不是可数的，这可以透过康托的对角论证法证明。