集合、逻辑符号与证明方法

这一页补的是第 1 讲最常用的“语言”：集合（把一些东西装进一个袋子）、逻辑符号（“如果……那么……”“对所有”“存在”），以及三种证明方法（当且仅当、数学归纳法、反证法）。第 1 讲几乎每一页都在用它们：第 3 页 的选择集 $X$，第 5 页 的最优选择集 $C(B;⪰)$，第 7 页 和 第 14 页 的归纳证明，第 10–12 页 的“当且仅当”，第 15 页 的反证法，第 16 页 的 ${\mathbb{R}}_{+}^n$。

怎么读这一页：每一节都按同样的顺序走——先用大白话说它是什么，再教你符号怎么念，然后是正式定义、真的算过的例子、易错点，最后一道自测题。第一次读看不懂正式定义没关系，先看例子，回头再读定义。

集合与元素

集合就是“把一些东西放在一起，当作一个整体来看”，像一个购物袋。食堂今天的菜单、你手机里装的 App、班上的同学，都是集合。袋子里的每一样东西叫这个集合的元素。

集合有两个特点要记住：

1. 只管“有没有”，不管顺序和重复。 $\{\text{米饭},\text{面条}\}$ 和 $\{\text{面条},\text{米饭}\}$ 是同一个集合；$\{\text{米饭},\text{米饭},\text{面条}\}$ 也还是这个集合，重复写的那个不算第二次。
2. 必须说得清。 任给一样东西，要么在里面，要么不在，不能含糊。“好吃的菜”不是一个集合（好不好吃因人而异）；“价格不超过 15 元的菜”是一个集合。

记号与读法

习惯上用大写字母（$A$、$B$、$X$）表示集合，小写字母（$a$、$x$、$y$）表示元素。符号 $\in$ 来自希腊字母 $ϵ$，可以记成“element 的 e”。

子集、交集与并集

子集说的是“小袋子装在大袋子里”：$A$ 里的每一样东西，$B$ 里都有。第 1 讲里最常见的子集是菜单：$X$ 是所有可能的选项，某一天能拿到的只是其中一部分 $B$，所以 $B\subseteq X$。

两个集合之间还有三种常用的“运算”，得到新的集合：

• 交集 $A\cap B$：两边都有的元素；
• 并集 $A\cup B$：至少一边有的元素；
• 差集 $A-B$（也写作 $A\setminus B$）：在 $A$ 里、但不在 $B$ 里的元素。

记号与读法

看图时盯住涂色的部分：（b）只涂两个圈重叠的“橄榄形”，所以交集只有苹果和香蕉；（c）两个圈全涂，并集有四样；（d）只涂左圈里不和右圈重叠的那一块，只剩橙子。

空集是任何集合的子集

$\varnothing \subseteq B$ 对任何 $B$ 都成立。按定义，它要求“$\varnothing$ 的每个元素都在 $B$ 里”。空集一个元素都没有，所以找不到任何一个元素违反这条要求，要求就算满足了。数学上叫“空真”（vacuously true）。生活中的类比：“我们班所有养恐龙的同学都考了满分”是真话，因为班上根本没人养恐龙，挑不出反例。

同理，任何集合都是它自己的子集：$B\subseteq B$。所以 $X=\{x,y,z\}$ 的子集一共 8 个，包括 $\varnothing$ 和 $X$ 本身（第 9 页的图把它们全画出来了）。

证明两个集合相等：双向包含

要证明 $S=T$，标准做法是分两步：先证 $S\subseteq T$（任取 $S$ 的元素，说明它在 $T$ 里），再证 $T\subseteq S$。两步都成立，两边的元素就完全一样。这叫双向包含，第 12 页证明命题 2 时用的就是它。

集合描述法与区间

元素少的时候可以一个个列出来；元素太多、甚至有无穷多个时，就改为写一条挑选规则：“从某个大集合里，把满足条件的元素挑出来”。这就是集合描述法（也叫集合构造式）。

记号与读法

$$\{x\in A\mid P(x)\}$$

读作“$A$ 中所有满足 $P(x)$ 的 $x$ 组成的集合”。

• 竖线 $\mid$ 读作“使得”（such that）。有的书写成冒号：$\{x\in A:P(x)\}$，意思一样（课程阅读材料常用冒号）。
• 竖线左边 $x\in A$ 说“从哪里挑”；竖线右边 $P(x)$ 说“挑的条件”。
• 字母 $x$ 只是个“占位符”，换成别的字母意思不变：$\{x\in B\mid x>3\}=\{t\in B\mid t>3\}$。

