一，二，三，很多……

有限群

有限群是可以数出个数来的。这“个数”的存在虽然看起来不起眼但其实是非常强力的条件。最明显的，设群 G 中有一个 m 阶的子群 N（即 N 含有 m 个元。一般地把有限群所含有的元的个数称为这个群的阶），则 N 的任意一个左（右）旁系显然都正好有 m 个元。这样我们就立即有下面的定理：

定理。如果 n 阶群 G 有一个 m 阶子群 H，则 m 是 n 的约数，而 n / m 是 H 的左（右）旁系的个数。

由这定理又立即作出下面的推论：

推论1。对 n 阶群 G 的任意元 a 都有 aⁿ = 1。

推论2。素数阶群 G 是循环的、单纯的。

证明只要考虑到 G 中任何一元的阶（元 a 的阶定义为由 a 所生成的子群的阶，易知这是满足条件 a^d = 1 的最小的自然数 d）都是 | G | 的约数就可以了。（用 | G | 来表示 G 的阶，一般地我们把有限集合 A 所包含的元的个数记为 | A |）

著名的费马小定理说，如果 p 是素数且 a 不被 p 整除，则 a^{p - 1} ≡ 1 ( mod p )。从推论1的角度来看，这件事只是因为不被 p 整除的所有整数除以 p 得到的同余等价类们，关于乘法做成一个有 p - 1 个元的群。顺便说一下，任何有理数都能表示成有限或循环小数，这件事也是因为有费马小定理。关键在于对任意一个不是 2 或 5 的素数 p， 10^{p - 1} - 1 总是 p 的倍数，于是 1 / p 可以表示成 x / ( 10^{p - 1} - 1 ) 的样子，这是一个循环节长度整除 p - 1 的循环小数。

定义。设有群 G 作用在集合 A 上。对于 A 的任意一元 x，把 G 作用于 x 所得到的像全体称为 x 的 G-轨道，记为 Gx。 G 中那些作用于 x 后仍然得到 x 的元所组成的子群称为 x 的固定群，记为 Stab ( x )。

定理。设 G 从左边作用于 A 上，则 Stab ( x ) 的左旁系与 Gx 的元自然地一一对应。如果是从右边的作用则反之。

证明。由定义这几乎是显然的。（证毕）

当 G 是有限的时候，我们得到 | Gx | = | G | / | Stab ( x ) |，特别的， | Gx | 一定是 | G | 的约数。由此出发我们得到很多有用的结论。

比如有时我们想计算一些东西的数量，这些东西有一定的对称性，我们希望把那些互相对称的东西看成是一样的，而计算所有的等价类的数量。这用数学的语言来说就是有一个群 G 作用在集合 A 上，我们想要计算 A 中所有 G-轨道的个数。这时我们有下面的定理：

定理。设有有限群 G 作用在有限集合 A 上，则 A 中所有 G-轨道的个数为 ( ∑ | A_σ | ) / | G |，其中 σ 跑过 G 中所有的元，而 A_σ 由 A 中所有在 σ 的作用下不变的元所组成。

证明。 A 中所有 G-轨道的个数

第一个等号是显然的，第二个等号由上一个定理，第三个等号是因为，“对 A 的所有元 x，把满足 σx = x 的 G 中所有 σ 的个数加起来”与“对 G 的所有元 σ，把满足 σx = x 的 A 中所有 x 的个数加起来”这两件事是一样的。（证毕）

举一个例子。六个苹果六个梨，分三堆，问有多少种分法？这问题中苹果和苹果之间，梨和梨之间，以及堆和堆之间都是没有区别的。现在我们先假设堆和堆之间是有区别的，即考虑“把六个苹果六个梨分到编号为一、二、三号的三个箱子里”，把这样的所有的分法的集合记为 A。把三个箱子的置换群记为 G，我们要求的是 G 作用于 A 上的所有轨道的个数。 G 的元可以分为三种：

• 长度 3 的巡回置换： ( 1 2 3 )， ( 3 2 1 )
• 两个元的对换： ( 1 2 )， ( 2 3 )， ( 3 1 )
• 恒等变换

被长度 3 的巡回置换所固定的 A 中的元，也就是使三个箱子里每个箱子的内容都一样的分法，总共只有一种，即每个箱子里都是两个苹果两个梨。而被对换所固定的 A 中的元，也就是有两个箱子的内容是一样的分法，考虑内容一样的两个箱子的其中一只，这箱子里可以有 0 到 3 个苹果和 0 到 3 个梨，因此共有 16 种可能。接下来被恒等变换固定的 A 中的元也就是 A 中所有的分法，这分法可以描述为：先把 6 个苹果分到 3 个箱子里（这共有 ( 2 + 6 ) ! / ( 2! × 6! ) = 28 种方法），再把 6 个梨也分到 3 个箱子里（同样是 28 种分法）。因此一共是 28 × 28 = 784 种分法。应用上面的定理，我们就得到把六个苹果六个梨分三堆的分法共有 ( 1 × 2 + 16 × 3 + 784 × 1 ) / 6 = 139 种。

接下来我们通过讨论群 G 在其本身上的作用来得到一些重要的定理。

定义。如果群 G 的阶是某素数 p 的幂，就称 G 为 p-群。

定义。我们把群 G 称为可解的，如果存在 G 的一个递降子群链 G = G₀ ⊃ G₁ ⊃ … ⊃ G_{n - 1} ⊃ G_n = { 1 } 满足条件：对于任意的 i， G_{i + 1} 是 G_i 的正规子群，并且 G_i / G_{i + 1} 是Abel群。

可解群的概念源于Galois理论，一个一元高次多项式的根能够用根号表示出来的充分必要条件是这多项式的Galois群是可解的。如果 G 是有限群，那么 G 可解等于是说 G 的组成因子都是素数阶的循环群，因为显然单纯的Abel群只能是素数阶的循环群。

定理。 p-群 G 是可解的。

证明。设 | G | = p^e，对 e 使用归纳法。 e = 1 的时候命题显然成立。对于一般的情形，考虑 G 通过取共轭作用于 G。这时其 G-轨道只有一点的 G 中的元，是与 G 中所有元都可换的元，它们组成 G 的中心 Z ( G )。而 G 中如果有某元 x 的 G-轨道多于一点，由前定理知 | Gx | 是 | G | 的约数，现在 | G | 是 p 的幂，所以 | Gx | 是 p 的大于一次的幂。特别的， | Gx | 是 p 的倍数。所有的轨道合起来正好拼成 G，所以我们得出结论 | Z ( G ) | 必是 p 的倍数。这样就有 Z ( G ) ≠ { 1 }。于是 | G / Z ( G ) | 严格比 | G | 小，并且 G / Z ( G ) 也是 p-群。这样就可以对 G / Z ( G ) 应用归纳法的假定，而 Z ( G ) 又显然是Abel群，于是命题得证。（证毕）

定义。对有限群 G，设 | G | = p^em，其中 p 是素数而 m 不被 p 整除。这时把 G 中正好含有 p^e 个元的子群称为 G 的Sylow p-子群。

定理。（Sylow定理）设 G 是有限群， p 是 | G | 的素因子，并设 G 中Sylow p-子群的个数为 n。我们有 n ≡ 1 ( mod p )，特别地Sylow p-子群总是存在。进一步设 P 是 G 的一个Sylow p-子群，则 G 的任意一个 p-子群 H 都一定被包含在 P 的某个共轭中，特别地 G 中的任意两个Sylow p-子群都共轭。

证明。设 | G | = p^em， m 不被 p 整除。考虑由 G 中所有包含 p^e 个元的子集所组成的集合 S，并让 G 以左乘作用于 S。 | S | 等于二项系数，通过计算我们知道 | S | ≡ m ( mod p )。如果你不会算这个东西，这证明的后面提供了一种方法。现在对于 S 中的一元也就是 G 的一个包含 p^e 个元的子集 X， Stab ( X ) 是 G 的 p-子群，因为我们可以考虑 Stab ( X ) 在集合 X 上左乘地作用，这样容易看出 X 是由 Stab ( X ) 的一些右旁系拼成的，而 | X | = p^e，所以 | Stab ( X ) | 是 p 的幂。如果 Stab ( X ) 不是Sylow p-子群，那 | GX | = | G | / | Stab ( X ) | 就是 p 的倍数；但现在 S 是由 X 们的 G-轨道拼成的而 | S | ≡ m ( mod p ) 不是 p 的倍数，所以使得 Stab ( Y ) 是Sylow p-子群的 Y 一定存在，对于这样的 Y 来说 | GY | = m。在这时 Y 显然是 Stab ( Y ) 的一个右旁系，把这右旁系记为 Stab ( Y ) x。于是 Y 的 G-轨道可以看成是由Sylow p-子群 x^-1 Stab ( Y ) x 的 m 个左旁系所组成的，特别地我们得到，每个这样的 Y 的 G-轨道里都正好有一个Sylow p-子群。设这样的 G-轨道共有 n 个，我们就有 nm ≡ | S | ≡ m ( mod p )，于是 n ≡ 1 ( mod p )。这样就证明了定理的前半部分。
后半部分，令 P 为 G 的一个Sylow p-子群，则 P 的 G-轨道是由 P 的 m 个左旁系组成的。对于 G 的任意一个 p-子群 H，考虑 H 在 GP 上左乘地作用，由于 | H | 是 p 的幂，所以每个多于一点的 H-轨道都是 p 的倍数，但现在 | GP | = m 不是 p 的倍数，因此 GP 中一定存在 H 作用下的不动点。但 GP 的元，也就是 P 的左旁系 xP，的固定群 Stab ( xP ) 显然是 xPx^-1，所以如果 xP 是 H 不动点，就有 H ⊆ xPx^-1。（证毕）

