Science 版 (精华区)

发信人: zjliu (分析数学), 信区: Science
标  题: 证明的证明（五）
发信站: 哈工大紫丁香 (Fri Sep 27 14:22:44 2002) , 转信

  

反过来说，如果我们有了一套符号和一组公式的形成规则和公式的变形规则（以及公理
），我们也就有了一个形式系统，可以在里面进行“证明”的活动了。最好让我们来看
一个例子，我举一个迷你型的形式系统。

1)这个形式系统中的符号就三个：a、b、★，前面两个我把它叫作“字母”，后面这个
叫“关联”（我随便取的名字）。

2)引入一个中间的概念“词”，一个词就是一个长度大于等于1但是有限的字母串，比如
abbabaa。

3)这个形式系统里的公式是这样的符号串：I★J，其中I和J都是词，比如aaab★ababa就
是一个公式，而aaabba★★a却不是。

4)公理就一条：a★b

5)变形规则：

　5-1)如果I★J是一个公式，那么可以同时在两个词后面加上一个字母，比如Ia★Ja，
或Ib★Jb。
它们的意义是很不相同的：第一个“证明”是在元理论中的证明，是我们平时所说的那
种证明，而后一个“证明”是形式系统中的证明，就是我们上面用公式串来定义的证明
）。观察两条变形规则和唯一的公理，我们知道一个定理左边的词一定至少和右边的一
样长，或者更长，而且5-2)会使左边的词加长，所以如果bba★aab被证出来了，那么这
个证明的最后一步（就是最后一次变形）一定是用了5-1)，但这不可能，因为通过5-1)
变形出来的命题两词一定有相同的结尾，而bba和aab却不是这样，所以bba★aab不可能
是定理。

　　我们还可以发现bab★aab也不可能是定理。如果它是定理，那么证明它的最后一步
一定是用了5-1)，也就是说它必须由ba★aa推出，同样，ba★aa必须由b★a推出。但是
很明显b★a不是定理，因为很容易看出左边词长度为1的定理只有a★b这一条。

　　于是通过上面两条，bbab★aab不可能是由5-2)证出来的，所以只能是由5-1)证出来
。于是如果bbab★aab是定理的话，bba★aa必须是定理。但是这是不可能的，为什么？
就留给大家思考了，推理完全和上面一样。

　　再强调一遍，“aabab★baab”是形式系统中的定理，而“aabab★baab是形式系统
中的定理”以及“bbab★aab不可能是系统中的定理”是元理论中的结论。
来源:·交大兵马俑BBS站 bbs.xjtu.edu.cn·[FROM:山城梁山]




--

※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 202.118.229.86]