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

0.3 Sets 集合

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

The most fundamental objects we will use in our studies (and really in all of math) are sets. Much of what follows might be review, but it is very important that you are fluent in the language of set theory. Most of the notation we use below is standard, although some might be a little different than what you have seen before.

在我们学习（乃至整个数学）中最基础的对象就是集合（sets）。下面的许多内容可能是复习，但熟练掌握集合论的语言至关重要。我们所用的大部分记法是标准的，尽管有些可能与你之前见过的略有不同。

For us, a set will simply be an unordered collection of objects. Two examples: we could consider the set of all actors who have played The Doctor on Doctor Who, or the set of natural numbers between 1 and 10 inclusive. In the first case, Tom Baker is a element (or member) of the set, while Idris Elba, among many others, is not an element of the set. Also, the two examples are of different sets. Two sets are equal exactly if they contain the exact same elements. For example, the set containing all of the vowels in the declaration of independence is precisely the same set as the set of vowels in the word "questionably" (namely, all of them); we do not care about order or repetitions, just whether the element is in the set or not.

对我们而言，集合就是一组无序的对象。例如：我们可以考虑所有在《神秘博士》中饰演过「博士」的演员的集合，或者介于 1 到 10（含端点）之间的自然数的集合。在前一个例子中，Tom Baker 是该集合的一个元素（成员），而 Idris Elba 等许多人则不是。此外，这两个例子是不同的集合。两个集合相等，当且仅当它们含有完全相同的元素。例如，「独立宣言」中出现的全部元音字母的集合，与单词 "questionably" 中的元音字母集合完全一样（即全部元音）；我们不在乎顺序或重复，只在乎某个元素是否属于该集合。

Notation 记法

We need some notation to make talking about sets easier. Consider,

我们需要一些记法，以便更方便地谈论集合。考虑如下集合：

$\begin{equation*} A = \{1, 2, 3\}. \end{equation*}$

This is read, "$A$ is the set containing the elements 1, 2 and 3." We use curly braces "$\{, \}$" to enclose elements of a set. Some more notation:

这读作：「$A$ 是包含元素 1、2、3 的集合。」我们用花括号「$\{, \}$」把集合的元素括起来。再看几个记法：

$\begin{equation*} a \in \{a, b, c\}. \end{equation*}$

The symbol "$\in$" is read "is in" or "is an element of." Thus the above means that $a$ is an element of the set containing the letters $a\text{,}$ $b\text{,}$ and $c\text{.}$ Note that this is a true statement. It would also be true to say that $d$ is not in that set:

符号「$\in$」读作「属于」或「是……的元素」。因此上式表示 $a$ 是属于该集合的一个元素，该集合含有字母 $a\text{、}$ $b\text{、}$ $c\text{。}$ 注意这是一个真命题。同样为真的是：$d$ 不属于那个集合：

$\begin{equation*} d \not\in \{a, b, c\}. \end{equation*}$

Be warned: we write "$x \in A$" when we wish to express that one of the elements of the set $A$ is $x\text{.}$ For example, consider the set,

需要提醒：当我们想表达集合 $A$ 的某个元素是 $x$ 时，就写作「$x \in A$」。例如，考虑如下集合：

$\begin{equation*} A = \{1, b, \{x, y, z\}, \emptyset\}. \end{equation*}$

This is a strange set, to be sure. It contains four elements: the number 1, the letter b, the set $\{x,y,z\}\text{,}$ and the empty set ($\emptyset = \{ \}\text{,}$ the set containing no elements). Is $x$ in $A\text{?}$ The answer is no. None of the four elements in $A$ are the letter $x\text{,}$ so we must conclude that $x \notin A\text{.}$ Similarly, consider the set $B = \{1,b\}\text{.}$ Even though the elements of $B$ are elements of $A\text{,}$ we cannot say that the set $B$ is one of the elements of $A\text{.}$ Therefore $B \notin A\text{.}$ (Soon we will see that $B$ is a subset of $A\text{,}$ but this is different from being an element of $A\text{.}$)

这确实是一个奇怪的集合。它含有四个元素：数字 1、字母 b、集合 $\{x,y,z\}\text{，}$以及空集（$\emptyset = \{ \}\text{，}$即不含任何元素的集合）。$x$ 在 $A$ 中吗？答案是否定的。$A$ 的四个元素中没有一个是字母 $x\text{，}$因此我们必然有 $x \notin A\text{。}$ 类似地，考虑集合 $B = \{1,b\}\text{。}$ 尽管 $B$ 的元素都是 $A$ 的元素，我们仍不能说集合 $B$ 是 $A$ 的某个元素。因此 $B \notin A\text{。}$（稍后我们会看到，$B$ 是 $A$ 的子集（subset），但这与作为 $A$ 的元素（element）不是一回事。）

We have described the sets above by listing their elements. Sometimes this is hard to do, especially when there are a lot of elements in the set (perhaps infinitely many). For instance, if we want $A$ to be the set of all even natural numbers, we could write,

