第6章
关系与函数

关系是指事物之间的联系。例如，我们知道一个数大于另一个数意味着什么。我们可以将“大于”关系视为所有这类“数对”所共享的属性。关系存在于任何事物之间，不仅仅是数字之间。例如，关系“父母亲”是所有“父母儿女对”所共享的属性。也就是说，我们发现关系是“事物对”的集合，这些“事物对”之间具有这种关系。

现代数学的成果之一就是约束超物理抽象，代之以集合论的具体定义。其基本思想是用这些抽象的 外延 （extension）的集合来表达这些抽象的含义。所以 关系 （relation）是一个有序 n 元组的集合，即集合叉 积 的任意子集。我们最感兴趣的是 二元 （binary）关系，也就是两个事物之间的关系，用有序对来表示。

例6.1 举一个具体的例子，看看住在小镇上不同地方的人（图6.1）。

这是人和地址之间的关系，也就是说，来自 P × A 有序对集合的子集，其中 P 是包含Alan、David、Grace、Mary四人的集合， A 是所有地址33 Turing Terrace、66 Hilbert Hill、77 Hopper Hollow、22 Jackson Junction的集合。具体而言，关系就是这四个有序对的集合：

{〈Alan，33TuringTerrace〉，〈David，66HilbertHill〉，〈Grace，77HopperHollow〉，〈Mary，22JacksonJunction〉}

这是一种特别简单的二元关系，其中每个第一元素只与一个且仅与一个第二元素配对，反之亦然。

例6.2 更具一般性的例子是学生和选课之间的关系。一个学生可以选多门课，每门课可以接受多个学生。例如，关系 E 可以表示学院的选课表：

在这个关系中，每个学生选三门课。也就是说，对于每个人 x ，有三个不同的 y ，使得有序对〈 x , y 〉属于 E 。此外，Aisha和Ben选了同样的一门课，即当 y =CS20时，有两个不同的 x 值，使得〈 x , y 〉∈ E 。不相交集合 A 和 B （示例中分别代表学生和课程的集合）上的关系 R 可以用图来表示，见图6.2。将 A 和 B 两个集合表示为blob（由点构成的区域），其中的点表示它们的元素，如果〈 x , y 〉∈ R ，则有一条从 x ∈ A 到 y ∈ B 的箭头。为了保持画面简单，我们省略了大部分箭头。一般情况下， A 和 B 不必像本例中那样不相交。

通常我们不会明确地列出关系元素。我们会采用第5章中表示集合的方式，通过给出有序对的规则描述来表示关系。例如，我们可以在 P （世界上所有人的集合）和 D （所有日期）上定义生日关系

B ={〈 p , d 〉: p 的出生日期是 d }

举一个数值的例子，用二维图可视化两个实变量之间关系。图6.3中的圆是距离原点为1的点的集合，即关系{〈 x ， y 〉： x ² + y ² =1}⊆ R × R 。

二元关系 R ⊆ A × B 的 逆 （inverse）是关系

R ^-1 ⊆ B × A ，其中 R ^-1 ={〈 y ， x 〉：〈 x ， y 〉∈ R }

也就是说， R ^-1 只是颠倒了blob-and-arrow（ 区域-箭头 ）图中 R 的箭头方向的关系，如图6.4所示。

函数是一种特殊的二元关系。在第1章中，我们将函数描述为一个规则，该规则将一个集合的每个成员与第二个集合的一个成员相关联。现在我们给出函数的形式化描述。

一个从集合 A 到集合 B 的 函数 （function） f 是一个关系 f ⊆ A × B ，并且对于每个 x ∈ A ，有且仅有一个 y ∈ B ，使得〈 x ， y 〉∈ f 。因为 f 是函数，那么对应于 x 的 y 值是唯一的，因此我们可以将唯一的 y 表示为 f （ x ）。我们称 y = f （ x ）是 f 关于 自变量 （argu-ment） x 的 值 （value）。如果 A 和 B 不相交，函数的blob-and-arrow图不同于关系的blob-and-arrow图，即图中左侧blob中的每个点，有且仅有一个出发箭头（见图6.5）。

例6.1中的人和地址之间的关系是一个函数，因为其中的每个人只有一个地址。例如，可以表示为

f (Alan)=33Turing Terrace

另一方面，例6.2的选课关系不是函数，因为学生可以选多门课。（当某名学生选了两门课时，这就不是一个函数。）圆关系也不是函数，因为对于任意的 x ，其中-1< x <1，都有两个 y 值使得 x ² + y ² =1，即 y =± 。生日关系是函数，因为每个人只能出生在一个时间。

