2　关　系

前面说过，一阶命题里的概念代表个体的关系，而在一阶语言中，谓词表达概念的外延，即关系所对应的个体序列组成的集合。比如，二元关系“……是……的卫星”对应于集合

｛〈月亮，地球〉，〈木卫一，木星〉，〈木卫二，木星〉，……｝，

也就是｛〈x，y〉｜x是y的卫星｝。这里有两样东西我们需要进一步考察，一是（有穷长的）个体序列，一是这种序列的集合。

一般而言，给定任意n（≥1）个对象x₁，x₂，…，x_n，我们都可以构造一个有序n元组（或n元组）〈x₁，x₂，…，x_n〉，其中的诸x_i不必不同，n称为这个有序组的长度。

有序组的构成对象是有序排列的，这是它区别于集合（其中元素无序）的特征。因此，我们规定：

〈x₁，x₂，…，x_m〉＝〈y₁，y₂，…，y_n〉当且仅当m＝n且x₁＝y₁，x₂＝y₂，…，x_n＝y_n。

这就是说，有序组被其长度、构成对象及其顺序所决定。对象的改变，导致有序组的改变。如〈月亮，地球〉和〈地球，地球〉是不同的有序二元组，因为二者中的第一个对象不同。即使长度和对象已经确定，一个有序n元组中任何顺序的改变，都使得它可能不再是原来的有序组。比如〈月亮，地球〉与〈地球，月亮〉也是不同的有序二元组。

有序二元组，我们简称有序对；有序一元组〈x〉就定义为x本身。

在许多情形下，一个由n元组组成的集合，恰好对应于一个我们熟悉的n元关系；但在另外一些情况下，这样的一个集合很难说就对应某个我们直观上容易理解的关系。无论如何，至少局限于个体n元组的集合，所有我们能够理解的关系，都对应于某个由n元组组成的集合。另外，我们以后说到关系时，关心的只是它对应的集合。因此，我们不妨直接称任何一个由n元组组成的集合为一个n元关系。

如果R是一个n元关系，那么对任何的〈x₁，x₂，…，x_n〉∈R，称x₁，x₂，…，x_n具有关系R。特别对二元关系来说，如果存在集合A，B，使得对任何的〈x，y〉∈R，都有x∈A，y∈B，则称R为从A到B的关系。

例如，｛〈x，y〉｜x是词，y是人，且x是y的姓名｝是从词的集合到人的集合的关系；｛〈x，y〉｜x是y的同时代人｝则是人的集合到自身的关系。

集合｛x｜存在y，使得〈x，y〉∈R｝叫做关系R的前域；

集合｛x｜存在y，使得〈y，x〉∈R｝叫做关系R的后域。

R是从A到B的关系，当且仅当R的前域是A的子集，而R的后域是B的子集。

反过来，任给集合A和B，我们可以把A作前域，B作后域，从而组成一些二元关系。把这些关系都并在一起，显然也组成一个从A到B的关系：

集合｛〈x，y〉｜x∈A且y∈B｝称为集合A和B的笛卡尔积，记为A×B。

直观上，A×B就是把A中所有元素与B中所有元素一一配成有序对而组成的二元关系。显然，任何从A到B的关系，都是A×B的子集。这使得我们可以把“R是从A到B的二元关系”简单地表示成：

　　R⊆A×B。

如果A＝B，则称R是A中的一个二元关系。

当然，笛卡尔积的概念，可以推广到任意多个集合上。设n≥1，A₁，…，A_n是集合，则

　　笛卡尔积A₁×A₂×…×A_n

　　＝｛〈x₁，x₂，…，x_n〉｜x₁∈A₁，x₂∈A₂，…，x_n∈A_n｝。

若A₁＝A₂＝…＝A_n＝A，则A₁×A₂×…×A_n就简记为Aⁿ。如果关系R⊆Aⁿ，则称R为A中的一个n元关系。如｛〈x，y〉｜x是y的配偶｝是｛x｜x是已婚的人｝中的二元关系，也是｛x｜x是人｝中的二元关系。

由于一元组〈x〉就是x本身，集合A中的一个一元关系，显然是A的一个子集，也称为A中的一个性质。比如，B＝｛x｜x是哲学家｝是A＝｛x｜x是人｝的子集，B表示人的一个性质：“……是哲学家”。

下面我们考虑两种常用的二元关系。

2.1　等价关系

2.1.1　定义　设R是集合A中的二元关系。