上面我们通过对元素逐一列举来描述集合。有时这很难做到，尤其是当集合中元素很多（甚至无穷多）时。例如，若要让 $A$ 表示全体偶自然数的集合，我们可以写作：

$\begin{equation*} A = \{0, 2, 4, 6, \ldots\}, \end{equation*}$

but this is a little imprecise. A better way would be

但这有点不精确。更好的写法是

$\begin{equation*} A = \{x \in \N \st \exists n\in \N ( x = 2 n)\}. \end{equation*}$

Breaking that down: "$x \in \N$" means $x$ is in the set $\N$ (the set of natural numbers, $\{0,1,2,\ldots\}$), "$\st$" is read "such that" and "$\exists n\in \N (x = 2n)$" is read "there exists an $n$ in the natural numbers for which $x$ is two times $n$" (in other words, $x$ is even). Slightly easier might be,

逐部分拆解：「$x \in \N$」表示 $x$ 属于集合 $\N$（自然数集，$\{0,1,2,\ldots\}$）；「$\st$」读作「使得」（such that）；而「$\exists n\in \N (x = 2n)$」读作「存在自然数 $n$ 使得 $x$ 等于 $2n$」（换言之，$x$ 是偶数）。更简洁一点的写法是：

$\begin{equation*} A = \{x \st x\text{ is even} \}. \end{equation*}$

Note: Sometimes people use $\mid$ or $\backepsilon$ for the "such that" symbol instead of the colon.

注：有时人们用 $\mid$ 或 $\backepsilon$ 代替冒号，作为「使得」（such that）的符号。

Defining a set using this sort of notation is very useful, although it takes some practice to read them correctly. It is a way to describe the set of all things that satisfy some condition (the condition is the logical statement after the "$\st$" symbol). Here are some more examples:

用这类记法来定义集合非常有用，尽管正确读出它们需要一些练习。这是一种描述「满足某条件的所有事物之集合」的方式（该条件就是「$\st$」符号之后的逻辑语句）。下面是更多例子：

Example 1

示例 1

Describe each of the following sets both in words and by listing out enough elements to see the pattern.

用语言描述下列各集合，并列出足够多的元素以看出规律。
  1. $\{x \st x + 3 \in \N\}\text{.}$
  2. $\{x \in \N \st x + 3 \in \N\}\text{.}$
  3. $\{x \st x \in \N \vee -x \in \N\}\text{.}$
  4. $\{x \st x \in \N \wedge -x \in \N\}\text{.}$
  1. $\{x \st x + 3 \in \N\}\text{。}$
  2. $\{x \in \N \st x + 3 \in \N\}\text{。}$
  3. $\{x \st x \in \N \vee -x \in \N\}\text{。}$
  4. $\{x \st x \in \N \wedge -x \in \N\}\text{。}$

Solution

解答
  1. This is the set of all numbers which are 3 less than a natural number (i.e., that if you add 3 to them, you get a natural number). The set could also be written as $\{-3, -2, -1, 0, 1, 2, \ldots\}$ (note that 0 is a natural number, so $-3$ is in this set because $-3 + 3 = 0$).
  2. This is the set of all natural numbers which are 3 less than a natural number. So here we just have $\{0, 1, 2, 3 \ldots\}\text{.}$
  3. This is the set of all integers (positive and negative whole numbers, written $\Z$). In other words, $\{\ldots, -2, -1, 0, 1, 2, \ldots\}\text{.}$
  4. Here we want all numbers $x$ such that $x$ and $-x$ are natural numbers. There is only one: 0. So we have the set $\{0\}\text{.}$
  1. 这是所有「比某个自然数小 3」的数的集合（即：给它加上 3 就得到自然数的数）。该集合也可写作 $\{-3, -2, -1, 0, 1, 2, \ldots\}$（注意 0 是自然数，所以 $-3$ 属于此集合，因为 $-3 + 3 = 0$）。
  2. 这是所有「比某个自然数小 3」的自然数的集合。因此这里只是 $\{0, 1, 2, 3 \ldots\}\text{。}$
  3. 这是所有整数（正整数与负整数，记作 $\Z$）的集合。换言之，即 $\{\ldots, -2, -1, 0, 1, 2, \ldots\}\text{。}$
  4. 此处我们要的是所有满足 $x$ 与 $-x$ 都是自然数的数 $x$。这样的数只有一个：0。因此我们得到集合 $\{0\}\text{。}$

We already have a lot of notation, and there is more yet. Below is a handy chart of symbols. Some of these will be discussed in greater detail as we move forward.

我们已经积累了不少记法，而且还有更多。下面是一张便于查阅的符号表。其中一些符号我们会在后续做更详细的讨论。

Special Sets 特殊集合

Set Theory Notation 集合论记号