附关于 | S | ≡ m ( mod p ) 的证明：
首先当 p 为素数且 i ≠ 0 或 p 的时候二项系数总是 p 的倍数，因为而比 p 小的数的阶乘中显然不会含有 p 的因子。这意味着我们有公式 ( a + b )^p ≡ a^p + b^p ( mod p )。 | S |是的二项展开中项的系数，所以应用公式我们有。（证毕）

Sylow定理几乎可以说是“有限群论的基本定理”。在决定一个 n 阶群的结构的时候我们通常都先用Sylow定理找出它的Sylow子群，再进行详细分析。这里举两个简单的例子，不过在举例之前还有一个小小的命题。

命题。设有有限群 G 和 G 的子群 N。则 N 的共轭的个数是 N 的旁系的个数的约数。

证明。考虑 N 的所有共轭所组成的集合 S， G 通过取共轭作用于 S。 S 中只有一个 G-轨道，而显然 N ⊆ Stab ( N )，因此 | S | = | G | / | Stab ( N ) | 是 | G | / | N | 的约数。（证毕）

现在我们来决定 6 阶和 15 阶的群的结构。
6 = 2 × 3，所以根据Sylow定理， 6 阶群中一定有一个 2 阶子群和一个 3 阶子群。 2、 3 都是素数，所以它们都是循环群，分别记为 C₂、 C₃。Sylow定理还说， 3 阶子群的共轭的个数除以 3 余 1；而前面那个定理说共轭的个数是 2 的约数。于是我们得出结论 C₃ 的共轭只有 1 个，也就是说 C₃ 是个正规子群。显然 C₃ ∩ C₂ = { 1 }， C₃C₂ 是全体，所以一个 6 阶的群一定分解为 C₂ 作用于 C₃ 上的半直积。容易知道 Aut ( C₃ ) 是 2 阶循环群，所以从 C₂ 到 Aut ( C₃ ) 的同态映射有两种，这两种同态映射所定义的两种半直积分别对应于 6 阶循环群 C₆ 和 3 次置换群 S₃。
同样的， 15 = 3 × 5，所以 15 阶群中一定有一个 3 阶子群和一个 5 阶子群。把它们记为 C₃、 C₅。通过完全类似的讨论我们知道 C₅ 是正规子群，一个 15 阶的群一定分解为 C₃ 作用于 C₅ 上的半直积。现在 Aut ( C₅ ) 是 4 阶循环群，所以从 C₃ 到 Aut ( C₅ ) 的同态映射只有平凡的一种，也就是说 15 阶的群只有循环群。

由以上的讨论我们特别地知道 3 次置换群 S₃ 是可解的。在最后我将来描述一下这可解性与 3 次方程的解法之间的关系。
为此我们先来看看 2 次方程的解法。我很讨厌配方法，嫌它实在是太难看了。而且也记不住公式。我愿意将 2 次方程的解法叙述成这种形式：设方程 x² - px + q = 0 的根为 a、 b，则有

然后我们计算 ( a - b ) ² = p² - 4q，开平方根就得到 a - b，再结合 a + b = p 的条件就可以解出来了。
但是这里的 ( a - b ) ² 是个什么东西？为什么要计算这个 ( a - b ) ² 呢？这个式子中的负号事实上来自于 1 的另外一个平方根， -1。我们把 a 和 b 互换一下，则 a - b 就变成了 b - a，它是原来的 a - b 的 -1 倍，所以平方了以后就是 1 倍了——也就是说， ( a - b ) ² 是关于 a、 b 对称的。方程的系数本质上就是根的基本对称式，所以 ( a - b ) ² 是可以用方程的系数表示出来的。
现在我们再来看 3 次方程的情况。设方程 x³ - rx² + sx - t = 0 的根为 a、 b、 c，我们取 1 的 3 次原根 ω（ = ），然后考虑 a + bω + cω²。把 a、 b、 c 巡回置换一下这式子就变成了 c + aω + bω²，是原来的 ω 倍。于是把 ( a + bω + cω² ) 三次方一下就变成关于 a、 b、 c 的巡回置换不变的式子了。一般的来说这种方法只能得到关于某种巡回置换不变的式子；我们能否通过不停地取这种关于巡回置换不变的式子而最终达到完全的对称式，决定了最终 a、 b、 c 是否可以用系数的加减乘除和根号表示出来。这也是方程用根号解的可能性与群的可解性联系起来的本质之处。非常幸运的， 3 次置换群模掉 3 阶巡回置换群后得到一个 2 阶巡回群，因此 a、 b、 c 是可以解出来的。具体计算（的概略）如下：
首先我们如果知道了 a + b + c、 a + bω + cω²、 a + bω² + cω，就可以通过解 3 元 1 次方程组求出 a、 b、 c。现在 a + bω + cω² 和 a + bω² + cω 取立方以后都是巡回置换不变的；这里以 a + bω + cω² 为例：

这结果中完全对称的部分，即 a³ + b³ + c³ 和 6abc，都是可以用系数表示出来的；因此我们接下来要求的是 a²b + b²c + c²a 和 ab² + bc² + ca²。这两个式子只有一部分的对称性，但是 3 次置换群作用于它们上面，要么保持各自不变，要么把一个映成另外一个，正是 S₃ 模 C₃ 的商 C₂ 的作用的样子。我们只要知道 a²b + b²c + c²a + ab² + bc² + ca² 和 ( a²b + b²c + c²a ) - ( ab² + bc² + ca² ) 就可以了，而前者已经是对称式，后者 ( a²b + b²c + c²a ) - ( ab² + bc² + ca² ) 的平方是完全对称的式子，可以用系数表示出来。

作用

设有集合 G 作用于集合 A 上。如果 G 是一个群，并且群的乘法和作用的合成是一致的，我们就说群 G 作用于 A 上。如果 G 是不可换的，那么“群的乘法和作用的合成是一致的”这话还会稍微有一点歧意。对于 G 的两个元 σ、 τ，先把 σ 作用于 A 再把 τ 作用于 A，这个合成是由 στ 来对应还是由 τσ 来对应呢？我们把前者称为 G 从右边作用于 A，后者则称为 G 从左边作用于 A。左和右的区别，来自于我们书写的时候，如果把映射写在左边，即对于 A 的元 a，把先作用 σ 再作用 τ 写成 τ ( σ ( a ) )，那么自然的这合成的样子就像是 τσ；反之如果把映射写在右边，记为 ( a^σ ) ^τ，这看起来的样子就像是 στ 了。

如果把群 G 本身看成一个集合，我们比如说可以这样定义群 G 在集合 G 上的作用：对于群 G 的任意一个元 σ， σ 的作用定义为把集合 G 上的每个元都“左乘” σ。即，对于集合 G 的任意元 g， σ 的作用把 g 映到 σg。这显然是从左边的作用。这作用有时被称为“左移动”。同样的我们也可以定义“右移动”。一个左（右）移动显然是集合 G 的一个置换，并且对于不同的 σ，其所对应的置换显然是不同的。于是群 G 就可以看成是集合 G 上的置换群的一个子群。于是我们得到，任何群都是某个置换群的子群。

G 还可以像这样作用于 G 本身：对于群 G 的任意一个元 σ， σ 的作用把 G 的任意元 g 映到 σgσ^-1。这作用的特点是它保持 G 的群结构不变。也就是说，把 G 的任意元 g 映到 σgσ^-1 是 G 的一个自同构。这是因为对于 G 的任意两元 f、 g，我们显然有 ( σfσ^-1 )( σgσ^-1 ) = σ ( fg ) σ^-1。这作用是从左边的，我们也可以同样地定义从右边的作用为， σ 把 G 的任意元 g 映到 σ^-1gσ。对于 G 的元 g 或 G 的子群 U，我们通常把形如 σgσ^-1 的元和形如 σUσ^-1 的子群分别称为 g 和 U 的共轭。于是 U 是正规子群的条件也可以陈述为， U 在取共轭的作用下不变。

一般的如果 X 是具有某种结构的集合，则 X 的所有自同构关于映射的合成做成一个群。这群一般写为 Aut ( X )。由于我们通常是把映射写在左边，所以默认 Aut ( X ) 是从左边作用于 X。如果 X 仅仅是一个集合，那么 Aut ( X ) 当然就是 X 上的置换群。在上一段中我们看到，取共轭的作用是 G 的自同构，因此把 G 的元 σ 映到“取关于 σ 的共轭”这也就给出了一个从 G 到 Aut ( G ) 的同态映射。这同态映射的核称为 G 的中心，记为 Z ( G )，显然 Z ( G ) 是由“与 G 中所有元都可换的元”所组成的。同态映射的像记为 In ( G )，称为 G 的内部自同构群。 In ( G ) 是 Aut ( G ) 的正规子群，因为假如有一个 Aut ( G ) 的元也就是 G 的自同构 γ，我们依次将：γ^-1、关于 G 中某个元 σ 的共轭、 γ，作用于 G 中某个元 g，得到的也仍然是 g 的共轭（这也就是说 γ In ( G ) γ^-1 ⊆ In ( G )）：

Aut ( G ) / In ( G ) 记为 Out ( G )，称为 G 的外部自同构群。

直积，半直积