R是A中的自反关系，如果对于任意的x∈A，都有xRx（为了看起来更自然一些，我们把〈x，y〉∈R记为xRy）。

R是A中的对称关系，如果对任意的x，y∈A，若xRy则yRx。

R是A中的传递关系，如果对任意的x，y，z∈A，若（xRy且yRz）则xRz。

例如，自然数集合N中的“＝”关系，就是自反、对称、传递的。所有人的集合中的二元关系“……是……的同时代人”也是自反、对称、传递的。N中的“＜”关系是传递的，但不是自反的，也不是对称的。人的集合中的二元关系“……是……的母亲”非自反，不对称，也不传递。

2.1.2　习题　上一章谈到一阶语言的语义学的时候，我们提到了结构的概念。一个结构包含一个非空集合（称为它的论域或个体域），以及其中的一些关系（可能包含一些函数），还可能特别列出集合中的一些元素。一个特别设计的一阶语言，就是用来描述这样一个结构的，语言中的任一n元谓词表达结构中的某个n元关系，语言中的个体常项指称结构中的特定元素。神学家、哲学家阿奎那（Thomas Aquinas）认为（或有人认为他如此设想），上帝是一个结构，其论域中仅含有三个元素，分别命名为圣父、圣子和圣灵。这个论域中只有一个二元关系R（读作relatio originis），它是禁对称的，也就是说，对论域中任意的x，y，如果xRy，则并非yRx。另外，三个元素可以利用R唯一地确定下来，或彼此分别开来（就是说，对其中任意两者，一定有一个借助R所表达的性质，使得一个具有这个性质，而另一个不具有）。阿奎那断言，如果〈圣父，圣子〉∈R，且〈圣父，圣灵〉∈R，那么有序对〈圣子，圣灵〉和〈圣灵，圣子〉有且仅有一个属于R。请证明阿奎那的断言。^②

2.1.3　定义　集合A中的二元关系R是A中的等价关系，如果R是A中的自反关系、对称关系和传递关系。

因此，“＝”是N中的等价关系；｛〈x，y〉｜x与y是同时代的人｝是集合｛x｜x是人｝中的等价关系。｛〈x，y〉｜x与y平行｝是平面上直线的集合中的等价关系。

在一个集合中，相互间有等价关系的元素不能用这个关系来区别，因此，从这个关系来考虑，我们可以把那些元素看作性质相同的一类甚至一个东西。这是数学中非常有用的一个方法，我们将来会用到它。

2.1.4　定义　令R是集合A中的一个等价关系，a是A的一个元素。称A的子集｛x｜x∈A且aRx｝为a生成的R-等价类，记为［a］_R。

一个R-等价类反映了其中元素的某类共同性质，我们也可以从中挑出一个元素，作为这个等价类的代表元。考虑［a］_R，由于R是自反的，所以aRa，根据定义2.1.4，有a∈［a］_R。因此，我们自然可以选取a作等价类［a］_R的代表元。但是，［a］_R其他的元素也可以充当代表元，只要它们也生成等价类［a］_R。假设b∈［a］_R，因为aRb，且R是传递的，所以对任意的x，如果bRx，则aRx。这说明，［b］_R⊆［a］_R。另一方面，R是对称的，所以有bRa。再根据R的传递性，对任意的x，如果aRx，则bRx。由此得到［a］_R⊆［b］_R。两者结合，［a］_R＝［b］_R。由a和b的任意性，我们实际上证明了如下引理：

2.1.5　引理　令R是集合A中的一个等价关系。那么，

对所有x，y∈A，如果y∈［x］_R，则［x］_R＝［y］_R。

因此，一个等价类的所有元素都是“平等的”，它们都生成同一个等价类，其代表元可以在这个等价类中任意选取。

2.1.6　习题　令R是集合A中的一个等价关系。证明：对所有x，y∈A，如果，［x］_R＝［y］_R，则xRy。

一个有趣的事实是，集合A中的等价关系R把A中全部的元素划分成互不相交的等价类。这称为R对A的划分。首先，A的每个元素都在某个（它生成的）等价类中：任一个x∈A，因为xRx，所以x∈［x］_R。其次，不同的等价类不相交，就是说，如果［x］_R≠［y］_R，则［x］_R∩［y］_R＝∅。否则存在z∈［x］_R∩［y］_R，因此有z∈［x］_R和z∈［y］_R。根据引理2.1.5，我们得到［x］_R＝［z］_R＝［y］_R。这与［x］_R≠［y］_R矛盾。

