习题2.2
2.2.1 证明:用归纳法. 归纳基始——首先证明基础情形
. 由定义2.2.1
有
和
. 由此
. 归纳步骤——假设
,现在我们要证
. 再由定义2.2.1
有
,由归纳假设有
,再由定义2.2.1
. 这就完成了归纳. 所以对任何自然数a,b,c有
.
我们也可以对等式
中的b或c进行归纳. 其中对c进行归纳和对a的归纳是类似的,只要我们注意到了命题2.2.4. 而对b进行的归纳中还要用到引理2.2.3,其余部分的推理和对a的归纳是一样的.
最后要注意的两点是证明过程中用到了“两个自然数的和仍是自然数”这个命题(“文内补充”部分有证明),比如由定义2.2.1
推理得到
.
2.2.2 证明:用归纳法. 1是正数,由定义2.1.3知存在自然数0,使得
. 假设仍存在自然数c使得
. 由此得
,再由公理2.4知
,则只存在一个自然数0使得
. 现归纳假设对正数a,恰存在一个自然数b使得
. 现在要证对正数a++(由引理2.2.2和引理2.2.3知
,再由命题2.2.8知a+1是正的,即a++是正的)命题也成立. 由归纳假设知
,则存在自然数b++(由公理2.2知b++是自然数)使得
,同理由公理2.4知b++的唯一性.
还可以用反证法证明其存在性和唯一性. 但要用到函数的概念,等以后再做证明,基本思路是证明a不等于任何正数,这显然与a是正数相矛盾.
最后要注意的一点是归纳法不一定要用0作为基始,可以是任何自然数。至于为什么,以上面的命题为例子,我们可以把命题改成“设a+1是正数,那么恰存在一个自然数b,使得
”,这时候我们就可以从零开始归纳证明了。更一般地情况可以参考徐明编《符号逻辑讲义》附录里面的数学归纳法部分:弱归纳原理及其变形.
2.2.3 证明:(a)由定义2.2.1知
,即
,由定义2.2.11知
.
(b)若
且
,由定义2.2.11知存在自然数d,e使得
且
,则
. 由“两个自然数的和仍是自然数”与定义2.2.11知
.
(c)若
且
,由定义2.2.11知存在自然数d,e使得
且
,则
. 由命题2.2.6知
,即
,由推论2.2.9知
且
,再由引理2.2.2知
.
(d)如果
,由定义2.2.11知存在自然数d使得
. 由引理2.2.2知有
. 现归纳假设对自然数c有
,由引理2.2.3知
,由归纳假设和以及引理2.2.3有
,这就完成了归纳,对所有自然数c都有
,由定义2.2.11知
. 其实不用归纳法也可以,因为
,由相等中的代入公理一定有
. 至于自然数的相等,我们下面再说.
如果
,由定义2.2.11以及命题2.2.4和命题2.2.5存在自然数d使得
,由命题2.2.4以及命题2.2.6有
. 再由定义2.2.11有
.
综上,我们证明了
当且仅当
. 补充一点:a当且仅当b的意思是如果a则b,并且如果b则a. 关于常用真值函数联结词的语义解释可以参考任意一本数学基础或当代逻辑的书,比如汪芳庭《数学基础》、徐明《符号逻辑讲义》.
(e)如果
,由定义2.2.11知存在自然数d使得
且
. 已知
,我们证明
当且仅当
. 如果
,由
和命题2.2.6知
,即
. 如果
,由引理2.2.2则
. 现在是
,说明
,即d是正数,由引理2.2.10知恰存在一个自然数e使得
,由引理2.2.3有
,再由定义2.2.1知
,由定义2.2.11知
. 由此我们也知定义2.2.11中的“n严格大于m”定义中
的要求可以改成
中a是正数.
如果
,由定义2.2.11知存在自然数d使得
. 由定义2.2.1和引理2.2.3知
,由公理2.3知
,即d++是正数,由定义2.2.11和上的讨论知
.
综上我们有
当且仅当
.
(f)由(e)中的讨论我们知道对自然数n,m,a命题“
并且
”等价于命题“
并且
”. 那么
等价于对某正数d有
.
2.2.4 证明:(1)若
,由定义2.2.1知对一切自然数b有
,即
,由定义2.2.11知
.
(2)若
,由定义2.2.11知存在自然数c使得
. 由引理2.2.3知有
. 由习题2.2.3(f)和公理2.3知
.
(3)若
,由相等中代入公理和引理2.2.2和引理2.2.3的推论有
. 假设
,由命题2.2.6知
,这与公理2.3矛盾,故
. 再由
和定义2.2.11知
.
2.2.5 证明:定义Q(n)为性质“P(m)对于一切
成立”. 现在归纳证明对一切自然数n都有Q(n)成立. 显然,当
时Q(n)是莫须有地成立,空真地成立. 因为此时不存在满足
的m.(可以先看本书的附录A-数理逻辑基础).
当
时,由题意知有有蕴涵关系“如果P(m’)对一切满足
的自然数都成立,那么P(m)也成立”. 由于此时蕴涵关系的前件“P(m’)对一切满足
的自然数都成立”是真空地成立的,那么就有蕴涵关系的后件也真,即P(n)成立,即P(
)成立. 而此时Q(n)是与
时一样莫须有地成立,空真地成立.
当
时,由于已知P(
)成立,所以对一切
有P(m)成立,所以Q(n)此时是实在地成立,不是真空地成立. 这样我们就完成了归纳奠基.
现在进行归纳步骤,假设
时Q(n)成立. 要证对
亦有Q(n++)成立. 由于
,则有
,所以对n也有蕴涵关系“如果P(m’)对一切满足
的自然数都成立,那么P(n)也成立”,由归纳假设Q(n)成立说明蕴涵关系的条件成立,所以蕴涵关系的后件P(n)也成立. 结合归纳假设Q(n)成立和P(n)成立知对一切
都有P(n)成立,即对一切
都有P(n)成立,所以Q(n++)成立. 这样我们就完成了归纳:对一切自然数n都有Q(n)成立. 由于对任一自然数
,有Q(m+1)成立,由Q(m+1)成立知P(m)成立. 所以对一切自然数
都有P(m)成立.
强归纳原理的证明主要在于理清其中的逻辑,如果上面的证明看不懂,请先看本书的附录A-数理逻辑基础,再看徐明《符号逻辑讲义》附录里的数学归纳法部分:强归纳原理及其变形。还有一点是我们使用归纳原理证明命题时,归纳基始不能是空真地成立的(这常常会出现在含有量词的命题中),所以上面的证明我们验证了当
时Q(n)成立才说我们完成了归纳奠基。本书(中文第一版)的另一个例子是P51引理3.5.12(有限选择)的证明,归纳奠基是从1开始而不是从0开始,因为对于0命题是空真地成立的.
2.2.6 证明:对n进行归纳. 考虑基础情形——假设P(0)成立,对一切
,显然有P(m)成立,因为由定义2.2.11和推论2.2.9知
. 现归纳假设命题成立,即若P(n)成立,那么对
,P(m)成立. 对n++,若P(n++)成立,由性质P满足的条件知P(n)成立,由归纳假设说明对
,P(m)成立. 加上P(n++)成立知:若P(n++)成立,则对
,P(m)成立. 这就完成了归纳.
文内补充
1.证明两个自然数的和仍是自然数.
证明:设n,m是自然数. 我们可以对任一变量进行归纳,比如对m进行归纳. 归纳基始——由定义2.2.1知
,所以0+n是自然数. 归纳步骤——假设m+n的和是自然数. 由定义2.2.1知
,再由公理2.2和归纳假设知(m+n)++是自然数,所以(m++)+n也是自然数. 这就完成了归纳. 其说明0+n,1+n,…结果都是自然数. 由n的任意性,我们知道任意两个自然数的和仍是自然数.
一点题外话:可能有人认为这个证明不能说明对任意的两个自然数的和是自然数,因为证明只对“一个变量进行了归纳”. 其说的没错,我们只是对一个变量进行了归纳,上面关于加法的各种性质的证明都只是对“一个变量进行了归纳”,甚至加法的定义都是只对“一个变量进行了归纳”. 但这个归纳仍是有效的,可以这样理解,我们这个“一个变量进行了归纳”其实是一个模板,我们固定了其他的变量来进行归纳证明,但固定的变量值是不指定的. 只要一旦固定其他变量的值,我们就用“一个变量进行了归纳”来进行证明. 比如,我们都不会去质疑用归纳法可以证明
(a是自然数),因为其只有一个变量,同理我们不会质疑可以用归纳法证明
,
,…等等. 而用“一个变量进行了归纳”证明
(a,b是自然数)时,这个证明可以代表上面一系列证明的任意一个,这就是其是“模板”的意思,既然其可以代表上面的证明的任意一个,也就说明我们对任意的b证明了对任意的a都有
. 这就像极限语言里面我们要证明对任意实数
,都有性质P,这里我们不可能对实数进行归纳然后说明对任意实数
,都有性质P,我们做的也是固定
的值,然后去证性质P成立. 最后说明对任意
,都有性质P. 但对于自然数的多变量命题可不可以对每个变量都进行归纳来证明呢?这是肯定的,比如我们证明自然数加法的交换律:要证明对任意a,有对任意b,有
. 归纳基始——证明有
,归纳步骤——假设已证明
,证明
,这就是对a的归纳. 而在证明
和
时就要用到对b的归纳,注意此时a++是固定的值. 显然,这样证明繁琐了许多. 但多变量的归纳并不是没有用的,比如对加法的合理性和唯一性的证明,可以参考汪芳庭《数学基础》1.2附3-皮亚诺算术的适当展开.
2.对自然数n,
.
证明:由引理2.2.2和引理2.2.3有
.
3.为什么证明了命题2.2.4和命题2.2.5,我们就可以说明对有限多(某个自然数个)的自然数
进行依次相加而不考虑这些数是依怎样的次序加起来的?
可以看到的是当自然数数量为0个或1个时,讨论加法是没有意义的,所以我们只需考虑自然数数量不少于2.
第一步,编序:由于有有限多(自然数个)自然数
(这些互不相同符号(避免符号混淆)均是常元符号,其代表一个自然数.),于是可以用自然数0, 1, …, n来编码以上有限的自然数符号常元,进而即也是用自然数0, 1, …, n来编码以上有限的自然数(严格来说我们考虑的是函数
. 对于任意
,我们不妨记
.). 于是我们可以用
来代替
.
第二步,相加:有限个自然数依某次序加起来的过程可以看成依某n阶排列中从左到右的数i对应的被加数
相加的过程,比如
从左到右依次相加可以看成对应自然排列
. 任意两个n阶排列都是可以通过相邻对换相互转化,相邻对换对应命题2.2.4与命题2.2.5的结合运用,不改变这些依n阶排列的从左到右的数i对应的被加数
加起来的自然数的和. 这样我们就证明了这些自然数无论是以怎样的次序相加,其和都是相等的. 具体的来说,我们证明了:

依照加法结合律
依照加法交换律
再次依照加法结合律
这就说明了依某一次序加起来的自然数,相邻的两个自然数可以交换位置而不改变加起来的和,这就对应n阶排列中的“相邻对换”. 再由n阶排列的知识知
中的
可以在式子的任意一个位置(+号的空位),而不改变整体的和,这样就说明了有限多的自然数
进行依次相加可以不考虑这些数是依怎样的次序加起来的.
但这还没有完全解决问题. 比如一个这样的式子
(a,b,c,d均是某个自然数),其不是如
依次相加起来的,但容易证明这两个式子是相等的. 更一般地,我们要证明每一个由自然数
合理利用加法形成的式子的和都是与
依次相加的和是相等的. 所谓“合理形成”,要求的是加法式子括号的位置是正确的,不会有歧义或病态构成. 比如我们如果取消掉“省略括号的左结合原则”后,式子
就会有歧义,这么多个自然数我们不知道哪个先进行相加计算;病态的就更好理解,比如
就是病态的. 具体说来,我们要形成正确的加法式子,就是重复n次的使用加法,每一次重复都需要一对括号“()”标明这一次使用的加法. 对于n次重复的严格定义,我们是用归纳来表述的:
我们先来看看“对自然数n次重复使用加法(n是自然数)”的过程对应的直观是怎样的:
(1)所有自然数变量m’, m”, m”’, …都是合理的加法式子(虽然其没有用到加法). ——注意,我们只是用不同上标来区分不同的自然数变量,但我们不考虑其数量是否是可数的,是否可以排序等.
(2)如果a,b是合理的加法式子,那么(a+b)也是合理的加法式子.
(3)只有这些是合理的加法式子.
但(1)、(2)与(3)组成的定义绝不是关于“自然数重复n次使用加法”的归纳定义,虽然其颇有几分“归纳”的味道在里面. 因为(1)、(2)与(3)组成的定义为我们展现了一个⌈金字塔⌋结构:在塔尖是自然数变量,其用到了0次加法;下一层是两个自然数变量之间的相加,其用到了1次加法;再下一层是两个上两层形成的加法式子之间的相加,用到的加法次数是两个上两层形成的加法式子用到的加法次数之和加一(比如⌈(1+(2+3))⌋用到了(0+1)+1=2次加法;而⌈((1+2)+(3+4))⌋用到了(1+1)+1=3次加法.);以此类推到对每个
都定义了第n层. 进一步的我们看到除了第0层和第1层使用的加法次数分别是唯一的0和1,其余层使用的加法次数并不唯一,这导致了很难借助上述(1)、(2)与(3)构成归纳定义. 我们需要严格审视“自然数重复n次使用加法”到底在说什么.
故下面的论述并不是归纳法论述.
我们首先证明几个推论:
(a)所有合理的加法式子用到的“+”号是有限的,即某个自然数个的.
证明:对所有自然数变量n',n'',n''',...,其没有用到“+”号,显然是0个. 现归纳
假设合理的加法式子a,b用到了有限个“+”号,那么(a+b)显然也是用到了有限个的. 这
就完成了归纳. 所有合理的加法式子使用到的“+”号是有限个的. 同理可证所有合理的
加法式子使用到的自然数变号是有限个的. 所以我们可以对一个合理的加法式子用自然数
对其中的自然数变号排序,如此可以用排序的自然数做下标区分它们.
(b)形如
(p为自然数)的合理的加法式子叫作
自然数依次相加的. 我们现在来证明:两个自然数依次相加的的合理的加法式子的和也可以表达成
自然数依次相加的.
依加法交换律
依加法结合律
依上方法再重复q次
命题的证明用到了q+1次重复,说明这个命题也可以用归纳法证明如下:
归纳基始——对只有1个命题变号的合理的加法式子A,其与任意大于0自然数个命题变号
的自然数依次相加的合理的加法式子B的和,其显然是可以表达成自然数依次相加的.
因为我们可以把这个和看成自然数先依B中的次序相加,最后再加上A,这个过程显然是
自然数依次相加的,只不过增加了一个命题变号A最后相加.
归纳步骤——现归纳假设对有自然数k个命题变号的自然数依次相加的合理的加法式子A,
其与任意大于0自然数个命题变号的自然数依次相加的合理的加法式子B的和是可以表达成
自然数依次相加的. 那么对有k+1个命题变号的自然数依次相加的合理的加法式子A,对
任意大于0自然数n,有n个命题变号的自然数依次相加的合理的加法式子B的和,由上面的
方法(使用加法交换律后使用加法结合律)可以变成有k个命题变号的自然数依次相加的
合理的加法式子A'和有n+1个命题变号的自然数依次相加的合理的加法式子B'的和(这个变换过程
由加法交换律和加法结合律保证他们是相等的),由归纳假设知A'和B'的和是可以表达成自然数
依次相加的,进而A和B也是可以表达成自然数依次相加的,由于n的任意性,我们证明了对有
自然数k+1个命题变号的自然数依次相加的合理的加法式子A,其与任意大于0自然数个命题变号的
自然数依次相加的合理的加法式子B的和是可以表达成自然数依次相加的. 这就完成了归纳.
现在我们归纳证明所以合理的加法式子都是可以表达成自然数依次相加的.
归纳基始——对所有自然数变量n',n'',n''',...,其显然是自然数依次相加的.
归纳步骤——假设合理的加法式子a,b是自然数依次相加的,由(b)的证明我们知道
其和(a+b)也可以表达成自然数依次相加的.
这样我们就完成了我们的证明. 对于有交换律和结合律的数系,我们都可以以同样的证明方法来说明.
值得注意的是,我们将在第七章7.1节的博文中文内补充第5点用级数的方法给出另一个证明.
回顾自然数的加法,可以认为其说的是只要有两个自然数a,b,我们就可以将他们相加得到一个自然数. 于是如果现在有两自然数
,我们知道怎么将它们相加了. 那么3个自然数
呢?自然数
又该怎么相加呢?我们发现我们所说的有限个自然数相加过程其实就是:对有限个自然数变量
,从上述⌈金字塔⌋中找到加法式子使得每个自然数变量
恰好在+号的左或右占位出现唯一的一次,然后计算此加法式子用到的加法次数就是重复几次使用了加法(我们可以从⌈金字塔⌋给出的直观中发现:用到的加法次数就是此加法式子中‘+’出现的次数).
下面严格叙述此事.
我们要将有限个自然数相加.
在前面对“可以将有限个自然数进行依次相加而不用考虑依怎样次序加起来”问题的讨论中我们已经在“第一步,编序”中说明了语句“有限个自然数”表达的内涵,我们将其沿用至此. 设函数
,对于任意
,我们不妨记
. 于是我们可以用
表示有限个自然数.
在有限个自然数上的一次相加:已知有
有限个自然数,我们说在其上的一次相加即为——从
选中两个自然数
(由于自然数n>0这是可行的),得到它们的和记为
. 然后从
中删去
后添加进
,此操作形成比原
少一个自然数的新的有限个自然数
. 当然上面的定义是比较口语化好理解的,现在给出其严格叙述形式.
首先证明命题3.0——对一切自然数
,我们可以从集合
选取两个不同元素.
证明:使用归纳法. 对自然数1,容易知有
;对自然数i,若
且
:由于i为自然数,故有
,结合
看到
,进而有
,结合
看到
. 于是从逆否命题来看对自然数i若
则
或
. 进而看到对一切
,有p为自然数且
,进而
,于是有
或
,于是
,进而
. 进而看到
. 于是我们确实可以从
选取两个不同元素0和1. 这就完成了归纳基始.
归纳假设对自然数
,可以从
选取两个不同元素,即存在
使得
.
那么对自然数
,容易看到
,于是从归纳假设看到若存在
使得
,那么也是存在
使得
. 这就完成了归纳.
于是我们可以说:对一切自然数
,我们可以从集合
选取两个不同元素. 进而也是对一切自然数
,我们可以从集合
选取两个不同元素.(这里使用归纳法证明的存在性命题而不是取巧直接说明
有两个不同元素
(或者
等),是为了让我们的选取依存在性命题看起来像是“随机、随意、非决定性”. 此存在性命题告诉了我们“存在”两个不同元素但没有告诉我们如何具体选取,于是让我们的选取看起来是“随机、具有不确定性、具有选择自由性”;而取巧的证明直接告诉你选取的“规律、决定性、非自由性”. 这里的探讨有点触及更深层哲学问题在里面:我们在讨论寻求“规律”的时候实质是在干什么?这里只给出一个引子,我没有能力进行更深层次的探究. 回顾人的成长历程,我们发现小孩子对新鲜事物总是有莫名其妙的好奇,尽管这些事物对大人来说是无聊无趣无用的. 我猜测这与大脑的发育进程密切相关,我们的大脑是十分“理性”的事物,喜欢探求“规律美、可解释性”. 怎么去描述这样的发展历程呢?有点类似“模糊”到“精确”、“散漫”到“目的”的感觉,如同印象画派(比如梵高《星月夜》)和文艺复兴画派(比如达芬奇《维特鲁威人》)的对比、如同多人在线互动游戏和单机流程游戏的对比. “随机、自由”与“规律、确定”的矛盾与平衡好像无处不在. 之所以大脑会出现这样的发展历程,我猜测、我认为(没有任何理论依据,只是个人的体悟)与⌈我⌋这个概念在脑中生根发芽逐渐根深蒂固有关. 因为有⌈我⌋,执着于⌈我⌋,所以会趋利避害来保全⌈我⌋. 在保全⌈我⌋的过程中,大脑习惯于站在⌈我⌋(即自己)的角度进行各种可能性分析后再来做各种选择. 但可能性是无限的,你能想到的、未想到的;已发生的、未发生的都有可能成为现实,大脑能处理的可能性终归是有限的,所以大脑更习惯于站在⌈我⌋的角度进行各种坏的可能性分析后再来做各种选择,以避免坏的可能性伤害⌈我⌋,这就是⌈怕⌋.)
于是可以看到对一切自然数
:我们容易验证集合
与集合
之间存在双射
,于是根据定义3.6.5我们知道集合
具有基数n+1. 由于已证命题3.0“对一切自然数
,我们可以从集合
选取两个不同元素.”,即存在
使得
,于是根据引理3.6.9我们看到
,
. 也即集合
映射到集合
存在双射
. 在双射
基础上定义函数
,若
则
;若
则
. 从函数
得到函数
的过程我们称作“在有限个自然数上的一次相加”. 换句话说,设
,设
,我们将
叫做“在有限个自然数上的一次相加”当且仅当——存在
使得
且存在从
到
的双射
使得:
和若
则
. 这是因为此时
可以看作是
经过一次“在有限个自然数上的一次相加”的过程得到的.
有了上面的论述,我们现在可以讨论什么叫做“有限个自然数相加”.
对函数
,经过“在有限个自然数上的一次相加”后我们得到函数
,即
. 换句话说,对自然数1:对函数
确实存在双射函数(因为容易验证对一切
如果
,进而简单讨论可知
,那么
定义域的有限基数2就大于
定义域的有限基数1,由此可知
此时确实是单射函数,进而是双射函数.)
使得满足以下a.和b.和c.三条件——a.
;b. 对一切
,如果
那么
是
经过“在有限个自然数上的一次相加”后变换得到的;c.
是
映射到
的函数. 讲人话就是指——存在一个各项互不相同的有限函数序列
,使得
,并且此有限序列相邻的两个对象之间后者可以从前者经过“在有限个自然数上的一次相加”后得到,并且最终
是定义域为
值域为自然数集的函数.(这里采用有些绕口的陈述是为了避免写下“经过重复有限次“在有限个自然数上的一次相加””之类的语句,否则我们还是要继续解释什么叫“重复有限次“在有限个自然数上的一次相加””.)
归纳假设对自然数
:对函数
存在双射函数
使得满足以下a.和b.和c.三条件——a.
;b. 对一切
,如果
那么
是
经过“在有限个自然数上的一次相加”后变换得到的;c.
是
映射到
的函数.
那么对自然数
:我们要证明对函数
存在双射函数
使得满足以下a.和b.和c.三条件——a.
;b. 对一切
,如果
那么
是
经过“在有限个自然数上的一次相加”后变换得到的;c.
是
映射到
的函数. 接下来就做此事.
由于
,于是我们可以从集合
选取两个不同元素,再经过“在有限个自然数上的一次相加”我们可以从函数
得到函数
. 由归纳假设我们知对函数
存在双射函数
使得满足上面已陈述的a.和b.和c.三条件. 现在我们来构建函数
. 对一切
:对
,则定义
,也即
是定义域为
值域为
的函数;对
,由于
故有
,结合
我们看到
,进而看到
,结合
我们得到
. 前面我们已说明集合
与集合
之间存在双射
,于是此情况我们可以定义
(函数
为函数
的逆,详见注3.3.24下面一段.). 接下来我们只需逐步验证
是符合要求的函数. 由于
,于是条件a.是满足的了. 对一切
,如果
:说明
,进而看到
. (1)若
,那么
,由于
进而看到
,进而陈述“
是
经过“在有限个自然数上的一次相加”后变换得到的”是由归纳假设保证的;若
,进而
,那么陈述“
是
经过“在有限个自然数上的一次相加”后变换得到的”是明显成立的. 于是条件b.也是满足的了. 由于
,而
是
映射到
的函数是归纳假设所保证的,于是条件c.也是满足的. 现在来验证
是单射. 对一切
,如果
:由于自然数序三歧性我们知道有
或
. 当
时,由于
我们知道
,于是看到
,进一步的如果有
,也即有
,于是我们看到
,由于
,进而
,于是
是由双射函数
保证的了,于是此情形下有
;否则我们有
,进而
. 由归纳假设我们看到
,而函数
的定义域为
且函数
的定义域为
,于是
,即
并且函数
定义域的有限基数大于函数
定义域的有限基数,这就完成了内部归纳基始. 现在内部归纳假设对自然数
——若
则
并且函数
定义域的有限基数大于函数
定义域的有限基数. 那么对自然数
,若
,由于我们已经验证函数
满足条件b.,于是
是
经过“在有限个自然数上的一次相加”后变换得到的,于是从上面对“在有限个自然数上的一次相加”的说明我们可以看到函数
定义域的有限基数大于函数
定义域的有限基数(相差1),结合内部归纳假设中“函数
定义域的有限基数大于函数
定义域的有限基数”进而我们看到函数
定义域的有限基数大于函数
定义域的有限基数,于是可以知道函数
定义域不同于函数
定义域,于是看到
,这就完成了内部归纳. 于是我们可以说“对一切自然数
——若
则
并且函数
定义域的有限基数大于函数
定义域的有限基数.”. 于是对
有
,这就讨论完当
的情形也有
. 综上,当
我们总有
. 当
,也即
,类似的论证我们同样可以证明
. 至此我们证明了
的单射性. 既然已经证明了
为单射,我们可以采用偷懒的做法,使用ZFC中替换公理将
值域限制为
,这样
就自动为满射了. 但这样做是有一定风险的,可能会影响上面论证有效性,因为上面的论证可能直接或间接涉及到
的值域,改变
的值域就将牵一发而动全身. 为了排除这种风险,我们需要将上面对原
的论述再一次对新
证明一遍,但绝大多数时候我们省略了这一步,所以说其是一种偷懒的做法. 究其原因,除了归纳基始(此处不是指内部归纳基始,而是指最外部的归纳基始.)对自然数1对函数
存在的满足a.和b.和c.三条件的双射函数
的值域
是明确定义的,上面从“归纳假设”开始函数
的值域
我们未严格说明表示的是什么?想一想未明确定义的东西我们要如何进一步讨论?可以看到这些值域集合的书写是省略简化形式(我可以简单说明一下我为什么使用如此写法. 1.首先函数
想表达的是从
不断使用“在有限个自然数上的一次相加”变换,最终得到无法使用“在有限个自然数上的一次相加”变换的
,于是
的值域就是从
开始经过此变换得到
等等. 2.至于为什么我不用
表示
、
表示
诸如此类,这个想法很好,但我们并不知道“不断使用“在有限个自然数上的一次相加””是否在有限步(某个正自然数)内结束,是否可以进行可数无限步,甚至是不可数无限步. 这些在我们完成我们的归纳前我们都不应该给予假定,所以用自然数来为
编序不太好. 3.为什么不用ZFC的公理来严格构造这些函数的值域?确实可以这样,但此章节还未涉及ZFC初步入门,所以在可读性和严格性之间进行了取舍,我们将在后面补充上这些函数值域的严格形式. 于是这些不严格的省略简化形式集合现在就当做一种方便之门、方便的记号.),这些省略简化形式的值域集合好像预设了:1.这些值域集合均是有限集;2.这些省略简化形式的值域集合的元素是定义域形如
而值域是
的函数. 对于第1.点,在我下面给出这些值域的严格ZFC书写形式、进而论证完
是满射、进而完成归纳后,将看到第1.点是明显成立的;对于第2.点,同样是在我下面给出这些值域的严格ZFC书写形式后将是明显的. 或者说我们的条件b.已经隐性要求这些值域集合的元素是定义域形如
而值域是
的函数,于是我们可以改换为将此点显性陈述出来,也即对条件b从“b. 对一切
,如果
那么
是
经过“在有限个自然数上的一次相加”后变换得到的;”修改为“b. 对一切
,如果
那么——
是定义域形如
而值域是
的函数,(并且
是定义域形如
而值域是
的函数,)并且
是
经过“在有限个自然数上的一次相加”后变换得到的;”(括号内“并且
是定义域形如
而值域是
的函数,”可以省略的原因是只要
是定义域形如
而值域是
的函数,那么经过“在有限个自然数上的一次相加”变换后得到的
就肯定是定义域形如
而值域是
的函数.),进而小范围修改归纳基始、归纳假设以及归纳步骤后可以发现上面从归纳基始到验证完
是单射的论证仍是有效的. 在此修改基础上,依据归纳假设我们使用归纳法(类似上面的内部归纳,其是对具有某种形式有限的自然数使用归纳法的一种小技巧)可以推出:对归纳假设中的
,对一切
有
是定义域形如
而值域是
的函数. 至此,我想说明的基本已陈述完毕,所以接下来就严格化这些省略简化形式的值域集合. 正如前面所讨论的结果,我们需要从归纳假设中的函数
开始. 现在已经知
,对一切
,从公理3.10(幂集公理)知我们可以考虑集合
,从公理3.6(替换公理)和公理3.11(并)知存在集合
,从引理3.4.9我们可以考虑集合{Y : Y是
的子集},进而容易验证:对一切Z
{Y : Y是
的子集}当且仅当对象Z是集合并且Z中的元素均为定义域形如
而值域是
的函数. 然后再使用替换公理和并公理考虑集合
{
: Z
{Y : Y是
的子集}},然后函数
就是满足a.、b.、c.三条件以及双射的集合
{
: Z
{Y : Y是
的子集}}的一个元素,于是值域
严格形式就是某Z
{Y : Y是
的子集}. 于是由于
定义域
是有限集并且
是双射可知此Z也是有限集,也即可以说值域
是有限集. 对归纳假设的严格说明就至就完成了,我们继续对归纳步骤进行严格说明. 在归纳步骤中我们从
经过“在有限个自然数上的一次相加”后得到
,然后依(严格后的)归纳假设知道存在函数
{
: Z
{Y : Y是
的子集}}使得满足a.、b.、c.三条件以及双射,为了方便书写,我们将函数
简记为
,进而依据前面论证我们知道
的值域
是有限集合. 那么我们接下来定义的
的值域
表示的是
,于是我们也可以看到
是有限的. 至此,我们终于可以开始严格证明
是满射了,因为我们已经严格说明值域
的ZFC形式. 对一切
,也即
:若
,即
,此时存在
使得
;若
,由
的满射性知存在
使得
,进而也即存在
使得
,进而也即存在
使得
. 这就完成了
满射性的验证.
这就完成了归纳.
综上,对一切自然数
我们都可以说明:对函数
存在双射函数
使得满足以下a.和b.和c.三条件——a.
;b. 对一切
,如果
那么
是
经过“在有限个自然数上的一次相加”后变换得到的;c.
是
映射到
的函数.
于是对函数
,我们就将双射函数
叫做“有限个自然数上的(全部)相加”,并将
定义为“有限个自然数上的(全部)相加的和”,并将
的定义域的有限基数减一
叫做“有限个自然数
上的(全部)相加重复n次使用了加法”. 也就是说实际上n+1个自然数
(因为此函数表示用自然数0, 1, …, n来编码自然数,编码的自然数数量就是0, 1, …, n组成的集合
的基数n+1)需要n次重复使用加法才能最终得到一个自然数来代表它们的和. 并且对一切
,我们把
叫做“有限个自然数上的(全部)相加的第j次相加”,自然而然地可以看到
也是“在有限个自然数上的一次相加”.
实际上对函数
,依存在的双射函数
得到的有限序列
代表的其实就是:从前文提到的可数层⌈金字塔⌋的第0层开始并最终找到使得有限个自然数变量
恰好在+号的左或右占位出现唯一的一次的加法式子的具体操作过程.
正如前文哲学的思辨说到的一样,我们只是笼统地简单地说明了对函数
,“存在”双射函数
. 到底存在多少个这样的双射函数?是有限个还是无限个?我们没有进行进一步的探讨,也不是这里我们关心的重点. 我们更加关注的是每一个“有限个自然数
上的(全部)相加
”对应的和
是不是相同的?接下来我们就是要解决这个事情.
我将分两个阶段来解决此事情.
有限个自然数上的依次相加的和:我们在问题3.解答的最开始已经简要论证过此小点,现在要做的工作是将其严格化. 当我们想证明“有限个自然数上的依次相加的和均相等”时,一般来说前面的简要论述足以解答疑惑,这是因为我们已经假定、默认我们知道如何“重复使用加法”将有限个自然数依次加起来,所以前面的简要论述中我们可以大胆的写下诸如
这样的重复使用加法的(省略简化)语句. 于是当我们考虑什么是“重复使用加法”?我们是否可以大胆写下诸如
的语句就值得怀疑了. 为此,我们在ZFC框架内严格化定义了“有限个自然数上的(全部)相加”,进而说明什么是“(有限个自然数上的(全部)相加)重复使用加法”,于是现在要考虑的问题是什么叫做“依次相加”?对于有限个自然数
,简单的回答就是形如
就叫做有限个自然数
的依次相加. 好像这个答案不太严格,因为其为省略简化形式,那不如将“有限个自然数依某次序加起来”直接定义为“依某n阶排列中从左到右的数i对应的被加数
相加的过程”. 于是我们知道怎样在ZFC内严格化定义“有限个自然数上的依次相加”.
有限个自然数上的依次相加:“有限个自然数上的依次相加”是“有限个自然数上的(全部)相加”的特殊形式,其关键在于每一次“在有限个自然数上的一次相加”中选取的两个不同元素有一定要求、规律、看起来更加不随机. 我们先来证明一个小命题3.o:对函数
,由前面论证知存在双射函数
满足a.、b.、c.三条件,那么我们有对一切自然数
——若
则有
. 用归纳法. 对自然数0,显然有
,由条件a.知
,于是
,进而
,这就完成了归纳基始. 归纳假设对自然数
有若
则有
. 那么对自然数
,若
,由归纳假设知
为自然数,由
我们容易知道
,于是根据条件b.我们知道
,进而看到
,这就完成了归纳. 下面就是严格的陈述形式. 对函数
,由前面论证知“存在”双射函数
满足a.、b.、c.三条件. 进而对一切
,若
,进而我们可以看到
,于是根据条件b.知
是
经过“在有限个自然数上的一次相加”后变换得到的,换句话说也即“
是定义域形如
而值域是
的函数,并且
是定义域形如
而值域是
的函数,并且存在
使得
且存在从
到
的双射
使得:
和若
则
.”,此时我们对上面的
要求满足条件:
,那么我们就称双射函数
是有限个自然数上的依次相加. 结合已经证明的小命题3.0,我们可以将“有限个自然数上的依次相加”定义整理如下:设函数
,设双射函数
是关于
上的“有限个自然数上的(全部)相加”,我们说
是关于
上的“有限个自然数上的依次相加”当且仅当满足条件d.——对一切
,若
那么:存在
使得
且“
”,且存在从
到
的双射
使得
和若
则
(破折号后面陈述的条件d.结合前面已知已证不可以推出条件b.,原因是条件d.对情形“
”未作需要的说明来满足条件b.;反之条件b.明显也推不出此条件d.)(此处有一个值得探讨的问题:对一切
,若
,那么由满足条件d.给出的两个自然数
与由满足条件b.给出的两个自然数
是否有
或者部分成立?也即我们在问由满足条件d.给出的两个自然数
是否就是由满足条件b.给出的两个自然数
?答案其实是否定的,两者之间并没有太强的联系(可以相同也可以部分相同也可以完全不同),微妙就在于条件b.和条件d.定义中只是要求“存在”两个自然数满足一定条件,却没有其它限制(比如只存在两个这样的自然数),这给了我们较大的自由度去寻找与选取这两个自然数. 我可以举一个例子:从
经过“在有限个自然数上的一次相加”得到
,为满足条件d.我们可以选取
的前两项
,为满足条件b.我们可以选取
的后两项
. 更进一步的深究原因,是因为我们在根据条件b.或条件d.给出那两个自然数时已经涉及到了选择公理,而“存在性命题与选择公理的联系”详见下面引用段落里命题3.1.1的证明中粗体标记出来的部分.). 于是如果双射函数
是关于
上的“有限个自然数上的依次相加”那么显然其也是关于
上的“有限个自然数上的(全部)相加”.
设函数
是双射函数(这样的函数是存在的,最简单的如
. 这保证了我们接下来的论述不是空洞无趣的.),我们可以将其看作排列. 接下来我们需要证明““有限个自然数上的依次相加”给出的和是相等的”,这就是第一阶段的目的. 为此我们需要将“有限个自然数上的依次相加”同排列联系起来.
“有限个自然数上的依次相加”同排列的联系由下面命题给出——命题3.1:设函数
,设双射函数
是关于
上的“有限个自然数上的依次相加”. 那么存在双射函数
使得
并且对一切
若
那么
.
命题3.1证明:我们的任务就是构造出满足要求的双射函数
(函数
可能不唯一(由
共同影响),但我们只需要构造一个实例即可.).
——此引用段落的证明因有瑕疵可跳过不看,但有助于理解思考过程.
为此我们需要观察到这样一个事实命题3.1.1:对一切
,若
,那么由
是依次相加的知其满足条件d.,也即存在两个相异自然数
满足条件d.陈述的一系列性质,进而我们可以观察到有
(此处涉及到定义3.4.1(集合的象)). 此观察的直观已经在“在有限个自然数上的一次相加”口语化说明中给出,实际上此观察是在说明在有限个自然数依次相加过程中(除第一次)每次操作加法时选取的两个自然数中的一个可以看作是从最开始的有限个自然数
中选取的.
首先来给出命题3.1.1的证明.我们先来证明对一切
我们有
. 使用归纳法. 对自然数1,显然
,同时容易看到
(其中双射函数
以及自然数
是由于
根据条件b.(而不是条件d.)给出),这就完成了归纳基始. 归纳假设——对某自然数
,若
则
. 那么对自然数
,若
,那么——我们可以看到
同时有
(其中双射函数
以及自然数
是由于
根据条件d.(而不是条件b.)给出;倒数第二步是根据条件d.中
得出;最后一步推理是结合归纳假设得出.). 这就完成了归纳,于是对一切
我们有
. (结合平凡的情形
我们可以进一步得到对一切
我们有
.)
我们回到命题3.1.1的证明. 对一切
,若
,那么由
是依次相加的知其满足条件d.,也即存在两个相异自然数
满足条件d.陈述的一系列性质,结合上一段已证我们可以观察到有
. 命题3.1.1得证.
注意到在有限个自然数依次相加过程中第一次操作加法时选取的两个自然数均是从最开始的有限个自然数
上选取的,故命题3.1.1在
情形也是成立的. 这就是上面出现的“(除第一次)”可以省略也可以不省略的原因. 也即对自然数0,显然有
,由于
满足条件b.知存在两个相异自然数
满足条件b.陈述的一系列性质,于是我们看到有
. 于是命题3.1.1可以修改为“对一切
,若
,那么存在两个相异自然数
满足
.”. 在
是自然数的前提下,我们看到
,于是命题3.1.1可以进一步修改为“对一切
,若
,那么存在两个相异自然数
满足
.”.
我们现在可以回到命题3.1的证明. 我们现在着手构建双射函数
. 可以看到
,由
满足条件b.我们知道存在两个相异自然数
使得
,即
. 于是我们不妨取
(定义
也可以,并不妨碍下一步论述.)(要注意这里用到了有限选择,因为我们只是知道存在
满足条件但不知道其具体的、确定的值(或者说可能有许多组
满足要求). 关于有限选择详见引理3.5.12(引理3.1.6是引理3.5.12的特殊情形),其使用过程的具体操作就不展开了,其涉及到了借助笛卡尔乘积的表示使用一次引理3.1.6[实际上此处不一定要用笛卡尔乘积.]、或者使用两次引理3.1.6.
[
实际上此处说“使用两次引理3.1.6”有些许不精确. 为了解释清楚此点我多花点口舌. 我们知道
,进而我可以说
使得
. 进而我可以说
使得
,因为我们已经知道
就是使得上述陈述(存在性命题)成立的一个实例或解答(此处“实例(解答)”的涵义应该理解为:让我们可以按一定规则在有限步骤内验证陈述为真的例子,通俗的说就是可以帮助我们完成证明的例子. 而“例子”应该理解为:具体的、有确定数值的、可计算的、可构造的、按某种步骤可知晓的等等类似表述的某种东西(本质上这里所说的“例子”的作用是对(一阶)命题中出现的存在量词约束的变量指定(赋值)一个此变量论域中的值),在此处的语境下其(也即指“例子”)应该理解为“(用来分别给变量
赋值的)具体的、有确定数值的自然数对”,比如
.). 那好,现在开始假装你不知道(使得
成立的)
这个实例,我只是直接告诉你“
使得
”是正确的. 你相信了我的话认为它是正确的,这就相当于你确信你能通过某种方式(别人告诉你、书里、自己构造等等)找到一个实例满足上述陈述(也即找到一个实例证明陈述为真). 进而你确信“存在一个实例满足上述陈述”,到这一步通常我们就直接拿此实例来用,这也是许多数学证明的叙述方式. 但是如果我们钻牛角尖,认为“存在”不意味着我们“取到、得到、获得、实有…”,就像银行金库里有许多钱但不意味着我们拥有它们,那我们又怎么从真命题“
使得
”中得到一个使其成立的实例呢?你可能会想:只需要根据真命题“
使得
”先对
中的约束变量
使用一次引理3.1.6得到
的具体值记为
,接着再对
中的约束变量
使用一次引理3.1.6得到
的具体值记为
,至此我们就可以得到上述真命题的一个实例
. 实际上我们需要解释清楚的一点是:两次使用引理3.1.6并不是直接对集合
进行操作,而是分别对集合
和
进行操作. 但多数时候我们都忽略了此点,认为可以从
和
的论域
根据引理3.1.6直接取到我们想要的对象,虽然引理3.1.6并没有给出这样的保证.
(PS: 一旦我们取到了满足上述陈述的一个实例
,
我们就可以通过
验证“
使得
”成立.
这就是说:在一阶逻辑中公式语句里出现的相邻的两个存在量词约束的变量
可以交换位置而不改变公式语句的真值,本质上这是因为在两个公式语句中
我们要证明的性质一样(都是
). 比如我们已经知道“
使得
”是正确的,
依上面的论述我们可以根据引理3.1.6取到一个实例
,
也即知道“
使得
”是正确的,
于是我们知道“
”是正确的,进而“
使得
”是正确的,
进而“
使得
”是正确的,
于是“
使得
”成立.
类似地,在一阶逻辑中公式语句里出现的相邻的两个全称量词约束的变量
可以交换位置而不改变公式语句的真值,相关的讨论可见于徐明《符号逻辑讲义》11.4.1).
]
下面我们来讨论“存在性命题与选择公理的联系”. 一般来说,当我们使用(同义近义词还有:应用、引用、援引、依据、根据等)存在性命题时(比如上面的命题3.0),已经默认选择公理成立了(可能是弱化版本,比如上面的有限选择引理3.5.12). 因为我们需要选择公理来帮助我们选取出一个确定的对象,除非我们能为此存在性命题找到一个构造性证明(对存在性命题命题3.0——使用归纳法给出的命题3.0的证明,以及命题3.0的另一个依靠实例
(或者
等)的证明,我们可以说两者均是构造性的. 后者是构造性的我们大家应该不会有异议;而前者也是构造性的是因为:对某个确定的自然数
,我们总可以在确定归纳基始的实例后,按照命题3.0的归纳证明给出的归纳步骤在有限步骤内构造出使得命题3.0的特殊情形
成立的实例(这个实例亦是
). 只不过后者的构造性比前者的构造性更加节省计算资源(比如时间和空间等). 值得说明的是,并非所有存在性命题都有构造性证明,这里我举几个例子:命题3.1.6以及章节§8.5中的许多命题(比如命题8.5.13、(实数的)良序原理等)). 但我们使用一个命题之前一般都不会再检查其证明,而是相信命题(经学术共同体检查)是正确的可以直接使用它,进而不知道它是否存在构造性证明,所以我们经常忽略了我们已经使用了选择公理. 最后我在这里强调一点(我认为值得一提),我现在倾向于使用“选择公理”这个名词来统一指代引理3.1.6(单个选取)、引理3.5.12(有限选择)、依序选择公理DC、可数选择公理、公理8.1、(习题8.4中出现的)各种与公理8.1等价的命题等等与选择相关的陈述,主要原因有三点:a.这些陈述实际上都是在做同一件事——严格化“重复(一次、有限次、可数次、不可数次等等)使用3.1.6”,只是适用的条件、范围有差别. b.这些陈述之间有的蕴含另一些(个),我们借助这些陈述进行命题的证明时大多不会考虑哪一个“刚好够用”而是考虑哪一个更方便我的证明叙述. 除非你专门研究数理逻辑. c.这些陈述的使用像是在“黑箱抽奖”,其帮你取出来的对象具有“随机性”. 根本的原因在于命题3.1.6本身就是一个存在性命题. 比如我告诉你集合
只有两个不同对象1和2,或者你自己就可以看到集合
只有两个不同对象1和2,但无论哪种方式你都知道了信息“
,且对一切
有
”,这时你使用引理3.1.6根本不能确定你取出来的是1还是2(所见不能所得). 于是从“随机性”这个角度上说做一次选择和多次选择是一样的.) 这样我们就看到
. 现在对一切
,若
:根据命题3.1.1知存在两个相异自然数
使得
,根据条件d.知
还满足
. 由
我们知有
或
. 不失一般性,我们假设
,结合
知
,于是我们看到
,进而看到
. 进而可以看到存在
使得
,于是我们可以定义
(要注意这里用到了有限单次选择,因为我们只是知道对每个满足条件的
存在这样一个
满足条件但不知道其具体的确定的值(或者说可能有许多个
满足要求). 关于有限选择详见引理3.5.12.),于是可以看到
.
接下来我们需要说明我们上述关于
的定义是成功的(良定义)以及验证
是双射.
容易证明
. 当
时我们由前面我们看到我们已经定义
并且可以看到
;当
,我们看到
,同由前面我们看到我们已经定义了
并且有
. 综上我们函数
是良定义,其确实为定义域里的每个元素指定了值域里的一个元素为输出. 剩下的就是验证函数
是双射.
可惜至此我们不能证明我们构建的函数
是单射. 我可以举一个简单的反例. 对三个自然数
,
是
的依次相加. 按照上面构建
的思路我们可以构造出
,于是
就不是
到
的单射,因为有
.
综上,如上那样的步骤构建函数
并不能帮助我们证明命题3.1. 究其原因,对依次相加
虽然命题3.1.1给出了一些有用信息,但还不足以帮助我们证明命题3.1,命题3.1.1损失的信息(从已知可以推理出但还未被我们获得的信息)才是帮助我们证明命题3.1的关键.
为了证明命题3.1,不妨先考虑一个简单例子(比如5个自然数的相加)的依次相加
,我们通过画出
中每次“在有限个自然数上的一次相加”过程的具体操作图可以发现:在每次使用加法后,我们只不过是为此次加法求得的和以及此次加法未相加的数进行重新编码(重新编码的具体操作方式是——和用0编码,并且此次加法未相加数的新码与其旧码之间的关系是由条件d.(第1次相加是由条件b.)中的双射
给出). 比如
是
的依次相加,考虑
,其是一个
的函数. 对任意
(排除掉0是因为:在
中0是编码了第3次相加的和,那么从对简单例子画的图可以看出
定义域里排除0的数编码的就是第3次相加中未相加的数(平凡观察),同时
定义域里排除0的数编码的也是
编码的全部待相加数中(在第3次加法后)仍未相加的数(非平凡观察). 为了避免行文因追求精确性而过于繁缛,以便于读者阅读理解,我将在接下来的行文中用“未相加的数”来指称“
编码的全部待相加数中(在第n次加法后)仍未相加的数”(括号里的
是多少读者应该依上下文而定). 但读者要避免混淆上述“未相加的数”和“某次加法未相加的数”,它们之间的区别就如同上述的“(非平凡观察)”和“(平凡观察)”. 换句话说,当我的行文中出现“未相加的数”之类的字眼时,只要此字眼之前没有“某次加法”之类的定语,那么“未相加的数”指称的就是“
编码的全部待相加数中(在第n次加法后)仍未相加的数”.),我们可以看到
(
就是对
由条件d.给出的双射
,
同理;
就是对
由条件b.给出的双射
. 为了避免变量混淆,分别为它们赋予一个下标.)均是编码了同一个未相加的数(非平凡观察),也即
. 于是从此特例我们知道怎么证明命题3.1了(证明类似重新编码的逆过程,也即依次相加
的时间倒转). 如上面简单例子展示的那样,我们“重复”使用到了函数的复合(虽然例子中使用到的重复次数比较少),但如同前面讨论“有限个自然数相加”时我们采用了绕口的定义来避免写下“经过重复有限次“在有限个自然数上的一次相加””之类的语句,我们同样也需要类似地绕口操作来避免我们的证明是建立在“另一种重复”之上的(而关于“重复”的进一步探讨,我们在证明完成后的结尾再给出.).
现在回到命题3.1的证明. 已知函数
和双射函数
是关于
上的“有限个自然数上的依次相加”. 通过上面一段对简单例子的讨论,我们可以发现:为了证明命题3.1,我们必须确定依次相加
中每次“在有限个自然数上的一次相加”过程中求和的那两个数以及未相加数重新编码的关系
. 我们现在来考虑一个可能会出现的情形:从五个自然数
经过“在有限个自然数上的一次相加”得到四个自然数
. 求和的那两个数可以是
中第1项数字“9”与第3项数字“3”,也可以是
中第5项数字“9”与第3项数字“3”;进一步地,就算我们假定求和的那两个数是
中第1项数字“9”与第3项数字“3”后,未相加数重新编码的关系
也是不确定的,其可以是
,也可以是
,这是因为一次相加过程中
有两个相同的未相加数1. 综上,我们从依次相加
并不能确认每次“在有限个自然数上的一次相加”过程中求和的那两个数以及未相加数重新编码的关系
具体是哪个,虽然从依次相加
我们知道它们存在. 换句话说,我们需要使用选择公理(至少是有限选择)来帮助我们从依次相加
中选取出每次“在有限个自然数上的一次相加”过程中求和的那两个数以及未相加数重新编码的关系
,虽然大多数时候我们都没有明确说明这一点. 但思考到这里又需要考虑另一个小问题:我们从依次相加
中选取出每次“在有限个自然数上的一次相加”过程中求和的那两个数以及未相加数重新编码的关系
过程中可能多次重复使用到了有限选择. 比如我们可能对每次“在有限个自然数上的一次相加”过程都使用到了至少一次有限选择来选取出此次相加求和的那两个数以及未相加数重新编码的关系
,在这种情况下我们使用有限选择的次数与函数
中
的大小正相关,也就是说整个待相加的数越多,使用有限选择的次数越多. 正如同我们前面已说过的那样,我们不希望我们的证明是建立在“另一种重复”之上,于是我们也不希望我们的证明是建立在对“选择公理(有限选择)”的重复使用之上,否则我们上面大费周章的讨论什么是“有限个自然数上的(全部)相加”、“(有限个自然数上的(全部)相加)重复使用加法”等等就是脱裤子放屁了. 换句话说,在证明中我们需要使用选择公理(有限选择),但选择公理(有限选择)从证明叙述展现的表象上来说不能明显地被看出是“(无次数上界、无次数限制的)重复”使用,虽然从本质上、某种实质意义上来说选择公理(有限选择)的无限次使用是不可避免的. 下面我就给出这个小问题的解决大纲.
- 小问题:先对一切
,若
,那么利用有限选择引理3.5.12对自然数
根据条件b.或条件d.(只有当
时才是根据条件b.,其余情形均是根据条件d.)选取出两个自然数
.(这里好像“无次数上界、无次数限制的重复”使用到了有限选择)
- 有两种解决方案:1.使用归纳法将这种重复包装一下,也即将这种重复转化成需要使用归纳法证明的存在性命题,就如同我们对“有限个自然数上的(全部)相加”中加法的重复和下面命题3.1.2中函数复合的重复所做的那样(在此处我不选择将此存在性命题完整地陈述出来,是因为其形式是“对一切自然数
在
条件下存在一个笛卡尔乘积中的元素(
,
代表第
次相加)满足一系列性质(条件b.或d.).”,而这个笛卡尔乘积比较复杂(其是二重笛卡尔乘积,也即笛卡尔乘积的笛卡尔乘积),不管其是采用严格但繁琐的集合论构造形式还是定义3.5.7中简单明了的形式. 但实际上使用归纳法证明此存在性命题就是引理3.5.12的再一次证明(我已经在心里写过一次证明了,不信你自己写一下证明,哼.),因为从引理3.5.12的证明我们可以知道引理3.5.12不过是使用归纳法包装了“重复有限次使用引理3.1.6”. 证明了此存在性命题,我们只需要对其考虑
的情形,只需要使用一次有限选择(引理3.1.6或引理3.5.12)从
中选取出一个满足一系列性质的元素
,而
满足的一系列性质就可以说明:对一切
,若
,那么
可以看作是对依次相加
在第
次相加中具体选取的那两个自然数
(也即其就是对自然数
满足条件b.或条件d.(只有当
时才是根据条件b.,其余情形均是根据条件d.)的两个有具体确定值的自然数),其中
代表笛卡尔乘积有序n元组
的第
个分量). 2.注意到只要对任意
在第一层笛卡尔乘积中使用分类公理提前筛选出符合条件的元素(也即考虑集合
),那么可以直接对依次相加
考虑集合
,于是实际只需要使用一次有限选择(也就是引理3.5.12)就可以选取出需要的一系列
. 第1种方案像是我们亲自操作了一遍有限自然数上的依次相加(这里指的是使用归纳法证明存在性命题的过程),在操作的过程中我们自然会取出一系列具体的
;第2种方案像是有人直接给了你关于
的依次相加
,接着你就只需要在
的基础上使用一次有限选择来获得一系列具体的
. 这2种方案的具体细节我就不写了,留给读者自验(有闲情我会补上). 行文至此我想到一个问题:我们可以在多大程度上“重复”使用选择公理?对此问题我将在合适的时机给予探讨.)
- 但不管采取哪种解决方案,只要你明白我想解释清楚什么就可以了(有时候换种表达方式可以化解沟通的难题,生活中也是如此 :-). 这让我想起了林忆莲唱的《词不达意》,有兴趣的可以去听听.).
至此,我们可以说我们已经解决上面小问题. 经过上面对小问题的解决后,于是我们可以说对一切
都已选取出有具体确定值的(而不只是“存在”)
都满足——若
,则:
,且存在从
到
的双射
使得
和若
则
; 若
,则:
,且“
”,且存在从
到
的双射
使得
和若
则
. 这就是说,对依次相加
我们已经成功选取出每次“在有限个自然数上的一次相加”过程中求和的那两个数. 接下来我们需要对依次相加
选取出每次“在有限个自然数上的一次相加”过程中未相加数重新编码的关系
.
由前面一段我们知道对一切
都已选取出有具体确定值的(而不只是“存在”)
都满足——存在从
到
的双射
使得:
和若
则
. 于是我们只要使用一次有限选择引理3.5.12就可以选取出一系列
.
至此,我们可以说:对一切
都已选取出有具体确定值的(而不只是“存在”)
双射
使得——
,
且若
则
,且若
则“
”.
至此,对依次相加
:对一切
我们已经借助选择公理(有限选择)(由依次相加
)选取出“在有限个自然数上的一次相加
”过程中求和的那两个具体数
以及未相加数重新编码的具体关系
.(注意到
,这说明对依次相加
的每次“在有限个自然数上的一次相加”过程上述陈述都已考虑到了,因为我们容易验证依次相加
上的任意“在有限个自然数上的一次相加”结构都可以写成
(对某个
)的形式.) 换句话说,我们可以认为我们是按照上面的一系列具体的
从函数
开始,经过重复有限次“在有限个自然数上的一次相加”过程,最终得到双射函数
(显然此双射函数
是
的“有限个自然数上的依次相加”).
现在我们给出命题3.1.2:设函数
,设双射函数
是关于
上的“有限个自然数上的依次相加”. 对一切自然数
,对一切
(其为
定义域里的一个不为0元素),存在一个函数
(函数
拥有(同一个未相加数)码之间关系的信息)使得——对一切
,若
那么有
(码之间关系的一个小片段)(此处需要两点说明:1.关系
用到了一次函数的复合,这是允许的,因为类似于我们已经知道“怎么将两个自然数加在一起”,我们是知道怎么将两个函数复合在一起,详见定义3.3.10(复合). 一般来说,只要你的表达式是详细形式而不是省略形式,我们都认为你的叙述是严格的,更进一步的说明,详见下方关于“某种有限步骤的操作所蕴涵的信念”. 而实际上,我们接受上述“严格的”这般理解也是出于一种合情合理地“偷工减料”的无奈之举,我现在不明说这种“无奈”是什么是因为还未到时候,等到叙述的时机成熟之时再来点破此点就犹如画龙点睛之笔让各位恍然大悟;2.函数
就是前面对依次相加
已经选取出来符合要求的
);并且有
;并且对一切
有
(编码了同一个未加自然数(非平凡观察)).
命题3.1.2的证明. 使用归纳法. 首先对自然数1,显然有
. 设
. 我们需要构建出满足要求的函数
. 我们定义
. 由于有
使得
且有从
到
的双射
使得
和若
则
. 于是我们看到
,于是我们可以定义
,并且可以知道
是定义成功的了(其确实为定义域里的每个元素指定了值域里的一个元素为输出). 于是我们可以看到对一切
,若
,于是我们可以看到
,此时显然有
. 并且我们看到
. 并且由于
和
,于是看到对一切
,有
. 这就完成了归纳基始.
归纳假设. 对某自然数
,若
,那么有:对一切
,存在一个函数
使得——对一切
,若
那么有
;并且有
;并且对一切
有
.
那么对自然数
.
由归纳假设知
,进一步知
. 现在假定
,于是看到
,进而
,结合
进一步得到
,于是有
. 那么对一切
,由于有
使得
且“
”,且有从
到
的双射
使得
和若
则
. 于是我们看到
. 由于
,根据归纳假设知对
存在一个函数
满足归纳假设已说明的一系列性质. 我们将在
的基础上构建出我们需要的函数
. 现在来构建函数
:对一切
,我们定义
;对一切
,我们定义
. 容易发现
是良定义(其确实为定义域里的每个元素指定了值域里的一个元素为输出). 接下来我们只需验证函数
满足我们希望有的性质. 对一切
,若
,我们分情形讨论:1.若
,进而我们容易看到
,也即
. 此时有
;2.若
,即
,即
. 此时
. 综上,我们有对一切
,若
那么有
. 同时我们也看到有
. 同时对一切
:当
时,可以看到
;当
时,可以看到
. 综上,函数
满足所有我们需要的性质. 这就完成了归纳.
现在继续命题3.1的证明. 现在我们正式开始着手双射函数
的构建. 容易证明
. 显然
,于是由前面论述我们可以定义
(定义
也可以,并不妨碍下一步论述.),同时我们可以看到
. 当
时,我们看到
,于是可以看到有
,进而同样由前面论述我们看到对
有
且“
”且
. 由“
”知有
或
,不失一般性,我们假定
,于是结合
我们可以看到
,再结合
可以看到
. 那么根据命题3.1.2我们知存在函数
使得——对一切
,若
那么有
;并且有
;并且对一切
有
. 至此我们可以定义
. 于是此时对一切
,若
,那么可以看到
,进而有
,也即
.
回顾上述双射函数
的构建过程,我们使用到了存在性命题3.1.2. 正如我们前面所说的那样,在使用存在性命题时我们要万分小心,也许我们需要选择公理(有限选择)来帮助我们取得一个所需对象. 除此之外我们还要求整个证明对“选择公理(有限选择)”的使用是有限度的(正如前面所做的那样). 至此,我们回顾命题3.1.2的证明可以发现其是用归纳法证明的(存在性命题),命题3.1.2的证明是构造性的(换句话说,每个函数
都可以按照命题3.1.2的证明给出的步骤在有限步内构造出来,我们只是用归纳法包装了这个有限步构造.). 我们注意到了此点之后,就明白我们在双射函数
的构建过程中使用到的
是确定的实例,并不需要选择公理(有限选择)帮我们选出一个所需对象. 于是我们对证明的要求(“选择公理(有限选择)”的使用是有限度的)是自动成立的. 当然,这里我给出另外两种处理方式:I.忽视命题3.1.2的构造性证明,而是仿照上面对小问题的处理方式,依命题3.1.2的存在性陈述“有限度”使用选择公理(有限选择)来选出函数
进而以备在
构建过程中使用;II.将命题3.1.2中陈述“存在一个函数
”修改为“恰存在一个函数
”,然后再进行命题3.1.2的证明. 两种处理方式前者应该走得通(借助笛卡尔乘积的概念),后者也许可行,留给读者自验,我就不写了.
接下来我们需要说明我们上述关于
的定义是成功的(良定义)以及验证
是双射.
由前面可以看到我们已经定义
并且可以看到
;当
,我们看到
,同由前面可以看到我们已经定义了
并且有
. 综上我们函数
是良定义,其确实为定义域里的每个元素指定了值域里的一个元素为输出. 剩下的就是验证函数
是双射.
首先来验证
的单射性. 设
且
. I.当
时:显然由
知
,进而有
. II.当
时:有
. 而同时由
是函数
定义域中的一个元素我们看到