设群 G 有一个正规子群 N 和一个子群 H。我们已经知道 NH = HN 是 G 的子群，现在假设 NH = G 并且 N ∩ H = { 1 }。由 NH = G 我们知道 G 中的每个元都可以表示成 nh（ n∈N， h∈H）的样子，现在我们证明当 N ∩ H = { 1 } 时这表示是唯一的：如果 n₁h₁ = n₂h₂，则 n₂^-1n₁ = h₂h₁^-1，这等式的左边是 N 的元，右边是 H 的元，所以它们都等于 1。于是 n₁ = n₂， h₁ = h₂。接下来我们考虑 G 中两个元 n₁h₁ 和 n₂h₂ 的积。把 n₂ 关于 h₁ 的共轭记为 x，我们有 ( n₁h₁ )( n₂h₂ ) = n₁ ( h₁n₂ ) h₂ = n₁ ( xh₁ ) h₂ = ( n₁x )( h₁h₂ )。 N 是正规子群，所以 x 也是 N 的元；于是取关于 h₁ 的共轭是 N 的一个自同构。换句话说就是， H 作用于 N 上，而 n₁h₁ 和 n₂h₂ 的积 ( n₁h₁ )( n₂h₂ ) = ( n₁x )( h₁h₂ ) 描述为： h₁ 和 h₂ 相乘， n₁ 和 n₂ 在 h₁ 作用后的像 x 相乘。这时如果进一步假定 H 是正规的，就有 x = n₂，这是因为

等式的左边括号中是 h₁^-1 的共轭，现在假设 H 是正规的所以这是 H 的元，于是等号左边是 H 的元；而等式的右边，括号中为 x 是 N 的元，所以等号右边是 N 的元。 N ∩ H = { 1 }，所以等号两边都等于 1，于是 x = n₂。

反过来，假设有群 N 和 H，并且规定了 H 在 N 上的作用（也可以说成是，规定了 H 到 Aut ( N ) 的一个同态映射），我们给所有形如 ( n, h )（ n∈N， h∈H）的有序对之间这样来规定乘法：规定 ( n₁, h₁ ) ∙ ( n₂, h₂ ) = ( n₁x, h₁h₂ )，其中 x 是 n₂ 在 h₁ 作用后的像。容易验证所有有序对关于这个乘法做成一个群 G，并且 G 中所有形如 ( 1, h ) 的元组成一个和 H 同构的子群，所有形如 ( n, 1 ) 的元组成一个和 N 同构的正规子群。（把这正规子群也记做N）容易看出这时 G / N 与 H 同构。我们把像这样规定的群 G 称为群 H 作用于群 N 上的半直积。如果 H 在 N 上的作用都是恒等映射，则把 G 称为 H 和 N 的直积。这时 H 和 N 的角色是对称的，因此 ( 1, h ) 们所组成的子群同样是正规的。

综合以上的讨论可知，对于群 G 和它的子群 N、 H， G 分解为 H 作用于 N 上的半直积的充分必要条件是， N 是正规的并且 NH = G， N ∩ H = { 1 }。在这时我们有 G / N 与 H 同构。半直积成为直积的充要条件是 H 也是正规子群。当 G 是加群的时候这件事变得简单了：G 分解为其子群 N 和 H 的直和（因为是加群，直积变成了直和）的充要条件是， N + H = G 并且 N ∩ H = { 0 }。

半直积的例子，比如有平面的（不包括镜像的）全等变换群，这群有“平移”和“绕原点O旋转”两个子群，显然它们的交只有恒等变换，而它们的积是全体（平面的不包括镜像的全等变换总可以描述为“先旋转一个角度，再平移至适当位置”），并且平移群是正规的。（注意旋转群不是正规的。）旋转群在平移群上的作用描述为，如果有一个方向a、距离b的平移和一个x度的旋转，则这旋转作用于这平移后得到的像，是一个把方向a转过了x度而距离仍然保持b不变的平移。

我愿意趁此机会再举一个例子，那就是魔方。而且贴张照片在下面。我很爱拧魔方，即使你没有玩过，至少也该看见过。这显然是一个群，因为我们只要考虑各个面块的位置，魔方的各个状态都可以理解为这六九五十四个面块的置换。（什么？你说每面的中心那块总是不动的？OK，那就六八四十八。）但这只是初学者的浮面的理解。我们现在就用直积的语言来更细致地描述这魔方群 G 的结构。

如果你碰过魔方或者稍具慧眼，一定会看出魔方的基本结构并不是面块，而是位于八个角上的“角块”和十二条棱上的“边块”。会玩魔方的人都知道，如果把魔方拆开（拆成这八个角块和十二个棱块的一堆零碎）再随便装回去，只有十二分之一的概率可以复原。但是这里我们先不考虑拧魔方的具体规则，而假设这些角块和边块是可以随便拆下和装上的，这样一个假想的魔方显然仍然是一个群，而真正的魔方群 G 是这个群的一个子群。我们先来讨论这稍大一些的群 H 的结构。

每个角块固定在其还原位置上可以有三种状态（即这角块上的三个面块的不同配置，在这里我们将其称为角块的旋转），这是一个 3 阶循环群。同样边块的旋转是一个 2 阶循环群。各角块和边块的旋转显然是互不相关的（因为我们现在讨论的是每个角块和边块都可以随便拆下和装上的情形），这意味着 H 有一个由八个 3 阶循环群和十二个 2 阶循环群的直积所构成的子群。把这子群记为 N。而假如我们忽略角块和边块的旋转只注意它们的位置，这显然是一个 8 个元的置换群和一个 12 个元的置换群的直积。所谓“忽略掉……”，用数学的语言来说我们实际上是在考虑 N 的旁系。这旁系做成一个群，所以特别的我们得到 N 是 H 的正规子群。

接下来我们在每个角块的三个面块中选出一个作为“标准面块”，同时在正方体的每个角的三个位置（即与这角邻接的三个面）中选出一个作为“标准位置”，这选择要使得魔方在还原状态的时候标准面块都在标准位置上。同样地定义边块的标准面块和边的标准位置。考虑角块和边块的所有满足条件“标准面块在标准位置上”的配置，这显然是 H 的一个子群，并且这子群正是由一个 8 个元的置换群和一个 12 个元的置换群的直积所构成的。把这子群记为 S，不难确认 S ∩ N = { 1 } 和 SN = H，因此 H 分解为 S 作用于 N 上的半直积。 S 在 N 上的作用是这样子的： S 的元 ( σ, τ )（ σ 是一个 8 个元的置换， τ 是一个 12 个元的置换）作用于 N 的元 ( a₁, a₂, …, a₈; b₁, b₂, …, b₁₂ )（各 a_i 是 3 阶循环群的元，而各 b_j 是 2 阶循环群的元）后得到的像是 ( a_{σ ( 1 )}, a_{σ ( 2 )}, …, a_{σ ( 8 )}; b_{τ ( 1 )}, b_{τ ( 2 )}, …, b_{τ ( 12 )})。这样 H 的结构就被完全记述出来了。

那么 G 是 H 中怎样的子群呢？我们考察拧魔方所允许的操作（即把某个面转动90度），就会发现这些操作总是保持三个量不变。即对于任何一个这样的操作，如果把它所对应的 H 中的元写为 ( ( a₁, a₂, …, a₈; b₁, b₂, …, b₁₂ ), ( σ, τ ) )，则总是有 ∏ a_i = 1、 ∏ b_j = 1 和 sign ( σ ) sign ( τ ) = 1（ sign 表示置换的符号。把这符号看成是 2 阶循环群的元。于是这式子的意思是 σ 和 τ 的符号总是相同的）。反之，从任何一种魔方还原法中都可以看出， H 中满足这三个条件的元总是可以通过若干次允许的操作实现的。因此， G 就是由 H 中所有满足条件 ∏ a_i = 1、 ∏ b_j = 1 和 sign ( σ ) sign ( τ ) = 1 的元 ( ( a₁, a₂, …, a₈; b₁, b₂, …, b₁₂ ), ( σ, τ ) ) 所组成的子群。由于这条件是关于 N 和 S 分别给出的，所以 G 也分解为 G ∩ S 作用于 G ∩ N 上的半直积。并且 G 还是 H 的正规子群，因为它是把 H 映到 C₃ × C₂ × C₂（把元 ( ( a₁, a₂, …, a₈; b₁, b₂, …, b₁₂ ), ( σ, τ ) ) 映到元 ( ∏ a_i, ∏ b_j, sign ( σ ) sign ( τ ) )）的同态映射的核。这同态映射显然是全射，而 C₃ × C₂ × C₂ 正好有 12 个元，这就解释了为什么把魔方拆开再随便装回去（即随便取出群 H 的一元），其复原（这元正好属于 G ）的概率是十二分之一。

（注意：以上的讨论是为了得到对于魔方群 G 的深入一些的理解，其本身并不包含任何魔方还原法。就像纽结理论研究扭结的不变量，其本身也并不包含任何解开扭结的方法一样。如果你是为了寻找一种魔方还原法而来到这里，那么很抱歉，你来错了地方）

群

群是一个集合，在这集合上定义了一种二项演算，也就是说存在一个映射，给这集合的任意两个元的有序对，都对应了这集合的另一个元，作为这两个元关于这种演算的结果。这演算通常称为乘法，两个元 a、 b 关于这乘法进行演算的结果，通常写为 a ∙ b 或者就简略记为 ab。乘法被要求满足下面三个条件：

1. 结合律。 a ∙ ( b ∙ c ) = ( a ∙ b ) ∙ c
2. 存在单位元 e，对任意元 a 都有 e ∙ a = a ∙ e = a
3. 对任意元 a，都存在 a 的逆元 a^-1，满足 a ∙ a^-1 = a^-1 ∙ a = e

如果这乘法还满足交换律 a ∙ b = b ∙ a，则把这群称为加群或Abel群。这时更多地把演算写成加法。群的单位元有时写为 1，Abel群的时候则写为 0。单位元是唯一的，这是因为如果 d 和 e 都是单位元，则根据定义我们有 d = de = e。同样逆元也是唯一的，因为如果 b 和 c 都是 a 的逆元，则 b = bac = c。显然 ( a^-1 ) ^-1 = a。