区间：数轴上的一段

实数里最常用的一类描述法集合是区间（区间）。方括号表示端点在里面，圆括号表示端点不在里面：

第 5 页的例子正是区间端点惹的祸：在 $[0,1)$ 上“越大越好”，最好的应该是 1，可 1 不在菜单里，于是选不出来；换成 $[0,1]$，就选 1。数轴上怎么画实心点、空心点，见 闭集。

元素个数

$|B|$ 就是“$B$ 里有几样东西”。第 7 页说“对 $|B|$ 归纳”，意思是按菜单上选项的个数 $1,2,3,\dots$ 一步步证明。

记号与读法：$|B|$ 读作“$B$ 的元素个数”，也叫 $B$ 的基数（cardinality）。数个数时，重复的元素只算一次。

$[0,1)$ 这样的集合有无穷多个元素，写不出 $|[0,1)|$ 等于几。无限集之间也能比“谁更多”，那是 可数与不可数 要讲的事。

实数与商品空间

实数就是数轴上的所有点：整数（$-2$、$0$、$7$）、分数（$\frac{1}{2}$、$-0.75$）、还有 $\sqrt{2}$、$\pi$ 这样写不成分数的数。全体实数记作 $\mathbb{R}$。效用函数 $u:X\to \mathbb{R}$ 的意思就是“给每个选项打一个实数分数”。

经济学里的选项常常是商品篮子：买 2 杯奶茶、3 个面包，可以写成一对数 $(2,3)$。两种商品的篮子是平面上的一个点，所有这样的点组成 ${\mathbb{R}}^2$；$n$ 种商品的篮子是 $n$ 个数排成一列 $(x_1,\dots ,x_n)$，所有这样的数组组成 ${\mathbb{R}}^n$。商品数量不能是负的，所以经济学最常用的是 ${\mathbb{R}}_{+}^n$：每个分量都不小于 0。

记号与读法

最后一行在 第 19 页 的单调性里要用到：$x\ge y$ 说的是“$x$ 每样东西都不比 $y$ 少”。

看右图时注意两条加粗的坐标轴：$(0,4)$ 表示“不买奶茶、买 4 个面包”，它在轴上，也属于 ${\mathbb{R}}_{+}^2$，因为条件是“$\ge 0$”，不是“$>0$”。

笛卡尔积

去食堂点一碗面，要做两个选择：吃什么（米饭还是面条），要多大份（小份还是大份）。把这两个选择配成一对，所有可能的配法组成的集合，就是笛卡尔积。

记号与读法：$X\times Y$ 读作“$X$ 叉乘 $Y$”或“$X$ 与 $Y$ 的笛卡尔积”。它的元素是有序对 $(x,y)$（有序对）：第一个位置从 $X$ 里取，第二个位置从 $Y$ 里取。

左图每一行是一种主食、每一列是一种份量，格子数正好是 $2\times 2=4$。右图告诉你：${\mathbb{R}}^2$ 本身就是笛卡尔积 $\mathbb{R}\times \mathbb{R}$，${\mathbb{R}}^n$ 是 $n$ 个 $\mathbb{R}$ 的笛卡尔积，所以商品篮子 $(x_1,\dots ,x_n)$ 就是一个“$n$ 元有序组”。

命题与“如果……那么……”

数学里的命题（statement）是一句能判断真假的话。“$2+3=5$”是真命题，“$2>3$”是假命题，“今天天气好吗”不是命题。

最重要的句式是“如果 $P$，那么 $Q$”，记作 $P\Rightarrow Q$。它的意思是：凡是 $P$ 成立的情形，$Q$ 都成立。 它是一个“承诺”：老师说“如果你考 90 分以上，我请你喝奶茶”。

• 你考了 95 分、老师请了：承诺兑现。
• 你考了 95 分、老师没请：承诺被打破——这是唯一让“$P\Rightarrow Q$”为假的情况。
• 你考了 70 分，老师请没请都不算违约：承诺只管“考了 90 分以上”的情形。

记号与读法

最后一行要特别注意：数学里的“或”包括“两个都成立”。第 3 页的完备性说“$x⪰y$ 或 $y⪰x$（或两者都成立）”，就是这个意思。

看左图找三个点：95 分在小圈里，也就一定在大圈里（充分）；50 分不在大圈里，也就不可能在小圈里（必要，也就是逆否命题）；75 分在大圈里却不在小圈里——这说明逆命题“及格 $\Rightarrow$ 90 分以上”是错的。