如果 f ⊆ A × B 是一个从 A 到 B 的函数，那么记为 f ： A → B 。集合 A 称为 定义域 （do-main），集合 B 称为 共域 （codomain）（见图6.5）。例如，生日函数的定义域是所有人的集合，共域是一年中所有日期的集合。如果我们考虑函数 f （ x ）= x ² 的自变量 x 是整数，那么定义域就是ℤ。由于整数的平方总是非负整数，所以共域可以为ℕ或ℤ。（根据函数的定义，定义域是必须具有函数值的元素所构成的集合。另一方面，共域必须包含函数的所有值，还可以包括其他的元素。）同样，生日函数的共域是一年中所有日期的集合，即使某些日期没有人出生。

定义域和共域可以是任何集合。它们不必是不相交的或者是不相同的。例如，函数 f ：ℤ→ℤ，其中对于每个 n ∈ℕ，有 f （ n ）= n +1，就具有相同的定义域和共域。

定义域或共域也可以是集合的集合。一个简单的例子是函数的值是一个集合。再回顾一下选课关系（例6.2），它不是一个函数，因为一个学生可以选多门课。但是对于每个学生来说，明确其所选课的集合是可能的。因此，根据例6.2中的信息可以得到一个从学生到选课集合的函数，如下所示。

例6.3

如果 S 是学生的集合， C 是课程的集合，那么例6.2就是 S × C 上的关系，而例6.3是函数 e : S → P ( C )。例如， e (Aisha)={CS20,Ec10,Lit26}。

如第1章所述，函数是将自变量 映射 到一个函数值，因此有时也称函数为 映射 （mapping）。对于给定的自变量，其函数值也称为该自变量的 像 （image），如果 A 是 f 定义域的子集，那么称 f [ A ]为集合 A 的像集合，即由集合 A 中所有元素的像构成的集合（见图6.6）。也就是说，如果有 f ： S → T ，并且有 A ⊆ S ，那么

f [ A ]={ f （ x ）： x ∈ A }⊆ T

打个比方：若将定义域视为一张图片，函数可以视为投影仪，图片的像就是屏幕上与图片对应点的集合。

例如函数 f ：ℤ→ℤ，对于任意的 n ，有 f （ n ）= n ² 。ℤ的像 f [ℤ]是完全平方数{0，4，9，…}的集合。如果对于任意的 n ，有 g （ n ）=2 n ，则 g [ℤ]是所有偶数的集合。如果设 E ⊆ℤ是偶数的集合，那么 f [ E ]={0，4，16，36，…}是偶平方数的集合 。

我们如何看待实值函数 呢？我们想说 f ：ℝ→ℝ，即 f 的自变量为实数，函数值也为实数。但这不完全正确， 无定义，从而 f （0）无定义。然而，对于每个 x ∈ℝ（0除外）， f （ x ）都有定义。因此，准确地说， f 是定义域为ℝ-{0}的函数。即 f ：ℝ-{0}→ℝ。

另一个术语区分了 偏 （partial）函数和 全 （total）函数，其中全函数是我们所说的函数，从 A 到 B 的偏函数是定义域为 A 的子集的全函数。通过这个术语，可以说 是ℝ到ℝ的偏函数。

接下来讲述常用函数类型的相关概念。

单射 （injective）函数是一个“共域中的每个元素至多是一个自变量的函数值”的函数。换言之，如果不存在两个不同的自变量映射为相同的值那么该函数是单射函数。例如，将每个整数 n 映射到其后继 n +1的函数是单射函数，因为对于任意整数 m ，只有一个 n 使得 m = n +1，即 n = m -1。此外，生日函数不是单射函数，因为有时两个人的生日可以是相同的。

一个函数是否是单射函数取决于定义域。如果限制人的集合，那么生日函数也可以是单射函数。函数 f ：ℕ→ℕ，对于每个 n ∈ℕ，有 f （ n ）= n ² ，是单射函数，因为每个自然数至多是一个自然数的平方。但是类似的函数 g ：ℤ→ℕ，对于每个 n ∈ℤ，有 g （ n ）= n ² ，不是单射函数，因为有 g （-1）= g （+1）=1。

blob-and-arrow图表示一个单射函数的情况（见图6.7）。它表示一个函数（定义域中的每个点正好发出一个箭头），并且共域中不存在两个不同的箭头终止于同一个点。

