第5期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） ·623. 上面命题中出现了两个假设，到底是哪个假设 F(2)={1,*,3,*,*,…},该集合包含1,3， 引起的矛盾，还要分析。 不包含2,4,5； 这个定理和下面的定理等价，下面证明“Cantor F(3)={1,*,3,*,5,…},该集合包含，1,3， 的对角线方法”表现更清晰。 5,不包含2,4： 定理17自然数集合演算中存在不动项 F(4)={1,2,3,*,5,…},该集合包含1,2,3， 如果自然数集合与它的幂集合之间能建立 一一一 5,不包含，4： 映射，那么，它的幂集合演算中存在一个不动项。 F(5)={*,2,3,*,5,…},该集合包含2,3， 证明这个定理可以看成定理16的特例，证明 5,不包含1,4： 过程与定理16相同。 双射关系F:w~P(w),w是自然数集合， F(n)Cw,F(n)都是w的子集，F(n)e P(w)是w的幂集合。 P(ω)； 假设在F:w~P(w)中，任意n∈w对应一个 定义一个新集合T:n∈F(n)n年T。,n F(n)∈P(w), F(n)n∈T。; 即：n∈wF(n)∈P(w),F(n))是w的子 显然集合T。={*,2,*,4,*,…}是上面集 集之一，F(n)Sw: 合序列对角线元素的集合在ω上的补集； n∈F(n),或者n年F(n); T.也是ω的子集，T。∈P(ω)，它也在上表 按规定：n∈F(n)n生T。。n使F(n) 中，设它对应F(k),T。=F(k): n∈Ta; 得到矛盾：k∈F(k)k生F(k)。 假定T,∈P(w),F:w~P(w),存在 注记7 Cantor的两个定理 k∈w→F(k)∈P(ω)，（设T.=F(k); 1)自然数集合的任意一个子集都可以与一个0 按规定：k∈F(k)k生F(k); 与1的序列建立一一映射关系。 k生F(k)k∈F(k)。 证明用一个函数来表示某自然数的集值域 再把P(ω)分为正反集合，设： 在属于该集的自然数处它取值0，在不属于该集的 +a={x:n∈x,n∈ω，x∈P(ω)，x=F(n)} 自然数处它取值1。某自然数集合代表的函数值的 -a={x:n使x,n∈w,x∈P(ω），x=F(n)} 序列便是由0与1组成的无穷序列。为表示方便把 U=P(ω)=+aU-a 自然数集合中的0排除，仅为ω= 按规定：n∈F(n)→n生T。,n生F(n)neT。: {1,2,3,4,5,6,…},P(ω)为w的幂集合。 自我指代：T=F(k); 例：A1={1,*,3,4,*,…}该集合包含1,3， 即keF(k)k使F(k),k∈Tk年T。。 4,不包含2,5，（空缺的用“*”标注）该序列为 P[F(n)]表示n∈F(n);则P[F(n)]表 F(A1)=01001…; 示n年F(n)。 A2={1,*,3,*,*,…}该集合包含1,3，不 命题k∈F(k)k生F(k),T.=F(k)可以表 包含2,4,5，该序列为F(A2)=01011…; 示为P(T.)P(T。);T。是不动项： A3={1,*,3,*,5,…}该集合包含，1,3,5， 如果(T∈P(ω))，则有悖论P(T)P(T); 不包含2,4，该序列为F(A3)=01010…; 即如果双射关系F:w~P(w)成立，那么T是 A4={1,2,3,*,5,…}该集合包含1,2,3,5， 不动项。 不包含，4，该序列为F(A,)=00010…; 同样以上证明有两个假设，可以表示为 A5={*,2,3,*,5,…}该集合包含2,3,5，不 如果双射关系F:w~P(ω)成立，且(T。∈ 包含1,4，该序列为F(A5)=10010…; P(w)),那么，P(T)P(T); 即：(F:w~P(w))∧(T,∈P(w))F 所以，自然数集合的任意一个子集都可以表示 P(T)P(T)o 成一个0与1的序列，即自然数集合的任意一个子 注记6“Cantor的对角线方法” 集都可以与一个0与1的序列建立一一映射关系。 假设自然数和它的幂集合有一一对应关系，即 2)全体实数与全体自然数集合的子集具有一 n∈wF(n)∈P(w),可以把自然数的所有子集 一映射关系。 排成如下集合序列。 以上两个定理已经被Cantor等证明，自然数集 F(1)={1,*,3,4,*,…},该集合包含1,3， 合的任意一个子集都可以表示成一个0与1的序 4,不包含2,5，（空缺的用“*”标注）： 列，任意实数都可以表示二进制0与1的序列，它们上面命题中出现了两个假设，到底是哪个假设 引起的矛盾，还要分析。 这个定理和下面的定理等价，下面证明“Ｃａｎｔｏｒ 的对角线方法”表现更清晰。 定理 １７ 自然数集合演算中存在不动项 如果自然数集合与它的幂集合之间能建立一一 映射，那么，它的幂集合演算中存在一个不动项。 证明 这个定理可以看成定理 １６ 的特例，证明 过程与定理 １６ 相同。 双射关系 Ｆ：ω ～ Ｐ（ω） ， ω 是自然数集合， Ｐ（ω） 是 ω 的幂集合。 假设在 Ｆ：ω ～ Ｐ（ω） 中，任意 ｎ ∈ ω 对应一个 Ｆ（ｎ） ∈ Ｐ（ω） ， 即： ｎ ∈ ω↔Ｆ（ｎ） ∈ Ｐ（ω） ， Ｆ（ｎ） ）是 ω 的子 集之一， Ｆ（ｎ） ⊆ ω ； ｎ ∈ Ｆ（ｎ） ，或者 ｎ ∉ Ｆ（ｎ） ； 按规定： ｎ ∈ Ｆ（ｎ）↔ｎ ∉ Ｔω 。 ｎ ∉ Ｆ（ｎ）↔ ｎ ∈Ｔω ； 假定 Ｔω ∈ Ｐ（ω） ， Ｆ：ω ～ Ｐ（ω） ，存在 ｋ ∈ ω↔Ｆ（ｋ） ∈ Ｐ（ω） ，（设 Ｔω ＝ Ｆ（ｋ） ； 按规定： ｋ ∈ Ｆ（ｋ）↔ｋ ∉ Ｆ（ｋ） ； ｋ ∉ Ｆ（ｋ）↔ｋ ∈ Ｆ（ｋ） 。 再把 Ｐ（ω） 分为正反集合，设： ＋ α ＝ {ｘ：ｎ ∈ ｘ，ｎ ∈ ω，ｘ ∈ Ｐ（ω），ｘ ＝ Ｆ（ｎ）} － α ＝ {ｘ：ｎ ∉ ｘ，ｎ ∈ ω，ｘ ∈ Ｐ（ω），ｘ ＝ Ｆ（ｎ）} Ｕ ＝ Ｐ（ω） ＝ ＋ α ∪－ α 按规定： ｎ ∈ Ｆ（ｎ）↔ｎ ∉ Ｔω ， ｎ ∉ Ｆ（ｎ）↔ｎ ∈ Ｔω ； 自我指代： Ｔω ＝ Ｆ（ｋ） ； 即 ｋ ∈ Ｆ（ｋ）↔ｋ ∉ Ｆ（ｋ） ， ｋ ∈ Ｔω↔ｋ ∉ Ｔω 。 Ｐ［Ｆ（ｎ）］ 表示 ｎ ∈ Ｆ（ｎ） ；则 ¬ Ｐ［Ｆ（ｎ）］ 表 示 ｎ ∉ Ｆ（ｎ） 。 命题 ｋ ∈ Ｆ（ｋ）↔ｋ ∉ Ｆ（ｋ） ， Ｔω ＝ Ｆ（ｋ） 可以表 示为 Ｐ（Ｔω）↔¬ Ｐ（Ｔω） ； Ｔω 是不动项； 如果 （Ｔω ∈ Ｐ（ω）） ，则有悖论 Ｐ（Ｔω）↔¬ Ｐ（Ｔω） ； 即如果双射关系 Ｆ：ω ～ Ｐ（ω） 成立，那么 Ｔω 是 不动项。 同样以上证明有两个假设，可以表示为 如果双射关系 Ｆ：ω ～ Ｐ（ω） 成立，且 （Ｔω ∈ Ｐ（ω）） ，那么， Ｐ（Ｔω）↔¬ Ｐ（Ｔω） ； 即： （Ｆ：ω ～ Ｐ（ω）） ∧ （Ｔω ∈ Ｐ（ω）） ├ Ｐ（Ｔω）↔¬ Ｐ（Ｔω） 。 注记 ６ “Ｃａｎｔｏｒ 的对角线方法” 假设自然数和它的幂集合有一一对应关系，即 ｎ ∈ ω↔Ｆ（ｎ） ∈ Ｐ（ω） ，可以把自然数的所有子集 排成如下集合序列。 Ｆ（１） ＝ {１，∗，３，４，∗，…} ，该集合包含 １，３， ４，不包含 ２，５，（空缺的用“ ∗ ”标注）； Ｆ（２） ＝ {１，∗，３，∗，∗，…} ，该集合包含 １，３， 不包含 ２，４，５； Ｆ（３） ＝ {１，∗，３，∗，５，…} ，该集合包含，１，３， ５，不包含 ２，４； Ｆ（４） ＝ {１，２，３，∗，５，…} ，该集合包含 １，２，３， ５，不包含，４； Ｆ（５） ＝ {∗，２，３，∗，５，…} ，该集合包含 ２，３， ５，不包含 １，４； … Ｆ（ｎ） ⊆ ω ， Ｆ（ｎ） 都是 ω 的子集， Ｆ（ｎ） ∈ Ｐ（ω） ； 定义一个新集合 Ｔω ： ｎ ∈ Ｆ（ｎ）↔ｎ ∉ Ｔω ， ｎ ∉ Ｆ（ｎ）↔ｎ ∈ Ｔω ； 显然集合 Ｔω ＝ {∗，２，∗，４，∗，…} 是上面集 合序列对角线元素的集合在 ω 上的补集； Ｔω 也是 ω 的子集， Ｔω ∈ Ｐ（ω） ，它也在上表 中，设它对应 Ｆ（ｋ） ， Ｔω ＝ Ｆ（ｋ） ； 得到矛盾： ｋ ∈ Ｆ（ｋ）↔ｋ ∉ Ｆ（ｋ） 。 注记 ７ Ｃａｎｔｏｒ 的两个定理 １）自然数集合的任意一个子集都可以与一个 ０ 与 １ 的序列建立一一映射关系。 证明 用一个函数来表示某自然数的集值域， 在属于该集的自然数处它取值 ０，在不属于该集的 自然数处它取值 １。 某自然数集合代表的函数值的 序列便是由 ０ 与 １ 组成的无穷序列。 为表示方便把 自 然 数 集 合 中 的 ０ 排 除， 仅 为 ω ＝ {１，２，３，４，５，６，…} ， Ｐ（ω） 为 ω 的幂集合。 例： Ａ１ ＝ {１，∗，３，４，∗，…} 该集合包含 １，３， ４，不包含 ２，５， （ 空缺的用“ ∗ ” 标注） 该序列为 Ｆ（Ａ１ ） ＝ ０１００１… ； Ａ２ ＝ {１，∗，３，∗，∗，…} 该集合包含 １，３，不 包含 ２，４，５，该序列为 Ｆ（Ａ２ ） ＝ ０１０１１… ； Ａ３ ＝ {１，∗，３，∗，５，…} 该集合包含，１，３，５， 不包含 ２，４，该序列为 Ｆ（Ａ３ ） ＝ ０１０１０… ； Ａ４ ＝ {１，２，３，∗，５，…} 该集合包含 １，２，３，５， 不包含，４，该序列为 Ｆ（Ａ４ ） ＝ ０００１０… ； Ａ５ ＝ {∗，２，３，∗，５，…} 该集合包含 ２，３，５，不 包含 １，４，该序列为 Ｆ（Ａ５ ） ＝ １００１０… ； … 所以，自然数集合的任意一个子集都可以表示 成一个 ０ 与 １ 的序列，即自然数集合的任意一个子 集都可以与一个 ０ 与 １ 的序列建立一一映射关系。 ２）全体实数与全体自然数集合的子集具有一 一映射关系。 以上两个定理已经被 Ｃａｎｔｏｒ 等证明，自然数集 合的任意一个子集都可以表示成一个 ０ 与 １ 的序 列，任意实数都可以表示二进制 ０ 与 １ 的序列，它们 第 ５ 期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） ·６２３·