可数集是指其元素可以分别赋予互不相同的自然数的集合。按照包含有限集的约定，可数集既可以是有限集，也可以是可数无限集。可数无限集能与 (\mathbb N) 建立一一对应，因此可以将其元素逐一列出，既无遗漏，也无重复。可数性是集合论中的基本概念：它将最小的无限大小与更大的无限大小区分开来，后者包括实数集的大小。有些作者仅用“可数”指可数无限集，而用“至多可数”表达包含有限集的含义。(web.stanford.edu)
定义与等价刻画
设 (\mathbb N={0,1,2,\ldots})。如果存在单射函数 [ f:A\longrightarrow\mathbb N, ] 则集合 (A) 是可数集。单射性保证不同元素得到不同的编号。空集满足这一定义，每个有限集也都满足。如果 (A) 是无限集，那么它可数，当且仅当 (A) 与 (\mathbb N) 之间存在双射函数：此时，每个元素恰好对应一个序号，每个序号也恰好确定一个元素。(web.stanford.edu)
对于非空集合 (A)，另一个等价条件是存在满射函数 (g:\mathbb N\to A)。这样列出的元素可能重复；对于无限集，只保留每个元素第一次出现的位置，就可以得到无重复的枚举。用基数表示，可数性写作 [ |A|\leq\aleph_0, ] 其中，阿列夫零是 (\mathbb N) 的基数。等号成立，当且仅当 (A) 是可数无限集。这些条件所要求的是某个函数的存在，而不一定要求有能够计算该函数的有效过程。(web.stanford.edu)
例子与枚举方法
偶自然数集是可数无限集，因为 (n\mapsto 2n) 是从自然数集到偶自然数集的双射。因此，无限集可以与它的某个真子集具有相同的基数。整数集也是可数无限集，可以按以下顺序列出： [ 0,\ 1,\ -1,\ 2,\ -2,\ 3,\ -3,\ldots. ] 整数向正、负两个方向无限延伸，并不会使其具有更大的无限基数。(web.stanford.edu)
有理数集是一个不那么显而易见的例子。每个有理数都能表示为 (p/q)，其中 (p\in\mathbb Z)，(q) 为正整数。按照 (|p|+q) 的值，将这些数对分成依次排列的有限组，再略去那些与已列出数值相同的分数。每个有理数都会在经过有限组后出现，由此证明 (\mathbb Q) 是可数无限集。这一构造也说明了为什么先列完一整行无限多个分数、再开始下一行的方法不可行：有效的枚举必须最终能够到达每一项。(web.stanford.edu)
封闭性质
以下几种运算保持可数性：
- 可数集的每个子集都是可数集。
- 可数集在任意函数下的像都是可数集。
- 有限个可数集的笛卡尔积是可数集。
- 在带有选择公理的通常集合论框架中，可数个可数集的并仍是可数集。(web.stanford.edu)
对于积集 (\mathbb N\times\mathbb N)，可以按照 (i+j) 递增的顺序列出数对 ((i,j))。每条对角线上只有有限个数对，而每个数对都位于某条对角线上。反复使用这一构造，就能处理任意固定有限个因子的积。类似地，如果 (A_n) 已有枚举 (a_{n,0},a_{n,1},\ldots)，则沿对角线遍历下标 ((n,k))，就能列出这些集合的并；重复项可以删去。(math.mit.edu)
关于上述并集定理，还需要补充一个涉及集合论基础的条件。在不采用选择公理的集合论中，知道每个集合都存在枚举，并不意味着能同时为所有集合各选出一个枚举。选择公理保证可以作出这样的选择，而一般形式的可数并定理无法仅在策梅洛—弗兰克尔集合论中证明。如果各个枚举已经给定，那么沿对角线遍历就不需要额外的选择。(people.math.osu.edu)
不可数性与对角线论证
不是可数集的集合称为不可数集。一个重要的例子是所有无限二进制序列组成的集合 ({0,1}^{\mathbb N})。假设这些序列可以列为 (s_0,s_1,s_2,\ldots)。定义一个新序列： [ t(n)=1-s_n(n). ] 对于每个 (n)，序列 (t) 都在第 (n) 个位置上与 (s_n) 不同，因此它不可能出现在这份假定的列表中。这一康托尔对角线论证证明，没有任何列表能穷尽这个集合。(math.mit.edu)
通过表示元素是否属于某个子集的示性函数，二进制序列可以与 (\mathbb N) 的子集一一对应。因此，幂集 (\mathcal P(\mathbb N)) 是不可数集。类似的对角线证明也能说明实数集不可数。因此，可数集的有限积与无限积具有不同的性质：即使各个因子都只有两个元素，它们的无限积也可能不可数。(theory.stanford.edu)
在分析与计算中的意义
在数学分析和拓扑学中，可数性与几何上的稠密性是不同的概念。有理数集虽然可数，却是实数轴的稠密集，与每个非空开区间都有交集。具有可数稠密子集的度量空间称为可分空间。整个空间本身不一定可数。(math.mit.edu)
在测度论中，(\mathbb R) 的每个可数子集的勒贝格测度都为零。用总长度可以任意小的一系列区间依次覆盖各个点，就能证明这一性质。因此，稠密性与测度描述的是不同的特征：有理数集是稠密的，但其测度为零。(ocw.mit.edu)
在计算机科学中，有限字母表上的所有有限字符串组成的集合是可数的：先按长度排列，再将相同长度的字符串按某个固定顺序列出。因此，具有有限描述的程序也构成可数集。但这并不意味着可数性等同于可计算性；集合论意义上的枚举不一定能由算法生成。(theory.stanford.edu)