由于函数是一种特殊的二元关系，所以每个函数都有一个逆，逆是一个二元关系。但是，逆不一定是函数。例如，函数 f :{0,1}→{0}，有 f (0)= f (1)=0，它的逆是{〈0,0〉,〈0,1〉}，这个关系不是函数。

然而，单射函数是 可逆的 （invertible）。也就是说，单射函数的逆是一个函数。如果 f : A → B 是一个单射函数，那么函数 f ^-1 : f [ A ]→ A 称为 f 的逆，具有如下性质：

对于任意的 y ∈ f [ A ]，有 f （ f ^-1 （ y ））= y

f 的逆定义为对于任意的 y ∈ f [ A ]， f ^-1 （ y ）是唯一的元素 x ∈ A ，使得 f （ x ）= y 。因为 f 是单射函数，所以不存在两个这样的 x 。然而，一般来说，逆的定义域不必是整个 B ，因为有些 B 的元素可能不是任何自变量 x ∈ A 的 f 值。

例6.1的集合是一个单射函数，因为没有两个人住在同一个地址。如果我们用 f 表示这个函数，那么有 f (Alan)=22Turing Terrace，从而 f ^-1 (22Turing Terrace)=Alan。

借助于单射函数的概念，鸽笼原理（见第1章）可以简明地表述如下：如果 A 和 B 都是有穷集，并且| A |＞| B |，那么不存在从 A 到 B 的单射函数。它的逆否命题是，如果 f ： A → B 是一个单射，其中 A 和 B 都是有穷集，则有| A |≤| B |。

如果共域中的每个元素都是定义域中自变量的函数值，即像集合等于共域，那么函数被称为 满射函数 。换句话说， f : A → B 是满射的，则对于每个 y ∈ B ，至少有一个 x ∈ A 使得 f （ x ）= y 。blob-and-arrow图表示了一个满射函数的情况（见图6.8），即共域中的每个元素至少有一个指向它的箭头。

生日函数在所有人集合的定义域上实际上是满射的，因为生日可以是一年中的每一天。简单的地址簿函数（例6.1）也是满射的，因为给出的四个地址构成了整个共域。此外，我们考查一下自然数平方的函数，即 f ：ℕ→ℕ，其中 f （ x ）= x ² ，对于每个 x ∈ℕ。 f 不是满射的，因为不存在自然数 x 使得 x ² =2。

双射函数既是单射又是满射的，即 f : A → B 是一个双射，当且仅当对于每个元素 y ∈ B ，有且仅有一个元素 x ∈ A ，使得 f （ x ）= y 。或者用blob-and-arrow图表示， B 中每个元素都只有一个指向它的箭头（见图6.9）。

整数集合上的后继函数 f ，对于每个 n ∈ℕ，有 f （ n ）= n +1。 f ^-1 是一个从ℤ到ℤ的函数，对于任意的 m ∈ℕ，有 f （ m ）= m -1，我们称 f ^-1 为前驱函数。后继函数和前驱函数都是整数集合上的双射函数，因为对于每个整数都有唯一的后继整数和唯一的前驱整数。

更有趣的双射函数的例子是函数 f ：ℤ→E，其中E是偶数的集合，对每个 x ，有 f （ x ）=2 x 。对于每个 y ∈E，有一个且仅有一个整数 x ∈ℤ，使得 y =2 x ，即 （这是一个整数，因为 y 是偶数）。所以函数（见图6.10）是双射的。

如果 f : A → B 是一个双射，那么它有一个逆 f ^-1 ，因为任意双射函数都有逆函数。在双射的情况下，逆的定义域是 f 的整个共域，换句话说， f [ A ]= B ，则 f 的逆是 f ^-1 : B → A ，其中 f ^-1 （ y ）的值是 x ，即对于任意的 y ∈ B 有唯一的 x ∈ A ，使得 f （ x ）= y 。这个逆 f ^-1 也是一个双射：在相应的blob-and-arrow图中，我们可以反转箭头的方向，从而使 A 中的每个元素都有一个指向它的箭头。

如果 A 和 B 是有穷的，并且 f 是从 A 到 B 的单射函数，那么| A |≤| B |，因为所有 f （ x ）的值，相应于不同的 x （ x ∈ A ）也是不相同的。如果 f 是满射的，那么| A |≥| B |，因为 B 不能包含任何不是 A 中自变量像的元素。所以如果 f 是双射函数（既是单射又是满射），那么| A |和| B |必须相等。换句话说，如果有穷集之间存在双射，则这两个集合大小相同。

