从正整数的集合 N = { 1, 2, 3, ... } 到另一个集合 A 的函数。用 a_n 表示整数 n 的像，于是序列通常表示为：
a_1, a_2, a_3, ... 或 {a_n: n \in N}， 或简记为 { a_n }
有时也以非负整数的集合 { 0, 1, 2, ... } 而非 N 作为序列的定义域。在这一情况下，我们说 n 从 0 开始而不是从 1 开始。
列表 集合A上的有限序列是一个从 { 1, 2, ..., m } 到A的函数，通常表示为：
a_1, a_2, ..., a_m
这样的有限序列有时也称为一个 列表 或 m-元组。
考虑一个序列 a_1, a_2, a_3, ...，则和
a_1 + a_2 + ... + a_n 与 a_m + a_{m+1} + ... + a_n
将分别记作：
在上术表达式中，字母j称为哑指标或哑变量。
设I为任意非空集合，并设 S 为集族，从 I 到 S 的指标函数为一个函数f: I \to S。对于任意的 i \in I，记A_i表示其 像f(i)。
于是指标函数 f 通常表示为：
{A_i: i \in I} 或简记为 {A_i}
集合 I 称为指标集，I 的元素称为指标。 如果 f 为一一的 和 映上的，我们就说 S 可以由 I 标出。
集合的指标类的并与交定义为： $$ \cup_{i \in I} A_i = {x: x \in A，对于某i \in I}
\cap_{i \in I} A_i = {x: x \in A，对所有i \in I} $$
如果I为有限集，则这恰好是先前定义的并和交。如果I是 N（自然数集），可以分别定义并与交为：
递归定义 如果一个函数的定义与其自身有关，则称该函数是递归定义的。 为了避免循环定义，函数的递归需要满足以下两个性质：
- 必须存在一个称为基准值的叙述，不与函数自身相关。
- 在每一个时刻，函数都与自身相关，但函数的描述必须封闭于基准值。
具备这两个性质的递归函数称为良好定义的。
从 1 到 n 的所有正整数的积称为“n阶乘”，通常记作n!，即：
n! = 1 * 2 * 3 ... (n - 2) (n - 1) n
定义3.2 阶乘函数
1. 如果 n = 0，则 n! = 1
2. 如果 n > 0，则 n!= n * (n - 1)!
设P为一个用来确定f(X)的过程或者递归式，其中f为递归函数，X为输入值。 将P的每一步操作联系一个水平数。P的原始操作步骤规定为水平1；由于递归介入，P的每一时刻的操作的水平数都比其递归代入的水平数增加1。 递归的深度即获得f(X)的P的最大操作水平数。
Fibonacci序列（通常记作F_0, F_1, F_2，...）如下：
即F_0 = 0, F_1 = 1，以后每一项都是其前面两项的和。
定义3.3(Fibonacci序列) 1. 如果 n = 0 或者 n = 1，则 F_n = n 2. 如果 n > 1，则F_n = F_{n-2} + F_{n-1}
定义3.4(Ackermann函数) 1. 如果 m = 0，则 A(m, n) = n + 1 2. 如果 m != 0 但是 n = 0， 则 A(m, n) = A(m - 1, n) 3. 如果 m != 0 且 n != 0, 则 A(m, n) = A(m - 1, A(m, n - 1))
(条件2 经过递归之后，得到的值为1；条件3的情况较为复杂。)
两个集合A与B称为是 对等 的，或 具有同样多的元素，或 具有相同的基数，记作A \simeq B。如果存在一一对应 f: A \to B。
集合A称为有限的，如果对于某正整数n，A 与集合 { 1, 2, ..., n } 具有相同的基数。 如果一个集合不是有限的，就称之为无限的。
我们将基数简单地看做一种分配给集合的符号，两个集合被分配相同的符号，当且仅当它们具有相同的基数。 集合A的基数通常记作 |A| 或 n(A)，或 card(A)。
有限集的基数符号是自然（数）的，空集的基数为0；集合 {1, 2, ..., n} 的基数为n。 于是 |A| = n 当且仅当 A 与 {1, 2, ..., n} 具有相同的基数，即A含有n个元素。
具有基数 \aleph_0 的集合称为可数的或无限可数的。有限集和可数集都称为可数的。
定理3.2
可数集的可数并仍然是可数的。
如果A_1, A_2, ...都是可数的，则并集 $$ A_1 \cup A_2 \cup A_3 \cup \ldots $$ 也是可数的。
定理3.3 从 0 到 1 的所有字数的集合 I 是不可数的。
对于任意集合A与B，定义： $$ |A| \leq |B|，如果存在一一对应函数 f： A \to B $$
同样地：
定理3.4 (Cantor)
对于任意集合A，有 $$ |A| < |Power(A)| $$ （其中，Power(A)为A的幂集，即A的全体子集族）。
定理3.5 (Schroeder-Bernstein)
对于集合A和B： $$ |A| \leq |B| \land |B| \leq |A| \implies |A| = |B| $$