[音乐] 嗨,你好!欢迎回来,那么前面我们说了这个归纳
法,归纳法定义这个集合,而且我们顺便用归纳法
定义出自然数来了,你是不是觉得归纳法特别的强大
那么我们当然归纳法定义出来的集合,它是一个很好的一个集合
那么有了这个归纳定义之后,我们实际上可以用来做很多的事情 比如说这个归纳原理,那么假设一个集合A,它是通过归纳
定义所定义出来的集合,也就是它通过基础条款、 归纳条款以及
终极条款,然后规定出来的这么一个集合的话 那么,如果我想证明A当中所有的元素都具有某种性质P
所谓的具有性质P,也就是说,每一个元素放在这个
P的谓词里面,它访问都是为真,对吧,也就是说任意x 只要x属于A,它就必然蕴含着P(x),就P(x)也为真
那么如果想要证明这个,那么有归纳定义 所定义出来的集合就可以用归纳原理来做如下的证明
首先证明第一,证明归纳基础,就是针对这个归纳定义当中
的基础条款,我们来证明说基础条款当中所涉及的所有的这些初始
的元素,都使得这个P为真,每一个元素x。
,x₁他都会使 P为真,它就变成了命题了,P为真,这是归纳基础
然后归纳推理,也就是说我们要证明,想办法证明这个归纳条款,第二个条款,归纳条款是能够
保持这个性质P,那所谓的保持性质P呢,就是说
我先假设归纳条款当中已经确定的元素x 它是能够使得P(x)为真了
在这个假设的前提下,然后呢,证明用归纳条款当中的这个操作g
因为归纳条款总是从已知的元素 用一个映射然后变成一个新的元素,就是有一个规则生成器
新的元素,那么我们把这个生成的过程抽象成一个什么,抽象成一个操作
把这个操作叫一个名字,叫作g,那么它实际上就是一种函数了 它是一种函数,函数可以把x映射成另外一种别的东西
那么它生成的g(x)仍然具有性质P 也就是说P(g(x))为真,如果证明了这两个
有归纳基础,有归纳推理,那么我们就可以完成这个归纳
那么依据这个归纳原理,我们实际上可以去证明我们已经定义过的一些
用归纳定义的一些集合,它具有某种性质
我们曾经提到过,在数理逻辑里面这个命题公式也是用归纳定义来定义的,对吧
那么我们就试着说,看看命题公式里面它有一些什么性质,我可以用归纳原理来进行证明呢
那么我们来看看这个例子,命题公式当中的左括号的数量等于右括号的数量
当然,这个我们可能从来没有想过这会有什么问题 因为我们潜意识里头认为,括号嘛,它总是成对出现的
既然成对出现,那它肯定就会相等,对吧 当然,你这种话呢,并不严密
我们把它变成这个数学语言,变成符号,形式化的证明来看一看
我们用归纳原理来证明,因为命题公式本身它是由 归纳定义所对应的集合,所以呢,我们可以用归纳原理来证明它
那么我们假设这个有两个函数L和R
L[A]呢就返回左括号的数量,R[A]呢就返回公式A的右括号的数量
那么我们最终要证明任何一个公式A L[A]都等于R[A],是吧,那先我们看这个归纳基础
在命题公式当中,它的这个基础条款是 命题常元、
命题变元,这些都是命题公式 那么我们发现命题常元和命题变元P、
Q、 R、 S这些东西,它本身不带任何的括号,所以呢 它的左括号等于0,右括号也等于0,那当然自然就会相等
那归纳基础我们成立了,第二个呢,就是归纳推理
归纳推理我们假设因为它是,我们回忆一下命题公式这个归纳定义 第二个这个递推规则就是说
假设A、 B是公式的话,那么A蕴含B
加括号也是公式,A加上一个否定连接词加括号也是公式 对吧,那么所以呢,我们从假设
A和B这两个,它既然已经是命题公式了,那么我们假设呢 它这个性质是成立的,也就是L[A]=R[A]
L[B]=R[B],因为它是命题公式嘛 那好,我们来证明说,这个由A和B生成出来的这个新公式
它也符合这个左括号等于右括号的这个性质 那么我们先来看这个¬A加括号,那么¬A加括号的左边
它的左括号的数量是多少呢,它应该很明显 它是A的左括号的数量再加上1,因为它增加了一个左括号,对吧
那么L[A]既然等于R[A],那么我们就可以写成等于R[A]加1
那么等于R[A]加1,那么R[A]加1又恰恰是这个R[(¬A)]
因为R[(¬A)]是A的这个右括号的数量再加上1
哎那么它们之间就相等,就架起这个相等的桥梁,所以我们证明的第一个
这也是意料之中的一件事情,那么第二个呢,我们看这个
蕴含,蕴含呢稍微复杂一点,因为它涉及到2个公式,那么我们也是从两头往中间来走
那么L[(A→B)],那么它就等于A的左括号的数量加上B的左括号的数量再加上1
对吧,那么R呢,AB,A蕴含B,那么它也是
右括号的数量,A的右括号的数量加上B的右括号的数量再加1,因为多了一个右括号出来 然后呢,我们对比这2个式子
由归纳假设,归纳假设里头,L[A]=R[A],L[B]=R[B]
那么等量加等量,它还是等量,所以中间这个等号又终于
建立起这个桥梁,所以呢,L[(A→B)]它确实是等于R[(A→B)]的
是吧,那这样呢,我们就得出结论 对于一切的命题公式而言,左括号的数量就等于右括号的数量
这就是归纳原理所给我们带来的一个
强大的一个证明的工具,它可以证明用归纳定义所定义出来的集合
的每一个元素,不管是这个有限集合还是无穷的集合
它的每一个元素我不需要去挨个的去检验,它就能够具有某种性质P