设A，B分别是有限集合，A，B如果元素个数一样，当且仅当可以找到一种1-1对应的映射，实现A集合与B集合的互相映射。对忘记了数学，或者刚开始接触高中数学课程的同学，这话说的够别扭，够“高端”，其实无非是小学一年级就知道的用数数东西的泛化。

A={1,2,3},B={a，b，c}

1<->a，2<->b，3<->c

则|A|=|B|,其中|X|代表X集合中元素的个数。如果两个集合的元素是无穷多个，用数来具体表示集合元素的个数已经不可能了，所以数不能做为精确表达集合大小的工具。将集合元素的映射关系做为比较集合的大小的工具才可行。

例如全体负整数集合，{……,-3,-2,-1}与全体正整数集合{1，2，3，….}可以建立对应关系1->-1,2->-2,3->-3,…..,我们就可以建立这两个集合大小”相等”的印象。我们再看全体正偶数集合N2={2，4，6，8，……,2n,2n 2，……}与全体正整数集合N={1,2,….,n，n 1，…..} 也可以建立起对应关系：1->2,2->4,3->6,…..,n->2n,….。但是N2却是N的真子集。

被很多人认为是现代数学基石的集合论出现的很晚，发明的动机也非常单纯，是1874年，在康托尔CANTOR）的一篇论文里出现的。1872年，一次旅行让康托尔认识了理查德.戴德金（Richard.Dedekind德国的数学家）。理查德. 戴德金一直独立研究无理数以及数的连续性问题，康托尔在其影响下开始从数论研究转向三角函数展开序列（傅里叶变换）唯一性研究。他抓住了从我们1年级就知道的相等与对应的这个工具，利用这个工具，他研究了一系列无限序列的性质。如果一个无限集合可以用全体正整数来实现对应的话，那么这个无限集合就被称为可数集合。在康托尔论证超越数的存在性以及实数的不可数性时，他的核心技巧被称为对角线技巧。这一方法后来在数理逻辑，计算机科学的理论基础建立过程中也扮演了重要角色。

图1有理数对角线法

对每个对角线上的*上依次编码为1，2，3，.......，那么左边的有理数就可以和自然数1，2，3，......，建立起1-1对应的关系，所以有理数可数。

康托尔考察了形式为

的所有方程f(x,n)= 0的实数解总共有多少个的问题。其中全部a_i被限定为整数。如果方程的系数a_i全都是有理数，那么可以乘以分母的最小公倍数，变为整数方程。在处理这个问题时，康托为任何一条上面的方程定义了下面这样一个标记：

Index =|a_n| |a_n-1| |a_n-2| ... |a₁| |a₀| n

对Index=3来说，只有四个方程，分别是：2x=0, x 1 = 0, x - 1 = 0 and x² = 0，解只有3个：0，-1，1.

这个Index后来被人形象地称为方程的“高”（high），记作h.对每一个高h,只有有限多个方程，而每个方程又只有有限解，高为h的所有方程的总解数目必然是有限数.如果将全体方程f(x,n)= 0按其高h加以分类，用h乘以h类里含有的各个方程解数之和的话，会得到这个类里方程解的总数，累加起来，就可以获得其高小于等于h的方程解的总数目，设这个总数目为M_h

对高为h方程全体解进行排序，获得一个解序列，让第i个实数解对应小于h的各类里方程的总解数M_h-1数加上i，这样任何一个解就可以用唯一一个自然数进行编号。方程f(x,n)= 0的所有解的编号都可以对应唯一的自然数。

通过这种办法康托将f(x,n)= 0的全体实数解与自然数建立起了对应的关系，这样他得到了方程f(x,n)= 0所有代数解是可用自然数来“数”数或者计数这样一个重要结果。

利用集合论，我们来证明实数的不可数性。

设f是由“0”，“1”组成的无穷串。可以用函数f: N->{0,1}，N={0，1，2，。。。}是自然数集合来表达这种无穷串。以101010…..为例，则f(0)=1,f(1)=0,f(2)=1,….一个序列f的特征可以用集合C={i|i ∈N,f(i)=1}来表达，对任意自然数i,如果i∈C,则f(i)=1，反之则f(i)=0.

f反码形式的串f’的特征函数显然有这样的特性f’(i)=1-f(i).现在我们证明引理

康托尔引理：所有“0”，“1”组成的无穷串数目是不可数的。

康托尔定理：所有实数的集合不可数。

证明：因为二进制数0.101….可以与101。。。。形成1-1映射，故所有的0.101…

也不可数，全体0.101…是实数的子集合，所以实数也不可数,证完

推论：超越数是存在的，且实数中超越数的数目不可数。

证明：有理数与代数都是可数集，而实数是不可数集，所以实数中除了有理数，代数数还有另外的数不能用整数的加减乘除，以及开方算式表达，这样的数就是超越数了。而这类的超越数不可数。

以上的简单推理是近150年来数学中最伟大的推理之一，不论是其中对角线方法对20世纪数学发现的启示作用，还是人类对数本身的分类认识上，以上推理均为近代数学中最为重要的工作之一。

康托尔将一个集合（SET）的任意元素可以与另外一个集合的元素对应起来的两个集合，叫做等势（POWER）集合。显然即使都是无穷数的集合，有理数集合的势比全体实数的集合的势小，而与方程f(x,n)= 0的代数解的势一样大。这就明确指出了，无理数比有理数多得多！同时，他也指出了必然有一些数不能表达成代数数，这些数就是超越数，超越数比代数数多得多！这是种以前从来没出现过的描述问题，证明命题的方法。后来的人发现这种集合思想非常适合于论述基本数学对象，证明相关命题，遂成为今天的集合论。

实数的任何一个连续区间段也是不可数的，但任何两个线段之间可以建立起映射关系，我们简单用图说明.

如图X’->X。即使是可数的多个实数区间也可以与一个线段建立起对应关系，无非是将线段分成若干个与每一个区间对应的一小段，然后每一小段就按上图进行对应就可以了。因此每个连续实数区间都与全体实数形成对应关系，都等势。

以康托尔研究为基础，希尔伯特进一步发问：在可数集合与实数集合之间是否存在一个中间集合，其势比可数集合大，比实数集合小，做为20世纪初提出的23个著名问题的第一个问题：连续统问题。这充分证明了大家对康托尔工作的肯定。