在一个集合 A 上定义一个满足上面三个条件的演算使其做成一个群，这有时被称为“给集合 A 加上了群的结构”。有一种结构就有保持这种结构的映射。从群 G 到群 H 的映射 f 被称为同态映射，如果 f 满足条件：对于 G 中任意两个元 σ、 τ，总有 f ( στ ) = f ( σ ) f ( τ )。这也可以说成 f 是和两个群中的乘法演算相容的。容易看出同态映射一定把单位元映到单位元，逆元映到逆元。如果一个同态映射是全单射，那它一定是同构，也就是说其逆映射也一定是同态映射。

群的例子有比如说映一个集合 A 到其自身的所有全单射的全体，关于映射的合成做成一个群。映射的合成满足结合律，单位元是恒等映射，逆元正是逆映射。这样的群称为置换群。一般来说，一个“对称”就对应了一个群。所谓对称，是指某事物经过某种变换后仍然保持不变。这时所有这样的变换全体，关于变换的合成做成一个群。可以想见这样做成的一个群的代数性质，会在很大程度上反映出具有这种对称性的那个“某事物”的性质。

群也出现在各种基本的代数对象中。所有整数关于加法做成可换群。所有非 0 有理数关于通常的乘法做成可换群。所有 n 阶正方可逆矩阵关于矩阵的乘法做成所谓“一般线性群”，当 n ≥ 2 时这群是不可交换的。

置换群的元如前所述是映集合 A 到其自身的一个全单射，这有时被称为作用在集合 A 上的一个 置换。一般来说，如果一个集合 Γ 的每个元都对应了映集合 A 到其自身的一个映射，我们就说 Γ 作用在 A 上。而 Γ 的某个元 γ 所对应的这个映射，就被称为 γ 在 A 上的作用。在很多时候， Γ 是一个群，并且这群的乘法和映射的合成是一致的；同时 A 具有某种结构， Γ 的每个元在 A 上的作用都保持这结构不变。由于群的每个元都有逆元，这时 Γ 的每个元都是同构。这样的 Γ 有时被称为 A 的自同构群。

同样对于某个群 G 来说，如果有一个集合 Γ 的每个元都对应了映 G 到其自身的一个同态映射，我们就说 Γ 作用于 G 上，或说 G 是“Γ 上的群”，简称为“Γ-群”。这概念出现于代数中，比如“向量空间”，换个说法就是“体上的加群”。如果把“体”改成“环”，我们有关于“环上的加群”的理论。显然“XX上的群”的概念是群的概念的加强，我们这一节要证明的基本定理，全都适用于这加强之后的概念。 Γ-群 G 到 Γ-群 H 的 Γ-同态映射定义为与 Γ 的作用可换的同态映射 f，即 f 是从 G 到 H 的同态映射，并且满足：对于 Γ 中任意一元 γ 和 G 中任意一元 σ，总有 f ( γσ ) = γ f ( σ )。

一个群是可换的还是非可换的，这中间是有巨大差别的。非常初等的探讨就可以完全勾画出所有有限生成的可换群的结构，这就是被称为“有限生成Abel群的基本定理”的定理。但是对于非可换群，即使我们假定这群是有限的、单纯的（单纯的定义见后），分类也仍然是非常困难的。这分类虽然已经完成，就是被称为“有限单群的分类定理”的东西，但它的证明据说长达两万页，大部分都是繁琐、单调的计算，是几代人的共同努力的结果。这证明时不时会被发现有一点小错误，修修补补的工作似乎一直延续到现在还没有结束。

子群，正规子群，商群

定义。对于一个 Γ-群 G，其子群定义为满足下列条件的 G 的子集 H：

1. H 中任意两元的积仍然属于 H
2. H 中的元的逆元属于 H
3. 对于 Γ 中任意一元 γ 和 H 中任意一元 h， γh 属于 H

注意由条件 1、 2 立即得到单位元属于 H。

设一个 Γ-群 G 有子群 H，则对于 G 的任意两元 σ、 τ， G 的子集 σH 和 τH（ σH 定义为形如 σh ( h∈H ) 的元所组成的集。 τH 也是一样）要么不交，要么相等。这是因为如果 σH 和 τH 相交，即存在 h₁、 h₂ ∈H 满足 σh₁ = τh₂，则对于 H中任意一元 h，都有 σh = τh₂h₁^-1h，而根据子群的定义 h₂h₁^-1h 是 H 的元。这说明 σH ⊆ τH，而显然根据对称性反方向 σH ⊇ τH 也是成立的，于是 σH = τH。

形如 σH 的 G 的子集称为 H 的（左）旁系。由上可知左旁系将 G 分成几个互不相交的部分。对于右旁系也是一样。左旁系和右旁系一般说来是不同的，当它们相同的时候子群 H 称为 G 的正规子群。更具体的说，正规子群是指 G 中满足这样条件的子群 H：对于 G 中任意一元 σ 都有 σH = Hσ。如果 G 是可换的，当然 G 的任意子群都是正规的。

设一个 Γ-群 G 有正规子群 H，则 H 的所有旁系做成的集合自然地具有 Γ-群的结构。换句话说，在 G 上规定这样一个等价关系 ~： σ ~ τ 当且仅当 σH = τH。关于这个等价关系的等价类（即旁系）所做成的集合（即商集合）自然地具有 Γ-群的结构。如我在前文《关系》中所说的，一个集合的商集合可以理解为“还是那个集合，只不过把其中的一些元看成是一样的”，或者说同样的元有不同的表示。现在在 G 中已经定义了乘法和 Γ 的作用，我们所要确认的只是这定义在商集合中仍然是well-defined的——即不管我们采用什么样的表示，结果都是一样的。为了看出这一点，把形如 ab ( a∈σH, b∈τH ) 的所有元组成的集合记为 ( σH )( τH )，则 ( σH )( τH ) = ( σH )( Hτ ) = σ ( HH ) τ ⊆ σHτ = στH，即不管我们从 σ 和 τ 的等价类中选择了哪两个元，它们的积最后都是属于 στ 的等价类的，于是我们看到积是well-defined的。同样，对于 Γ 中任意一元 γ，因为 γ 是群的同态映射，所以 γ ( σH ) = ( γσ )( γH )，而由子群的条件 3 我们有 γH ⊆ H，所以 γ ( σH ) ⊆ ( γσ ) H，于是 γ 的作用也是well-defined的。这样在 G 的商集合上乘法和 Γ 的作用都定义好了，由于这是由原来的群 G 上的乘法和作用诱导出来的，显然它们确实满足乘法和作用所应该满足的条件（结合律什么的），因此这确实做成了一个 Γ-群。这群称为 G 的商群，记为 G / H。

同构定理

定义。设有 Γ-群 G、 H 以及 Γ-同态映射 f: G → H，我们把 f ( G ) 称为 f 的像，记为 Im f。把 f^-1 ( e )（ e 是 H 的单位元）称为 f 的核，记为 Ker f。

定理。 Im f 是 H 的子群， Ker f 是 G 的正规子群。

证明。由 Γ-同态映射的定义，这基本上是显然的。 Ker f 是正规的，因为对于 G 的任意一元 σ，有 σ ( Ker f ) = f^-1 ( f ( σ ) ) = ( Ker f ) σ。（证毕）

设一个 Γ-群 G 有正规子群 H，则从 G 到 G / H 的标准映射（把 G 的元 σ 映到 σ 的旁系）显然是一个全射并且是 Γ-同态，而它的核显然是 H。这件事的反之也是成立的，这就是第一同构定理。（总共有三个同构定理，它们是如此的显然以至于我几乎都不知道该如何写证明。请你也把它们如同常识一样融入自己的血液里）

定理。（第一同构定理）设有 Γ-群 G、 H 以及全射 Γ-同态映射 f: G → H。把 Ker f 记为 U，则 f 自然诱导出从 G / U 到 H 的同构。更一般的，“G 中包含 U 的子群” M 与“H 的子群” N 之间存在一一对应，这对应由 M |→ f ( M ) 和 N |→ f^-1 ( N ) 给出。如果 G 中某个包含 U 的子群 P 像这样对应于 H 的一个子群 Q，则 f 自然诱导出从 P / U 到 Q 的同构。

证明。对于 G 的任意一元 σ，其关于 U 的旁系正是 G 中其像与 σ 相同的所有那些元的的集合。因此 f 自然诱导出从 G / U 到 H 的全单射。接下来只要确认在 G / U 中定义的乘法和 Γ 的作用是与 H 中的一致的，这由 f 是 Γ-同态立得。后半部分子群的一一对应，只要注意对于 G 中任意一个包含 U 的子群 M，如果 x∈M，就一定有 xU ⊆ M。因此 M 一定是由若干个 U 的旁系拼成的。（证毕）

定理。（第二同构定理）设有 Γ-群 G 和 G 的正规子群 U。则对于 G 的任意子群 M， MU = UM（ MU定义为形如 ab ( a∈M, b∈U ) 的所有元组成的集合， UM 也是一样）是 G 的子群， M ∩ U 是 M 的正规子群，并且 MU / U 与 M / ( M ∩ U ) 同构。进一步，如果 M 也是正规的，则 MU 和 M ∩ U 都是 G 的正规子群。

证明。因为 U 是正规的，MU = UM 是显然的。不难确认 MU 关于乘法、取逆元、Γ 的作用都是封闭的，于是 MU 是子群。对于 M 的元 m，显然 m ( M ∩ U ) = ( mM ) ∩ ( mU ) = M ∩ ( Um ) = ( M ∩ U ) m，所以 M ∩ U 是 M 的正规子群。如果 M 是正规的，则对于 G 的任意元 σ 都有 σ ( MU ) = ( σM ) U = MσU = ( MU ) σ 和 σ ( M ∩ U ) = ( σM ) ∩ ( σU ) = ( Mσ ) ∩ ( Uσ ) = ( M ∩ U ) σ，于是 MU 和 M ∩ U 都是 G 的正规子群。剩下我们要证明 MU / U 与 M / ( M ∩ U ) 同构，为了看到这一点我们考虑标准映射 f: G → G / U，容易知道 f^-1 ( f ( M ) ) = MU，于是由第一同构定理我们知道 MU / U 与 f ( M ) 同构。另一方面如果把 f 限制在 M 上，考虑全射 f |_M: M → f ( M )，显然 f |_M 的核是 M ∩ U，于是再次根据第一同构定理，我们有 M / ( M ∩ U ) 与 f ( M ) 同构。（证毕）

