Yann | Tardis

Gödel, Escher, Bach: An Eternal Golden Braid 哥德尔、艾舍尔、巴赫：集异璧之大成 Douglas Hofstadter 侯世达 9787100013239

上一章里，作者介绍了一个叫做“命题演算”的形式系统，这章第八里作者开始介绍一个全新的形式系统，叫做“印符数论”，简称TNT（Typographical Number Theory）。我的理解是，这是一个用印符来描述数论（N）的形式系统，但与此同时TNT和N又是不一样的东西。所谓数论（N），是描述自然数（0，1，2，3……）的句子。

比如说这样一个数论“5是素数”，我们可以重新叙述一下，即“不存在这样的数a和b：它们都大于1，而且5等于a乘以b。”也就是说，对于数论的描述，我们通常可以通过以下这些短语来总结：对任何数b、存在一个数b使得、等于、乘以、加上……

那么我们现在就开始来构造这个TNT了。

数字：0，S
0表示0。
当在一个串前加上一个S，即表示这个东西的“后继”。例如，SS0表示2。

变元：a、b、c、d、e或者加撇的a’、b”等
表示那些非指定的数或者说可变的数。

术语：+，⋅，=
分别表示乘以和加上，但是必须加上括号来构成串、而且这样的运算永远是二元的。

原子与命题符号：P，Q，R，~x，<x∩y>，<x∪y> ，<x→y>
也就是上一章里命题演算的所有符号也都适用于TNT。

自由变元与量化变元
这两者都是在一个串中含有变元，但是区别在于：
1）前者是开公式，后者是闭公式；
2）前者表达的是一种性质，后者表达的是一种断言；
3）前者可以被认为是（不带主语的）一个谓语；后者则是带有主语的句子；
4）前者仅仅有变元，后者必然还带有量词。

量词：∃，∀
存在量词∃代表“存在”。例，∃b:(b+S0)=SS0，代表存在一个b使得b加1等于2。
全称量词∀代表“任何”或者“所有的”。例，∀b:(b+S0)=SS0，代表任何b都使得b加1等于2。

我们构造完TNT的所有元素之后，我们来尝试用TNT来描述前面那个数论“5是素数”，即“不存在这样的数a和b：它们都大于1，而且5等于a乘以b。”用TNT来描述的话就是：~∃a:∃b:SSSSS0=(SSa⋅SSb)

在这里我想特别提一句，因为这里出现了一个让我们后来非常困惑而且到现在也有点不解的地方，这里出现了~。表达“不存在这样的数a和b”的方式，为什么是“~∃a:∃b:”而不是“~∃a:~∃b:”呢？~的这个否定，到底否定在哪里呢？再比如“~∀b:”的意思，应该是“对于任何b都不使得”，还是“不是任何b都使得”吧？“对于任何b都不使得”不就是”不存在b使得”吗？“不是任何b都使得”不就是“存在一个b不使得”吗？

其实这一点我现在还有点头晕，先记下一笔，希望待会我再重做那几道练习题的时候可以想明白。

刚才作者已经用TNT表达了数论“5是素数”，那么我们在尝试表达数论“存在有无穷多个素数”，即“对于每一个数a，存在一个大于a的数b，具有这样的性质：不存在大于1的数c和d，使得b等于c乘以d。”
∀a:∃e:~∃c:∃d:(a+Se)=(SSc⋅SSd)

另外值得一提的是，对于同一个数论，TNT的表达方式可以是多种多样的。

接下来，作者给大家出了6道翻译题。这6道题目大家翻来覆去做了好几遍，互相讨论，不断推翻和被推翻得出的结论。但是却依旧很难达成作者给出的提示，即这6题中有两个为真四个为假，或者四个为真两个为假。

我先把题目抄下来。

1. ~∀c:∃b:(SS0⋅b)=c
2. ∀c:~∃b:(SS0⋅b)=c
3. ∀c:∃b:~(SS0⋅b)=c
4. ~∃b:∀c:(SS0⋅b)=c
5. ∃b:~∀c:(SS0⋅b)=c
6. ∃b:∀c:~(SS0⋅b)=c

据我的理解，翻译是这样的：

1. 不是所有数都是偶数。（真）
2. 所有数都是奇数。（假）
3. 对于任何一个c，总存在一个b使得2b≠c。（真）
4. 不存在一个b，使得任何一个c=2b。（真）
5. 存在一个b，使得不是所有c=2b。（真）
6. 存在一个b，使得任何一个c≠2b。（假）

现在我再想起来，似乎又能达成作者的“四真二假”的提示了。后来我在网上试图寻找这几道题目的“官方答案”，却只找到似乎是一个学生的解释。总体而言和上面的是一样的，却不知道到底对还是不对。