反之亦然。假设 A 和 B 都是具有 n 个成员的集合，形式如下：

A ={ a ₁ ,…, a _n }

B ={ b ₁ ,…, b _n }

其中，如果 i ≠ j （1≤ i , j ≤ n ），那么 a _i ≠ a _j 和 b _i ≠ b _j 。函数 f : A → B 使得 f （ a _i ）= b _i 是双射，其中 i =1,…, n 。

所以，有穷集具有相同的大小当且仅当它们之间存在双射。这似乎是显而易见的，无须用复杂的语言修饰，但其实是有理由的，我们将使用集合之间存在双射来作为两个无穷集大小相等的 定义 。应用这个定义，我们不仅会看到不是所有无穷集都是大小相同的，而且还会得到重要的结论。

我们需要更多双射相关集合之间的性质作为基础，即如果存在从集合 A 到集合 B 和从集合 A 到集合 C 的两个双射，那么 B 和 C 之间存在双射。因此，具有双射关系的集合之间彼此具有“同族相似性”。我们首先来证明具体的性质，然后考虑它的含义。

定理6.4 设 A 、 B 和 C 为任意集合。假设存在双射 f : A → B 和 g : A → C ，那么存在双射 h : B → C 。

证明 ：因为 f 是双射，所以它的逆 f ^-1 : B → A 存在，并且是从 B 到 A 的双射。定义函数 h : B → C 如下：对于任意的 y ∈ B ，有 h （ y ）= g （ f ^-1 （ y ））。也就是说，给定 y ∈ B ，沿着 f 的箭头向后找到 A 的对应元素，然后沿着 g 的箭头向前找到 C 的元素（见图6.11）。 B 中不同的元素对应于 f ^-1 作用下 A 的不同元素，再将这些元素通过 g 映射到 C 的不同元素。因此， h 既是一个单射，也是一个满射，因为对于任意元素 z ∈ C ， z 是 h 关于自变量 f （ g ^-1 （ z ））∈ B 的值：

所以 h 是从 B 到 C 的双射。

在这个证明中，我们将 f ^-1 和 g 连在一起定义函数 h 为 h （ y ）= g （ f ^-1 （ y ））。换言之，我们对两个函数应用了某种运算，从而产生了第三个函数。此运算称为 复合 （composi-tion）运算，表示为◦：

h = g ◦ f ^-1

一般来说，如果有 f ： A → B ， g ： C → D ，并且有 f [ A ]⊆ C ，则对于任意的 a ∈ A ，函数 g ◦ f ： A → D 定义为（ g ◦ f ）（ a ）= g （ f （ a ））。

定理6.4的证明给出了一种比较任意集合大小的方法：如果它们之间存在双射，则它们的大小相同。这就产生了有穷集的自然结果，即如果它们具有相同数量的元素，那么它们的大小是相同的。然而，这种想法与我们对无穷集产生的直觉相悖。例如，由于整数集合和偶数集合之间存在双射，我们必须接受整数集和偶数集具有相同的大小，尽管偶数集合是整数集合的真子集。虽然这听起来很奇怪，但这正是我们想要的，我们将在下一章中继续讨论。

一个函数可以有多个自变量。乘法可以看作一个带有两个自变量的函数 M ：ℤ×ℤ→ℤ，其中对于任意的 m ， n ∈ℤ， M （ m ， n ）= m · n 。例如， M （3，5）=15。当然，传统的做法是在自变量之间使用类似于·的符号，而不是在自变量之前使用 M 之类的字母。当一个函数有两个自变量，并且函数名放在自变量之间时，称为 中缀 （infix）表示法；将函数名写在自变量之前时，称为 前缀 （prefix）表示法。

具有多个自变量的函数并不是一个新概念。两个自变量的函数 f : A × B → C 实际上是一个定义域为 A × B 、共域为 C 的单自变量函数。

为了简化表示，我们用 f ( a , b )= c 来代替 f (〈 a , b 〉)= c ，即没有将自变量明确表示为有序对。同样， k 个自变量的函数，也称为 k 元函数，定义域是 k 个集合的笛卡儿积，我们用 f ( x ₁ ,…, x _k )= y 来代替 f (〈 x ₁ ,…, x _k 〉)= y 。

本章小结