定理。（第三同构定理）设有 Γ-群 G 和 G 的正规子群 U，并设 M 是 G 的包含 U 的子群。则 M / U 是 G / U 的正规子群当且仅当 M 是 G 的正规子群，进一步当这条件成立时我们有 G / M 与 ( G / U ) / ( M / U ) 同构。

证明。考虑商群的定义，这基本上是显然的。（证毕）

Jordan-Hölder定理和极大极小条件

同构定理的一个几乎是立即的应用体现在Jordan-Hölder定理中。为了说明这个定理我们需要先做一些定义。

定义。我们说一个 Γ-群 G 是单纯的，如果 G 的正规子群只有 { 1 } 和 G 全体。

由第一同构定理，我们知道一个单纯群 G 的同态像要么是单位元，要么就与 G 同构。

定义。Γ-群 G 的一个递降子群链 G = G₀ ⊃ G₁ ⊃ … ⊃ G_{n - 1} ⊃ G_n = { 1 } 如果满足条件：对于任意的 i， G_{i + 1} 是 G_i 的正规子群，并且 G_i / G_{i + 1} 是单纯的。就把这递降子群链称为 G 的组成链。各个 G_i / G_{i + 1}称为 G 的组成因子，n 称为组成链的长度，简称为 G 的长度。

设 Γ-群 G 有组成链 G = G₀ ⊃ G₁ ⊃ … ⊃ G_{n - 1} ⊃ G_n = { 1 }，其组成因子依次为 H₁、 H₂、…、 H_n。这时对于 G 的任意正规子群 N，我们把 N ∩ G_i 记为 P_i，把 G_i 在 G / N 中的像记为 Q_i。

命题。在上述假定下， N = P₀ ⊇ P₁ ⊇ … ⊇ P_{n - 1} ⊇ P_n = { 1 } 和 G / N = Q₀ ⊇ Q₁ ⊇ … ⊇ Q_{n - 1} ⊇ Q_n = { 1 } 分别是 N 和 G / N 的（可能重复的）组成链，并且 H₁、 H₂、…、 H_n 正好被分配到这两条组成链中。也就是说，对于任意的 i，要么 P_i / P_{i + 1} 与 H_{i + 1} 同构而且 Q_i = Q_{i + 1}，要么 Q_i / Q_{i + 1} 与 H_{i + 1} 同构而且 P_i = P_{i + 1}。

证明。首先我们证明，对于任意的 i， P_{i + 1} 是 P_i 的正规子群，Q_{i + 1} 也是 Q_i 的正规子群：P_i = N ∩ G_i 是 G_i 的子群，而 G_{i + 1} 是 G_i 的正规子群，所以 P_{i + 1} = P_i ∩ G_{i + 1} 是 P_i 的正规子群； Q_i 可以看成是 G_i / ( N ∩ G_i )，而 G_{i + 1} 是 G_i 的正规子群，所以 ( N ∩ G_i ) G_{i + 1} 也是 G_i 的正规子群，于是 Q_{i + 1} = ( ( N ∩ G_i ) G_{i + 1} ) / ( N ∩ G_i ) 就是 G_i / ( N ∩ G_i ) 的正规子群。接下来我们有：

由于 G_i / G_{i + 1} = H_{i + 1} 是单纯的，而 ( N ∩ G_i ) G_{i + 1} 是 G_i 的正规子群，所以要么 ( N ∩ G_i ) G_{i + 1} = G_i，要么 ( N ∩ G_i ) G_{i + 1} = G_{i + 1}。（证毕）

定理。（Jordan-Hölder） G 的组成链如果存在，则其长度是一定的，而且组成因子（不记顺序但包括重复度）是唯一的。

证明。关于组成链的长度使用归纳法。如果 G 有一个长度为 1 的组成链，则 G 是单纯的，命题显然成立。现在假设 G 有一个长度为 n 的组成链 G = G₀ ⊃ G₁ ⊃ … ⊃ G_{n - 1} ⊃ G_n = { 1 }，要证明的是这时对于 G 的任意组成链 G = F₀ ⊃ F₁ ⊃ … ⊃ F_{m - 1} ⊃ F_m = { 1 }，都有 m = n 并且组成因子相同。由上面的命题， F₁ 具有长度为 n - 1 的组成链（考虑 F₁ 与各 G_i 的交），于是可以使用归纳法的假定。（证毕）

注意这里组成因子虽然是唯一的，但一般来说组成链绝不是唯一的。比如 6 阶循环群 C₆，显然 C₆ ⊃ C₃ ⊃ { 1 } 和 C₆ ⊃ C₂ ⊃ { 1 } 都是它的组成链。

接下来我们讨论 G 的组成链存在的条件。

定理。如果 G 是有限的，则存在组成链。

证明。取 G 的所有正规真子群的（关于包含关系的）极大元 G₁（由于 G 是有限的，这总是可以取到的），然后取 G₁ 的所有正规真子群的极大元 G₂， G₂ 的所有正规真子群的极大元 G₃，……这样一直取下去，仍然由于 G 是有限的，所以一定会在有限回的操作后到达 { 1 }。这样取出来的递降子群链显然是组成链。（证毕）

从这证明中容易看出，组成链存在的关键在于“取XXX的极大元”和“这样一直取下去，一定会在有限回操作后到达 { 1 }”这两件事。当 G 为可换群时，这两件事陈述为极大和极小条件。

命题。对于 Γ-加群 M，以下两个条件是等价的：

1. 不存在 M 的子群的无穷的严格递增链。
2. M 的随便一些子群所组成的集合总有（关于包含关系的）极大元。

证明。首先如果存在 M 的子群的无穷的严格递增链，则出现在这递增链中的所有子群构成的集合显然没有极大元。反过来，如果存在一个由 M 中某些子群构成的集合没有极大元，则在这集合中取一元 M₀，由于 M₀ 不是极大，就又有严格包含它的 M₁，而且 M₁ 也不是极大，于是又有严格包含 M₁ 的 M₂，像这样一直取下去（选择公理！参看前文《再说一点集合论》），就得到了一个 M 的子群的无穷的严格递增链。（证毕）

定义。我们把上面命题中等价的两个条件称为极大条件。同样地也定义极小条件。满足极大条件的加群称为Nöther加群，满足极小条件的加群称为Artin加群。

定理。 Γ-加群 M 具有组成链，当且仅当 M 满足极大和极小条件。

证明。如果 M 满足极大和极小条件，则 M 具有组成链，这和有限群的情况完全类似。反过来的主张是下面这个命题的显然的归结：

命题。设有 Γ-加群 M 和 M 的子群 N。则 M 满足极大（小）条件当且仅当 N 和 M / N 满足极大（小）条件。

证明。由于 N 的子群也是 M 的子群，并且 M / N 的子群和 M 中包含 N 的子群一一对应，所以如果 M 满足极大（小）条件，显然 N 和 G / N 也满足极大（小）条件。反过来，对于 M 中的递增（降）子群链，这子群链与 N 的交以及在 M / N 中的像显然分别是 N 与 M / N 中的子群链。如果 N 与 M / N 满足极大（小）条件，这 N 与 M / N 中的子群链总会停止。于是我们只要证明下列命题即可：
“对于 M 的子群 M₁ ⊇ M₂，如果 M₁ ∩ N = M₂ ∩ N 并且 M₁ + N = M₂ + N，则 M₁ = M₂”
这命题成立是因为：
（证毕）

满足极大和极小条件的加群的例子，比如说体上的有限维向量空间。容易证明体上的一维向量空间（作为体上的加群来说）是单纯的，因此对于体上的有限维向量空间，考虑其每次递减一维的子空间链，这显然构成一个组成链。而Jordan-Hölder定理说，组成因子是唯一的，于是就特别地得到，体上的有限维向量空间的维数是确定的。我们甚至没有使用解多元一次方程组的消元法之类，而完全用抽象的一般论就得到了这个结果。更一般的说，Artin环（体也是Artin环的特例）上的有限生成加群总是满足极大和极小条件的，这是因为我们有“Artin环一定是Nöther环”这一显著的结果。

最后给出极大条件的另一个等价的说法。

定义。对于 Γ-群 G 和 G 的任意子集 S，考虑所有包含 S 的 G 的子群们的交，这显然也是 G 的子群，并且是包含 S 的最小的子群。把这子群称为 S 生成的群，写为 <S>。 S 则称做 <S> 的生成系。显然 <S> 是由 S 中的元经过有限次的相乘、取逆和 Γ 的作用后所能够得到的所有元组成的。当 G 具有有限的生成系时，就称 G 是有限生成的。特别的，由一个元生成的群称为循环群。

定理。 Γ-加群 M 是Nöther加群（即满足极大条件），当且仅当 M 的任意子群都是有限生成的。

证明。假设 M 满足极大条件。这时对于 M 的任意子群 N，从 N 中取一个元 n₁，由 n₁生成的子群如果正好等于 N，则 N 当然是有限生成的。如果不是，就再从 N ∖ <{ n₁ }> 中取一个元 n₂。依此类推。由于 M 是满足极大条件的，所以一定会在有限次的操作后生成 N。反之，假设 M 的任意子群都是有限生成的。这时如果有 M 的递增子群链 M₁ ⊆ M₂ ⊆ …，考虑所有 M_i 的合并 ∪ M_i，这显然也是 M 的子群，因此是有限生成的。生成元当然属于 ∪ M_i，而现在它们只有有限个，于是我们可以取充分大的 k 使得 M_k 包含这有限个生成元。另一方面这些生成元生成的子群 ∪ M_i 是所有包含这些生成元的子群中最小的，所以显然子群链中 M_k 之后的部分都不会再严格增大了。（证毕）