量词：对所有、存在及其否定

很多数学句子是在说“每一个都……”或“至少有一个……”。这两种说法各有一个符号，叫量词。

• $\forall$：倒过来的 A，取自 All，读作“对所有”“对任意”。“$\forall x\in A$”是“$A$ 里每一个 $x$，没有例外”。
• $\exists$：反过来的 E，取自 Exists，读作“存在”。“$\exists x\in A$”是“$A$ 里至少能找到一个 $x$”，一个就够。

记号与读法

量词写在式子后面是数学书的常见写法，读的时候在脑子里把它挪到前面：“对 $B$ 中所有 $y$，都有 $x⪰y$”。

这张图说明了“所有”和“存在”怎样互相否定：要推翻“所有菜都 $\le 20$ 元”，不用证明“所有菜都贵”，只要找到一道超过 20 元的菜。

怎样证明“当且仅当”

“$P$ 当且仅当 $Q$”（$P$ if and only if $Q$，常缩写成 iff）是两句话合在一起：$P\Rightarrow Q$，而且 $Q\Rightarrow P$。用上一节的图说，就是两个圈完全重合，$P$ 和 $Q$ 说的是同一件事。

所以证明它必须分两个方向，各证一遍，缺一不可。

记号与读法

第 11 页证明命题 2 就是这样写的：（$\Rightarrow$）这一段假设存在理性偏好，推出 HARP；（$\Leftarrow$）这一段假设 HARP，造出理性偏好。

数字验证：第 14 页小张的打分 $u(\text{苹果})=3$、$u(\text{橙子})=2$，$3>2$，确实苹果 $\succ$ 橙子；$u(\text{苹果})=u(\text{香蕉})=3$，“$3>3$”不成立，确实苹果 $\succ$ 香蕉不成立（两者一样好）。

用一串“$⟺$”证明

第 16 页写过这样一串：

$$x⪰y⟺u(x)\ge u(y)⟺v(u(x))\ge v(u(y)).$$

这种写法要求每一个 $⟺$ 两个方向都对。第二个 $⟺$ 依赖 $v$ 严格递增，为什么见 复合函数。

数学归纳法

要证明“对每一个正整数 $n$，某件事都成立”，一个一个验证是不可能的——正整数有无穷多个。数学归纳法的办法是推倒一排多米诺骨牌：

1. 起点：推倒第 1 块（证明 $n=1$ 时成立）；
2. 传递：保证“任何一块倒下，都会推倒下一块”（证明：如果 $n$ 时成立，那么 $n+1$ 时也成立）。

两件事都做到，所有骨牌都会倒。也可以想成爬楼梯：你能站上第 1 级，并且能从任何一级迈上下一级，那么每一级你都到得了。

图里要注意第 2 步是对任意的 $n$ 说的：不是“第 1 块推倒第 2 块”这一次，而是“不管哪一块倒下，都会推倒它后面那一块”。

记号与读法：$P(n)$ 表示“关于 $n$ 的那句话”，例如 $P(n)$：“$1+2+\cdots +n=\frac{n(n+1)}{2}$”。第 2 步里先假设的“$P(n)$ 成立”叫归纳假设，它不是凭空假设，而是“前一块骨牌已经倒了”。第 7 页的“对 $|B|$ 归纳”，$P(n)$ 就是“有 $n$ 个选项的菜单都选得出”。

数字验证：$n=4$ 时 $1+2+3+4=10$，公式给出 $\frac{4\times 5}{2}=10$；$n=100$ 时公式给出 5050，不用真的加一百次。

反证法

反证法像侦探推理：“假设是他干的，那他那天晚上必须在现场；可监控拍到他整晚都在另一个城市——矛盾。所以不是他干的。”

要证明命题 $P$，先假设 $P$ 不成立，然后一步步推理，直到推出一件不可能的事（和已知事实、前提或定义冲突）。既然“$P$ 不成立”会导致不可能的事，它就是错的，所以 $P$ 成立。

记号与读法：证明里常写“假设……不成立”“这与……矛盾”。“矛盾”（contradiction）就是同一件事既成立又不成立，比如“$M$ 是最大的数”和“$M^{\prime }$ 比 $M$ 还大”同时出现。

数字感受一下：如果你说 $M=0.99$ 最大，我就拿出 $0.995$；你改口说 $0.999$，我拿出 $0.9995$。这正是第 5 页“在 $[0,1)$ 上越大越好，选不出最好的”的原因。