Investigate! 探究！

  1. Find the cardinality of each set below.
    1. $A = \{3,4,\ldots, 15\}\text{.}$
    2. $B = \{n \in \N \st 2 \lt n \le 200\}\text{.}$
    3. $C = \{n \le 100 \st n \in \N \wedge \exists m \in \N (n = 2m+1)\}\text{.}$
  2. Find two sets $A$ and $B$ for which $\|A\| = 5\text{,}$ $\|B\| = 6\text{,}$ and $\|A\cup B\| = 9\text{.}$ What is $\|A \cap B\|\text{?}$
  3. Find sets $A$ and $B$ with $\|A\| = \|B\|$ such that $\|A\cup B\| = 7$ and $\|A \cap B\| = 3\text{.}$ What is $\|A\|\text{?}$
  4. Let $A = \{1,2,\ldots, 10\}\text{.}$ Define $\mathcal{B}_2 = \{B \subseteq A \st \|B\| = 2\}\text{.}$ Find $\|\mathcal{B}_2\|\text{.}$
  5. For any sets $A$ and $B\text{,}$ define $AB = \{ab \st a\in A \wedge b \in B\}\text{.}$ If $A = \{1,2\}$ and $B = \{2,3,4\}\text{,}$ what is $\|AB\|\text{?}$ What is $\|A \times B\|\text{?}$
  1. 求下列每个集合的基数：
    1. $A = \{3,4,\ldots, 15\}\text{。}$
    2. $B = \{n \in \N \st 2 \lt n \le 200\}\text{。}$
    3. $C = \{n \le 100 \st n \in \N \wedge \exists m \in \N (n = 2m+1)\}\text{。}$
  2. 找出两个集合 $A$ 与 $B$，使得 $\|A\| = 5\text{、}$ $\|B\| = 6\text{、}$ 且 $\|A\cup B\| = 9\text{。}$ 问 $\|A \cap B\|$ 是多少？
  3. 找出集合 $A$ 与 $B$，满足 $\|A\| = \|B\|$、$\|A\cup B\| = 7$ 且 $\|A \cap B\| = 3\text{。}$ 问 $\|A\|$ 是多少？
  4. 令 $A = \{1,2,\ldots, 10\}\text{。}$ 定义 $\mathcal{B}_2 = \{B \subseteq A \st \|B\| = 2\}\text{。}$ 求 $\|\mathcal{B}_2\|\text{。}$
  5. 对任意集合 $A$ 与 $B$，定义 $AB = \{ab \st a\in A \wedge b \in B\}\text{。}$ 若 $A = \{1,2\}$ 且 $B = \{2,3,4\}\text{，}$ 问 $\|AB\|$ 是多少？$\|A \times B\|$ 又是多少？

Relationships Between Sets 集合之间的关系

We have already said what it means for two sets to be equal: they have exactly the same elements. Thus, for example,

我们已经说过两个集合相等意味着什么：它们含有完全相同的元素。例如：

$\begin{equation*} \{1, 2, 3\} = \{2, 1, 3\}. \end{equation*}$

(Remember, the order the elements are written down in does not matter.) Also,

（记住，元素被写下的顺序无关紧要。）此外，

$\begin{equation*} \{1, 2, 3\} = \{1, 1+1, 1+1+1\} = \{I, II, III\} \end{equation*}$