选择公理

出于对民主的一贯敬意，我愿意把选择公理理解成“人民要有选择的权利”。这不是你（政府，或者上帝）面对无数个非空的抽象集合时一次从每个集合里都选出一个元；这种强力干涉的独裁手腕是不可能的。我愿意把选择公理理解成，这是那无数个非空的抽象集合们每一个都自发地从自己的元中选举一个出来。当然这跟数学完全没有关系。选择公理的陈述是：

如果 ∀λ∈Λ, A_λ ≠ ∅，则 ∏ A_λ ( λ∈Λ ) ≠ ∅。

这意思是说，如果每个 A_λ 都非空，那么我们给集合 Λ 中的每一个元 λ 对应集合 A_λ 中的一个元，这样的对应是存在的。或者更直白一些，在每个 A_λ 中都选取一个元是可能的。如果一个集合非空，从里面选取一个元当然是可能的。但选择公理保证的是，即使有无限多个集合，甚至是不可数的无限多个，只要每个集合都非空，那我们就可以在一次神秘的操作之后从每个集合里都得到一个元。这中间当然存在逻辑的飞跃。注意在这里我们只知道 A_λ 是集合。如果我们还知道别的一些信息，有时不用选择公理也可以从每个 A_λ 里选出一个元来。比如说假如有无限多双鞋子，我们可以说“从每双鞋中取出左脚穿的那只”，这就没有用到选择公理。但是如果是无限多双袜子，由于袜子是不分左右的，要从每双里取一只出来就难了！

选择公理是非常强有力的公理。首先来看一个简单的应用：

定理。对于非空集合 A、 B，以下两个命题是等价的：
1) 存在从 A 到 B 的单射
2) 存在从 B 到 A 的全射

证明。 1) ⇒ 2) 并不需要借助选择公理。如果存在从 A 到 B 的单射 f，我们当然可以在 f ( A ) 上定义 f 的逆映射。而对于 B ∖ f ( A )，只要在 A 中随便选取一个元，把 B ∖ f ( A ) 都映到那个元就可以。这样定义的从 B 到 A 的映射显然是一个全射。注意这里只做了一次选择，所以是没有借助选择公理的。 2) ⇒ 1) 如果存在从 B 到 A 的全射，则对于 A 的每个元 a， f^-1 ( a ) 都非空。所以根据选择公理我们可以从每个 f^-1 ( a ) 中选出一个元 b_a。把 a 映到 b_a 定义了一个从 A 到 B 的映射，而 f^-1 ( a ) 们显然是互不相交的，所以这是一个单射。（证毕）

在数学中我们常常会想要做无限次的操作。比如说我们想要这么证明“ ℕ 是最小的无限集合”：对任意无限集合 A，显然 A 非空，所以从里面取出一个元 a₀。 A 是无限的，所以 A ∖ { a₀ } 也是无限的，于是又可以从里面取出一个元 a₁，……依此类推，我们就得到了一个从 ℕ 到 A 的单射。这个“证明”的省略号省略得有没有道理？一般来说无限次的操作是不被允许的。我们可以归纳地定义自然数的函数 f ( n )（也就是说，用 f ( 0 ), f ( 1 ), …, f ( k - 1 ) 的值来规定 f ( k )），这是因为本质上对于每一个 n 我们只要经过有限的操作就可以得到 f ( n ) 的值。但是这个“证明”中的并不是一个归纳的定义。所谓“取出一个元”是有任意性的。如果 A 只是一个抽象的集合，我们就没有办法明确规定到底取出的是哪一个元。那么选择公理呢？选择公理保证我们可以做无限次的选出操作。但是选择公理保证的是同时的、相互独立的选出操作，在这里每一个元的选出都依赖于以前做出的选择。所以看起来这个省略号是欠缺说服力的？然而只要稍用一点技巧，像这样的直观论证是可以通过选择公理来正当化的。

定理。 ℕ 是最小的无限集合。

证明。假设集合 A 是无限的，则对于 A 的任意有限子集 U， A ∖ U 都非空。于是根据选择公理，我们可以给每个有限子集 U 对应一个 A ∖ U 中的元。把这元记为 a_U。 ∅ 当然是 A 的有限子集，所以对应了一个元 a₀。现在我们定义把 0 映到 a₀。 { a₀ } 也是 A 的有限子集，所以也对应了一个元 a₁，然后定义把 1 映到 a₁。同样 { a₀, a₁ } 也是 A 的有限子集，所以对应了一个元 a₂, … 一般地，我们把有限子集 { a₀, a₁, …, a_k } 所对应的元记为 a_{k + 1}，然后定义把 k + 1映到 a_{k + 1}。这样就归纳地定义了一个从 ℕ 到 A 的函数，它显然是单射。（证毕）

接下来你也许会想用同样的直观论证来证明“任意两个集合都是可比较的”：从集合 A 中取一个元 a，让它对应集合 B 中的一个元 b。如果 A ∖ { a } 已经是空集，我们就得到了一个单射。而如果 B ∖ { b } 是空集，我们就得到了一个全射。如果都不是，那就可以再分别从 A ∖ { a } 和 B ∖ { b } 中各取出一个元来互相对应，这样一直进行下去，最后总会得到一个单射或者全射。然而遗憾的是，在这里集合 A 可能是不可数的，所以我们的严密论证不能再像前面的证明那样直接地使用归纳的定义了。解决这个问题方法来自于对“数数”这个直观概念中所蕴涵的逻辑的深入发掘，这发掘给我们带来了所谓的“超限归纳法”。使用超限归纳法再加上上面定理的证明中那样的技巧，我们能够得到一个非常具有通用性的框架来把“像这样的直观论证”化成严密的数学论证。

良序集合

良序集合的概念是关于“数出来的自然数”这一概念的扩张，从直观上来说良序集合简直也就是“可以数出来”的。

定义。把满足下列条件的偏序集合 X 称为良序集合： X 的任意非空子集都有最小元。显然良序集合的任意子集也是良序集合。

ℕ 是一个良序集合，这是因为对于 ℕ 的任意非空子集 V，只要从 V 中取出一个元 v，比 v 小的自然数就只有有限个，所以其中当然有一个是 V 的最小元。

定理。良序集合是全序集合。
证明。对于良序集合的任意两个元 a、 b， { a, b} 做成一个子集，这子集有最小元，所以当然 a 与 b 是可比较的。（证毕）

定义。对于一个元 a，如果 a < b 而且不存在满足 a < x < b 的元 x，就把 b 称为 a 的后继。
定理。良序集合除最大元之外的每个元都有后继。
证明。对良序集合的任意元 a，如果 a 不是最大元则集合 { 严格大于 a 的元全体 } 非空，这集合的最小元就是 a 的后继。（证毕）

定义。对于良序集合 X 和 X 的任意元 a，定义 X_a := { x∈X | x < a }，称为 X 的a-切片。显然一个切片 X_a 满足条件“比 X_a 中某个元小的所有元都属于 X_a”。反过来，如果 X 的任意真子集 A 满足这个条件，它就是 X 的一个切片：我们只要取 X ∖ A 的最小元 b，易知 A = X_b。

定理。（超限归纳法）假设对一个良序集合 X 的每个元都规定了一个命题P。这时如果 1) P对于 X 的最小元成立；2) 对于 X 的任意元 a，只要命题对 X_a 的每个元成立，它就对 a 成立。 这两个条件满足，P就一定对 X 的所有元成立。
证明。假设集合 { a∈X | P对 a不成立 } 不为空，就一定有最小元 b。由于P对于 X 的最小元成立，所以 b 不是 X 的最小元。这时切片 X_b 不为空且P对 X_b 的每个元都成立，所以P也应该对 b 成立，矛盾。（证毕）

定理。对于任意良序集合 X：
1) 如果 f: X ← X 是保持顺序不变的单射，则 ∀x∈X, x ≥ f ( x )。
2) ∀a∈X, X 与 X_a（作为偏序集合）不同构。同样 ∀ a, b ∈X, 只要 a、 b 不同， X_a 与 X_b 就不同构。
证明。 1) 假设集合 A := { a∈X | f ( x ) < x } 不为空，取它的最小元 b。我们有 f ( b ) < b，而 f 是保持顺序不变的单射，所以 f ( f ( b ) ) < f ( b )，于是 f ( b ) ∈ A，这和 b 的定义矛盾。 2) 假设有从 X 到 X_a 的同构 f。 X_a 是 X 的子集，所以 f 可以看成是从 X 到 X 的保持顺序不变的单射，并且 f ( a ) ∈X_a 所以 f ( a ) < a，由 1) 这是不可能的。对于 X_a 和 X_b 也是一样。（证毕）

定理。（良序集合的比较定理）对于良序集合 X、 Y，以下三种情况总有唯一一种成立：
1) X 与 Y 同构
2) X 与 Y 的某一切片同构
3) Y 与 X 的某一切片同构

证明。定义 X 的子集 U := { x∈X | X_x 与 Y 的某个切片同构 }。则对于 U 的任意元 u， X_u 就与 Y 的某个切片 Y_y 同构。而根据前定理，这 y 是由 u 所唯一确定的。于是我们规定把 u 映到这样的 y 就定义了一个从 U 到 Y 的映射 f， f 显然是单射且保持顺序不变（这映射 f 相当于是说，如果在所有比 x 小的元上定义了对应，就自然地把这对应扩张到 x 上）。如果 f 是全射且 U = X，当然 X 与 Y 同构；如果 f 是全射但 U 是 X 的真子集，由于 U 显然满足条件“比 U 中某个元小的所有元都属于 U”，所以 U 是 X 的一个切片，于是 Y 与 X 的某一切片同构。而如果 f 不是全射，显然 f ( U ) 是 Y 的一个切片，这时假如 U 也是 X 的真子集则 U 等于一个切片 X_b 并且 X_b 与 Y 的切片 f ( U ) 同构。可是 b∉U，这与 U 的定义矛盾。所以 U 必须等于 X，于是 X 与 Y 的某一切片同构。（证毕）

