← 学习库 Discrete Mathematics (Levin) · 中英对照 目录

0.4 Functions 函数

本页译自 LibreTexts · Discrete Mathematics (Levin) 第 0.4 章。公式经 MathJax 渲染,自定义宏已注入。

A function is a rule that assigns each input exactly one output. We call the output the image of the input. The set of all inputs for a function is called the domain. The set of all allowable outputs is called the codomain. We would write $f:X \to Y$ to describe a function with name $f\text{,}$ domain $X$ and codomain $Y\text{.}$ This does not tell us which function $f$ is though. To define the function, we must describe the rule. This is often done by giving a formula to compute the output for any input (although this is certainly not the only way to describe the rule).

函数是一条规则,它为每一个输入恰好指派一个输出。我们把这个输出称为该输入的像(image)。函数所有输入组成的集合称为定义域(domain)。所有允许的输出组成的集合称为上域(codomain)。我们写作 $f:X \to Y$ 来表示一个函数,其名称为 $f\text{、}$定义域为 $X$、上域为 $Y\text{。}$但这并未说明函数 $f$ 究竟是哪一个。要确定这个函数,必须描述其对应规则。常见做法是给出一个公式,用以计算任意输入对应的输出(当然,这绝非描述规则的唯一方式)。

For example, consider the function $f:\N \to \N$ defined by $f(x) = x^2 + 3\text{.}$ Here the domain and codomain are the same set (the natural numbers). The rule is: take your input, multiply it by itself and add 3. This works because we can apply this rule to every natural number (every element of the domain) and the result is always a natural number (an element of the codomain). Notice though that not every natural number actually is an output (there is no way to get 0, 1, 2, 5, etc.). The set of natural numbers that are actually outputs is called the range of the function (in this case, the range is $\{3, 4, 7, 12, 19, 28, \ldots\}\text{,}$ all the natural numbers that are 3 more than a perfect square).

例如,考虑由 $f(x) = x^2 + 3\text{。}$ 定义的函数 $f:\N \to \N$。此处定义域与上域是同一个集合(自然数集)。其规则是:取输入,将其自乘再加 3。这一规则可行,因为我们可以把它应用于每一个自然数(定义域的每个元素),而结果始终是自然数(上域的一个元素)。但请注意,并非每个自然数都真的能成为输出(无法得到 0、1、2、5 等)。那些实际成为输出的自然数组成的集合称为该函数的值域(range)(在本例中,值域为 $\{3, 4, 7, 12, 19, 28, \ldots\}\text{,}$即所有比某个完全平方数大 3 的自然数)。

The key thing that makes a rule actually a function is that there is exactly one output for each input. That is, it is important that the rule be a good rule. What output do we assign to the input 7? There can only be one answer for any particular function.

使一条规则真正成为函数的关键在于:每个输入都有唯一一个输出。也就是说,这条规则必须是一条良好的规则。我们该把什么输出指派给输入 7?对任何一个具体的函数而言,答案只能有一个。

The description of the rule can vary greatly. We might just give a list of the images of each input. You could also describe the function with a table or a graph or in words.

对规则的描述可以千差万别。我们可以直接列出每个输入对应的像,也可以用表格、图像或文字来描述这个函数。

Example 1

示例 1

The following are all examples of functions:

以下全都是函数的例子:
  1. $f:\Z \to \Z$ defined by $f(n) = 3n\text{.}$ The domain and codomain are both the set of integers. However, the range is only the set of integer multiples of 3.
  2. $g:\{1,2,3\} \to \{a,b,c\}$ defined by $g(1) = c\text{,}$ $g(2) = a$ and $g(3) = a\text{.}$ The domain is the set $\{1,2,3\}\text{,}$ the codomain is the set $\{a,b,c\}$ and the range is the set $\{a,c\}\text{.}$ Note that $g(2)$ and $g(3)$ are the same element of the codomain. This is okay since each element in the domain still has only one output.
  3. $h:\{1,2,3\} \to \{1,2,3\}$ defined as follows:

    箭头函数示意图:1→2,2→1,3→3

    This means that the function $f$ sends 1 to 2, 2 to 1 and 3 to 3: just follow the arrows.
  1. $f:\Z \to \Z$,由 $f(n) = 3n\text{。}$ 定义。定义域与上域都是整数集。不过,值域仅仅是 3 的整数倍所组成的集合。
  2. $g:\{1,2,3\} \to \{a,b,c\}$,由 $g(1) = c\text{、}$ $g(2) = a$、$g(3) = a$ 定义。定义域是集合 $\{1,2,3\}\text{,}$上域是集合 $\{a,b,c\}$,值域是集合 $\{a,c\}\text{。}$注意 $g(2)$ 与 $g(3)$ 是上域中的同一个元素。这没有问题,因为定义域中每个元素仍然只有一个输出。
  3. $h:\{1,2,3\} \to \{1,2,3\}$,定义如下(见上方箭头示意图):该函数把 1 送到 2、把 2 送到 1、把 3 送到 3——只需顺着箭头看即可。

