集合、函数与三种映射

集合及其运算

[[ana-set|集合]]是一些对象的搜集，这些对象是它的元素。我们写 x ∈ A 表示「x 在 A 中」，并通过列举构造集合，{1, 2, 3}，或通过性质，{x ∈ ℝ : x² < 2}。当 A 的每个元素都在 B 中时，A 是 B 的[[subset|子集]]（A ⊆ B）——注意这是一个 ∀ 命题：∀x (x ∈ A ⇒ x ∈ B)。两个集合相等恰当 A ⊆ B 且 B ⊆ A，这就是为何集合相等通常用双向包含来证明。

由两个集合我们构成并集 A ∪ B（在至少一个中）、交集 A ∩ B（在两者中）、差集 A \ B（在 A 中但不在 B 中），以及相对某全集的补集 Aᶜ。每个运算都是伪装的连接词：∪ 是「或」，∩ 是「且」，补集是「非」。这就是为何德摩根律——(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ 与 (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ——看起来与上一篇的量词否定规则一模一样。

作为映射的函数

[[function-map|函数]] f : A → B 把定义域 A 的每个元素指派给陪域 B 中恰好一个元素。这里藏着两个要求：每个 x 都必须有输出（全定义），且绝不有两个输出（单值）。当你用公式或法则定义 f 时，检查它是否[[well-defined|良定义]]，就是验证这两个要求确实成立——例如，一条作用在分数上的法则必须对 1/2 与 2/4 给出相同的答案。

值域（像） f(A) = {f(x) : x ∈ A} 是真正被取到的值的集合；它可能小于陪域 B。把定义域、陪域与值域区分清楚——分析学的大部分内容，正是在定义域固定后控制函数的值域（它的有界性、它的上确界）。

单射、满射、双射

[[ana-injection|单射]]（一对一）从不把两个输入合并：f(x) = f(y) ⇒ x = y。[[surjection|满射]]（映上）覆盖一切：∀b ∈ B, ∃a ∈ A 使 f(a) = b——它的值域是整个 B。[[bijection|双射]]同时兼具二者，而恰好是双射拥有双侧逆映射 f⁻¹。双射是我们把「一样大」的想法精确化的方式：当 A 与 B 之间存在某个双射时，它们有相同的[[cardinality|基数]]。这一条定义驱动了整篇下一份指南。

Sorting three maps on the natural numbers N = {0,1,2,...}.

(a) f(n) = 2n               doubling
    Injective? f(n)=f(m) => 2n=2m => n=m.  YES one-to-one.
    Surjective onto N? 3 is never hit (no n with 2n=3).  NO.
    => injection, not surjection. Image = even numbers.

(b) g(n) = floor(n/2)       0,0,1,1,2,2,...
    Injective? g(0)=g(1)=0, so two inputs collapse.  NO.
    Surjective onto N? every k = g(2k).  YES onto.
    => surjection, not injection.

(c) h(n) = n+1 on positive integers {1,2,3,...} -> {2,3,4,...}
    Injective and onto its codomain {2,3,...}.  BIJECTION.
    Inverse h^{-1}(m) = m-1.

Note (a): N is in bijection with a PROPER subset of itself
(the even numbers, via n <-> 2n). For infinite sets this is
allowed and normal -- it is exactly what "infinite" feels like.