since these are all ways to write the set containing the first three positive integers (how we write them doesn't matter, just what they are).

因为这些都是书写「包含前三个正整数的集合」的不同方式（我们怎么写并不重要，重要的是它们是什么）。

What about the sets $A = \{1, 2, 3\}$ and $B = \{1, 2, 3, 4\}\text{?}$ Clearly $A \ne B\text{,}$ but notice that every element of $A$ is also an element of $B\text{.}$ Because of this we say that $A$ is a subset of $B\text{,}$ or in symbols $A \subset B$ or $A \subseteq B\text{.}$ Both symbols are read "is a subset of." The difference is that sometimes we want to say that $A$ is either equal to or is a subset of $B\text{,}$ in which case we use $\subseteq\text{.}$ This is analogous to the difference between $\lt$ and $\le\text{.}$

那么集合 $A = \{1, 2, 3\}$ 与 $B = \{1, 2, 3, 4\}$ 呢？显然 $A \ne B\text{，}$但注意 $A$ 的每个元素也都是 $B$ 的元素。因此我们称 $A$ 是 $B$ 的子集（subset），记作 $A \subset B$ 或 $A \subseteq B\text{。}$ 这两个符号都读作「是……的子集」。区别在于：有时我们想表达「$A$ 等于 $B$ 或是 $B$ 的子集」，这时就用 $\subseteq\text{。}$ 这类似于 $\lt$ 与 $\le$ 之间的区别。

Example 2

示例 2

Let $A = \{1, 2, 3, 4, 5, 6\}\text{,}$ $B = \{2, 4, 6\}\text{,}$ $C = \{1, 2, 3\}$ and $D = \{7, 8, 9\}\text{.}$ Determine which of the following are true, false, or meaningless.

令 $A = \{1, 2, 3, 4, 5, 6\}\text{、}$ $B = \{2, 4, 6\}\text{、}$ $C = \{1, 2, 3\}$、$D = \{7, 8, 9\}\text{。}$ 判断下列各项为真、为假，还是无意义。
  1. $A \subset B\text{.}$
  2. $B \subset A\text{.}$
  3. $B \in C\text{.}$
  4. $\emptyset \in A\text{.}$
  5. $\emptyset \subset A\text{.}$
  6. $A \lt D\text{.}$
  7. $3 \in C\text{.}$
  8. $3 \subset C\text{.}$
  9. $\{3\} \subset C\text{.}$
  1. $A \subset B\text{。}$
  2. $B \subset A\text{。}$
  3. $B \in C\text{。}$
  4. $\emptyset \in A\text{。}$
  5. $\emptyset \subset A\text{。}$
  6. $A \lt D\text{。}$
  7. $3 \in C\text{。}$
  8. $3 \subset C\text{。}$
  9. $\{3\} \subset C\text{。}$

Solution

解答
  1. False. For example, $1\in A$ but $1 \notin B\text{.}$
  2. True. Every element in $B$ is an element in $A\text{.}$
  3. False. The elements in $C$ are 1, 2, and 3. The set $B$ is not equal to 1, 2, or 3.
  4. False. $A$ has exactly 6 elements, and none of them are the empty set.
  5. True. Everything in the empty set (nothing) is also an element of $A\text{.}$ Notice that the empty set is a subset of every set.
  6. Meaningless. A set cannot be less than another set.
  7. True. $3$ is one of the elements of the set $C\text{.}$
  8. Meaningless. $3$ is not a set, so it cannot be a subset of another set.
  9. True. $\{3\}$ is the only element of the set $\{3\}\text{,}$ and is an element of $C\text{,}$ so every element in $\{3\}$ is an element of $C\text{.}$
  1. 假。例如，$1\in A$ 但 $1 \notin B\text{。}$
  2. 真。$B$ 中的每个元素都在 $A$ 中。
  3. 假。$C$ 的元素是 1、2、3。集合 $B$ 既不等于 1，也不等于 2 或 3。
  4. 假。$A$ 恰有 6 个元素，其中没有一个是空集。
  5. 真。空集里的所有东西（什么都没有）也都是 $A$ 的元素。注意：空集是任何集合的子集。
  6. 无意义。一个集合不能「小于」另一个集合。
  7. 真。$3$ 是集合 $C$ 的元素之一。
  8. 无意义。$3$ 不是集合，因此它不可能是另一个集合的子集。
  9. 真。$\{3\}$ 是集合 $\{3\}$ 的唯一元素，且它是 $C$ 的元素，因此 $\{3\}$ 中的每个元素都属于 $C\text{。}$

In the example above, $B$ is a subset of $A\text{.}$ You might wonder what other sets are subsets of $A\text{.}$ If you collect all these subsets of $A$ into a new set, we get a set of sets. We call the set of all subsets of $A$ the power set of $A\text{,}$ and write it $\pow(A)\text{.}$

在上例中，$B$ 是 $A$ 的子集。你或许会想：还有哪些集合是 $A$ 的子集？如果把 $A$ 的所有子集收集起来组成一个新的集合，我们就得到了一个「集合的集合」。我们把 $A$ 的所有子集组成的集合称为 $A$ 的幂集（power set），记作 $\pow(A)\text{。}$

Example 3

示例 3

Let $A = \{1,2,3\}\text{.}$ Find $\pow(A)\text{.}$

令 $A = \{1,2,3\}\text{。}$ 求 $\pow(A)\text{。}$

Solution

解答

$\pow(A)$ is a set of sets, all of which are subsets of $A\text{.}$ So

$\pow(A)$ 是一个由集合构成的集合，其中每个集合都是 $A$ 的子集。因此

$\begin{equation*} \pow(A) = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1, 3\}, \{2,3\}, \{1,2,3\}\}. \end{equation*}$

Notice that while $2 \in A\text{,}$ it is wrong to write $2 \in \pow(A)$ since none of the elements in $\pow(A)$ are numbers! On the other hand, we do have $\{2\} \in \pow(A)$ because $\{2\} \subseteq A\text{.}$

注意：虽然 $2 \in A\text{，}$但写作 $2 \in \pow(A)$ 是错误的，因为 $\pow(A)$ 的元素中没有数字！另一方面，我们确实有 $\{2\} \in \pow(A)$，因为 $\{2\} \subseteq A\text{。}$

What does a subset of $\pow(A)$ look like? Notice that $\{2\} \not\subseteq \pow(A)$ because not everything in $\{2\}$ is in $\pow(A)\text{.}$ But we do have $\{\{2\}\} \subseteq \pow(A)\text{.}$ The only element of $\{\{2\}\}$ is the set $\{2\}$ which is also an element of $\pow(A)\text{.}$ We could take the collection of all subsets of $\pow(A)$ and call that $\pow(\pow(A))\text{.}$ Or even the power set of that set of sets of sets.

$\pow(A)$ 的子集长什么样？注意 $\{2\} \not\subseteq \pow(A)$，因为 $\{2\}$ 里的东西并非都在 $\pow(A)$ 中。但我们确实有 $\{\{2\}\} \subseteq \pow(A)\text{。}$ $\{\{2\}\}$ 的唯一元素是集合 $\{2\}$，而它同时也是 $\pow(A)$ 的元素。我们可以把 $\pow(A)$ 的所有子集收集起来，称之为 $\pow(\pow(A))\text{。}$ 甚至可以再取这个「集合的集合的集合」的幂集。