The arrow diagram used to define the function above can be very helpful in visualizing functions. We will often be working with functions with finite domains, so this kind of picture is often more useful than a traditional graph of a function. A graph of the function in example 3 above would look like this:

上面用来定义函数的箭头图,对直观理解函数很有帮助。我们经常处理具有有限定义域的函数,因此这类图示往往比传统的函数图像更有用。示例 3 中那个函数的图像大致如下:

离散函数图像:三个点 (1,2)、(2,1)、(3,3)

It would be absolutely WRONG to connect the dots or try to fit them to some curve. There are only three elements in the domain. A curve suggests that the domain contains an entire interval of real numbers. Remember, we are not in calculus any more!

把这几个点连起来、或者试图用某条曲线去拟合它们,都是绝对错误的。定义域里只有三个元素。一条曲线会暗示定义域包含一整个实数区间。记住,我们已经不在微积分里了!

Since we will so often use functions with small domains and codomains, let's adopt some notation that is a little easier to work with than that of examples 2 and 3 above. All we need is some clear way of denoting the image of each element in the domain. In fact, writing a table of values would work perfectly:

由于我们常常会用到定义域和上域都很小的函数,不妨采用一种比上面示例 2、3 更易处理的记法。我们所需要的,只是某种清晰表示定义域中每个元素之像的方式。事实上,列一张数值表就能完美奏效:
$x$01234
$f(x)$33241
(上表:第一行为自变量 $x$ 的取值 0、1、2、3、4,第二行为对应的函数值 $f(x)$。)

We simplify this further by writing this as a matrix with each input directly over its output:

我们进一步简化,把它写成一个矩阵:每个输入直接写在其输出上方:

$\begin{equation*} f = \begin{pmatrix}0 & 1 & 2& 3 & 4 \\ 3 & 3 & 2 & 4 & 1\end{pmatrix} \end{equation*}$

Note this is just notation and not the same sort of matrix you would find in a linear algebra class (it does not make sense to do operations with these matrices, or row reduce them, for example).

注意,这仅仅是一种记法,与你在线性代数课上学到的矩阵并非同一种对象(例如,对这些矩阵做运算或行化简都是没有意义的)。

It is important to know how to determine if a rule is or is not a function. Drawing the arrow diagrams can help.

重要的是要学会判断一条规则究竟是不是函数。画箭头图能有所帮助。

Example 2

示例 2

Which of the following diagrams represent a function? Let $X = \{1,2,3,4\}$ and $Y = \{a,b,c,d\}\text{.}$

下面的哪些图表示一个函数?设 $X = \{1,2,3,4\}$,且 $Y = \{a,b,c,d\}\text{。}$

h 的箭头图:1 无映射;2→a,c;3→d;4→b f 的箭头图:1→d;2→a;3→c;4→b g 的箭头图:1→d;2→a;3→a;4→b

Solution

解答

$f$ is a function. So is $g\text{.}$ There is no problem with an element of the codomain not being the image of any input, and there is no problem with $a$ from the codomain being the image of both 2 and 3 from the domain. We could use our two-line notation to write these as

$f$ 是一个函数。 $g$ 也是。上域中某个元素不是任何输入之像,这没有问题;上域中的元素 $a$ 同时是定义域中 2 和 3 的像,也没有问题。我们可以用双行记法把它们写成

$\begin{equation*} f= \begin{pmatrix} 1 & 2 & 3 & 4 \\ d & a & c & b \end{pmatrix} \qquad g = \begin{pmatrix} 1 & 2 & 3 & 4 \\ d & a & a & b \end{pmatrix}. \end{equation*}$

However, $h$ is NOT a function. In fact, it fails for two reasons. First, the element 1 from the domain has not been mapped to any element from the codomain. Second, the element 2 from the domain has been mapped to more than one element from the codomain ($a$ and $c$). Note that either one of these problems is enough to make a rule not a function. In general, neither of the following mappings are functions:

然而,$h$ 不是函数。事实上,它因两个原因而不合格。第一,定义域中的元素 1 没有被映射到上域中的任何元素。第二,定义域中的元素 2 被映射到了上域中多于一个的元素($a$ 与 $c$)。注意,这两类问题中的任意一种,都足以使一条规则不成其为函数。一般而言,下面两种映射都不是函数:

非函数示例 a:一个输入映射到两个输出 非函数示例 b:一个输入没有任何映射

It might also be helpful to think about how you would write the two-line notation for $h\text{.}$ We would have something like:

换个角度想,你该如何写出 $h$ 的双行记法,也会有所帮助。结果大概会是这样:

$\begin{equation*} h=\begin{pmatrix} 1 & 2 & 3 & 4 \\ & a,c? & d & b\end{pmatrix}. \end{equation*}$

There is nothing under 1 (bad) and we needed to put more than one thing under 2 (very bad). With a rule that is actually a function, the two-line notation will always “work”.

1 下面什么都没有(糟糕),而 2 下面我们却要放多于一个东西(非常糟糕)。对于一条真正构成函数的规则,双行记法永远能「正常工作」。

Surjections, Injections, and Bijections 满射、单射与双射

We now turn to investigating special properties functions might or might not possess.

现在我们来研究函数可能具有、也可能不具有的一些特殊性质。

In the examples above, you may have noticed that sometimes there are elements of the codomain which are not in the range. When this sort of thing does not happen, (that is, when everything in the codomain is in the range) we say the function is onto or that the function maps the domain onto the codomain. This terminology should make sense: the function puts the domain (entirely) on top of the codomain. The fancy math term for an onto function is a surjection, and we say that an onto function is a surjective function.

在上面的例子中你可能已经注意到,有时上域中会有一些元素不在值域里。当这种情况发生时(也就是说,当上域中的每一个元素都在值域里),我们说该函数是满射(onto),或者说这个函数把定义域映到了上域上。这个术语应当不难理解:函数把定义域(整体)盖到了上域之上。onto 函数的正式数学术语是 surjection(满射),我们也称一个满射函数是 surjective(满射的)

In pictures:

图示如下:

非满射示例 满射示例

Example 3 Surjective Functions

示例 3 满射函数

Which functions are surjective (i.e., onto)?

下列哪些函数是满射(即映上的)?
  1. $f:\Z \to \Z$ defined by $f(n) = 3n\text{.}$
  2. $g:\{1,2,3\} \to \{a,b,c\}$ defined by $g = \begin{pmatrix}1 & 2 & 3 \\ c & a & a \end{pmatrix}\text{.}$
  3. $h:\{1,2,3\} \to \{1,2,3\}$ defined as follows:

    满射判定题中的 h 箭头图

  1. $f:\Z \to \Z$,由 $f(n) = 3n\text{。}$ 定义。
  2. $g:\{1,2,3\} \to \{a,b,c\}$,由 $g = \begin{pmatrix}1 & 2 & 3 \\ c & a & a \end{pmatrix}\text{。}$ 定义。
  3. $h:\{1,2,3\} \to \{1,2,3\}$,定义如下(见上方箭头图)。

Solution

解答
  1. $f$ is not surjective. There are elements in the codomain which are not in the range. For example, no $n \in \Z$ gets mapped to the number 1 (the rule would say that $\frac{1}{3}$ would be sent to 1, but $\frac{1}{3}$ is not in the domain). In fact, the range of the function is $3\Z$ (the integer multiples of 3), which is not equal to $\Z\text{.}$
  2. $g$ is not surjective. There is no $x \in \{1,2,3\}$ (the domain) for which $g(x) = b\text{,}$ so $b\text{,}$ which is in the codomain, is not in the range. Notice that there is an element from the codomain “missing” from the bottom row of the matrix.
  3. $h$ is surjective. Every element of the codomain is also in the range. Nothing in the codomain is missed.
  1. $f$ 不是满射。上域中有一些元素不在值域里。例如,没有 $n \in \Z$ 会被映射到数字 1(按规则,$\frac{1}{3}$ 会被送到 1,但 $\frac{1}{3}$ 不在定义域内)。事实上,该函数的值域是 $3\Z$(即 3 的整数倍),它不等于 $\Z\text{。}$
  2. $g$ 不是满射。在定义域 $\{1,2,3\}$ 中,不存在任何 $x$ 使得 $g(x) = b\text{,}$因此上域中的元素 $b$ 不在值域里。注意,矩阵的下一行中「缺失」了上域的一个元素。
  3. $h$ 是满射。上域中的每个元素也都在值域里。上域中没有任何元素被漏掉。