2.2　序关系

2.2.1　定义　集合A中的一个二元关系R是反对称的，如果对任意的x，y∈A，若（xRy且yRx）则x＝y．

R是反对称的，等价于说，对任意的x，y，若（xRy且x≠y）则并非yRx。（请读者自己验证这一点。）试比较反对称与习题2.1.2中提到的禁对称，注意其间的差别。反对称关系的一个明显的例子是自然数集N中的≤关系。

2.2.2　定义　集合A中的二元关系R称为A中的一个偏序，如果R是A中的自反、反对称和传递关系。

对于x∈A，如果不存在另一个y∈A，使得yRx，则称x为此偏序的一个极小元。

对于x∈A，如果不存在另一个y∈A，使得xRy，则称x为此偏序的一个极大元。

例如，N中的≤是N中的偏序，0是极小元，没有极大元。正整数集中的二元关系“……能被……整除”是其中的偏序，没有极小元，1是极大元。在一个集合族A（集合的集合，如N的幂集（N））中，可以定义二元关系⊆。从子集的定义易知，⊆是反对称的（习题1.2-1），传递的（习题1.2-2）和自反的（习题1.2-3）。所以“⊆”是A中的偏序。在（N）中，∅是⊆-极小元，N是⊆-极大元。

2.2.3　习题　证明：正整数集中的关系｛〈x，y〉｜存在正整数z，使得x＝y^z｝是其中的偏序。问：这个偏序的极小元和极大元是什么？

注意，一个集合A中的二元关系R是A中的偏序，并不意味着A中的随便两个元素之间都具有R。比如，正整数集中的2和3之间就不具有习题2.2.3中的关系：2不是3的幂，3也不是2的幂。（N）中有许多互不为子集的集合，如｛0，1，2｝和｛1，3｝。

2.2.4　定义　集合A中的一个偏序R称为全序（或线性序），如果对任意x，y∈A，xRy和yRx必有一个成立。

例如，N中的“≤”不但是N中的偏序，也是N中的全序。

假设集合A非空。如果R是A中的全序，则A中所有的元素就可以按这个全序排成一条线，其中y在x后面，当且仅当x≠y且xRy。这条线没有分叉（因为A的任何两个元素之间都有R关系，所以它们都在这条线上），也不会“打卷”，就是说，任给x，它后面的任何元素都不等于它前面的任何元素。这是因为：

2.2.5　习题　对于x后面的任何y，都有xRy，但对x前面的任意z，则有并非xRz。

因此，全序可以用一条直线或射线或线段来直观地表示，如N中的“≤”可以表示为：

　　0——1——2——3……

其中左到右的关系表示“≤”（自反性在线上没有表示，但我们可以把它作为缺省默认下来）。如果要表示整数集合中的“≤”，只要让这条线继续往左边延伸就行。

2.2.6　习题　证明：

1）一个全序至多有一个极小元，并且至多有一个极大元。

2）如果A是至少有两个元素的集合，则（A）中的关系⊆不是全序，且它有一个极小元和一个极大元。

一种特殊的偏序称为树。

2.2.7　定义　集合A中的一个偏序R称为一棵树，如果它有唯一的极小元a，而且对任意x∈A，｛y｜yRx｝中的R是全序。

A中元素称为此树的结点，极小元a称为此树的根。

A的一个子集B是一条枝，如果，（1）a∈B；（2）B中的R是全序；（3）B是满足（1）和（2）的最大子集。

枝上的极大元称为此树的叶。

我们以后要使用的，都是有穷树。它们的直观图示即如我们日常看到的树：任何树都只有一个根（因为极小元唯一），从根往上长出有穷多枝，每个枝都有一个顶点（叶），任何两个枝分开后再不相交（否则成为一枝）。例如，下图

就是一棵由6个结点组成的树，它从根往上生长，有3条枝，3个叶。从根往上沿任何一枝到任何一个结点，都是一个全序，而每一枝从根到叶形成极大全序（不能再生长了）。

最简单的树是单点树。它只有一个结点，此点既是根，又是叶，还形成一枝。

前面我们用树形图表示推理结构的时候，即是在一棵树的每个结点处写上一个或0个命题，前提在叶上（可空），结论在根上（不空），由此形成一个有标记的树（为简便计，仍称为树）。只不过我们那里为了表达方便，使用横线（而不是这里的竖线和斜线）显示结点上的命题之间的推导关系。以后我们继续采取横线表示法。