Another way to compare sets is by their size. Notice that in the example above, $A$ has 6 elements and $B\text{,}$ $C\text{,}$ and $D$ all have 3 elements. The size of a set is called the set's cardinality. We would write $\|A\| = 6\text{,}$ $\|B\| = 3\text{,}$ and so on. For sets that have a finite number of elements, the cardinality of the set is simply the number of elements in the set. Note that the cardinality of $\{ 1, 2, 3, 2, 1\}$ is 3. We do not count repeats (in fact, $\{1, 2, 3, 2, 1\}$ is exactly the same set as $\{1, 2, 3\}$). There are sets with infinite cardinality, such as $\N\text{,}$ the set of rational numbers (written $\Q$), the set of even natural numbers, and the set of real numbers ($\R$). It is possible to distinguish between different infinite cardinalities, but that is beyond the scope of this text. For us, a set will either be infinite, or finite; if it is finite, then we can determine its cardinality by counting elements.

比较集合的另一种方式是通过它们的大小。注意在上例中，$A$ 有 6 个元素，而 $B\text{、}$ $C\text{、}$ $D$ 都各有 3 个元素。集合的大小称为该集合的基数（cardinality）。我们会写作 $\|A\| = 6\text{、}$ $\|B\| = 3\text{，}$等等。对于元素个数有限的集合，其基数就是集合中元素的个数。注意 $\{ 1, 2, 3, 2, 1\}$ 的基数是 3。我们不重复计数（事实上，$\{1, 2, 3, 2, 1\}$ 与 $\{1, 2, 3\}$ 是完全相同的集合）。有些集合具有无穷基数，例如 $\N\text{、}$有理数集（记作 $\Q$）、偶自然数集，以及实数集（$\R$）。不同的无穷基数之间是可以区分的，但这超出了本书的范围。对我们而言，一个集合要么无穷，要么有限；若有限，则可通过计数元素来确定其基数。

Example 4

示例 4
  1. Find the cardinality of $A = \{23, 24, \ldots, 37, 38\}\text{.}$
  2. Find the cardinality of $B = \{1, \{2, 3, 4\}, \emptyset\}\text{.}$
  3. If $C = \{1,2,3\}\text{,}$ what is the cardinality of $\pow(C)\text{?}$
  1. 求 $A = \{23, 24, \ldots, 37, 38\}$ 的基数。
  2. 求 $B = \{1, \{2, 3, 4\}, \emptyset\}$ 的基数。
  3. 若 $C = \{1,2,3\}\text{，}$ 问 $\pow(C)$ 的基数是多少？

Solution

解答
  1. Since $38 - 23 = 15\text{,}$ we can conclude that the cardinality of the set is $\|A\| = 16$ (you need to add one since 23 is included).
  2. Here $\|B\| = 3\text{.}$ The three elements are the number 1, the set $\{2,3,4\}\text{,}$ and the empty set.
  3. We wrote out the elements of the power set $\pow(C)$ above, and there are 8 elements (each of which is a set). So $\|\pow(C)\| = 8\text{.}$ (You might wonder if there is a relationship between $\|A\|$ and $\|\pow(A)\|$ for all sets $A\text{.}$ This is a good question which we will return to in Chapter 1.)
  1. 因为 $38 - 23 = 15\text{，}$所以可推得该集合的基数为 $\|A\| = 16$（由于 23 也被包含在内，需要加 1）。
  2. 这里 $\|B\| = 3\text{。}$ 这三个元素分别是：数字 1、集合 $\{2,3,4\}\text{，}$以及空集。
  3. 我们在上面对幂集 $\pow(C)$ 列出了元素，共有 8 个元素（每个都是集合）。因此 $\|\pow(C)\| = 8\text{。}$（你或许会想：对所有集合 $A$，$\|A\|$ 与 $\|\pow(A)\|$ 之间是否存在某种关系？这是个好问题，我们将在第 1 章再来讨论。）

Operations On Sets 集合上的运算

Is it possible to add two sets? Not really, however there is something similar. If we want to combine two sets to get the collection of objects that are in either set, then we can take the union of the two sets. Symbolically,

两个集合可以相加吗？严格说不行，但存在类似的操作。如果我们想把两个集合合并，得到「属于其中任一集合」的对象的全体，那么可以取这两个集合的并集（union）。用符号表示：

$\begin{equation*} C = A \cup B, \end{equation*}$

read, "$C$ is the union of $A$ and $B\text{,}$" means that the elements of $C$ are exactly the elements which are either an element of $A$ or an element of $B$ (or an element of both). For example, if $A = \{1, 2, 3\}$ and $B = \{2, 3, 4\}\text{,}$ then $A \cup B = \{1, 2, 3, 4\}\text{.}$

