笛卡尔积

笛卡尔积（Cartesian product）把两个集合的元素按顺序配对。对集合 $A,B$，定义 $$A\times B=\{(a,b):a\in A,b\in B\}.$$ 第一位置必须来自 $A$，第二位置必须来自 $B$；有序对 $(a,b)$ 与 $(b,a)$ 一般不同。

列出一张完整的配对表

令 $A=\{1,2\}$，$B=\{x,y,z\}$。按第一个分量分组，可列出 $$A\times B=\{(1,x),(1,y),(1,z),(2,x),(2,y),(2,z)\}.$$ 每个 $a\in A$ 都能与 $B$ 的三个元素配对，所以总数为 $|A\times B|=|A||B|=2\cdot 3=6$。一般有限集合也由同样的逐行计数得到乘法公式。若任一集合为空，就没有可组成的有序对，笛卡尔积也为空。

顺序与关系

$B\times A$ 中有 $(x,1)$，而 $A\times B$ 中有 $(1,x)$；两者元素数量相同，却通常不是同一个集合。需要交换顺序时，可明确给出双射 $(a,b)\mapsto (b,a)$，不能直接把等势当作相等。

一个从 $A$ 到 $B$ 的二元关系，就是 $A\times B$ 的某个子集。例如“整数 $a$ 小于整数 $b$”选择了 $\mathbb{Z}\times \mathbb{Z}$ 中满足 $a<b$ 的有序对。函数则是一类特殊关系：每个允许的输入恰好配一个输出。

参考资料

• MIT，Mathematics for Computer Science，集合与关系章节。
• MIT 6.042J Fall 2010，Mathematics for Computer Science 课程讲义。
• 继续阅读：集合、等价关系、函数。