但是后来经过萨谢利、兰伯特、波约、罗巴切夫斯基和高斯的努力，终于发展了几种形式的非欧几何学。他们并不是直接否定第五公理，而是抛弃这个公理，即平行公理的假设，而代之以其他形式的假设。欧几里得平行公理假设，在平面上过一点只能引一条与已知直线平行的直线。非欧几何或者假设过一点可以引无数条具有这种性质的平行线，或者假设过一点无法引任何一条具有这种性质的平行线。而按照这两种不同的假设，都可以构造出无逻辑矛盾的几何学体系。对于新的几何学体系中的各个命题，同样可以作出合理的新解释。
在形式系统中，有些符号是加以定义的，有的却没有。我们已经提到，在欧几里得几何学中，有许多未加定义的术语。因此我们可以把欧氏几何与非欧几何中的术语分为两类。一类词汇具有固定的定义，是不能变通的。另一类则是末加定义的术语，它们的意义可以加以调节，从而保持整个系统的一致性。几何学需要有些第一类的词汇，它们是在几何学之外加以定义的。这些词汇构成了框架，而在这个框架中可以填充其他的材料。既可以填进欧几里得几何的材料，也可以填进非欧几何的材料。
因此，我们可以把某些形式系统分成同一系列的不同等级。一个形式系统可以把另一个形式系统包括在内，就像欧氏几何中包含着绝对几何学一样。用数学术语来讲，这就叫做把一个形式系统嵌入另一个更大的形式系统。例如，我们把形式系统1嵌入形式系统2。那就意味着，形式系统1中的公理和规则在形式系统2中仍然成立，是构成新系统的基础。但是在形式系统2中可以增添形式系统1中所没有的新公理或新的规则。需要补充的一点是，在一个形式系统中增加新的定理未必能构成能力更大的系统。关于这一点以后还要进一步加以阐述。
3.4 命题演算系统
我们已经了解了形式系统的一般结构，也构造了一些具体的形式系统，如pq系统、MIU系统等。现在我们要介绍一种重要的形式系统，即命题演算的形式系统。这是逻辑命题形式化的结果，也是形式逻辑的重要组成都分。读者可以在任何一本有关形式逻辑的教材中找到有关这个系统的详细介绍。由于各位逻辑学家的偏爱不同，所用的符号可能有所不同。但是它们的含义并不因此而受到影响。运用我们前面讲到的同构方法，读者很容易在这些不同的符号系统之间建立一一对应的关系。我们这里采用的符号表是：
＜ ＞
P Q R '
∧ ∨ ～
[ ]
我们把这里的P、Q、R称为原子，可以在原子的右上角加撇“”而构成新的原子。例如R'、Q''、P'''。我们定义这些原子是系统中良构的命题。
可以按照下面4种方法由良构的命题生成新的良构命题。
(1) ～x x的否定
(2) ＜x∧y＞ x与y的合取
(3) ＜x∨y＞ x与y的析取
(4) ＜X y＞ x蕴含y
这里的x、y都表示良构的命题。任何良构的命题都可以按照以上4种定则回归到最基本的要素——原子。从这种方法我们可以判定任何一个命题是不是良构的。这种过程一般称作是自上而下的。
这里的“＜”和“＞”是—组括号，表示括号中的逻辑符号构成了一个逻辑命题；“～”表示逻辑否定；“∧”表示逻辑积或者逻辑合取；“∨”表示逻辑和或逻辑析取。“ ”表示逻辑蕴涵。逻辑中的否定、合取、析取和蕴涵可以根据原命题与新命题的真假值表来定义，这是形式逻辑教材的基本内容。
对于原子我们无法单独作进一步的解释，可以把它理解为任何一个用日常语言描述的句子。但是命题演算并不关心这些句子的实际含义是否正确。例如“这支笔是红的”就是一个原子。这支笔实际上可能是绿的。但是在命题演算中，这一点无关宏旨。重要的是以确定的符号来表示这个命题，并对这些符号进行形式运算。这种运算是严格的、机械的，也可以说是无聊而乏味的。
由于命题演算系统的这种特点，因此在这个系统中只有运算的规则，而没有公理。按照前面几个形式系统的性质，我们知道如何按照规则从公理产生定理，再由这些定理产生新的定理。但是在这个系统中却没有公理。那么定理又从何而来呢？这很像是一个让巧妇做无米之炊的难题。幸好在这个系统中有一个定则可以使我们能“无中生有”地构造出系统的定理来。我们把这个定则称为想象定则。运用想象定则时，你可以先写下一条良构的命题，不妨设这个命题为x。然后设想x就是公理或者定理，再运用系统中的规则对它进行变换看看能得到什么样的结果。假设最后得到的结果为y。那么退出想象后就可以得到这样的定理：如果命题x成立，那么命题y也成立。用逻辑符号来表示就是＜x y＞。
我们用方括号的前后两部分分别表示“进入”或“退出”想象。例如：
[ 进入想象
＜P∧Q＞ 前堤
P 分离律
Q 分离律
＜Q∧P＞ 结合律
] 退出想象
＜＜P∧Q＞ ＜Q∧P＞＞ 定理
这里只有最后一行是命题演算系统中的定理，其他仅仅是一种设想。这种想象定则可以重复地使用，从而使定理中的命题分出不同的层次来。我们不妨把这些层次称为“现实性的层次”。运用这个概念可以描述命题演算系统中的贮存定则：在想象中可以运用“现实性”更高的层次中的任何定理。
命题演算系统中的其他定则可以归结如下：
结合律：如果x和y成立，那么＜x∧y＞也成立。
分离律：如果＜x∧y＞成立，那么x和y同时成立。
双重否定律：“～～”可以在定理中删去或者添上。
独立律：如果x和＜x y＞成立，则y也成立。
对照律：＜x y＞与＜～y ～x＞可以互换。
德·摩根律：＜～x∧～y＞与～＜x∨y＞可以互换。
斯威彻罗律：＜x～y＞与＜～x y＞可以互换。
要想验证这些定则，只要分别列出各个命题的真假值表就可以了。根据这些定则，可以产生命题演算系统中的各条定理。这些定理在有些人看来好像是纯思辨的，没有任何实际内容。按照这种观点，也可能把命题演算看成是白费时间的运算。因为它告诉我们的只是一些没有实际意义的东西。但是也有人会认为，它描述了所有命题的运算形式，它揭示的是对各种命题都普遍适用的规律，是更为深刻的真理。
形式系统要求严格按照规则来推导定理，或者说证明一个定理。但是怎么能够证明这种证明是正确的呢？这有点像一个鸡蛋。虽然有蛋壳的保护，但是在运输时，总要设法再加保护，使蛋壳不致于破碎。然而，不管保护层有多少层，总还存在这样的危险，有某种意想不到的灾难会使蛋壳破裂。当然这并不意味着，你永远不要去冒运输鸡蛋的风险。同样，你无法对形式系统证明的合理性给出一种绝对的证明。你可以给出一种证明的证明，一种证明的证明的证明。但是，仍然存在着未加证明的假设，我们人为地把它看成是真理。
例如，我们在命题演算系统个推出了＜P∧～P＞，现在要推出＜Q∧～Q＞。我们知道，这两个推导过程是平行的，那就可以直接得出来。这在平面几何的证明中是经常碰到的。“同理可证”对于中学生是不陌生的。我们不妨把这称为元定理，是关于系统中定理的定理。运用元定理可以使形式系统繁复的推理过程大大简化，不失为一种人们乐于采取的捷径。
我们也可以把元定理看成是一个更大的形式系统中的定理。但是，人们仍然可以找到关于元定理的定理——元元定理。这就是更高层次上的推理捷径。
有时，形式推理的结论会产生明显的矛盾。这时我们往往会努力去弥补这些漏洞，使该系统更加完善。因此我们可以说矛盾是使理论系统达到清晰和获得进展的主要源泉。数学史上的著名例子就是有关无穷级数：
1 -1 +1 -1 +1 ……
之和的争论。人们“证明”它可以等于0，1，1/2或许还有其他值。这显然是很荒唐的。这种争论后来导致关于无穷级数收敛性的认识，从而发展了关于无穷级数更加深刻、更加全面的理论。
命题演算是模仿我们的逻辑思维，它与我们的实际思维方式之间存在着很大的差异。这使许多逻辑学家感到不安，他们做出创造性的努力去补救这一点。这种努力推动了逻辑学的发展，使命题演算具有更大的灵活性。也有的逻辑学家甚至采取更加极端的立场，为了模仿人类的实际推理方式，宁可放弃对于完备性或者一致性的要求。
3.5 形式数论系统
最后，我们要讨论一种本书中最复杂但也是最重要的形式系统，即形式数论系统，简称TNT系统。它也是罗素和怀特海在《数学原理》中提出的形式系统。他们提出这个系统的目的是要用它囊括现有的全部数学理论。当然，这个目标后来被证明是永远达不到的。
形式数论使数论的所有命题形式化。为此我们先来看一些典型的数论命题：
(1) 5是素数。
(2) 2不是平方数。
(3) 1729为两个立方数之和。
(4) 没有两个正立方数之和是另一个立方数。
(5) 存在无限多的素数。
(6) 6是偶数。
我们将这些陈述分解成为一些基本的术语：
对于所有的数b
存在着数b使得
大于
乘以
加上
0，1，2，……
当然，这种分解并不是唯一的，例如“大于”可以进一步分解。a大于b可以表示成：
存在着数c不为0，使得c加b等于a。
分解成基本术语后，就可以进一步使这些术语形式化了。我们用这样一些符号来表示自然数。
数： 0 1 2 3 ……
符号：0 S0 SS0 SSS0 ……
这里的S表示后继者，这就是说任何自然数可以用0和后继者的概念来描述。也许有人对于这种形式的表示方法感到不习惯或者不耐烦。不过我们在前面已经讲过，形式化为获得严密性而付出的代价是单调、乏味和冗长。不过，如果人们想到，这将更加便于计算机来“理解”，也许会理解形式化的必要性。
和代数中一样，我们用字母a、b、c等来表示变量，用右上角加撇的方法则可以使变量的数目无限地增加。
加、乘、等于都可以用大家熟悉的符号“+”“·”和“＝”来表示。此外还要加上两个重要的量词符号：
b：表示存在b使得 (存在量词)
b：表示对于所有的b都有 (全称量词)
出现在可真可假命题中的变量，我们称为自由变量。就是说它的某些取值使命题为真，而另外一些取值使命题为假。受量词支配的变量则称为量词限定的变量，上面的b就是其中一例。
有了这些术语和符号，我们就可以使数论中的那些陈述形式化了。就以我们举出的那些数论陈述为例：
(6) 6是偶数。
e：(SS0·e) ＝SSSSSS0
(直译为：存在着e使得2乘以e等于6)
或者 e：(e·SS0) ＝SSSSSS0
或者 e：SSSSSS0＝ (SS0·e)
(2) 2不是平方数。
～ b： (b·b)＝SS0
(直译为：不存在b使得b乘以自己等于2)
或者 b：～ (b·b)＝SS0
(直译为：对于所有的b都不会自己相乘等于2)
(3) 1729是两个立方数之和。
b： c：SS……SS0
----------
1729个S
＝ (((b·b) ·b) 十 ((c·c)·c))
(4) 没有两个正立方数之和为另一个立方数。
a：～ b： c： ((a·a)·a)
＝ (((Sb·Sb)·Sb) 十 (Sc·Sc)·Sc))
或者 ～ a： b： c： ((a·a)·a)
＝ (((Sb·Sb)·Sb) 十 (Sc·Sc)·Sc))
这里之所以用Sb、Sc而不用b、c，是为了保证它们为正整数。
(5) 5是素数。
～ b： c： SSSSS0＝(SSb·SSc)
这里之所以用SSb、SSc是为了保证它们大于1。
(6) 素数是无限的。
d： e：～ b： c： (d十Se)
＝ (SSb·SSc)
(直译为：对于任意数d存在着数e使得d十e十1不是任何两个数(b十l)与(c十1)的乘积。)
从这些例子我们可以清楚地看到，运用上面例举的那些符号，就可以使得数论中的那些陈述形式化。
皮亚诺建立了关于自然数的公理体系。我们可以把他的公理体系归结为3个基本概念和5条公理。这3个基本概念是0、数和后继。5条公理是：
(1) 0是一个数。
(2) 任何数的后继是一个数。
(3) 没有两个数有相同的后继。
(4) 0不是任何数的后继。
(5) 任何性质，如果0有此性质；又如果任一数有此性质，它的后继必定也有此性质；那么所有的数也有此性质。
皮亚诺的公理系统对于数学理论的形式化具有很大的影响。我们可以在这里清楚地看到它对形式数论系统的影响。
我们还可以把命题演算系统中的所有规则都引进TNT系统来。也就是说用它们来构成TNT形式系统的框架。这就意味着，在形式数论系统中的推理必须遵循形式逻辑的法则。
根据TNT的规则和公理，我们很容易生成这样的塔状定理族
(0十0) ＝ 0
(0十S0) ＝ S0
(0十SS0) ＝ SS0
(0十SSS0 ) ＝ SSS0
……
把这族定理归结在一路起，就可以得出采用全称量词的公式：
a： (0十a) ＝ a
我们用这个例子来给出关于ω—不完备性的严格定义：
如果在一个系统中，某个塔状族中每一个定理单独都成立，可是用全称量词概括的定理却不成立，那么这个系统就是ω不完备的。如果这个全称量词的公式的否定也不是该系统中的定理。那就是说，原来的公式在该系统内是不可判定的。这看来好像不可思议，其实并没有什么神秘之处。这只是表明一个形式系统是可以扩张的。欧几里得第5公理即平行公理在绝对几何学(4公理系统)中是不可判定的。但是加上这个公理后便成了欧氏几何。而加上相反的命题后便成了非欧几何。
但是，如果在这种塔状族的定理中，每一行都可以从它的上面一行按一定的规则推导出来。那么我们完全有理由相信，这族中的所有定理都成立。
我们用X{a}表示带有自由变量a的良构的公式。X{Sa／a}则表示用Sa代替原公式中的a。那么上述情况就对以用TNT中的—条定则来表示。我们把这条定则称为归纳定则。
归纳定则：若u是自由变量、X{u}是以u为自由变量的良构公式。如果 u：〈X{u} X{ Su／u }〉和X{ o／u }都是定理，那么 u：X{u}也是定理。
显然这是皮亚诺第五公理在形式数论系统中的表述。在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)
这些公理的含义是很容易理解的。公理1陈述了有关0这个数的专门特点。公理2和3是有关加法运算的。公理4和5是有关乘法运算的性质，而且还涉及到与加法运算的关系。
我们不想在这儿详细叙述形式数论系统的所有公理和规则。这将会使许多读者感到厌烦。希望读者通过这些说明获得一个明确的印象，有关数论的命题和规则能够通过同构而形式化。
.1 阿基里斯和乌龟历险记
我们在上一章介绍了形式系统，并在最后介绍了形式数论系统，即TNT系统。TNT系统的一条定则就是归纳定则，也就是递归的定则。递归是极为重要的概念，它对于理解哥德尔定理的证明是必不可少的。为了说明这个重要的概念，我们先从一段故事讲起。
(乌龟和阿基里斯在科尼岛上消磨时光，他们坐在大转轮上谈笑风生。)
龟：我有—种预感，今天幸运之神将会赐福于我。
阿：这可太好了。你看！有一架直升飞机正朝着我们飞来了。
龟：它还放下了一段绳子。看！快到我们身边了。
阿：啊，绳子上有一个大钩子，上面挂着一张纸条。
(他们按照纸条上的吩咐，松开自己座椅上的皮带，在轮椅再度上升到顶的一刹那抓住钩子上了直升飞机)
声音：哈、哈、哈！朋友们，你们上钩了。先在我的书房里呆着吧。不妨吃点爆米花。等我磨好刀子就来收拾你们。乌龟陷阱，这可是我最喜爱的食品。
(声音消失后，乌龟阿基里斯在书房里面面相觑。忽然他们发现了一本名叫《阿基里斯和乌龟历险记》的书)
龟：这可真是一个富有刺激性的题目。我们读一读怎么样？你扮演书中阿基里斯的角色，而我扮演书中乌龟的角色。
(他们开始读这本书)
[在书中：
(阿基里斯邀请乌龟参观他所收藏的画家埃舍尔的作品。)
龟：这些作品真迷人！我最喜欢那幅《凸与凹》(图9)，那里有两个内部一致的世界，可是结合在一起便成了不一致的复合世界。如果能访问一下这种不一致的世界倒是非常有趣的。不过，我可不愿长久地生活在这样的世界里。
阿：你要知道，不一致的世界是根本不可能存在的。你怎么能去访问这样的世界呢？再说，埃舍尔的画是一个二维的世界，你怎么能进得去呢？
龟：我自有办法。我只要喝一小杯神奇的“进入剂”就可以做到这一点。如果我想从进入的画面再退出来，只须喝一小杯“退出剂”就可以了。
(阿基里斯与乌龟倒了两杯“进入剂”并带上“退出剂”一起干杯。)
阿：我们这是到了哪儿？在一只小小的平底船上。船顺着运河而下。喂，船夫，快让我们下船。
(可是船夫根本不理睬他们。他们终于明自了，船夫听不懂他们的话。他们来到了一个完全陌生的国度。就只好在这个希奇古怪的世界里乱闯乱窜。后来阿基里斯意外地得到了一盏铜灯。他慢慢擦着灯上镌刻的字样。突然冒起一股浓烟。阿拉伯神话中的奇景再现了。灯神愿意满足新主人的三个愿望。可是阿基里斯却想满足上百个愿望。灯神不忍心让阿基里斯失望，就从自己的长袍中取出一盏形状相仿的银灯。)
阿：这是什么？
灯神：这是我的元灯，它可以满足人们的元希望。
(灯神摩擦元灯，在烟雾中出现了元灯神。元灯神又从自己的长袍中取出金制的元元灯。而元元灯神可以满足元元希望……这个无限的过程通向上帝。上帝可以许诺无形的希望，包括任何希望的希望。但是这种希望却是没有保障的。)
阿：这使我产生了—种特殊的希望。我希望自己的希望是无法实现的。
(灯神实现了他的愿望。于是灯神、神灯连同那些神奇的法力统统都消失了。整个系统都崩溃了。阿基里斯发现他们又来到了埃舍尔的另一幅画《蜥蜴》(图10)之中。)
[在《蜥蜴》画中
龟：看，在这串蜥蜴旁边居然还有一瓶“退出剂”。我们真算是有福气。
阿：我想最好还是从埃合尔的画退回到我们自己的房子里去。
龟：这桌子上还有两本书呢，书的题目恰好也是《阿基里斯和乌龟历险记》。
(阿基里斯一心想离开这儿，他怕失去那瓶“退出剂”。可是他在慌乱中把那瓶药水碰翻在地、滚下搂去了。于是他只好和乌龟一起读起那本书来了。)
[在书的故事中
(阿基里斯和乌龟置身于迷宫的层层高墙之中。他们怀着求生的急切心情寻找着迷宫的出路。忽然他们听到了巴赫的变调乐曲《和谐的小迷宫》。正当他们被深深吸引住的时候，却听到了在迷宫中等侯他们的魔鬼的笑声。他们处于极度恐惧之中，却发现了一碗爆米花。于是两个人就大嚼特嚼起来。突然砰的一声巨响。)
[回到《蜥蜴》画中
龟：多么有趣的故事。
阿：我只关心他们最后能否逃脱那只魔鬼的手掌。可怜的阿基里斯，他可不想首尸分离。
龟：不必担忧，只要他们有“退出剂”就万事大吉了。
阿：可是那些蜥蜴从画中出来进去并没有喝什么“进入剂”或“退出剂”啊。我们是否也能仿照它们从埃舍尔的这幅画中退出去啊？
龟：当然可以，你跟着我一起做。
(于是阿基里斯和乌龟就从《蜥蜴》中退出来了。可是阿基里斯发现，自己并没有回到原来看画的书房，而是来到了乌龟的书房中。乌龟当然十分满意，阿基里斯也想就此牧场。这可算得上是一段奇妙而幸运的经历。)
4.2 形形色色的递归
我们在上一章介绍了形式系统，并在最后介绍了形式数论系统，即TNT系统。TNT系统的一条定则就是归纳定则，也就是递归的定则。递归是极为重要的概念，它对于理解哥德尔定理的证明是必不可少的。为了说明这个重要的概念，我们先从一段故事讲起。
在上面这一节令人眼花缭乱的历险记中，阿基里斯与乌龟从—个世界进入另一个世界。这暗示着一种重要的形式系统的结构，即递归结构。
这段历险记是一个很复杂的递归例子。阿基里斯和乌龟出现在各个不同的层次上。有时他们从一个层次进入另一个层次，有时则在读自己在其中扮演角色的故事。图30“阿基里斯和乌龟历险记”的结构图显示了这段经历的递归结构。
这张图显示了历险记中各个层次的结构。垂直地下降为“进入”，垂直地上升则为“退出”。从图中我们也可以看到，由幸运之神一开始的威胁所带来的紧张始终汉没有消退。阿基里斯和乌龟一直在直升飞机里晃悠。有些读者可能为此而感到不安，以有人会无动于衷。尽管有这么多层次，但是它们都有一个共同的特点。在每一个层次里，主角都是阿基里斯和乌龟。这提醒我们注意，对于同样的符号可以从不同的层次去理解它的意义。
在我们生活中，递归的例子并不罕见。故事中的故事、画中之画、电影中的电影乃至中国式的套盒等等都具有递归的结构。在音乐中也可以找到递归的例子，像普柯菲耶夫的第5钢琴协奏曲和拉赫马尼诺夫的第2交响曲。
20世纪50年代，人工智能的语言就已经引进了“压进”、 “退出”、 “叠加式存储器”这样一些相互关联的概念。“压进”意味着暂时停止目前进行的操作，但是并没有把它忘掉，而是去完成更低一层的任务。“退出”则正好相反，是结束在这个层次上的操作，回到更高的层次上来，重新开始因为“压进”而中断的操作。这些术语是受到食堂里弹簧，可以保持盆子最上面的高度不变。每当你压进一只盘子时，这叠盘子就下沉—层，而当你取出一只盘子时，它就上升一层。
递归过程也是电子计算机的基础。在计算机程序中，一种关键的技术就是在重复使用某一部分的程序时可以采用模式化的方法。也就是说，把总任务分解成一些子任务。例如在进行一系列相同的操作时，就不必把它们全都写出来，而是画一个圈。这个圈就表示重复一组固定的操作，直到满足某种条件为止。因此，我们可以这样来理解圈，即重复地执行一系列预定的操作，而当预定的条件满足时，就中断这一操作。这实际上就是从一个层次进入另一个层次，然后又退回到原来的层次来。还有一种圈，我称它为“自由圈”。这种圈是很危险的陷阱。因为它要满足的条件可能永远不会出现。因此计算机一旦陷入这种圈里，就会进行无限的循环而无法解脱出来。把这种自由圈和有界圈区别开来在计算机科学中是很重要的。比圈更一般的概念是子程序。它的基本思想就是把一组操作结合在一起而形成一个单元。它们作为一个整体而被调用。
有一个典型的递归例子，这就是用计算机下棋时选挥一种“最佳”的步骡。这就要对每一步以后的各种可能的步骤进行评价。要进行这种评价，就是设想在自己采取的每一步之后，对手有可能采取什么样的对策。而对于这样的每一种对策，自己又可以来取什么样的反对策。这样一步步地设想下去就是一种递归结构。一位高明的棋手与一般下棋爱好者的区别之一，就是他能设想好几步棋之后的局势。这实质上是一种利用递归结构的优势。所谓“深谋远虑”也有这种含义。
我们在智力上的叠加存贮能力显然要比语言上的叠加存贮能力更强。在语言中也有一种压进——退出的叠加结构。但是这种结构的层次一多，理解句子的困难性就会大大增加。中国人往往喜欢较短的句子，这样文字就显得流畅。对于有些译文中出现的带有许多从句的长句子，有人则感到费解和不习惯。不过在英语中，使用从句增加句子的层次是司空见惯的，而在书面德语中，层次叠加的现象就更加明显了。即使这样，也总有办法重组这些句子使得结构的层次减到最少。
句子的结构为我们提供了一个很好的例子来说明递归的结构。这就是所谓的“语次转变”的递归网络。这种图的模式是由一些结点或者其中有单词的小方块以及带箭头的弧或者线组成。
图31(a)显示了一个语次转变的递归网络图，即带修饰的名词。可以有单独的名词，也可以有带形容词的名词或者是带冠词的名词，还可以是同时带冠词和形容词的名词。图31(b)则是一个想象名词的语次转变递归网络。在这个网络中我们可以看到，每—条途径都必须经过“带修饰的名词”，而且有三条途径中都有“想象名词”。这看来好像是在用白己定义自己。但是，因为存在着从“带修饰的名词”到“结束”的途径，就保证了这个递归过程可以是有限的。
我们也可以这样理解有递归结构的网络图。这就是用整个“想象名词”的网络图来代替图31(b)中的“想象名词”这一格。我们把称为网络中纳结点的扩张。而扩张后的网络中的结点还可以再扩张。
几何结构的无穷扩张也可以采用这种逐层扩张结点的方式来定义。作为一个例子，我们来定义一种G图。在图32(a)给出了未经扩张的G图。图32(b)则给出了经过一次扩张的G图。图中从下往上依次标上了字号。这个无限的树具有一种十分有趣的性质。最右边的数字依次构成了费波那奇数列。这个数列最好是用一对公式来进行递归定义
FIBO(n)＝FIBO(n-1)十FIBO(n-2), n>3
FIBO(1)＝FIBO(2)＝1
这种G图还有—种更令人惊奇的性质，它的结构完全可以用一个递归定义来表示：
G(n)＝n-G(G(n-1)) n>2
G(0)＝0
为什么函数G(n)能表示G图的树结构呢？非常简单，只要把G(n)放在每一个值n之下来构造一个树，就可以重新构造G图。实际上，我一开始就是用这种方法发现G图的。当我研究函数G时，为了迅速计算它的值，就把已经知道的值都标在树上，结果竟然得到了这样有序的几何结构。
同样，对于函数H(n)，可以给出这样的递归定义：
H(n)＝n-H(H(H(n一1))) n>0
H(0)＝0
有兴趣的渎者可以思考这样一个问题：如果对G图作镜反射的变换，然后将树上的每个节点都这达种新图的代数递归定义呢？若将H图作这种变换，结果又会怎样呢？它们有没有共同的规律性？
还有一个有趣的问题是把两种递归定义“嫁接”在一起。例如：