读作「$C$ 是 $A$ 与 $B$ 的并集」，意思是：$C$ 的元素恰好是那些「属于 $A$ 或属于 $B$（或同时属于两者）」的元素。例如，若 $A = \{1, 2, 3\}$、$B = \{2, 3, 4\}\text{，}$则 $A \cup B = \{1, 2, 3, 4\}\text{。}$

The other common operation on sets is intersection. We write,

集合上另一种常见运算是交集（intersection）。我们写作：

$\begin{equation*} C = A \cap B \end{equation*}$

and say, "$C$ is the intersection of $A$ and $B\text{,}$" when the elements in $C$ are precisely those both in $A$ and in $B\text{.}$ So if $A = \{1, 2, 3\}$ and $B = \{2, 3, 4\}\text{,}$ then $A \cap B = \{2, 3\}\text{.}$

并说「$C$ 是 $A$ 与 $B$ 的交集」，此时 $C$ 中的元素恰好是那些既在 $A$ 中又在 $B$ 中的元素。因此若 $A = \{1, 2, 3\}$、$B = \{2, 3, 4\}\text{，}$则 $A \cap B = \{2, 3\}\text{。}$

Often when dealing with sets, we will have some understanding as to what "everything" is. Perhaps we are only concerned with natural numbers. In this case we would say that our universe is $\N\text{.}$ Sometimes we denote this universe by $\U\text{.}$ Given this context, we might wish to speak of all the elements which are not in a particular set. We say $B$ is the complement of $A\text{,}$ and write,

在处理集合时，我们通常会对「全体」有所约定。也许我们只关心自然数。此时我们会说我们的全集（universe）是 $\N\text{。}$ 有时我们把这个全集记作 $\U\text{。}$ 在这一背景下，我们可能想谈论某个特定集合中不在其中的所有元素。我们说 $B$ 是 $A$ 的补集（complement），写作：

$\begin{equation*} B = \bar A \end{equation*}$

when $B$ contains every element not contained in $A\text{.}$ So, if our universe is $\{1, 2,\ldots, 9, 10\}\text{,}$ and $A = \{2, 3, 5, 7\}\text{,}$ then $\bar A = \{1, 4, 6, 8, 9,10\}\text{.}$

此时 $B$ 含有所有不属于 $A$ 的元素。因此，若全集为 $\{1, 2,\ldots, 9, 10\}\text{、}$且 $A = \{2, 3, 5, 7\}\text{，}$则 $\bar A = \{1, 4, 6, 8, 9,10\}\text{。}$

Of course we can perform more than one operation at a time. For example, consider

当然，我们可以一次执行多个运算。例如，考虑

$\begin{equation*} A \cap \bar B. \end{equation*}$

This is the set of all elements which are both elements of $A$ and not elements of $B\text{.}$ What have we done? We've started with $A$ and removed all of the elements which were in $B\text{.}$ Another way to write this is the set difference:

这是所有「既属于 $A$ 又不属于 $B$」的元素的集合。我们做了什么？我们从 $A$ 出发，去掉了所有属于 $B$ 的元素。另一种写法是差集（set difference）：

$\begin{equation*} A \cap \bar B = A \setminus B. \end{equation*}$

It is important to remember that these operations (union, intersection, complement, and difference) on sets produce other sets. Don't confuse these with the symbols from the previous section (element of and subset of). $A \cap B$ is a set, while $A \subseteq B$ is true or false. This is the same difference as between $3 + 2$ (which is a number) and $3 \le 2$ (which is false).

重要的是要记住：集合上的这些运算（并、交、补、差）产生的是另一些集合。不要把它们与上节的符号（属于、包含于）混淆。$A \cap B$ 是一个集合，而 $A \subseteq B$ 是一个真假判断。这类似于 $3 + 2$（是一个数）与 $3 \le 2$（是假命题）之间的区别。

Example 5

示例 5

Let $A = \{1, 2, 3, 4, 5, 6\}\text{,}$ $B = \{2, 4, 6\}\text{,}$ $C = \{1, 2, 3\}$ and $D = \{7, 8, 9\}\text{.}$ If the universe is $\U = \{1, 2, \ldots, 10\}\text{,}$ find:

令 $A = \{1, 2, 3, 4, 5, 6\}\text{、}$ $B = \{2, 4, 6\}\text{、}$ $C = \{1, 2, 3\}$、$D = \{7, 8, 9\}\text{。}$ 若全集为 $\U = \{1, 2, \ldots, 10\}\text{，}$求：
  1. $A \cup B\text{.}$
  2. $A \cap B\text{.}$
  3. $B \cap C\text{.}$
  4. $A \cap D\text{.}$
  5. $\bar{B \cup C}\text{.}$
  6. $A \setminus B\text{.}$
  7. $(D \cap \bar C) \cup \bar{A \cap B}\text{.}$
  8. $\emptyset \cup C\text{.}$
  9. $\emptyset \cap C\text{.}$
  1. $A \cup B\text{。}$
  2. $A \cap B\text{。}$
  3. $B \cap C\text{。}$
  4. $A \cap D\text{。}$
  5. $\bar{B \cup C}\text{。}$
  6. $A \setminus B\text{。}$
  7. $(D \cap \bar C) \cup \bar{A \cap B}\text{。}$
  8. $\emptyset \cup C\text{。}$
  9. $\emptyset \cap C\text{。}$