To be a function, a rule cannot assign a single element of the domain to two or more different elements of the codomain. However, we have seen that the reverse is permissible: a function might assign the same element of the codomain to two or more different elements of the domain. When this does not occur (that is, when each element of the codomain is the image of at most one element of the domain) then we say the function is one-to-one. Again, this terminology makes sense: we are sending at most one element from the domain to one element from the codomain. One input to one output. The fancy math term for a one-to-one function is an injection. We call one-to-one functions injective functions.

要成为一个函数,一条规则不能把定义域中的单个元素指派给上域中两个或更多不同的元素。然而我们已经看到,反过来允许的:一个函数可以把上域中的同一个元素指派给定义域中两个或更多不同的元素。当这种情况发生时(即上域中每个元素至多是一个定义域元素的像),我们就说该函数是单射(one-to-one)。这个术语同样说得通:我们至多用定义域中的一个元素去对应上域中的一个元素,一一对应。单射的正式数学术语是 injection(单射)。我们也称单射函数为 injective(单射的)

In pictures:

图示如下:

单射示例 非单射示例

Example 4

示例 4

Which functions are injective (i.e., one-to-one)?

下列哪些函数是单射(即一一对应的)?
> >

Solution

解答
  1. $f$ is injective. Each element in the codomain is assigned to at most one element from the domain. If $x$ is a multiple of three, then only $x/3$ is mapped to $x\text{.}$ If $x$ is not a multiple of 3, then there is no input corresponding to the output $x\text{.}$
  2. $g$ is not injective. Both inputs $2$ and $3$ are assigned the output $a\text{.}$ Notice that there is an element from the codomain that appears more than once on the bottom row of the matrix.
  3. $h$ is injective. Each output is only an output once.
  1. $f$ 是单射。上域中的每个元素至多被指派给定义域中的一个元素。若 $x$ 是 3 的倍数,则只有 $x/3$ 被映射到 $x\text{。}$ 若 $x$ 不是 3 的倍数,则没有任何输入对应于输出 $x\text{。}$
  2. $g$ 不是单射。输入 $2$ 与 $3$ 都被指派给了输出 $a\text{。}$注意,矩阵下一行中出现了多于一次的上域元素。
  3. $h$ 是单射。每个输出只充当了一次输出。

From the examples above, it should be clear that there are functions which are surjective, injective, both, or neither. In the case when a function is both one-to-one and onto (an injection and surjection), we say the function is a bijection, or that the function is a bijective function.

从上述例子应当可以看出:存在满射、单射、二者兼具、以及二者皆非的函数。当一个函数既是一一对应又是映上的(既是单射又是满射)时,我们称该函数为一个双射(bijection),或者说它是一个 bijective(双射的) 函数。

Inverse Image 逆像

When discussing functions, we have notation for talking about an element of the domain (say $x$) and its corresponding element in the codomain (we write $f(x)\text{,}$ which is the image of $x$). It would also be nice to start with some element of the codomain (say $y$) and talk about which element or elements (if any) from the domain it is the image of. We could write “those $x$ in the domain such that $f(x) = y\text{,}$” but this is a lot of writing. Here is some notation to make our lives easier.

在讨论函数时,我们有记号来谈论定义域中的一个元素(比如 $x$)及其在上域中对应的元素(我们写作 $f(x)\text{,}$它就是 $x$ 的像)。如果能反过来,从一个上域中的元素(比如 $y$)出发,去谈论定义域中哪些元素(如果有的话)以它为像,也会很方便。我们可以写「定义域中满足 $f(x) = y$ 的那些 $x$」,但这写起来太繁琐。下面这则记号能让我们的工作轻松些。

Suppose $f:X \to Y$ is a function. For $y \in Y$ (an element of the codomain), we write $f\inv(y)$ to represent the set of all elements in the domain $X$ which get sent to $y\text{.}$ That is, $f\inv(y) = \{x \in X \st f(x) = y\}\text{.}$ We say that $f\inv(y)$ is the complete inverse image of $y$ under $f\text{.}$

设 $f:X \to Y$ 是一个函数。对 $y \in Y$(上域中的元素),我们写作 $f\inv(y)$,用来表示定义域 $X$ 中所有被送到 $y$ 的元素所组成的集合。也就是说,$f\inv(y) = \{x \in X \st f(x) = y\}\text{。}$我们称 $f\inv(y)$ 为 $y$ 在函数 $f$ 下的完全逆像(complete inverse image)

WARNING: $f\inv(y)$ is not an inverse function! Inverse functions only exist for bijections, but $f\inv(y)$ is defined for any function $f\text{.}$ The point: $f\inv(y)$ is a set, not an element of the domain.