定理。如果良序集合 X 和 Y 同构，则同构映射是唯一的。

证明。设有两个同构 f、 g，我们用超限归纳法证明 ∀x∈X, f ( x ) = g ( x )：首先 f 和 g 都把 X 的最小元映到 Y 的最小元，所以对 X 的最小元命题成立；然后假设 f 和 g 在切片 X_a 上是一致的，这时由于 f ( X_a ) = g ( X_a ) 是 Y 上某个元 b 的 b-切片，所以 f 和 g 都必须把 a 映到 b。（证毕）

Zorn引理

应用良序集合的理论结合选择公理的技巧，Zorn引理提供了一个把我们的直观论证化成严密数学论证的非常方便的框架。

定义。我们把满足下面条件的偏序集合 A 称为归纳的：对于 A 的任意良序子集 V，在 A 中总有一个元要大于 V 中所有的元。（大于的意思包括等于）

定理。（Zorn引理）任意一个非空的归纳的偏序集合 A 都有极大元。更细致的说，我们从 A 的任意元 x 开始，“数过一个良序集合之后”，总能到达一个极大元。也就是说，对于 A 的任意元 x，总存在一个 A 的良序子集 V 满足： x 是 V 的最小元， V 有最大元，而且那个最大元是 A 的极大元。

证明。从直观上来说，我们可能想这么证明：从 A 中取一个元，如果它已经是极大的那当然好。如果不是，就有比它大的另一个元，像这样不停的取下去就做成了一个良序子集。然后又有比这良序子集大的元，如果它还不是极大，就再取比它大的，这样一直取下去，最后比把取出来的所有这些元都大的应该就是极大元了吧。这论证当然绝不能算严密，但严密的论证本质上也就是这么做的。
对于 A 的任意一个以 x 为最小元的良序子集 T，把比 T 中所有元都大的元的集合记为 S_T。因为 A 是归纳的，所以 S_T 非空。如果 S_T ⊆ T，这也就是说 S_T 中的元比 T 的元都大而其本身又属于 T，这时当然 S_T 中只能有一个元就是 T 的最大元。但 S_T 是比 T 中所有元都大的元的集合，它只有一个 T 的最大元说明 A 中再没有比这个最大元更大的了，因此这个 T 的最大元就是 A 的极大元。如果对于任何 T， S_T都不被包含在 T 里面，则根据选择公理，我们可以给每个 T 对应一个 S_T ∖ T 的元 f ( T )。我们将证明这会导致矛盾。
导致矛盾的战略是，从 x 出发， { x } 是 A 的良序子集，所以对应了一个元 f ( { x } )，把 f ( { x } ) 记为 x₁。然后 { x, x₁ } 也是 A 的良序子集，所以对应了一个 f ( { x, x₁ } )……把所有这些搜集起来，这整个也是一个良序集合，于是又有比它大的新的元，但这和“把所有这些搜集起来”的定义矛盾。严密的论证如下：
把 R 定义为所有满足下列条件 (*) 的 A 的良序子集 X 的集合： X 的最小元为 x 且对于 X 的任意切片 X_a 都有 a = f ( X_a )。我们将证明，对于 R 中任意两个元 X、 Y，要么 X = Y，要么 X 是 Y 的切片或 Y 是 X 的切片。这样一来把 R 中所有元合并起来就仍然是一个良序子集，对这个良序子集 T 定义了一个 f ( T )， T ∪ { f ( T ) } 也满足条件 (*) 所以属于 R，但 f ( T ) 又不是 T 的元，这和 T 的定义是矛盾的。
至于为什么对于 R 中任意两个元 X、 Y，要么 X = Y，要么 X 是 Y 的切片或 Y 是 X 的切片，这是因为由良序集合的比较定理可得要么 X 和 Y 同构，要么 X 和 Y 的切片同构或 Y 和 X 的切片同构，不妨设 X 和 Y 同构，这时设同构映射为 h: X → Y，我们用超限归纳法证明 h 是恒等映射：首先 X 和 Y 的最小元都是 x，所以命题对最小元成立。然后假设在切片 X_s 上 h 是恒等映射，设 h ( X_s ) 是 Y 的 t-切片，由于 X 和 Y 都满足条件 (*)，所以 s = f ( X_s )， t = f ( h ( X_s ) ) = f ( X_s )，所以 t = s，而 h 是同构所以必须把 s 映到 t。（证毕）

Zorn引理的应用非常广泛，单在集合论里就做出强有力的结论。

定理。（Zermelo的良序定理）对于任意集合 A 都存在适当的顺序使得 A 成为良序集合。

证明。考虑所有这样的有序对 ( U, ≤ )：其中 U 是 A 的子集而 ≤ 是 U 上的一个良序。对任意两个 ( U, ≤₁ )、( V, ≤₂ )，我们说 ( U, ≤₁ ) 比 ( V, ≤₂ )“小”当且仅当 U、 V 包括良序结构完全相等或者 U 是 V 的切片。这是一个归纳的偏序关系，所以有极大元 ( W, ≤ )。如果 W 不等于 A，在 A ∖ W 上任选一元 a，在 W ∪ { a } 上定义顺序“W 上保持已有顺序不变， a 大于所有的元”这就做成了一个良序集合而且 W 是它的切片。这和 W 的极大性矛盾。（证毕）

推论。任意两个集合都是可比较的。这由良序集合的比较定理即得。

推论。对于任意集合 A，都存在集合 B，其浓度严格大于 A，并且是所有浓度严格大于 A 的集合中浓度最小的。

证明。 X := ℘ ( A ) 的浓度严格大于 A，由Zermelo的良序定理可以把 X 看成良序集合，X 的子集 { x∈X | X_x 的浓度严格大于A } 如果非空就取其最小元 b 的切片 X_b、否则的话取集合 X，就是满足条件的集合 B。这是因为对于任意浓度严格比 A 大的集合 C，由Zermelo的良序定理把它看成良序集合，再由良序集合的比较定理得要么 B 与 C 同构，要么 B 与 C 的切片同构或反之，而由 B 的定义， C 与 B 的切片同构是不可能的。（证毕）

定理。对于任意无限集合 A，都有 A ~ A ∐ A ~ A × A。

证明。对于无限集合 A，由于 ℕ 是最小的无限集合，因此可以在 A 中找出一个子集 V₁ 与 ℕ 同等。如果 A ∖ V₁ 仍然是无限的，又可以在里面找出一个子集 V₂ 与 ℕ 同等，依此类推，最后总可以把 A 分成一些与 ℕ 同等的部分和一个有限集合（这是直观论证，严密论证当然是用Zorn引理：考虑所有这样的有序对 ( U, ∐ )：其中 U 是 A 的子集，∐ 是把 U 分成一些与 ℕ 同等的部分的一个分割。定义 ( U, ∐₁ ) 与 ( V, ∐₂ ) 的大小关系为，如果 U 在分割 ∐₁ 下的每一部分，要么正好是 V 在分割 ∐₂ 下的一部分，要么与 V 不相交。这时就说 ( V, ∐₂ ) 比 ( U, ∐₁ ) 小。确认这是归纳的偏序关系，并且其极大元正是把 A 分成了一些与 ℕ 同等的部分和一个有限集合），把有限集合“吸收”到某个与 ℕ 同等的部分里，于是 A 就被分成了一些与 ℕ 同等的部分的非交和。由于 ℕ ~ ℕ ∐ ℕ，所以 A ~ A ∐ A。
要证明 A ~ A × A，考虑所有这样的有序对 ( U, f )：其中 U 是 A 的子集，f 是一个把 U × U 映到 U 上的一一映射。（这样的有序对存在，因为 A 是无限的所以包含 ℕ，而 ℕ ~ ℕ × ℕ）我们说 ( U, f ) 比 ( V, g ) 小，如果 V 包含 U 并且在 U × U 上 f 与 g 相同。这是一个偏序，它是归纳的因为如果 { ( U_i, f_i ) } 是良序子集，我们就可以定义从 ( ∪ U_i ) × ( ∪ U_i ) 到 ∪ U_i 的一一映射。根据Zorn引理，存在一个极大元 ( W, h )，这时如果 A ∖ W 的浓度大于 W，就可以找到一个 W’ ⊆ A ∖ W 与 W 浓度相同。我们有 ( W’ × W ) ∐ ( W × W’ ) ∐ ( W’ × W’ ) ~ W’ ∐ W’ ~ W’，而由于 ( W’ ∐ W ) × ( W’ ∐ W ) = ( W × W ) ∐ ( W’ × W ) ∐ ( W × W’ ) ∐ ( W’ × W’ )，所以我们可以定义这样一个有序对 ( W’ ∐ W, h’ )： h’ 把 W × W 像 h 一样地映到 W，而把 ( W’ × W ) ∐ ( W × W’ ) ∐ ( W’ × W’ ) 一一对应到 W’。这样就定义了一个从 ( W’ ∐ W ) × ( W’ ∐ W ) 到 W’ ∐ W 的一一对应，并且这样的 ( W’ ∐ W, h’ ) 显然是大于 ( W, h ) 的。这与 ( W, h ) 的极大性矛盾，所以 A ∖ W 的浓度小于 W，于是 W ≤ A ≤ W ∐ W ~ W，即 A 与 W 的浓度相同。（证毕）