Solution

解答
  1. $A \cup B = \{1, 2, 3, 4, 5, 6\} = A$ since everything in $B$ is already in $A\text{.}$
  2. $A \cap B = \{2, 4, 6\} = B$ since everything in $B$ is in $A\text{.}$
  3. $B \cap C = \{2\}$ as the only element of both $B$ and $C$ is 2.
  4. $A \cap D = \emptyset$ since $A$ and $D$ have no common elements.
  5. $\bar{B \cup C} = \{5, 7, 8, 9, 10\}\text{.}$ First we find that $B \cup C = \{1, 2, 3, 4, 6\}\text{,}$ then we take everything not in that set.
  6. $A \setminus B = \{1, 3, 5\}$ since the elements 1, 3, and 5 are in $A$ but not in $B\text{.}$ This is the same as $A \cap \bar B\text{.}$
  7. $(D \cap \bar C) \cup \bar{A \cap B} = \{1, 3, 5, 7, 8, 9, 10\}\text{.}$ The set contains all elements that are either in $D$ but not in $C$ (i.e., $\{7,8,9\}$), or not in both $A$ and $B$ (i.e., $\{1,3,5,7,8,9,10\}$).
  8. $\emptyset \cup C = C$ since nothing is added by the empty set.
  9. $\emptyset \cap C = \emptyset$ since nothing can be both in a set and in the empty set.
  1. $A \cup B = \{1, 2, 3, 4, 5, 6\} = A$，因为 $B$ 中的所有元素都已经在 $A$ 中。
  2. $A \cap B = \{2, 4, 6\} = B$，因为 $B$ 中的所有元素都在 $A$ 中。
  3. $B \cap C = \{2\}$，因为 $B$ 与 $C$ 的唯一公共元素是 2。
  4. $A \cap D = \emptyset$，因为 $A$ 与 $D$ 没有公共元素。
  5. $\bar{B \cup C} = \{5, 7, 8, 9, 10\}\text{。}$ 先求得 $B \cup C = \{1, 2, 3, 4, 6\}\text{，}$ 再取不在这个集合中的所有元素。
  6. $A \setminus B = \{1, 3, 5\}$，因为元素 1、3、5 属于 $A$ 但不属于 $B\text{。}$ 这与 $A \cap \bar B$ 相同。
  7. $(D \cap \bar C) \cup \bar{A \cap B} = \{1, 3, 5, 7, 8, 9, 10\}\text{。}$ 该集合包含所有满足以下条件的元素：要么在 $D$ 中但不在 $C$ 中（即 $\{7,8,9\}$），要么不同时属于 $A$ 和 $B$（即 $\{1,3,5,7,8,9,10\}$）。
  8. $\emptyset \cup C = C$，因为空集没有添加任何元素。
  9. $\emptyset \cap C = \emptyset$，因为没有任何东西能同时「在一个集合中」又「在空集中」。

You might notice that the symbols for union and intersection slightly resemble the logic symbols for "or" and "and." This is no accident. What does it mean for $x$ to be an element of $A\cup B\text{?}$ It means that $x$ is an element of $A$ or $x$ is an element of $B$ (or both). That is,

你或许已经注意到，并集与交集的符号和逻辑中「或」与「且」的符号略有相似之处。这并非巧合。说 $x$ 是 $A\cup B$ 的元素是什么意思？它的意思是：$x$ 是 $A$ 的元素或 $x$ 是 $B$ 的元素（或两者皆是）。即：

$\begin{equation*} x \in A \cup B \qquad \Iff \qquad x \in A \vee x \in B. \end{equation*}$

Similarly,

类似地，

$\begin{equation*} x \in A \cap B \qquad \Iff \qquad x \in A \wedge x \in B. \end{equation*}$

Also,

还有，

$\begin{equation*} x \in \bar A \qquad \Iff \qquad \neg (x \in A). \end{equation*}$

which says $x$ is an element of the complement of $A$ if $x$ is not an element of $A\text{.}$

这表示：若 $x$ 不是 $A$ 的元素，则 $x$ 是 $A$ 的补集的元素。

There is one more way to combine sets which will be useful for us: the Cartesian product, $A \times B\text{.}$ This sounds fancy but is nothing you haven't seen before. When you graph a function in calculus, you graph it in the Cartesian plane. This is the set of all ordered pairs of real numbers $(x,y)\text{.}$ We can do this for any pair of sets, not just the real numbers with themselves.

还有一种我们日后会用到的集合组合方式：笛卡尔积（Cartesian product），$A \times B\text{。}$ 这听起来很花哨，但其实你之前已经见过。在微积分中画函数图像时，你是在笛卡尔平面上作图。那就是所有实数有序对 $(x,y)$ 的集合。对于任意一对集合我们都可以这样做，而不限于实数与自身。