~∀c: ∃b:(SS0⋅b)=c    TRUE
I found it useful to translate ∃b:(SS0⋅b)=c (leaving c as a free variable) before I started to worry about the second quantifier. Proceeding directly, this says “There exists a number b such that two times b = c.” Thinking about the meaning of this phrase, I arrive at “c is a multiple of 2”, or simply “c is even”. Then the entire expression becomes ~∀c: c is even and direct translation gives “It is not the case that every number c is even”, or simply “Not all numbers are even”. This is certainly true.

∀c: ~∃b:(SS0⋅b)=c    FALSE
Starting again with ∃b:(SS0⋅b)=c as “c is even”, handling the negation as “It is not the case that c is even” or “c is odd”, and then proceeding with the universal quantifier, I arrive at “Every number c is odd” or “All numbers are odd”. This is false.

∀c: ∃b:~(SS0⋅b)=c    TRUE
I’m most comfortable with ~(SS0⋅b)=c as “2⋅b ≠ c”. Then, working to the left, I see “There exists a b such that 2⋅b ≠ c” and I handle the second quantifier as “For every number c there is a number b such that 2⋅b ≠ c” or “Given the number c, I can find a number b that forces the inequality 2⋅b ≠ c”. This is true even when c is even; for example, take b to be 1 if c is not 2, and take b to be 2 if c is 2.

~∃b: ∀c: (SS0⋅b)=c    TRUE
I find it useful again to start on the left. I understand ∀c: (SS0⋅b)=c as “For every number c, 2⋅b=c”. Then the entire sentence becomes “It is not the case that there exists a number b with the property that for every number c, 2⋅b=c” or, if you like, “There is no single number b for which the equation 2⋅b=c holds for every c”. This is true.

∃b: ~∀c: (SS0⋅b)=c    TRUE
This one’s tough because of where the negation sits. My ear likes the negation expressed as “It’s not true that 2⋅b=c holds for every c”. This helps me to avoid the mistranslation “For every c, 2⋅b ≠ c”.Well, it is almost certainly true that the statement “2⋅b=c holds for every c” is false, so that our ~∀c: (SS0⋅b)=c is almost certainly true, no matter what b we choose to work with. Let me be specific. “There exists a number b such that the statement “2⋅b=c holds for every c” is not true”. With b=10, for example, the equality 2⋅b=c only holds for c=20 and not for every c.
In fact, you can make a stronger true statement: ∀b: ~∀c: (SS0⋅b)=c, because for any b you choose, 2⋅b=c will only hold for one value of c and not for every c.

∃b: ∀c: ~(SS0⋅b)=c    FALSE
While the last expression had us working with “it is not the case that equality holds for every c”, this one has us consider “it is the case that inequality holds for every c”. Thus the statement is “There exists a number b such that no matter what number c you choose 2⋅b ≠ c”. This is false: given b=10, for example, choose c=20 causing the inequality to fail.

关于这几道习题，又带来了更多的问题：

1. 为什么量词的前后顺序有着不同的意义呢？
2. “~∀b:”应被解释为“不是任何b都使得”，那它是否等价于“∃b:~”呢？
3. 还有那个依然没有解答的问题，表达“不存在这样的数a和b”的方式，为什么是“~∃a:∃b:”而不是“~∃a:~∃b:”呢？位于最前面的那个~，它的否定作用仅限于自身还是应用于所有后面的量词？

再接下来，作者又给我们做了几道反过来的练习。大家普遍觉得反过来的题目似乎相对容易一点，不过还是没有标准的官方答案。

1）所有的自然数都等于4。
∀a:a=SSSS0

2）不存在等于它自身平方的自然数。
~∃a:a=(a⋅a)

3）不同的自然数有不同的后继。
∀a:∀b:<~a=b→~Sa=Sb>
这道题目我跟大家有点不同的想法，我觉得应该是这样的：
∀a:∀b:~Sa=S(a+Sb)

4）如果1等于0，那么每个数都是奇数。
<S0=0→∀a:~∃b:(SS0⋅Sb)=a>

5）b是2的某次方。
做不出来。同样，后来这道题目我也去google了，其结果要比刚才那6道题的多得多。（果然前面那6题在美国人看来要容易得不值一提很多吗？）同样，这里也没有官方答案，我找到这样的一个答案：
∀a: <∃c: (SSa⋅c) = b → ∃d: (SS0⋅d) = SSa>