警告:$f\inv(y)$ 并不是一个反函数!反函数只存在于双射情形,但 $f\inv(y)$ 对任意函数 $f$ 都有定义。要点在于:$f\inv(y)$ 是一个集合,而不是定义域中的一个元素

Example 5

示例 5

Consider the function $f:\{1,2,3,4,5,6\} \to \{a,b,c,d\}$ given by

考虑由下式给出的函数 $f:\{1,2,3,4,5,6\} \to \{a,b,c,d\}$:

$\begin{equation*} f = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 \\ a & a & b & c & c & c\end{pmatrix}. \end{equation*}$

Find the complete inverse image of each element in the codomain.

求上域中每个元素的完全逆像。

Solution

解答

Remember, we are looking for sets.

记住,我们要求的是集合。

$\begin{aligned} f\inv(a) &= \{1,2\}\\ f\inv(b) &= \{3\}\\ f\inv(c) &= \{4,5,6\}\\ f\inv(d) &= \emptyset. \end{aligned}$

即:$f\inv(a) = \{1,2\}$,$f\inv(b) = \{3\}$,$f\inv(c) = \{4,5,6\}$,$f\inv(d) = \emptyset$。

Example 6

示例 6

Consider the function $g:\Z \to \Z$ defined by $g(n) = n^2 + 1\text{.}$ Find $g\inv(1)\text{,}$ $g\inv(2)\text{,}$ $g\inv(3)$ and $g\inv(10)\text{.}$

考虑函数 $g:\Z \to \Z$,其定义为 $g(n) = n^2 + 1\text{。}$求 $g\inv(1)\text{、}$ $g\inv(2)\text{、}$ $g\inv(3)$ 与 $g\inv(10)\text{。}$

Solution

解答

To find $g\inv(1)\text{,}$ we need to find all integers $n$ such that $n^2 + 1 = 1\text{.}$ Clearly only 0 works, so $g\inv(1) = \{0\}$ (note that even though there is only one element, we still write it as a set with one element in it).

为求 $g\inv(1)\text{,}$我们需要找出所有满足 $n^2 + 1 = 1$ 的整数 $n$。显然只有 0 满足,因此 $g\inv(1) = \{0\}$(注意,即使其中只有一个元素,我们仍把它写成含一个元素的集合)。

To find $g\inv(2)\text{,}$ we need to find all $n$ such that $n^2 + 1 = 2\text{.}$ We see $g\inv(2) = \{-1,1\}\text{.}$

为求 $g\inv(2)\text{,}$我们需要找出所有满足 $n^2 + 1 = 2$ 的 $n$。我们得到 $g\inv(2) = \{-1,1\}\text{。}$

If $n^2 + 1 = 3\text{,}$ then we are looking for an $n$ such that $n^2 = 2\text{.}$ There are no such integers so $g\inv(3) = \emptyset\text{.}$

若 $n^2 + 1 = 3\text{,}$那么我们就在寻找满足 $n^2 = 2$ 的 $n$。不存在这样的整数,因此 $g\inv(3) = \emptyset\text{。}$

Finally, $g\inv(10) = \{-3, 3\}$ because $g(-3) = 10$ and $g(3) = 10\text{.}$

最后,$g\inv(10) = \{-3, 3\}$,因为 $g(-3) = 10$ 且 $g(3) = 10\text{。}$

Since $f\inv(y)$ is a set, it makes sense to ask for $\|f\inv(y)\|\text{,}$ the number of elements in the domain which map to $y\text{.}$

既然 $f\inv(y)$ 是一个集合,那么去问 $\|f\inv(y)\|$——即定义域中映射到 $y$ 的元素个数——便是顺理成章的。

Example 7

示例 7

Find a function $f:\{1,2,3,4,5\} \to \N$ such that $\|f\inv(7)\| = 5\text{.}$

找一个函数 $f:\{1,2,3,4,5\} \to \N$,使得 $\|f\inv(7)\| = 5\text{。}$

Solution

解答

There is only one such function. We need five elements of the domain to map to the number $7 \in \N\text{.}$ Since there are only five elements in the domain, all of them must map to 7. So

满足条件的函数只有一个。我们需要定义域中的五个元素全都映射到 $7 \in \N\text{。}$由于定义域中恰好只有五个元素,它们必须全部映射到 7。于是

$\begin{equation*} f = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 7 & 7 & 7 & 7 & 7\end{pmatrix}. \end{equation*}$

Function Definitions

函数定义