Put another way, $A \times B = \{(a,b) \st a \in A \wedge b \in B\}\text{.}$ The first coordinate comes from the first set and the second coordinate comes from the second set. Sometimes we will want to take the Cartesian product of a set with itself, and this is fine: $A \times A = \{(a,b) \st a, b \in A\}$ (we might also write $A^2$ for this set). Notice that in $A \times A\text{,}$ we still want all ordered pairs, not just the ones where the first and second coordinate are the same. We can also take products of 3 or more sets, getting ordered triples, or quadruples, and so on.

换句话说，$A \times B = \{(a,b) \st a \in A \wedge b \in B\}\text{。}$ 第一个坐标来自第一个集合，第二个坐标来自第二个集合。有时我们想取一个集合与自身的笛卡尔积，这也完全可行：$A \times A = \{(a,b) \st a, b \in A\}$（这个集合也可记作 $A^2$）。注意在 $A \times A$ 中，我们仍然要所有有序对，而不只是第一、第二坐标相同的那些。我们也可以取 3 个或更多集合的积，得到有序三元组、四元组，依此类推。

Example 6

示例 6

Let $A = \{1,2\}$ and $B = \{3,4,5\}\text{.}$ Find $A \times B$ and $A \times A\text{.}$ How many elements do you expect to be in $B \times B\text{?}$

令 $A = \{1,2\}$、$B = \{3,4,5\}\text{。}$ 求 $A \times B$ 与 $A \times A\text{。}$ 你预期 $B \times B$ 中有多少个元素？

Solution

解答

$A \times B = \{(1,3), (1,4), (1,5), (2,3), (2,4), (2,5)\}\text{.}$

$A \times B = \{(1,3), (1,4), (1,5), (2,3), (2,4), (2,5)\}\text{。}$

$A \times A = A^2 = \{(1,1), (1,2), (2,1), (2,2)\}\text{.}$

$A \times A = A^2 = \{(1,1), (1,2), (2,1), (2,2)\}\text{。}$

$\|B\times B\| = 9\text{.}$ There will be 3 pairs with first coordinate $3\text{,}$ three more with first coordinate $4\text{,}$ and a final three with first coordinate $5\text{.}$

$\|B\times B\| = 9\text{。}$ 其中第一坐标为 $3$ 的有序对 3 个，第一坐标为 $4$ 的又有 3 个，最后第一坐标为 $5$ 的还有 3 个。

Venn Diagrams 韦恩图

There is a very nice visual tool we can use to represent operations on sets. A Venn diagram displays sets as intersecting circles. We can shade the region we are talking about when we carry out an operation. We can also represent cardinality of a particular set by putting the number in the corresponding region.

我们有一种很好的可视化工具来表示集合上的运算。韦恩图（Venn diagram）把集合画成相交的圆。在执行某种运算时，我们可以把所讨论的区域涂上阴影。我们也可以把某个特定集合的基数写到对应的区域中。

Two-set Venn diagram (empty) Three-set Venn diagram (empty)

（两集合与三集合的韦恩图空框；矩形表示全集，圆表示各集合。）

Each circle represents a set. The rectangle containing the circles represents the universe. To represent combinations of these sets, we shade the corresponding region. For example, we could draw $A \cap B$ as:

每个圆表示一个集合。包围这些圆的矩形表示全集。要表示这些集合的组合，我们就把相应的区域涂上阴影。例如，我们可以把 $A \cap B$ 画成：

Venn diagram of A intersect B

（韦恩图：$A \cap B$ 的阴影区域。）

Here is a representation of $A \cap \bar B\text{,}$ or equivalently $A \setminus B\text{:}$

下面是 $A \cap \bar B$（等价于 $A \setminus B$）的图示：

Venn diagram of A minus B

（韦恩图：$A \setminus B$ 的阴影区域。）

A more complicated example is $(B \cap C) \cup (C \cap \bar A)\text{,}$ as seen below.

一个更复杂的例子是 $(B \cap C) \cup (C \cap \bar A)\text{，}$如下图所示。

Venn diagram of a complicated three-set expression

（韦恩图：上述三集合复杂表达式的阴影区域。）

Notice that the shaded regions above could also be arrived at in another way. We could have started with all of $C\text{,}$ then excluded the region where $C$ and $A$ overlap outside of $B\text{.}$ That region is $(A \cap C) \cap \bar B\text{.}$ So the above Venn diagram also represents $C \cap \bar{\left((A\cap C)\cap \bar B\right)}\text{.}$ So using just the picture, we have determined that

注意，上面这些阴影区域也可以换一种方式得到。我们可以先取整个 $C\text{，}$再去掉「$C$ 与 $A$ 相交、却在 $B$ 之外」的区域。那个区域就是 $(A \cap C) \cap \bar B\text{。}$ 因此上面的韦恩图也表示 $C \cap \bar{\left((A\cap C)\cap \bar B\right)}\text{。}$ 仅凭借这幅图，我们就已经确定了

$\begin{equation*} (B \cap C) \cup (C \cap \bar A) = C \cap \bar{\left((A\cap C)\cap \bar B\right)}. \end{equation*}$