他的意思是，所谓的“b是2的某次方”，也就是说“b的因子除了1之外，都是2的某次方”。摘录一下他的解释，以及后面他谈到的作者让大家试图翻译的“b是10的某次方”的见解。

It seemed to me that there were a few simple things that can be done in TNT with relative ease, but as you move up the line of complexity it becomes exponentially harder to express something in such a simple language. I knew for sure I could express a few basic things in TNT, such as “a is a factor of b” or “if something then something else”.

I eventually figured that if all factors of b are multiples of two then b is most certainly a power of two. This is because this power’s only prime factor would be two, with a multiplicity of the given exponent. Think about it, its powers will have no other factors than itself and other powers of 2. You can only divide 32 by 16, 8, 4, and 2. Hence, the stubborn statement can be written in English as “all factors of b are multiples of 2″. In TNT, that would be the following.

5.    ∀a: <∃c: (SSa⋅c) = b ⊂ ∃d: (SS0⋅d) = SSa> [For all a > 1, if there exists c such that a times c is equal to b, then there exists d such that d times 2 is equal to a.]

Edit: Because this confused people, I’d like to clear a few things up. Basically, all this says is the following. For all a, if a is a factor of b then it is also a multiple of 2. If this statement is true for each and every single value of a, then b is a power of two. If there are any exceptions, such as b = 12 and a = 3, then b is not a power of 2. If there is one true case, such as b = 12 and a = 4, then it does not necessarily mean that b is a power of 2.

Edit #2: The difference is that every case of a is necessary for b to be a power of 2, but not sufficient. The overall statement, however, with the “for all a” included, is both necessary AND sufficient.

And there we go. I’m not quite sure whether this is too dissimilar to be considered a translation, but I do believe that the set of all powers of two is equal to the set of numbers for which this TNT statement comes out true. At first I thought the exact same technique would work for powers of 10 just as well. But how could it be that easy? Of course, it wasn’t. I was actually quite bewildered, until I realized my error.

Obviously, this translation is only valid when b is a power of a prime number. If it is a power of a composite number, like 10 in the final challenge, then it will have many factors that do not comply with the above theorem of TNT. For example, 100 has factors 2, 5, 20, and 50 (as well as 10), where both 2 and 5 are not divisible by 10. On the other hand, 32 is only divisible by 16, 8, 4, and 2; all divisible by 2.

Since I’m dealing with things I don’t know much about here, I probably screwed up pretty badly at least once. Please let me know if I’m an idiot and this is totally wrong. Thanks! Anyways, back to being totally bewildered and awed by GEB and its amazingness.

翻译题目之后，作者提供了TNT的五条公理以及一系列的规则。

TNT五条公理：

1. ∀a:~Sa=0
2. ∀a:(a+0)=a
3. ∀a:∀b:(a+Sb)=S(a+b)
4. ∀a:(a⋅0)=0
5. ∀a:∀b:(a⋅Sb)=((a⋅b)+a)

在五条皮亚诺公设中，他用神怪定义自然数、怪物定义0、元定义后继。

特称规则：若∀u:x是定理，则x是定理，且可用任何项代替x中的u。（限制：用来代替u的项必须不包含任何在x中被量化了的变元。）
例：∀a:~Sa=0，则~S0=0

概括规则：若x是定理，则∀u:x是定理。（限制：在一个幻想里面，不允许对任何自由出现在该幻想的前提中的变元作概括。）

互换规则：∀u:~与~∃u:可互换。
这一点其实我们在之前就已经注意到了。但是~∀u:与∃u:~可互换吗？

存在规则：若x是定理，则可用一个新的变元b来代替x中的任何一项，∃b:x也是定理。
例：∀a:~Sa=0，则∃b:∀a:~Sa=b
在这里作者提到可以通过现有的规则去调拨符号，从∃b:∀a:~Sa=b产生定理~∀b:∃a:Sa=b。这里的过程我没想出来，求解释。

等号规则：
对称：如果r=s是一个定理，那么s=r同样也是定理。
传递：如果r=s和s=t都是定理，那么r=t同样也是定理。

后继规则：
加S：如果r=t是一个定理，那么Sr=St同样也是定理。
去S：如果Sr=St是一个定理，那么r=t同样也是定理。

然后作者提到一个推导出∀a:a=a的方法，并说其中可能是有问题的。我们都没有看出来问题在哪。难道在量化的闭公式里面不能用对称规则？作者又比较详细地举例说明了特称规则和概括规则里面那两个限制的必要性和合理性。作者又说，我们可以从一个模型中看出来有这么一条串：∀a:(0+a)=a。他说这样的串只能从外部对系统进行考察才能得出的，但是这里看得我们云里雾里──这个不就是公理2吗？