集合可以说是最简单的结构。或者说简直简单得没有结构。对于一个抽象的集合（意思是说，我们只知道它是一个集合，其他什么也不知道）来说，它的每个元都是完全一样的，元和元的相互之间也没有任何关系——当然，要说的话还是有那么一点关系，我们总是能判断两个元是否相等。从这个角度来看，我们关于一个抽象的集合所能知道的唯一信息，就是它的元的“个数”。这是集合这种“结构”的最重要的“不变量”，也是唯一的不变量。

当然我还根本没有说过所谓“个数”是什么。OK，那现在我就这样来定义：所谓个数，就是指集合的不变量。讲这话并不是找打。我们已经定义了集合的“同构”，也就是一一对应（参看前文《映射》）。所谓“不变量”，当然是指“在同构映射下不变的东西”，于是我们就得到下面的定义：

定义。如果两个集合 A 和 B 是同构的（也就是说它们之间存在一一对应），我们就说它们同等。写做 A ~ B。这显然是一个等价关系（参看前文《关系》）。我们把关于这个等价关系的任意等价类称为个数，或者为了区别于我们的直观，换一个词称做浓度。对于任意一个集合 A，它的浓度当然定义为与 A 同等的所有集合做成的等价类。

从我们的直观上来说，“部分”的个数要比“全体”的个数来的“小”。这句话中已经暗示了一个重要的定理。

首先，所谓“部分”当然可以指“子集”。而鉴于现在我们考虑的同等关系，下面的定义应该是恰当的：

定义。如果存在一个从集合 A 到集合 B 的单射 f: A → B（这时 A 和 f ( A ) 同等），我们就说 A 比 B 小。写做 A ≤ B。

而所谓的“小”，当然不只是说说就算了。我们谈论大小的时候在暗默中就假定了一些事，关于这个请参看前文《关系》。这些“暗默中假定的事”确实成立，这就是下面的定理。

定理。≤ 是一个偏序关系。

证明。显然对任意集合 A 都有 A ≤ A。而如果 A ≤ B， B ≤ C，只要考虑映射的合成我们就有 A ≤ C。这个定理最主要的部分在于，如果 A ≤ B 且 B ≤ A，就一定有 A ~ B。或者换句话说，如果既有从 A 到 B 的单射，又有从 B 到 A 的单射，那就一定有 A 和 B 间的一一对应。这个有时被叫做Bernstein定理，证明如下：
假设有单射 f: A → B 和 g: B → A。我们的战略是把 A、 B 分别分割成 A₁ 和 A₂、 B₁ 和 B₂ 两个不相交的部分，使得 f ( A₁ ) = B₁， g ( B₂ ) = A₂。这样一来显然有 A ~ B。
先假设有这样的分割存在，这时因为 B₁ = f ( A₁ ) ⊆ f ( A )，所以 B₂ 应当要包含 B ∖ f ( A )。我们把 B ∖ f ( A ) 记为 C₀。 C₀ 既然被包含在 B₂ 里面， g ( C₀ ) 当然被包含在 A₂ 里，而 f 是单射，所以 f ∘ g ( C₀ ) 也一定被包含在 B₂ 里。依此类推，我们把 f ∘ g ( C₀ ) 记为 C₁， f ∘ g ( C₁ ) 记为 C₂，… ， f ∘ g ( C_k ) 记为 C_{k + 1}，… ，显然 B₂ 应当包含所有 C_k。
我们将证明，把 B₂ 定义为所有 C_k 的合并就可以了。这时令 A₂ = g ( B₂ )， A₁ = A \ A₂， B₁ = B ∖ B₂，剩下我们只要证明 f ( A₁ ) = B₁。由于我们最早已经把 B ∖ f ( A ) 包含在 B₂ 里面了，所以 B₁ = B ∖ B₂ 当然被包含在 f ( A ) 里。 f 是单射，所以 f ( A ) 分成 f ( A₁ ) 和 f ( A₂ ) 两个不相交的部分，而根据 B₂ 的定义我们有 f ( A₂ ) = f ( g ( B₂ ) ) = f ∘ g ( B₂ ) ⊆ B₂，所以当然 f ( A₁ ) = B₁。（证毕）

定理。对任意集合 A、 B、 C，我们有
1) ( A ∐ B ) × C ~ ( A × C ) ∐ ( B × C )
2) A^B × A^C ~ A ^{B ∐ C}
3) ( A × B )^C ~ A^C × B^C
4) ( A^B ) ^C ~ A^{B × C}
5) ℘ ( A ) ~ 2^A
注意 ∐ 和 × 分别代表非交和与笛卡儿积， ℘ ( A ) 代表幂集合（参看前文《集合》），而 A^B 表示从 B 到 A 的所有映射的集合， 2 则表示集合 { 0, 1 }。

证明。考虑这些集合的意义，定理基本是显然的。这里证明 4) 和 5) 做为例子。4) ( A^B ) ^C 的元是从 C 到 A^B 的映射，把它写成 f。于是对于任意的 c∈C， f ( c ) 是 A^B 的元也就是从 B 到 A 的映射，于是 f ( c ) 把 B 中的元 b 映到 A 中的元 f ( c ) ( b )。所以合起来说 f 正好就是把 B × C 的元 ( b, c ) 映到 A 中的元 f ( c ) ( b )。 5) 对 A 的任意一个子集 U，我们定义从 A 到 { 0, 1 } 的映射 f_U 为：如果 x∈U 则 f_U ( x ) = 1，否则 f_U ( x ) = 0。这显然是 ℘ ( A ) 和 2^A 的一个一一对应。（证毕）

定理。把所有自然数的集合记为 ℕ。我们有
1) ℕ ∐ ℕ ~ ℕ
2) ℕ × ℕ ~ ℕ

证明。 1) ℕ = { 奇数 } ∐ { 偶数 }。映射 n |→ 2n 给出了一个从 ℕ 到 { 偶数 } 的全单射，所以 { 偶数 } ~ ℕ。对于 { 奇数 } 也是一样。
2) 像这样列出 ℕ × ℕ 的所有的元： ( 1, 1 ); ( 1, 2 ), ( 2, 1 ); ( 1, 3 ), ( 2, 2 ), ( 3, 1 ); ( 1, 4 ), ( 2, 3 ), ( 3, 2 ), ( 4, 1 ); ……; ( 1, k ), ( 2, k - 1 ), …, ( k - 1, 2 ), ( k, 1 ); ( 1, k + 1 ), …… 把把这序列从头开始往后依次编为 1 号， 2 号， 3 号， … 这就给出了从 ℕ × ℕ 到 ℕ 的一个一一对应。如果你有兴趣，可以试着把这对应用式子写出来。（证毕）

ℕ 的浓度通常称为可数浓度。可数浓度的集合称为可数集合。
推论。有理数集 ℚ 是可数的。这是因为显然 ℕ ≤ ℚ ≤ℕ × ℕ，而前定理的 2) 说 ℕ × ℕ ~ ℕ。

定理。（Cantor的对角线论法） A < ℘ ( A )。

证明。显然 A ≤ ℘ ( A )。所以我们只要证明 A 和 ℘ ( A ) 间不存在一一对应。假设有这样一个对应，对于 A 的每个元 a 都对应了一个 A 的子集 U_a。 a 可能属于 U_a 也可能不属于 U_a。所以我们考虑集合 V := { a∈A | a∉U_a }，这也是 A 的一个子集，所以对应了一个 A 的元 b。但不论 b 属于 V 或不属于 V 都会引发矛盾。这矛盾是由假定 A 和 ℘ ( A ) 间存在一一对应而产生的，所以结论是 A 和 ℘ ( A ) 间不可能存在一一对应。（证毕）

℘ ( ℕ ) 的浓度通常称为连续浓度。由以上定理知它严格大于可数浓度。

定理。实数集 ℝ ~ ℘ ( ℕ )。

证明。我们证明 ℝ ~ 2^ℕ。首先 2^ℕ 的元可以看成是一条由 0、 1 组成的排成一排的序列，在这序列前加上一个“0.”就可以把它看成是一个（十进制）小数。因此 ℝ ≥ 2^ℕ。另一方面，函数 arctan ( x ) / π + 1 / 2 把 ℝ 单射地映到 ( 0, 1 ) 区间，而 ( 0, 1 ) 区间的实数可以用二进制的小数来表示，把这小数表示前的“0.”去掉就可以得到一条由 0、1 组成的排成一排的序列，从而看成 2^ℕ 的元。因此 ℝ ≤ 2^ℕ。（证毕）

定理。ℝ ~ ℝ ∐ ℝ ~ ℝ × ℝ ~ ℝ^ℕ

证明。显然我们只要证明 ℝ^ℕ ~ ℝ。把 ℝ 看成是 2^ℕ，我们有 ( 2^ℕ ) ^ℕ ~ 2^{ℕ × ℕ} ~ 2^ℕ。（证毕）

定理。 ℝ^ℝ ~ 2^ℝ

证明。显然 2^ℝ ≤ ℝ^ℝ。另一方面， ℝ^ℝ ≤ ( 2^ℝ ) ^ℝ ~ 2^{ℝ × ℝ} ~ 2^ℝ。（证毕）

ℝ^ℝ 的浓度通常称为函数浓度。由以上可知它严格大于连续浓度。但是如果我们只考虑从 ℝ 到 ℝ 的连续函数的集合 C ( ℝ, ℝ )，这个浓度就是连续浓度了。这是因为 ℚ 在 ℝ 中是稠密的，所以一个连续函数只要在 ℚ 上确定了函数值，通过取极限操作它在整个 ℝ 上的函数值也就唯一确定了。而 ℚ 是可数的，所以 C ( ℝ, ℝ ) ≤ ℝ^ℚ ~ ℝ^ℕ ~ ℝ。反方向的不等式是显然的。