Borel 可归约性

归约把原分类问题的每个对象变成目标问题的对象。目标若能区分两个像，原问题也就能区分这两个原对象。因此方向 $E{\le }_{B}F$ 表示 $F$ 至少有能力承载 $E$ 的分类难度。

只有正向蕴涵的映射可能把全部点压到一个类中，完全丢失区别。反向蕴涵要求不同类不能合并；Borel 条件则禁止靠任意选择一个极端不可测的代表来伪装分类已经完成。

整数差关系有一个完整、可算的标签 ​

在 $\mathbb{R}$ 上定义 $xEy⟺x-y\in \mathbb{Z}$。取小数部分

$f$ 在每个 $[n,n+1)$ 上连续，故 Borel。若 $x-y$ 为整数，小数部分相同；若小数部分相同，移项得 $x-y=\lfloor x\rfloor -\lfloor y\rfloor \in \mathbb{Z}$。因此 $f$ 是到相等关系的归约。

例如 $1.2$ 与 $-0.8$ 都映到 $0.2$，确属同一类；$1.2$ 与 $1.3$ 的像不同，类别被保留。映射对点显然不单射，但对类别恰好一一对应。

一个看似相关、实际不够的映射 ​

令 $E$ 为 $\mathbb{R}$ 上的相等关系，$F$ 也为相等关系。常值函数满足 $x=x^{\prime }\Rightarrow f(x)=f(x^{\prime })$，却不能满足逆向条件。因此它是一个保等价的同态，不是归约。若忘掉双向箭头，所有非空分类问题都会被错误地判为同样简单。

最终相同关系越过光滑边界 ​

在 Cantor 空间定义

每个类可数，因为只改动有限前缀；$E_0$ 本身是 $F_{\sigma }$ Borel 关系。但 $E_0$ 不光滑：不存在 Borel 实数标签精确标记所有最终相同类。[1, §9] “每个类可数”不等于“能可测地给每类挑一个唯一编号”。

这个阻碍可用公平独立比特的概率 $P$ 具体证明。记坐标为 $X_0,X_1,\dots$。若 Borel 集 $A$ 在 $E_0$ 下不变，把任意前 $n$ 位改成全零不会改变是否属于 $A$。令

固定前缀的嵌入连续，所以 $A_n$ 是 Borel 集，且 $A$ 恰是 $A_n$ 在尾坐标投影下的原像。因此 $A\in \sigma (X_n,X_{n+1},\dots )$ 对每个 $n$ 都成立。独立比特的乘积律使这个尾事件与前 $n$ 位产生的事件独立公理库独立性Statistical independence从概率表理解独立性，区分两两、相互和条件独立，并用可计算反例澄清零协方差与条件均值的限度。，故它与每个只依赖有限前缀的柱事件 $B$ 都满足 $P(A\cap B)=P(A)P(B)$。

还要把这个等式延伸到 $B=A$。有限柱集代数能在概率中逼近每个 Borel 事件：可逼近的事件族对补集封闭；处理可数并时，先用概率的下连续性把并集截到有限项，再分别逼近这些项，就证明它也对可数并封闭。它因而是包含全部柱集的 $\sigma$-代数。给定 $\epsilon >0$，取有限柱事件 $B$ 使 $P(A\mathrm{△}B)<\epsilon$，便有

令 $\epsilon \downarrow 0$，得到 $P(A)=P(A{)}^2$，即尾事件的概率只能是零或一。这是本例所需的零一律机制。[3, Theorem 2.5.3]

现在假设存在完整实数标签 $f$。实数可数基中每个开集的原像都是上述不变 Borel 事件。对概率为一的原像取它本身，对概率为零的原像取其补集，再作可数交，得到概率为一的集合 $B_0$。其中所有点的标签具有相同的基集成员模式；可数基能分离不同实数，所以这些标签相等，$B_0$ 包含在一个 $E_0$ 类中。但单点概率不超过任意长度前缀的概率 $2^{-n}$，故为零；每个类又可数，因而也为零。这与 $P(B_0)=1$ 矛盾。[1, Lemmas 9.14–9.15]

归约可按函数复合公理库函数复合Function composition · Composition of maps按先 f 后 g 的次序把映射串联为 g∘f。连接：若 $f$ 归约 $E$ 到 $F$，$g$ 归约 $F$ 到 $G$，则 $g\circ f$ Borel 且双向保持等价，所以 $E{\le }_{B}G$。因此，证明 $E_0{\le }_{B}E$ 就能证明 $E$ 不光滑，否则复合会把 $E_0$ 归约到相等关系。

Borel 归约比较可测分类的可能性，不提供运行时间界，也不保证编码可计算。它与复杂性理论中以有限输入和资源界为核心的归约有相似逻辑，却在对象、允许映射和难度尺度上不同。