• 关系 是事物之间的一种联系，可以用相互之间具有这种关系的事物的元组集合来表示，例如，对于某些性质 P , R ={〈 x , y 〉: P ( x , y )}。 二元关系 是两个事物之间的关系。

• 二元关系中，第一元素 x 可以与任意多个第二元素 y 相关联，并且第二元素 y 也可以与任意多个第一元素 x 相关联。元素 x 和 y 可以来自不同的集合，也可以来自相同的集合。

• 二元关系的 逆 是将该关系中所有有序对的元素对调顺序而得的关系，即如果原关系中包含〈 x , y 〉，则其逆关系包含〈 y , x 〉。

• 从集合 A 到集合 B 的 函数 （或 映射 ） f 表示为 f : A → B ，是将每个 x ∈ A 与唯一的 y ∈ B 相关联的关系。唯一的 y 称为 自变量 x 的函数 值 。

• 对于函数 f : A → B ， A 是 定义域 ， B 是 共域 。

• 函数 f 关于自变量 x 的值是 x 的像。 f 关于集合 X 中所有自变量的值的集合是 X 的像集合，表示为 f [ X ]。

• 单射 函数 f : A → B 将 A 中不同的元素映射到 B 中不同的元素。

• 每个函数 f : A → B 都有一个逆关系 f ^-1 ，只有当 f 是单射时， f ^-1 才是一个函数。因此，单射函数称为 可逆的 。 f ^-1 的定义域是 B 的子集（也可能相等）。

• 满射 函数 f : A → B 对于每个 B 中的元素都是 A 中某些自变量的 f 值。

• 双射 函数 f : A → B 既是单射又是满射，即每个 B 中的元素都恰好是 A 中一个自变量的 f 值。

• 两个集合（有穷或无穷）大小相同，当且仅当它们之间存在双射。

• 可以用 复合运算 （符号为◦）将两个函数组合在一起。

• 一个函数可以带有多个自变量。与单个自变量函数一样，其定义域是这多个集合的笛卡儿积。

习题

6.1 设 f 为任意函数。假设 f 的逆关系

f ^-1 ={〈 y , x 〉: y = f ( x )}

是一个函数，那么 f ^-1 是双射吗？请给出理由。

6.2 对于以下每个函数，确定它是单射、满射和/或双射。如果函数是双射，它的逆是什么？如果它是单射而不是满射，那么它的逆（关于定义域的像）又是什么？

（a） f ：ℤ→ℤ，其中 f （ n ）=2 n 。

（b） f ：ℝ→{ x ∈ ^ℝ ：0≤ x ＜1}，其中 。

（c） f ：ℕ→ ^ℕ ，其中 f （ n ， m ）表示 m 和 n 的较大者。

（d） f ：ℤ→ℝ，其中 。

（e） f ：ℝ→ℝ，其中 。

（f） f ：ℕ→ℤ，如果 n 是偶数，则 ；如果 n 是奇数，则 。

6.3 （a）证明：如果两个有穷集 A 和 B 的大小相同，并且 r 是从 A 到 B 的单射函数，那么 r 也是满射的，即 r 是一个双射函数。

（b）给出一个反例，表明如果 A 和 B 是两个有双射关系的无穷集，则上一问的结论不一定成立。

6.4 在图6.3中，圆关系的逆是什么？

6.5 假设 f ： A → B 和 g ： C → D ，并且 A ⊆ D 。说明：在什么情况下，（ f ◦ g ） ^-1 是一个从 B 的子集到 C 的函数，并用 f ^-1 和 g ^-1 表示。

6.6 15个人在不同的时间段使用同一台计算机，不存在两个人同时使用的情况。每人每天只有一个小时的机会，从整点开始到整点结束。例如，某人的使用时间可能是每天凌晨3点到4点，而另一个人的使用时间可能是晚上11点到午夜。证明：存在5个不同的人在连续7小时内使用了计算机。 提示 ：定义一个函数 s ，带有两个自变量，分别代表人和0到6之间的整数（包括0和6），因此 s （ p , i ）表示在一个7小时的时间段里， p 从第 i 小时开始使用计算机。应用扩展鸽笼原理。

6.7 函数 f （ n ）=2 n 是从ℤ到偶数集合的双射，函数 g （ n ）=2 n +1是从ℤ到奇数集合的双射。那么 f ^-1 和 g ^-1 分别是什么？定理6.4中的函数 h 是什么？ hJ8H0yV7d7nWnpqUUfXvc8N3ovsPIOkxFkFchnJVyqTDjlwvenHhPGL+jug86T6e