,
于是我们看到
,进而看到
. III.同II.理可证当
时有
. IV.当
时,类似的说明可以看到
和
. 我们“假设”在此IV.情形下有
,也即
. 不失一般性我们假定
,由于
均是双射函数,于是我们看到
(对双射函数
,其逆
的定义详见注3.3.24. 此说明也适用于其余双射函数),也即
(我们根据命题3.1.2中函数
从
不断倒推回到
过程中的一系列码编码的应该是同一个未相加数(非平凡观察),故不应该出现
编码了第
次相加中的相加数
. 简而言之不应该有
,于是我们知道怎么继续证明了.). 同样地由
是函数
定义域中的一个元素我们看到



(当
时结合
以及
可知
,此时有
,说明此步由于不存在而跳过并直接取得推理最后一步. 对后续省略的推理步骤中类似的情况不再说明,换句话说由于
,即
,于是我们总是在情形
之前取得推理最后一步(情形
),也即情形
不会出现在推理链中.)

(
),进而我们看到
,结合前面已经得到的
我们看到一个矛盾,故我们的“假设”不成立,也即在IV.情形下仍有
.
综合上述对情形I.~IV.的讨论,我们证明了
是单射.
现在来验证
的满射性. 由于
是单射,于是由命题3.6.14(d)我们知
,这就说明了
是满射. 因为如果
不是满射,那么至少存在值域里的一个元素
使得对一切
都有
,进而
. 而我们容易看到
,由命题3.6.14(a)、(c)知
,此矛盾说明“
不是满射”不正确,故
是满射.
综上,
是双射.
综合
是双射,以及在
的构建过程中已经验证过的性质
、对一切
若
那么
我们可以看到命题3.1得证.
回顾上述对“函数
是双射”的证明,若我们非要鸡蛋里面挑骨头的话,可以看到:在证明
的单射性对情形II.、III.以及IV.的证明过程中“重复”使用到了函数的复合. 正如我前面多次强调我们不希望我们的整个证明是建立在“另一种重复”之上的,所以我们需要将这种“函数复合的重复”用归纳法包装一下,就类似于命题3.1.2及其证明. 有了上面的简单讨论,对情形II.,我们应该用归纳法证明如下命题3.1.3:设
. 对于上述函数
构建过程中使用到的由命题3.1.2给出的函数
,对一切
,若
那么有
.
命题3.1.3的证明:
命题3.1.3展现的直观是——对于
编码的同一个未加数(非平凡观察),此未加数在第
次相加过程中(即
)的(相邻)编码分别为
和
. 由于我们前面已经说明:对于依次相加
,在每次使用加法后,我们只不过是为此次加法求得的和以及此次加法未相加的数进行重新编码(更一般地说,这句话对“有限个自然数上的(全部)相加
”也适用,
不要求必须是依次相加的.). 于是我们可以看到此未加数在
中的新码
可以根据双射函数
转换回在
中的旧码
. 所以我们可以看到旧码
应该属于函数
的值域,所以我们有
,也即
.
当然,以上直观并不是命题3.1.3的严格证明,下面我将给出其严格的归纳证明.
归纳基始——对自然数0:显然有
. 此时有
. 于是我们看到
是双射函数
定义域里的一个元素. 于是我们看到
是
值域里的一个元素,也即
. 这就完成了归纳基始.
归纳假设——对自然数
:若
那么
.
归纳步骤——对自然数
:设
. 于是我们看到
. 于是根据命题3.1.2我们看到
. 同时结合归纳假设我们看到
. 由于已知
,于是可以看到有
,进而可以看到
. 这说明
是双射函数
定义域里的一个元素. 于是我们看到
是
值域里的一个元素,也即
. 这就完成了归纳(本质上此归纳是向后归纳原理,详见习题2.2.6.).
至此,我们可以说:对一切自然数
,若
那么
.
回到命题3.1.3的证明. 已知
,于是我们看到
,进而有
,于是看到
. 于是对自然数
:我们看到
,结合上面的归纳证明我们看到
.
综上,命题3.1.3得证.
有了命题3.1.3,我们现在继续上面包装情形II.论述中出现的“函数复合的重复”.
对自然数
,显然有
,于是由命题3.1.3知有
,也即
.
至此,沿用上述情形II.证明中的说明. 由于
,于是看到
(
是根据
的定义,也即函数
的定义.),结合上一段的论述我们看到
,进而看到
且
,而接下来需要的论述已在上述情形II.证明中展现过,就不再重复了. 至此,我们用归纳法(命题3.1.3用到)完成了对上述情形II.的证明中出现的“函数复合的重复”包装.
由于情形III.与情形II.是类同的,只不过是变量
与
的互换. 也就是说上述关于情形II.的包装只需少量修改即是关于情形III.的包装,故省略.
现在我们只需要对剩下的“情形IV.”进行类似的包装就可以达成我们前面的目标(鸡蛋里面挑不出骨头). 我还是写一下吧,反正我挺无聊的.
沿用上述情形IV.证明中的说明,我们可以看到
. 同时我们沿用上述情形IV.证明中假定的
至此. 结合已证的命题3.1.3以及上面有过的论述,我们容易看到
以及
.
沿用上述情形IV.证明中说过的“假设”
,结合上一段得到的
,我们可以用一个符号
来同时指称
和
,也即我们有
. 显然我们可以看到
.
在命题3.1.3的证明中给出的直观里我已经说过:对于依次相加(或全部相加)
,在每次使用加法后,我们只不过是为此次加法求得的和以及此次加法未相加的数进行重新编码. 现在,让我们在整个依次相加
中考察
所编码的那个自然数
. 由于
,也即
,所以在(依次相加
中)第1次相加并未使用到
所编码的那个自然数
. 接着我们为此待相加自然数
赋予一个新的编码
,以便进行
的第2次相加. 如此地重复操作下去,直至待相加自然数
在
的某一次相加中被使用到. 这就是待相加数
在
中的“轨迹”,此“轨迹”由
的各个编码
逐步展现.
有了上面的说明,现在再来回顾命题3.1.2,我们发现命题3.1.2中的函数
就是上面所说的关于待相加数
(非平凡观察)在
中的“轨迹”. 由于
,也即
,这就是在说“轨迹”
和“轨迹”
具有相同的“起点”
,进而“轨迹”
应该重合于“轨迹”
(这是由于假定了
,所以“轨迹”
相比于“轨迹”
应该更“长”.) 至此,我们知道我们应该证明什么命题了,我将其陈述如下.
命题3.1.4:设
,设
. 现在考虑根据命题3.1.2构造出来的两个“轨迹”函数
,我们有:如果
那么——对一切
均有
.
命题3.1.4的证明:使用归纳法. 设
.
归纳基始——对自然数0,显然有
,并且已知有
.
归纳假设——对自然数
,我们有若
则
.
归纳步骤——对自然数
,我们假定
. 进而我们看到
,于是我们看到
,进而我们看到
,同理可得
. 再由
结合归纳假设我们看到
,进而有
,也即
. 这就完成了归纳步骤.
综上这就完成了归纳,于是我们可以说:在“
”前提下可以说对一切自然数
有若
则
.
我们回到对情形IV.证明的包装上来. 由“假设”
我们看到
,
结合已证命题3.1.4我们就可以看到
,也即
(这是因为
).
等式
对应于上面情形IV.证明中的原等式
,换句话说我们对“情形IV.证明”的包装进行到了“
”出现的地方.
我已经在情形IV.的证明中解释了等式
不合理之处,所以我们只需要将原解释套用给等式
,下面做的就是这件事.
命题3.1.5:设
,设
. 考虑由命题3.1.2构造出来的“轨迹”函数
,我们有:对一切
不等式
和
均成立.
命题3.1.5的证明:命题3.1.5展现的直观是——对“轨迹”函数
编码的待相加数
(非平凡观察),其(
)是在(依次相加
的)第
次相加(即
)过程中仍未被加法相加起来的,换句话说我们应该有
. 进一步地,对小于
的第
次相加(也就是说
),我们也应该有
在第
次相加过程中仍未被加法相加起来,也即应该有
.
有了上面的说明,我们现在就给出命题3.1.5的严格证明. 设
. 于是我们看到
,进而根据命题3.1.3我们看到
,也即
,进而有
. 这就完成了命题3.1.5的证明.
有了命题3.1.5,我们马上就看到
(这是因为
). 至此我们得到了矛盾“
”. 至此我们用归纳法(命题3.1.4用到)完成了对上述情形IV.的证明中出现的“函数复合的重复”包装.
显然,上述情形IV.的证明(以及其包装)使用到了反证法(因为我们“假设”了
). 我们当然也可以直接证明情形IV.,下面就给出情形IV.的直接证明.
为了达成我们的上述目的,现在还是回到(我们先前已经讲过的)依次相加(或全部相加)
的直观.
考虑
,其是一个定义域形如
而值域为
的函数. 换句话说,
为依次相加
的全部待相加自然数进行了逐一编码,进而这些编码即为各待相加自然数在依次相加
中“轨迹”的“起点”.
在经过
的第1次相加后:
编码的各待相加数中已被相加数的“轨迹”已经从“起点”走到相加的“终点”而不再延续;同时
编码的各待相加数中仍是(下一次相加的)待相加数的新编码可以根据双射函数
依旧编码得出. 这里我们有一个重要的发现——对于经过第1次相加后
编码的各待相加数中仍是待相加数的自然数,它们“轨迹”的“起点”必定是不同的,本质上这是因为
是双射. 进一步地,由于
均为双射,我们可以猜测——每一次相加后,
编码的各待相加数中仍是待相加数的自然数,它们“轨迹”的“起点”也必定是不同的. 这就引出了下面的命题3.1.6.
命题3.1.6:设
,设
且
. 考虑根据命题3.1.2构造出来的两个“轨迹”函数
,我们有
. 我这里再多嘴一次,我们可以认为我们在证明命题3.1.2后有:对一切
,对一切
(也即对一切
)均已选取出确定的唯一实例
. 关于这点我在函数
构建完后的下一段已经阐述过. 换句话说,我们从函数
的构建开始(也即命题3.1.2的证明完成之后),一切出现的(由命题3.1.2给出)形如
的“轨迹”函数均是由
确定的唯一实例(比如在
的构建(及其验证)中、命题3.1.3及其证明中、命题3.1.4及其证明中、命题3.1.5及其证明中、现在的命题3.1.6及其证明中、其余边边角角的叙述说明中等等以及接下来的所有叙述说明).
为了证明命题3.1.6,我们先来做一个观察. 设
,设
. 根据命题3.1.2我们知道对未相加数
(非平凡观察)有一个其在依次相加
中的“轨迹”函数
,但就如同命题3.1.4为我们揭示的那样,各“轨迹”之间有重合的情况,换句话说有些“轨迹”是另一些“轨迹”的前段. 实际上这是因为重合的“轨迹”编码的是同一个未相加数(非平凡观察),也就是说不同的
和
表示的未相加数
可能是同一个未相加数(非平凡观察). 而就如同命题3.1.4前一段中我们说过的那样,重合的“轨迹”具有相同的“起点”,这就引出了证明命题3.1.6需要的命题3.1.7,我将其陈述在下面.
命题3.1.7:设
,设
. 考虑根据命题3.1.2给出的“轨迹”函数
,我们有——对一切
均有
.
为了证明命题3.1.7,我们再来做一个观察. 设
,设
. 由
可以看到
. 再由
看到
,进而有
. 于是
结合
可以看到
. 综上现在我们考虑根据命题3.1.2给出的两个“轨迹”函数
是合理的. 而“轨迹”
可以理解成是:“轨迹”
在第
次相加(即
)后在节点
末添加一个新节点
,换句话说即“轨迹”
重合于“轨迹”
并且“轨迹”
只比“轨迹”
“长”一个节点
. 这就引出了证明命题3.1.7需要的命题3.1.8.
命题3.1.8:设
,设
. 由前面一段的讨论我们知考虑根据命题3.1.2给出的两个“轨迹”函数
是合理的. 我们有结论——
(即两个“轨迹”是重合的).
为了证明命题3.1.8,我们还是来做一个观察. 设
. 设
. 设
. 现在我们来考虑根据命题3.1.2给出的两个“轨迹”函数
,设有
. 这就是说两“轨迹”
有个共同的节点
,而此共同的节点编码的未加自然数(非平凡观察)是唯一确定的,同时任一“轨迹”函数的各节点编码的均是同一个未加自然数(这从命题3.1.2也可以看出),进而此两“轨迹”函数编码的是同一个未相加自然数(非平凡观察),用公式来阐述就是我们发现了
. 综上,“轨迹”
是重合的,进而它们有相同的“起点”,也即有
. 这就引出了证明命题3.1.8需要的命题3.1.9.
命题3.1.9:设
. 设
. 设
. 现在我们来考虑根据命题3.1.2给出的两个“轨迹”函数
,设有
. 我们有结论——
(即两个“轨迹”是重合的).
命题3.1.9的证明:使用归纳法.
归纳基始. 对自然数0:显然有
. 此时我们看到有蕴涵式成立——若
那么
. 这就完成了归纳基始.
归纳假设. 对自然数
:若
那么我们有蕴涵式成立——若
那么
.
归纳步骤. 对自然数
:假设
. 再接着假设
. 我们需要证明此时有
. 由已知容易看到
. 于是由命题3.1.2我们看到
,结合已经假设了的
我们容易看到
,也即
. 再由
和
以及归纳假设中的蕴涵式我们看到蕴涵式的后件成立,即有
. 这就完成了归纳步骤.
至此,我们可以说:对一切自然数
,若
那么我们有蕴涵式成立——若
那么
.
进而看到:对一切
那么我们有蕴涵式成立——若
那么
.
由于在命题3.1.9的陈述中我们已经假设了有
和
,于是结合前一段可以看到有
. 这就完成了命题3.1.9的证明.
现在我们回到命题3.1.8的证明.
命题3.1.8的证明:由命题3.1.8的已知我们看到
,进而看到
,于是根据命题3.1.2我们看到
,即
. 结合前面论证根据命题3.1.9我们看到有
. 这就完成了命题3.1.8的证明.
现在我们回到命题3.1.7的证明.
命题3.1.7的证明:使用归纳法.
归纳基始——对自然数
:显然有
,此时
. 这就完成了归纳基始.
归纳假设——对自然数
:如果
那么有
.
归纳步骤——对自然数
:假定
,进而看到
. 由于
,于是我们看到
,进而看到
,也即
.
结合
我们看到
,也即
. 至此从归纳假设可以看到有
.
由已知以及
,根据命题3.1.3我们看到有
. 进而我们看到
. 由双射函数
的定义(主要是看其定义域和值域)以及可以看到
,进而看到
,也即
.
至此,我们看到
,以及
. 于是我们可以运用命题3.1.8,根据命题3.1.8我们看到
.
再结合
我们可以看到
. 这就完成了归纳步骤.
综上,命题3.1.7得证.
现在回到命题3.1.6的证明.
命题3.1.6的证明:使用归纳法,对变量
进行归纳.
归纳基始——对自然数1,显然有
. 设
且
. 进而我们看到
,根据命题3.1.2可以看到
. 由于函数
是双射以及
,于是我们看到
,亦即
. 这就完成了归纳基始.(当然,从命题3.1.4我们可以看到若
那么有
,也即
(这是个矛盾). 但本质上这样的论证方式使用了反证法,因为我们需要假设
(这与命题3.1.6给出的结论
是相矛盾的). 所以,为了“直接证明情形IV.”的目的,在这里我们不应该采用这样的论证方式.)
归纳假设——对自然数
,若
那么:若(
且
)则
.
归纳步骤——对自然数
,我们假定
. 我们接着假定有
且
. 现在我们需要证明
.
由归纳假设中“对自然数
”可知对在归纳步骤中出现的自然数
我们有:
. 进而归纳步骤中的假定
可以改进为
,进而我们可以看到有
. 综上,我们有
.
由命题3.1.2我们知道有
. 由于
是双射并且
,于是可以看到
,也即
. 现在考虑双射
(的值域),结合上一段
我们可以看到
,进而观察到
,也即
.
综上,我们可以看到
、
以及
,那么根据前面的归纳假设我们可以看到
.
而根据命题3.1.7我们知道有
,结合上一段我们可以看到
. 这就完成了归纳步骤.
综上,我们证明了——对任意正自然数
,若
那么:若(
且
)则
.
至此,上一段论述结合命题3.1.6的题设我们容易看到
,也即我们用归纳法完成了对命题3.1.6的证明.
回顾上面命题3.1.6的证明,我们发现我们是将命题3.1.6转化为了可以用归纳法证明的一阶命题“对任意正自然数
,若
那么:若(
且
)则
.”. 实际上当我们面对需要证明一个关于自然数的命题时,这样的转化是经常出现的. 但有的人不习惯以及不熟练于寻找这样的(可以用归纳法证明的)转化命题,这是因为寻找的过程需要你花点心思来做各种一阶命题的变换. 这些人更习惯于直接对所证命题中关于自然数的变量(对命题3.1.6即为对变量
)进行归纳,我将在下方以证明命题3.1.6为例展示这种归纳证明方式的证明梗概,进而便于你理解和比较.
直接对所证(涉及自然数的)命题中关于自然数的变量进行归纳(命题3.1.6的证明梗概).
归纳基始——对自然数1,假定
后证明命题3.1.6在此特例情形下成立.
归纳假设——对自然数
,若
那么命题3.1.6成立.
归纳步骤——对自然数
,假定
后结合归纳假设证明命题3.1.6在此特例情形下依然成立. 进而完成归纳证明.
上面的归纳证明看似比前面转化命题的归纳证明要简略简洁,但实际上当我们着手把上面的证明梗概写成完整证明时,发现事实并不是这样. 当我们对上面的证明梗概展开分析时,本质上我们是在证明这样的一个一阶命题:对任意正自然数
,若
那么——若(
且
且
)则
(当然还有许多类似的等价一阶命题,这里就不过多讨论了.).
至此,我们可以看到两种归纳证明的证明思路本质上是一样的,甚至转化命题的归纳证明比另外一种更加简洁简略让人易跟随易懂,所以在上面的大部分论述中我采取了使用“转化命题”的这种论述方式. 简而言之,采用“转化命题”这种论述方式会使得我们的思考稍许繁琐(因为要找“转化命题”)但证明的(形式化)叙述更加简洁(如果抛弃形式化的要求,大部分的数学证明可以写的相当简洁简略,比如参照数学哲学里面的直觉主义.);同时对于读者来说表象上证明叙述是变得简洁了但内在的证明思路(比如为啥要证一个看似和原命题没有多大关系的转化命题)可能不能马上从证明的叙述里领悟到,读者往往是在证明叙述的末尾才明白证明的核心“转化命题、以及其与原命题的关系”. 而另一种归纳证明对证明者来说思路是简单直接的,但证明的(形式化)叙述不一定也是简洁的;同时对于读者来说证明的内在思路是清晰明了的但证明的表象叙述可能更加繁杂. 这有点类似于人类写的(稍简略)证明和机器写的形式化证明,至于我们应该采用哪种归纳证明方式,要看证明者的取与舍了.
现在我们回到对情形IV.的证明. 已知
,进而可知
. 沿用假定
,我们可以看到
. 我们现在需要证明此情形下有
,也即证明
.
由于
,进而可以知道“轨迹”
比“轨迹”
要“长”. 为了利用上命题3.1.6,我们要把“轨迹”
“截短”到和“轨迹”
一样“长”,而前面证明的命题3.1.7正好可以帮助我们达成目的. 由于
、
(从函数
的构建过程中)、并且
,根据命题3.1.7我们可以看到
.
这就将
之间的比较转化为
和
的比较. 接着我们只需要证明
以及
即可利用上命题3.1.6.
从函数
的构建过程我们容易知道
. 而前面对情形IV.使用到反证法的证明的包装中(也即反证法证明情形IV.的严格重写论述)我们已经证明
,而我们可以注意的到得到结论“
”的过程并没有用到反证法,因为只要对前面的论述仔细检查审核就可以发现得到结论“
”只需要命题3.1.3以及命题3.1.5(而两者均没有用到反证法). 这就是说,此处我们可以直接把“
”当作一个结论来使用,因为我们可以照搬前面的论述只用命题3.1.3和命题3.1.5而不用反证法就可以证明“
”. 综上,我们只需要证明
即可利用上命题3.1.6.
而“
”是根据命题3.1.3在情形
下(结合
以及命题3.1.2中的部分结论,这里的作用主要是为了论证
与
)容易得到的.
综上,我们知道了
、
以及
成立,进而根据命题3.1.6我们马上得到
,进而结合已证
可以看到
,也即
.
至此,我们分别使用反证法(至少证明主体是反证法)以及(纯血的)直接证明完成了对(
单射性讨论中)情形IV.的证明. 可以看到使用反证法的证明要比直接证明简洁很多,但反证法的使用也是有前提条件的,反证法需要以演绎法(即真命题只能推理出真命题)和排中律的承认作为前提. 现在我们来审视一下反证法的证明结构,进而了解反证法是如何起作用的.
反证法的证明结构:I.在使用反证法之前,我们有一些不证自明的公设公理(一般来说,公设公理是建立在不思辨(辩)的原始概念、符号等(比如“点”的概念)之上的. 这也是机器证明(也许)可行的理论基础,我们只需要用一些符号来代表表示这些原始概念,然后形式化公设公理,剩下的推理证明工作就交给机器来做. 但并非所有理论都可以被有限形式化,比如ZFC,ZFC的替换公理实际上是公理模式.)、已知的引理命题定理等等陈述组成的集合(类等等诸如此类的将某些事物收集在一起的概念)作为整个证明(反证法也是如此)的起点,换句话说我们认为整个证明的起点中的陈述为真(一般来说“陈述”的数量是有限个. 因为如果为无限个(比如可数个(实际上当我们讨论非有限、无限个陈述、前提时,至多也只能是可数个,不可数个陈述前提是不可(用有限的语言来)描述的))的话,原则上我们可以将结论作为整个证明的起点的一个陈述(也即将结论作为已知)而不改变整个证明起点中所有陈述组成的基数(即集合的势,此概念衡量集合中元素的多少.).
II.为了使用反证法证明我们的结论,我们先假定我们的结论为假,根据排中律我们知道结论的否定为真. 然后我们将结论的否定与已知前提综合起来进行逻辑演绎推理,最终在推理的某一步得到一个矛盾.
III.此矛盾说明结论的否定与已知前提是不一致的,这说明在我们承认结论的否定为真时我们不能(完全)承认已知前提为真,这是不可接受的.
IV.由于我们默认已知前提为真,故结论的否定只能为假,否则我们不能(完全)承认已知前提为真.
V.由于结论的否定只能为假,再次根据排中律,我们知道结论为真.
一般来说,当直接证明命题比较困难时就会尝试使用反证法.
读者应该也发现了,上述对情形IV.的直接证明中采用了倒叙倒推的论述方式,但许多数学书的叙述方式更多是搭手脚架建大楼的形式. 实际上倒叙倒推的论述方式更符合我们的思考过程.
从上述对情形IV.的直接证明中我们也可以看到直觉主义、构造主义、结构主义、逻辑主义以及形式主义的影子. 柏拉图主义和有限主义的讨论在此不表.
我们当然可以先证明函数
的满射性再接着证明其单射性,但证明留给读者自证了,我就不写了.
¶ 一点题外话.
¶ 当我们分析思考问题时(不一定是数学问题,任何问题都可以,包括日常生活中的问题,只要你有疑问.),就像在爬一座山一样. 不同高度、不同时间、不同天气、不同心情、不同同伴等等因素都会让你看到不同的风景,这些风景就如同我们在寻找问题答案(解决办法)的过程中产生的思绪,思绪一开始可能是杂乱无章毫无头绪的,⌈横看成岭侧成峰,远近高低各不同。⌋很好地描述了这种状态.
¶ 但只要你坚定自己的信心一定要得到一个答案来解答内心疑惑时
(这个答案更偏向于让你获得自身内在的安宁,而不是偏向于让你
取得与自身(狭义上的)利益相关的什么东西,比如外在的金钱、物
质、美色、专利、荣誉、名声、威望、职位、权力、地位等等诸
如此类. 但这并不是说“内在安宁”与“自身利益”像鱼与熊掌一样不
可兼得,而是想强调选择这样的生活实践路径后你能得到的“自身
利益”更像是附属品、妙手偶得之物(甚至其与你付出的时间精力心
血相比在世俗层面上可以忽略不计). 如果你现在更注重“自身利
益”,那么选择这样的生活实践路径就是南辕北辙了. 实际上就如
同人的两条腿大差不差才能正常行走,两者并没有什么优劣之
分,都是帮助你获得身心灵的平衡,进而更好地、更加自在地生活.)
,就如同一定要爬到山顶的信念给你带来的方向感,你心里自然而然就有个解决问题的大方向. 这个解决问题的大方向就像目所能及的山路,这段山路你只有动脚去走才能知道通不通山顶,这个解决问题的大方向你只有去做才知道行不行的通(孙楠的歌曲《方向感》或能带给你些许鼓舞信心勇气,潘松和的《青春之火》、魏允熙的《炙热》、打扰一下乐团的《艰难之路》和ILLENIUM/Nevve的《Fractures》也不错.).
¶ 进而要么经过有限次尝试发现解决问题的大方向行得通你寻获到了一个满意的答案,要么不行(比如上面对于命题3.1我观察到的命题3.1.1这个大方向). 如果解决问题的大方向经过尝试后确实行不通,就如同你爬山中发现大道人山人海通行不畅,你也许就会将目光扫向旁边四周,在机缘巧合之下或许会发现一个因陡峭而人少的小路,这条小路就是你从原先爬山路径中获得的经验或发现,这些经验或发现会让你找到另一个爬山路线,类似的那么依照原先解决问题的大方向的实践中获得的经验或发现同样会帮助你找到另一个大方向(比如上面我发现命题3.1.1不能帮助我完成命题3.1的证明,促使我借助特例来更加细致地分析我忽略了依次相加中的什么信息,从而寻找到新的方向命题3.1.2).
¶ 继续前进下去,也许你会发现此小路是条死路返回大道才是正解,也许你会发现此小路是通往山顶的一条快道. 但你在分岔口时知道现实中选择的对错好坏吗
(这里对现实中选择的优劣判断不是根据你在实际做出选择之前的
模拟选择预测臆想结果(由于想象力是无限的,所以对模拟选择在
某种意义上是无言真假. 实际上对虚幻的东西(比如一款电子游
戏、一部玄幻小说等)我们更重视自身体验感而不是在意其中的各
种真假对错善恶,尤其当其中的各种判断影响到你的体验感沉浸
感时,因为你总能意识到其是虚幻的、不真的(就如同当你对一部
电视剧中的反派人物恨之入骨时可能下一秒你就出戏了,你会
想:自己为什么要这么生气,演戏嘛,现实中不一定会有这么坏
的人,就算有自己也不一定会碰到,生气有什么用还伤身,还是
想想电视剧中的XX哥哥/妹妹吧,他好帅好Man/她好可爱...;或
者你会想:我不开心了,还是打打电子游戏开心一下吧. 然后你自
己就又开心了.). 而对于个人体验感那只能说是萝卜青菜各有所
爱,这就叫千金难买爷高兴,也叫⌈天真⌋难求.),而是以实际做出
选择之后某时刻的结果、现实为依据(颇有事后诸葛之味). 但我们
要明白福祸相依的道理,你对选择优劣的判断并不总是一成不变
的,其是会随着之后结果现实的变化而改变. 关于选择之道,我的
建议是遵从你自己的内心意愿,主打一个不后悔、不到黄河心不
死、不撞南墙不回头、不见棺材不落泪、自己选的自己受着.)
?别人告诉你的就一定适合你吗?除去登上山顶,沿路的风景也很重要啊. 就这样如此地前进下去(有点类似在路上开车,你会不断调整自己的路道、道路、速度等等因素直至到达目的地.),并不断观察周围的风景与发现进而有意无意地在心灵脑海里留下印象与思绪,边走边分析整理,你会发现一开始杂乱的风景、思绪以及两者之间原来有许多关联. 比如你在分岔口偶然听见别人说山顶有一座塔,后来你独自一人走在小路上时真就在一个转弯处初见到了山顶上的塔. 这就叫⌈生活并不缺少美,而是缺少发现美的眼睛。⌋,你所获得的所有(不管你认为是对的错的好的坏的有意义的无意义的有趣的无聊的等等)信息在某种程度上都可以帮助你来修正你的认知与方向,进而让你对整座山和问题有更全貌与全局的理解. 这就叫⌈兼听则明⌋、⌈真理越辩越明,道理越讲越清,事实胜于雄辩。⌋、⌈魔鬼藏在细节中⌋.(当然,我可以就此处展开长篇大论,但我不这么做,原因有两点:1.为了整个题外话讨论的结构更加合理与紧凑,避免喧宾夺主、主次不分. 就如同你看到的那样,在整个题外话的讨论中我时不时需要在括号“()”内加以进一步的解释,这是为了让我的陈述更加精确准确正确的同时减少歧义,进而便于让你理解的同时避免我的言论被(无意或恶意地)曲解. 但大量括号“()”里的解释也让整个题外话讨论的结构比较破碎,陈述不够连贯. 这就是我做的取舍与平衡,为了陈述的语义准确性而牺牲掉了些许陈述的连贯性、整个陈述结构的紧凑性,这就叫⌈有舍才有得⌋,这也是矛盾化解与平衡的一个实例. 2.只要你通过我的言论思想获得了正知正念,你自己也就可以就着“⌈兼听则明⌋、⌈真理越辩越明,道理越讲越清,事实胜于雄辩。⌋、⌈魔鬼藏在细节中⌋”三者展开长篇大论,而不必我写. 换句话说,我的目标是让你获得正知正念后接着自己能够成长起来(⌈正知正念⌋与⌈自我成长⌋是相辅相成互相促进的;相反的,⌈邪念恶知⌋与⌈自我堕落⌋也是相生相成互为因果的.),而不是一直要依靠别人、依靠别人给你判断而没有自己的主见,简而言之就是我要让你能够⌈知微见著⌋、⌈扬善弃恶⌋(我觉得此处用⌈扬善弃恶⌋比⌈扬善抑恶⌋好,因为有时候个人的恶的念头不可避免,甚至在某些情景下越抑止恶的念头反而其会反弹地越厉害. 所以我们能做的就是察觉我们自身恶的念头是如何有意无意产生的,接着习惯它的产生方式和套路,进而可以容易地忽略、舍弃它. 当然,如果你能改变自身不良习性以及人格劣性那就更好,但这个更难达成的操作也是需要“你更好地认识你自己”为前提的. 简而言之,⌈扬善弃恶⌋更偏向适用于个体以及原因(“原因”意指:未行动前、未攀缘前),⌈扬善抑恶⌋更偏向适用于整体(比如整个社会)以及结果(“结果”意指:行动后、攀缘后. 比如常说的⌈知错能改善莫大焉⌋与⌈扬善抑恶⌋在“避免接着犯下更大的错误”这个角度来说是差不多的;而⌈扬善弃恶⌋在这个角度就有些许不准确,因为小恶已经造成,如果改成⌈扬善弃大恶⌋那么就比较契合这个角度了.),两者都是对的只是观察的角度不同,两者又都是错的因为适用范围有限,全因观察者的观察角度而定.).)
¶ 当你到达了山顶开心(或不开心)下山、寻获到了一个答案后(不管此答案在当时(寻获到的时候)给你的个人感受是满意、开心、惊讶、悲伤还是怎么样的),在某日再回想起来
(这里就要假定你得到答案后还是在好好生活,没有放弃自己.
可能此刻的你对我强调的这个假定感到有点奇怪和莫名其妙,但
是只要你仔细一想就容易知道这个假定是必不可少的,否则下面
接下来的话语就成了空谈. 如果你偏要问我为什么一定要强调这一
点,我只能回答:“这是学数学的人要有的严谨性!严格的论述说
明懂不懂(狗头保命o.0”. 如果你在得到答案的那一刻想放弃自
己,去听听棉花糖的《无以名状的快乐与悲伤》吧,白色海岸的
《雨和我们拥抱在一起》、《我们想去的地方 I'll take you anywhere》
也不错;如果你觉得我上面推荐的三首歌的基调有点悲伤,你或许
会喜欢胡夏的《那些年》,虽然我觉得《那些年》更应该在下面
你获得体验性的智慧时被推荐. 这类型的歌曲很多的,听听歌曲
放轻松总是不错的.)
,你发现你那次爬山经历的风景就如同一幅(动态)全景图、你发现你寻找问题答案的过程中产生的思绪竟然自动串成了一条条逻辑清晰结构层次优美的主线支线明线暗线,与你自己寻找答案的经历(准确地说是指记忆在你心识脑海中的画面、声音、情绪等信息)交相呼应构成了一个(大制作)电影. 虽然现实中没有那个(动态)全景图和(大制作)电影,但它们却真真实实存在于你的心思脑海中(心印),美不胜收,(内心)余音不绝.
(此处我强烈推荐Priscilla Ahn的《I am not alone》,杰伦哥的
《花海》、许绍洋的《花香》也不错哦,李宇春的《忽然之间》、
鹿晗的《我们的明天》、胡歌的《忘记时间》、胡夏的《那些年》、
钟汉良的《嘿,你还好吗》、杨坤/郭采洁的《答案》和傅如乔的《微微》
也是不错的视角,还有很多类似歌曲,我就不一一举例了.)
如果非要用语言来形容描述那种感觉的话,我觉得⌈山河粉碎,大地平沉。(虚空粉碎,大地平沉。)⌋和⌈观察者(首次)观察到自身⌋再贴切不过了;或者借苏格拉底之言⌈I know nothing except the fact of my ignorance.⌋来解释:初见⌈I know nothing except the fact of my ignorance.⌋时我们也许会将它翻译成“我一无所知除了我的无知(这一事实)。”;但现在我们还可以将其翻译成“我体悟到了(证悟到了、感觉到了、察觉到了等)空性(道、真空、真如、空非(虚)空、我心光明、真相大白、不存在、不可言说之物、不可思议之物、超越等)除了我的无知(此处的⌈无知⌋应该理解为——无:没有;知:知识、识、分辨等,其与⌈慧⌋相对.)这一事实。”. 后一种翻译化简一下就是在说“我体悟到了(而不是单单知道)空性除了我的没有知识、我体悟到了(而不是单单知道)空性除了我的慧、我发现了我的本心并已了解一切(包括真相、实相)(这里的“了解一切”并非意指⌈全知全能⌋,而是指:有能力、有潜力去探究理解一切事物、存在、甚至是超越存在的不存在等等. 本质上⌈全知全能⌋和⌈慧⌋就像一枚硬币的两面,都是真相的表达与体现.)、我的心已经空空如也了、我明心见性了”,当然由于我不是专业的翻译,加之对宗教哲学历史文化人文等也涉猎不深(用大白话讲我就是个⌈半文盲⌋,没有著作等身,只会随处看看到处东拼西凑些东西胡诌些文字聊以自慰),上面对⌈I know nothing except the fact of my ignorance.⌋的翻译也许有学贯中西的大家翻译的更加信达雅,所以若我的翻译不好也请众人高抬贵手而不要指责我误人子弟(凑合着看吧). 这两种翻译让我想到了康德的⌈二律背反⌋,但我对康德没什么研究,所以就在这里提一下作个引子留给有缘人来探究吧. 所以在这里我只讲讲我的初步理解:前一种翻译中对⌈nothing⌋以及⌈ignorance⌋的翻译是“绝对否定”的(⌈一无所知、一无所有⌋,⌈无知⌋);而后一种翻译却为我们揭示了“绝对否定就是绝对肯定”,⌈一无所知、一无所有⌋就是对⌈空⌋的肯定,⌈无知⌋就是对⌈慧⌋的肯定,就如同无穷大的反面就是无穷小. 我们中国的语言文字里有太多成语词语诗句文章等描述此种感觉了,比如:⌈否极泰来⌋、⌈山重水复疑无路,柳暗花明又一村。⌋、⌈众里寻他千百度。慕然回首,那人却在,灯火阑珊处。⌋、⌈苦海无涯,回头是岸。⌋、⌈踏破铁鞋无觅处,得来全不费工夫。⌋、苏轼的《定风波·莫听穿林打叶声》、⌈星星之火,可以燎原。⌋等等. 当然,对此种感觉西方人也有描述,比如维特根斯坦说:“不能说的东西必须对之保持沉默。”,所以我们才会用⌈不可说⌋、⌈不可思议⌋、⌈妙不可言⌋等词语来指称此种感觉此种境界;再比如雨果说:“世界上最宽阔的是海洋,比海洋更宽阔的是天空,比天空更宽阔的是人的心灵。”. 让我们把眼光放广一点,其实数学中也有对此的描述:概率为0的事件不一定是不可能事件. 借用一下克里希那穆提Jiddu Krishnamurti的话语⌈观者即被观之物⌋,你是风景的观察者,但在你的心里还有一个观察者觉知着你以及你的所有观察,两个观察者类似于脑和心、小我与大(高)我的区别
(当然克里希那穆提自己讲⌈观者即被观之物⌋时想表达的内涵应该
不是我这里想表达的意思. 换句话说,⌈观者即被观之物⌋这句话可
以有多种角度的理解和解读,不同理解和解读的正确性准确性要
依不同情景状况、不同目的、甚至是各观察者的观察角度等而定
(这就如同⌈盲人摸象⌋). 所以我这里只是借用克里希那穆提之语来
表达我自己的观点,从我的观点言论里读者你自己解读出来的意
思观点理解以及后续行动等与我无关,那是你自己的事情,你是
你自己的第一责任人,本质上你也只能为你自己负责(这就叫⌈君子
之交淡如水⌋,看似淡如水的交流互动等因没有直接参杂过多利益
纠葛等而⌈无所得⌋,但这何尝不是一种对君子们的保护. ⌈上山容易
下山难⌋、⌈上了贼船想下来就难了⌋、⌈只因一著错,满盘俱是
空。⌋、⌈一着不慎,满盘皆输。⌋、⌈一失足成千古恨⌋讲的正是⌈君
子之交淡如水⌋的另一面啊.). 至于⌈观者即被观之物⌋更深层更隐秘
的内涵,我冥冥之中察觉到那与世界运行的本质有关,或者说它
让我们窥见了世界运行机制的冰山一角,但我没有能力进行更加
深入的探讨了.)
. 行文至此我又再一次想起了林忆莲唱的《词不达意》,或许《词不达意》除了可以表达单相思之人对所爱之人“词不达意”的情感,还有我上面所表达的另一层意思,类似的歌曲还有范玮琪的《是非题》、杨宗纬的《洋葱》等等. 你发现了,爬到山顶找到答案不是最重要的目的,风景才是;下山一样有美丽的风景,甚至比爬山更美!至此你也明白了这就叫做⌈不识庐山真面目,只缘身在此山中。⌋,不管经历中你的感受体会在不同时间不同阶段是怎样的(好的坏的、对的错的、美的丑的、被理解的被误解的等等),那只不过是整个过程中的一个小片段、一次小曲折、一段小高潮,并不会影响你最终获得美的感受、获得体验性的智慧. 所有的一切都是在帮助你看明白山和问题,所有的一切都是传递真相的手段和方法,这就叫⌈尽善尽美⌋,虽然多数时候我们如同管中窥豹一般对待这一切. 也许兴奋的你会用画、文字、音乐、游戏等媒介传递出你心中的美,希望别人也能领略一下. 至此只属于你自己的个人历险完美画上了句号,我想用两首歌分别呼应历险的开始和结束:陈明的《快乐老家》和南征北战NZBZ的《我的天空》;而在追求美的感受的历险过程中,我送给你蔡依林的《看我72变》.
PS: 我只是想借用爬山来类比思考的过程. 这种思维方式十分有用,尤其是当我们面对新问题或未知挑战时. 但其缺点也十分明显,它讲究一个事无巨细亲力亲为,故耗时耗力耗神. 在现代快节奏生活中,不是每个人都能有机会去接触此种思维方式,更不用提在理解和实践的相互促进中掌握它了. 实际上这种思维方式最难之处在于其需要你自己内观自身的思维,只有这样你才能观察到你的万千细微思绪,进而才能分析整理好思绪之间的前因后果、才能对自身思维的联想造作跳跃链条有个较为清晰的认识. 一旦你学会了内观自身的思维,主要的好处有两个:第一是你能够根据现实情况灵活地“随机应变”而不是再拘囿于头脑中的知识或条条框框,这是因为你已通过内观训练明白自身思维的习性、易犯错之处以及局限性. 但有的人剑走偏锋,利用上述第一点使自己处事变得⌈圆滑⌋而不是⌈周全⌋,我希望所有读者都能注意到⌈圆滑⌋与⌈周全⌋两者之间的根本区别,进而可以减少自己被好心办了坏事、减少自己被人卖了还帮着数钱、减少自己被太过不合理的PUA等等诸如此类;第二是你能更容易地大幅度改造改进改正自己头脑中的思维定势,俗称“自己革自己的命”,因为这就是内观训练的本质.
从上面我们可以看到命题3.1.2能够帮助我们证明命题3.1而命题3.1.1不能.
现在回到第一阶段的目的:证明“有限个自然数上的依次相加”给出的和是相等的.
设函数
,设双射函数
是关于
上的“有限个自然数上的依次相加”、双射函数
也是关于
上的“有限个自然数上的依次相加”.
现在我们要证明
. 现在我们很难从命题3.1直接得到此结论
,我们还是要回到最初的直观上来帮助我们思考进而完成第一阶段的目的.
n阶排列的“相邻对换”:设
是排列(此处是为了论证的需要,将0也包含进了n阶排列中. 一般来说n阶排列中数字均为正整数.),也即
均是双射. 我们称
为关于
“相邻对换”的n阶排列当且仅当——存在
使得
,并且对一切
均有
.
上述n阶排列的“相邻对换”的定义还是很直观的,一个简单的例子就是排列
.
由命题3.1知存在双射函数
使得
并且对一切
若
那么
、以及存在双射函数
使得
并且对一切
若
那么
.
我们现在假定n阶排列
是关于
“相邻对换”的,借助直觉我们知道接下来我们需要证明
. 换句话说,只要某(有限自然数)依次相加
由命题3.1给出的排列是“相邻对换”的,那么就应该有
.
设
,我们将分三部分来逐一考察
的关系. 已知
.
I.
;
II.
;
III.
.
I. 我们先来证明——对一切自然数
,若
那么有
.
I. 证明:当自然数
时命题是空真的成立的(此时
是关于
“相邻对换”的,情形I.应省略过.),故我们只需考虑自然数
的情形. 此时显然有
.
使用归纳法. 显然有
. 对自然数1,若
,由于
以及
是关于
“相邻对换”的,我们可以看到
. 这就完成了归纳基始.
归纳假设某自然数
,若
那么
.
那么对自然数
,若
,进而容易验证
以及
,于是我们可以看到
. 由于
,我们可以看到
,结合归纳假设我们看到
. 这就完成了归纳步骤. 故对一切
均有
.
II. 我们再证明
.
II. 证明:当
时我们要证的就是
,此时n阶排列
是关于
“相邻对换”的. 根据命题3.1我们知
并且
. 再由于n阶排列
是关于
“相邻对换”的我们知道有
,进而我们可以看到
. 这就证明了当
时有
. 我们只需再考虑
的情形.
假定
,结合
进而看到
,进而看到
,于是我们考虑
与
是合理的.
由第一部分I.的证明可知有
. 现在我们只需继续考虑
与
的关系. 由于已经假定
以及已知
,所以我们容易看到
,再根据命题3.1我们看到
以及
.
当
时
可以写成
,以及
可以写成
. 再由于此时
是关于
“相邻对换”的我们看到
以及
,于是我们可以看到
,这就证明了当
时有
.
考虑完了
的情形后,我们只需再考虑
的情形. 此时我们容易知道
,由命题3.1可以知道
以及
. 由于
是关于
“相邻对换”的我们看到
,结合第一部分I.的已证
我们可以看到
.
综上,我们当
时恒有
.(此情形的讨论有些繁杂是因为我们要仔细地处理某些边界情况. 比如排列
的“相邻对换”位置出现在排列的开端、中间或者尾端.)
III. 现在我们来证明——对一切自然数
,若
那么有
.
III. 证明:当
时,也即
,也即
,结合已知
我们知道此时有
. 换句话说,此时
是关于
“相邻对换”的,情形III.应该省略. 故现在我们只需考虑
的情形.
使用归纳法. 当
时命题是空真地成立的.
现在对自然数
,容易知道
. 此时容易知道
,故由命题3.1知道
以及
. 由于
是关于
“相邻对换”的,故我们知道有
. 结合第二部分的已证
我们看到
. 这就完成了归纳基始.
归纳假设对某自然数
,若
那么有
.
那么对自然数
,假定
. 容易看到
以及
,进而由命题3.1可以看到
. 由于
是关于
“相邻对换”的,故我们有
(这是因为
). 由于
结合归纳假设我们看到
. 这就完成了归纳步骤.
综上,我们可以说对一切自然数
那么有
.
至此我们马上可以看到有
.
至此,只要某(有限自然数)依次相加
由命题3.1给出的排列是“相邻对换”的,那么就应该有
.
以上“只要某(有限自然数)依次相加
由命题3.1给出的排列是“相邻对换”的,那么就应该有
”的证明所做的工作其实就只是严格逻辑化形式化下面的省略形式(博文前面亦出现过)
省略形式
依照加法结合律
依照加法交换律
再次依照加法结合律
对直觉主义者和构造(结构)主义者来说,上面的省略形式就已经十分严格了,但逻辑主义者和形式主义者会认为上面的省略形式只是证明的大体框架.(笑,我在写数学八股文.)
由于n阶排列均可以“重复”使用“相邻对换”进行转化,故对任意依次相加
我们均有
,这就完成了第一阶段的目的:证明“有限个自然数上的依次相加”给出的和是相等的.
正如前面所说,我们希望证明不是明显的建立在某种步骤的重复之上,我们还是需要使用归纳法将““重复”使用“相邻对换””进行包装一下.
关于“n阶排列均可以“重复”使用“相邻对换”进行转化”此命题,我们可以这样想:任意n阶排列均可以“重复”使用“相邻对换”转化成标准排列
,反过来
也可以“重复”使用“相邻对换”转化成任意n阶排列. 故任意n阶排列均可以通过先转化成标准排列再转化成目标排列.
现在我们还是用归纳法的语言来给出“n阶排列均可以“重复”使用“相邻对换”进行转化”的严格证明.
设
是排列,那么我们有对任意对换
均可以通过“相邻对换”得到.
证明:对自然数1,若
,显然
是“相邻对换”,这就完成了归纳基始.
归纳假设对自然数
,若
那么对换
可以通过“相邻对换”得到.
那么对自然数
,若
,不失一般性,我们假定
,进而有
,进而有
. 由归纳假设知对换
可以通过“相邻对换”得到,而同时
也是“相邻对换”,故
可以通过“相邻对换”得到,这就完成了归纳步骤. 综上,对一切自然数
,只要若
那么对换
可以通过“相邻对换”得到. 进而对任意对换
,显然有
,故对换
均可以通过“相邻对换”得到.
有了上面的结论,我们很容易得到:n阶排列均可以“重复”使用“相邻对换”进行转化.
证明:对自然数0,0阶排列就是
,此情形是平凡的.
对自然数1,1阶排列有
,显然只需要一次“相邻对换”就可以在
之间进行转化. 这就完成了归纳基始.
归纳假设对自然数
,
阶排列均可以只使用“相邻对换”进行转化.
那么对自然数
,对
阶排列
,若
,那么
阶排列去掉最后一个数字后即是
阶排列,由归纳假设可知此时
阶排列可以只使用“相邻对换”进行转化;若
,由前面结论知对换
可以通过“相邻对换”得到,做完对换
后我们可以看到
,这就回到了前面的情形
,故
情形与情形
也可以只使用“相邻对换”进行转化;再由于
情形的排列可以以情形
的排列为中间步骤进行变换,也即先通过“相邻对换”均变为情形
的排列,再利用上归纳假设即可证明
情形的排列可以只使用“相邻对换”进行转化. 这就完成了归纳步骤.
故n阶排列均可以使用“相邻对换”进行转化.
完成了第一阶段的目的后,我们开始第二阶段目的的证明:“有限个自然数上的全部相加”给出的和是相等的.
设函数
,设双射函数
是关于
上的“有限个自然数上的全部相加”. 我们现在要证明“有限个自然数上的全部相加”给出的和是相等的,其就是等于“有限个自然数上的依次相加”给出的和.
由于函数
是双射函数,也即对
值域中任一元素恰存在一个定义域中元素映射到它,于是
值域中元素
可以用
定义域中元素来编码成
,也即我们有对一切
我们有
.
对一切
我们在前面的讨论中已经说明
其是定义域形如
而值域是
的函数.
下面我们将证明:对关于
的“有限个自然数上的全部相加”
,我们有——对一切
,对一切
存在集合
使得
,并且有
,并且对任意
只要
那么均有
.
证明:使用归纳法. 首先显然有
. 设
,显然存在集合
使得
. 并且有
. 且对任意
只要
那么均有
. 这就完成了归纳基始.
归纳假设——对某
,对一切
存在集合
使得
,并且有
,并且对任意
只要
那么均有
.
归纳步骤——对自然数
,设
. 设
. 考虑第
次相加
,也即
,其是“在有限个自然数上的一次相加”. 换句话说,存在
使得
,并且存在从
到
的双射
使得
和若
则
. 进而那么对0,由归纳假设我们知存在集合
使得
,进而我们看到
. 再由于
以及归纳假设我们知道
,进而有
. 综上,对
确实存在
使得
. 现在来考虑
,由前面已知我们看到
. 由归纳假设我们知道对
存在
使得
. 进而对一切
,我们看到存在
使得
.
由前面讨论显然我们可以看到
;对一切
可以看到
,故有
. 现在我们来证明
. 我们将使用归纳法证明:对任意
,对任意
均有
. 归纳基始. 显然
,此时
,故对任意
均有
. 这就完成了归纳基始. 归纳假设. 对某
,对任意
均有
. 归纳步骤. 那么对自然数
,假定
,
. 由归纳假设可知对某
有
. 若
或者
,我们可以看到
;否则我们有
,进而看到
. 综上,我们总有
. 这就完成了归纳步骤. 故对任意
,对任意
均有
. 这就证明了
. 综上,我们证明了
.
现在我们只需证明:对任意
只要
那么有
,就可以完成我们上面的归纳证明. 不失一般性,我们可以假定
,此时
. 由于
,故我们可以看到
,进而可以看到
. 由函数
的定义可以看到
. 于是由归纳假设可知
,也即
,也即
. 当
时也有类似论述. 那么剩下的情形就为
. 此时可以看到
. 由于
是双射,故由
可知
. 再由归纳假设可知
,也即
. 这就完成了全部的讨论,至此我们可以说:对一切
,对一切
存在集合
使得
,并且有
,并且对任意
只要
那么均有
.
现在,我们取
,由上讨论知存在集合
使得
. 再由
我们可以看到
,进而看到
,这就说明了“有限个自然数上的全部相加”给出的和是相等的,其就是等于“有限个自然数上的依次相加”给出的和.
实际上,上面的证明只能算是“证明大纲”,因为上面的证明用到了大量的后置知识,比如说减法等等. 这就是前面所提的“画龙点睛之笔”让各位恍然大悟.
某种有限步骤的操作所蕴涵的信念:我们总是抱有这种信念——有限步骤的重复操作总可以使用归纳法严格表达出来. 因为我们抱有此种信念,故有时候我们并不总是采取严格的归纳法形式,而是更易于阅读理解的省略口语化形式.
重复的探讨:重复重复,什么是重复?每天的日升月落应该算作重复,但如同哲人所说:我们并不能两次踏入同一条河流,那么重复的本质是什么呢?我认为是事物所具有的“共性、相同点、相似处”. 那抽象出来的“共性、相同点、相似处”即被理解为“重复”.
4.自然数的排序. 定义2.2.11定义了自然数的排序,其“
”的定义不是使用“
或
”,而是“存在某自然数c,使得
”. 我们来证明两种定义的等价性.
若知道
或
. 如果
,由命题2.2.12(a)知
;若
,由定义2.2.11中“严格大于”的定义知有
.
若知道
,由定义2.2.11知存在某自然数c,使得
. 如果自然数
,则
,即
;如果
,由命题2.2.12中(e)中讨论知
,再由
和定义2.2.11知
. 综上由
可知
或
.
所以,当我们用自然数中“
”的概念时,可以用定义2.2.11,也可以用“
或
”. 使用后者在证明某些命题时可能带来方便,而且和后面比例数和实数的序的定义是相容的.
我们还可以证明
如果
且
,那么
.
当且仅当
.
当且仅当
.
这些命题在上面某些习题中用到.
并且容易验证自然数的序满足代入公理(因为自然数的序是由加法定义的,而加法满足代入公理).
5.自然数的相等. 注意到上面的许多证明上我们都用到了自然数的相等的概念,并默认其遵从相等的四条公理——自反、对称、传递和代入公理. 前面三条统称等价关系. 而后面整数、比例数、实数的相等概念却要定义和验证. 这是因为我们的自然数定义是公理化的,不是构造性的. 皮亚诺公理定义的自然数只是给了我们这样的直观:0,0++,(0++)++,…,而没有给出它的模型,所以我们为了逻辑的目的默认其遵从相等要求的四条公理.