数据与可计算结构 [data-structure]
数据与可计算结构 [data-structure]
$\gdef\spaces#1{~ #1 ~}$ 二叉树意味树的每个结点最多两个子树. 其类型由两个构造器归纳给出 叶结点构造器 换言之, 二叉树可定义为某种满足 $B=1+B^2$ 的 (代数) 结构. 回顾 $6$ 次分圆多项式 $$ \Phi_6(x) \spaces= x^2-x+1 $$ 其复根 $\zeta_6$, $\zeta^{-1}_6$ 是所谓的 $6$ 次本原单位根. $\gdef\N{\mathbf{N}}$
$\gdef\Z{\mathbf{Z}}$ 记 $B$ 是二叉树类型, 则存在一个 “极精确的双射” $B \xrightarrow{\sim} B^7$. 显然并非所有 $\zeta_6$ 满足的等式都能提升到 $B$ 之间的同构, 如 $B^6 \ncong 1$. 自然的问题是, 哪些等式能提升到同构? 这个问题由下面的 Fiore–Leinster 定理 回答. $\gdef\N{\mathbf{N}}$
$\gdef\Z{\mathbf{Z}}$ 设 $f,g_1,g_2 \in \N[x]$, 其中 $f$ 有非零常数项且 $\deg f \ge 2$. 若 $f(x) - x$ 整除非常值的 $g_1-g_2$ (在 $\Z[x]$ 中), 则在 $\N[x]/(x=f(x))$ 中, $g_1(x)=g_2(x)$. 特别的, 取 $f(x)=1+x^2$, Fiore–Leinster 定理 表明, 若在 $\N[x]/(x=1+x^2)$ 中成立 $f(x) = g(x)$, 则存在 “极精确的双射” $f(B) \cong g(B)$. 在 $\N[x]/(x=1+x^2)$ 中可以演绎得到 $x=x^7$ 但无法给出 $1=x^6$. 对于前者 $x^7-x = (x^2-x+1)(x^5+x^4-x^2-x) = 0$. 再看 $x^4 + x^2 + 1 = (x^2 + x + 1)(x^2 - x + 1)$, 这给出 $B^4+B^2+1 \ncong 0$, $B^4+B^2+B+1=B$. 这套想法亦可应用于其他树结构, 如有根平面树, 其每个结点有 $0$, $1$ 或 $2$ 个子结点, 即 $T \cong 1+T+T^2$. 由 Fiore–Leinster 定理, 存在 “极精确的双射” $T \cong T^5$. 栈置换 (stack permutation) 也称作栈混洗 (stack shuffle). 给定一个非空栈 $A$ 和空栈 $B$ 与 $S$, 每次只允许 $(i)$ 弹出 $A$ 并压入 $S$. $(ii)$ 弹出 $S$ 并压入 $B$. 可以想见, 最终 $A$ 的元素一定会全部进入 $B$. 这样的 $B$ 就称为 $A$ 的一个栈置换. 不难发现, $A$ 的所有栈置换其实就是 $A$ 的所有出栈可能. 熟知 $n$ 元素栈共有 $\frac1{n+1}{2n \choose n}$ 种出栈情况. 另一方面, $n$ 个节点能构成 $\frac1{n+1}{2n \choose n}$ 种二叉树, 两者的计算都可以在 Catalan 数的相关条目中找到. 这表明两者作为集合同构, 一个可以考虑的问题是, 如何实现该同构? 即, 具体地写出这个双射. 这方面的 开创性工作 来自 R. F. Hille. 以下三条规则给出 Hille 编码到二叉树的转换过程. 同时不难验证, 任给一个二叉树, 可以通过这三条规则得到其 Hille 编码. 注意到每个树节点的双亲 (parent) 节点是唯一的, 因此回溯操作良定, 一次回溯就是将当前节点改为其双亲. 相应的, 可以据此定义 Hille 编码的解析规则, 用于将这样一段有效的二进制序列转换为构造一颗二叉树的若干操作. 我们使用一种类 BNF 文法来定义这个解析器, 仅供读者理解. 由于我们的讨论不涉及具体元素, 不失一般性, 可以固定栈置换的入栈顺序为 $123\cdots n$. 同时这些数字也是二叉树节点的标签. 影响出栈序列的只有压入和弹出两个操作, 而构建二叉树允许的操作粗看起来要多一些. 因此首先需要通过一些技巧将二叉树构建操作的表示简化. 我们将栈的压入和弹出分别编码为 以下写出三节点二叉树的所有 $5$ 种情况, 以展示这些树的二进制序列如何对应到栈置换.
此处二进制序列按栈弹空为标准, 补充了末尾的零. 这个过程的反向实际上并不平凡, 如果只考虑 $n=3$ 也就是上图的情况, 敏锐的读者可以发现, 这些栈置换其实就是二叉树按节点添加顺序 1 编号后的中序遍历序列 2. 我们接下来将解释其中的不平凡之处, 以及这一巧合发生的 具体条件. 首先是对原始文献的一个观察, Hille 原始文献 当中提出的算法实际上存在错误, 将之改写成 Lean4 语言, 即 只要考虑下面这个例子即可发现, 将一棵二叉树转化为它的 Hille 编码并非是简单的中序遍历. 可以验证, 从 首先容易验证的是, 中序遍历总是能够给出二叉树 $b \in B$ 到栈置换 $s \in S$ 的映射, 而对于每一个栈置换 $s \in S$, 都能够写出唯一的二进制序列, 即栈编码 $c \in C$. 不考虑末尾连续的 $$
\begin{CD}
B @>>> S \\
@VVV @VVV \\
H @>>> C
\end{CD}
$$ 记 $B \to H$ 为 $f$, 根据 Hille 编码 的定义, $f$ 是一个双射. 根据二叉树的性质, $g: B \to S$ 是中序遍历, 前文已经固定栈置换的入栈顺序为 $123\cdots n$, 这样一来就固定了 $B$ 的层序遍历, 因此 $g$ 也是双射. 现在来看 $h: S \to C$, 这显然也是一个双射. 最后, 我们能够从 $h \in H$ 当中恢复出 $c \in C$ 的信息, 只要将 $h$ 序列视为栈编码, 并且忽略空栈的弹出, 这就意味着 $H \to C$ 是满射, 随后利用 $C \to S \to B \to H$, 这样就得到了 $H \cong C$. 现在, Hille 原文所使用的 $\gdef\eqdef{\overset{\scriptscriptstyle\text{def}}{=}}$
$\gdef\spaces#1{~ #1 ~}$ 所有 $n$ 节点二叉树的 Hille 编码构成的集合记为 $H_n$, 所有 $n$ 节点二叉树的栈编码构成的集合记为 $C_n$. 对于 $H_n \cap C_n$ 的大小 $a_n \eqdef |H_n \cap C_n|$, 我们有如下刻画. $$
a_n \spaces= \sum_{k = 0}^{n-1} \sum_{j = 0}^{n-k} \frac{1}{j+1}\binom{n-k-j}j \binom kj \binom{k+j+2}j
$$ 记 $N = n+1$. 等式的证明可以通过分析一个半长为 $N$ 且不包含 记 Catalan 数为 $c_n$, 也即 $H_n$ 或 $C_n$ 的个数. 自然要问 $|H \cap C_n|$ 在全体 $n$ 节点二叉树个数中所占的比例与 $n$ 的关系. 根据 相交数 与 Catalan 数的渐进估计 $a_{n} \sim \frac{\sqrt{2 + r}}{2\sqrt{\pi}n^{3/2}r^{n}}$, $c_n \sim \frac{4^n}{\sqrt\pi n^{3/2}}$ 可以知道 $\lim\limits_{n\to\infty} \frac{a_n}{c_n} = 0$. 并且事实上只要二叉树的节点个数 $n$ 大于 $8$, $H_n$ 与 $C_n$ 相同的部分就会少于整体的一半. $\gdef\spaces#1{~ #1 ~}$ 一个可供探究的问题是, 给定 $n$ 节点二叉树, 询问其 Hille 编码 $H_n$ 有效长度 $\ell(H_n)$ 的范围. 这里的有效不外乎是指去除末尾连续的 任意 $n$ 节点二叉树的 Hille 编码的有效长度满足下面的不等式 $$n \spaces\leqslant \ell_{n} \spaces\leqslant \max(0,2n - 1,3n - 4)$$ 下界 $n$ 的验证是容易的, 构造一棵 $n$ 节点二叉树最少也需要 $n$ 个 注意到为使有效长度最大, 相应的二叉树中的右节点个数和回溯次数要尽可能多.
同时满足这两个要求意味着 $(i)$ 除根节点外至少有一个左结点 1. $(ii)$
该二叉树必有一个位于根节点右侧的节点 2. 如下图所示 由此出发, 我们将剩余的所有 $n-3$ 个节点全部添加到树中唯一的左节点的右侧. 即 下面我们只需算出 $\ell(M)$, 便可得到 $\ell_n$ 的最大值. 不妨直接写出 $h(M)$ 立刻看出 $\ell(M) = 2 + 2(n-3) + (n-2) + 2 = 3n-4$. 如若不然, 这颗二叉树只会形如 否则回溯贡献的长度便不是最大值 $n-2$. 反过来, 从树 $M$ 出发, 也可以验证任何使得节点总数不变的操作都不会增加其 Hille 编码的有效长度. 更进一步, 我们可以断言任何使得节点总数不变的操作都将严格减小其 Hille 编码的有效长度. 换言之, 使得 $\ell(B) = 3n-4$ 的二叉树 $B$ 的结构是唯一的, 即 $M$. 即按照 Hille 编码逐步添加节点的顺序. 如二叉树 $\gdef\spaces#1{~ #1 ~}$
$\gdef\quads#1{\quad #1 \quad}$
$\gdef\eqq{\quads=}$
$\gdef\str#1{{\footnotesize #1}}$ $\gdef\R{\mathbf{R}}$
$\gdef\C{\mathbf{C}}$ $\gdef\spaces#1{~ #1 ~}$
$\gdef\quads#1{\quad #1 \quad}$
$\gdef\eqq{\quads=}$ 我们首先观察朴素的数值微分的计算过程. 待微分函数为 $(x+3)^2$, 此处不妨取 $x=-2$, $h=10^{-5}$, 这一位置的导数 $A$ 近似为 $$
A \quads\approx \frac{f(x+h)-f(x)}h \eqq \frac{(1 + 10^{-5})^2 - 1^2}{10^{-5}} \eqq 2.00001
$$ 并且如果试图得到与预期的 $A=2$ 更接近的结果, 则须将无穷小近似 $h$ 选取为更靠近 $0$ 的数值, 这对于浮点精度有限的计算机来说极为不利. 而朴素的符号微分视表达式为树结构, 通过遍历树并对符合模式的节点应用求导规则 $(uv)' = u'v+uv'$. 即 $$
\begin{aligned}
(x+3)^2
& \spaces\to (x+3)'(x+3) + (x+3)(x+3)' \\
& \spaces\to 1 \cdot (x+3) + (x+3) \cdot 1 \\
& \spaces\to 2x+6
\end{aligned}
$$ 此时再应用 $x=-2$ 得到 $A=2$. 这个做法在结果上可行, 但处理复杂的表达式时, 复合求导的中间过程本身会产生大量新的结点, 使递归遍历的实际时间达到指数级 $\mathcal{O}(2^N)$. 有没有方法可以既避免递归又减少中间结点呢? 我们先看一个涉及复数域的观察. $\gdef\quads#1{\quad #1 \quad}$
$\gdef\spaces#1{~ #1 ~}$ Mathworks 的创始人 Cleve Moler 约 60 年 1 前提出了借用虚数单位 $i$ 的数值微分, 相关文献称为 complex step 微分法 2. 考虑光滑函数 $f(x)$, 其在 $x=a$ 处可表为关于 $X$ 的 Taylor 级数 3 $f(a) + f'(a)(X-a) + \text{etc.}$, 注意 $$
f(a+i h) \spaces= f(a) + i h f'(a) - \frac{h^2}{2!}f''(a) - \frac{ih^3}{3!}f'''(a) + \cdots
$$ 这个其实就是将 Taylor 级数的每一项完全展开, 在 后续 的计算中也会继续用到. 如此便有
$$
\frac{\partial f}{\partial x} \spaces= \frac{\Im f(x+ih)}{h} + \mathcal{O}(h^2) \quads\implies
\frac{\partial f}{\partial x} \quads\approx \frac{\Im f(x+ih)}{h}
$$ 这个方法最初被设计用于处理数值微分问题, 但稍加思考就能发现, 该过程也适用于符号微分. 与前一个问题所改进的结果的精度不同, 用于 符号微分 时, 所取得的优势是更精简的中间表达式和非递归的计算过程. 即 1967 年. 不过这个名字要等到 1998 年, William Squire 和 George Trapp 才正式提出. 按方法的内容来说, “complex step 微分” 可以翻译为 “复步微分”. $\gdef\C{\mathbf{C}}$
$\gdef\quads#1{\quad #1 \quad}$
$\gdef\eqq{\quads=}$ 选取同样的 $h=10^{-5}$, 以下计算表明 Moler 的方法 相比 此处 基于有限差分的数值微分方法能够很好的避免精度损失. $$
\frac{\Im(1 + 10^{-5}i)^{2}}{10^{-5}} \eqq \frac{\Im(\square + 2 \times 10^{- 5}i)}{10^{- 5}} \eqq 2
$$ 实际上此处 $h$ 的选取, 只要其非零, 从而带有 $i$ 的项不消失, 就不会影响到最终的结果. 换言之, 这个方法从根本上来说, 是无关于 $h \in \R\smallsetminus\{0\}$ 和 $i$ 的, 只是在数值计算时借由复数算术和复函数值可以免去一些幂零结构的讨论. 一旦意识到这一点, 我们便可以将 复步微分法 的 $$ \frac{\partial f}{\partial x} \quads\approx \frac{\Im f(x+ih)}{h} $$ 中的近似 “$\approx$” 修正为严格等于 “$=$”, 这只需要将 $\{z \in \C : z^2 = -1\}$ 替换为 $D = \{x \in R : x^2 = 0\}$, 问题就来到了如何构造这样的 $R$ 使得 $D$ 中有非零的元素, 这样的结构实际上会 动摇 经典逻辑中对于排中律的看法. $\gdef\R{\mathbf{R}}$
$\gdef\C{\mathbf{C}}$ 一种通俗的讲法是, 认为对偶数 $R[x]/(x^2)$ 可以作为复数 $\R[x]/(x^2+1)$ 的类比. 如果有读者能轻率地暂时忽略 $R[x]/(x^2)$ 这种结构的存在性, 或者说接受了下面的 $d$ 的定义 $$ \exists ~ d \in R\smallsetminus\{0\}, ~ d^2 = 0 $$ 不能接受也很正常, 因为这轻易就会导致某个经典逻辑中的 矛盾. 相比之下满足 $x^2 = -1$ 的 $x$ 对于大众而言要更容易接受的多, 甚至对于三次方程是 必须品. 为此我们需要下面的准备工作. $\gdef\spaces#1{~ #1 ~}$
$\gdef\R{\mathbf{R}}$ 首先需要强调的是, 这个公理所涉及到的结构的有效性全都依赖于 意象理论, 而相关基础的严格性保证基本上在 1970 年之前就已经由 William Lawvere 完工. 记 $\mathcal{E}$ 是光滑空间之间的光滑映射构成的范畴, 同时假定 $\mathcal{E}$ 还是笛卡尔闭范畴, 也就是 $\mathcal{E}$ 中的箭头对笛卡尔积封闭. 我们可以从 $\mathcal{E}$ 中选出一条几何直线 $R$, 通过指定 $R$ 上两点 $0$ 和 $1$ 之间的距离作为单位长度来确定其他线段的长度. 发挥一些古希腊精神, 线段的移动可以给出 $R$ 上的加法, 尺规作图所构造的 相似三角形 能给出 $R$ 上的乘法 $\gamma = \alpha\beta$. 因此 $R$ 带有交换环结构, 并且允许经典数学中的对象实数环 $\R$ 成为 $R$ 的模型, 注意这里我们只能考虑 $\R$ 作为环的部分, 因为 $R$ 中存在着幂零元. Kock–Lawvere 公理说的是, 对任意映射 $f: D \to R$, 存在唯一的 $a,b \in R$, 使得 $$
f(\epsilon) \spaces= a + b \epsilon, \quad \forall \epsilon \in D
$$ 将这里的 $a$ 换成 $f(0)$, 并完全使用量词叙述, 则是 $$
\forall ~ f \in R^D, ~ \exists! ~ b ~ \text{s.t.} ~ \forall ~ d \in D \quad (f(d) = f(0) + b d)
$$ 如果说这个公理的形式还不足以暗示它的目的, 那么下面这个推论就完全能做到了. $\gdef\quads#1{\quad #1 \quad}$
$\gdef\spaces#1{~ #1 ~}$ 对任意函数 $f:R \rightarrow R$, 存在唯一的函数 $f':R \rightarrow R$ 满足 $$
f(x + \varepsilon) \spaces= f(x) + f'(x)\varepsilon,\quad \forall ~ x \in R, ~ \forall ~ \varepsilon \in D
$$ 这个通常作为 Kock–Lawvere 公理 的推论出现, 不过从 $\mathcal{E}$ 的定义来看, 这才是整套框架真正的目的之一. 即, 为全体函数恢复牛顿时期 “幂零无穷小量” 计算上的直观, 而不导致矛盾.
Axiom is incompatible with the law of excluded middle.
Either the one or the other has to leave the scene.
In Part I of this book, the law of excluded middle has to leave,
being incompatible with the natural synthetic reasoning
on smooth geometry to be presented here.
In the terms which the logicians use, this means that
the logic employed is ‘constructive’ or ‘intuitionistic’.
We prefer to think of it just as ‘that reasoning
which can be carried out in all sufficiently good
cartesian closed categories’. — Anders Kock, Synthetic Differential Geometry七树合一定理 [seven-trees-in-one]
Definition 1. 二叉树类型 [binary-tree]
inductive Tree α
| leaf : Tree α
| node : α → Tree α → Tree α → Tree α
leaf
用于构造出一棵空树, 空树作为某个结点的所有子结点时, 该结点正是叶结点. 相应的, 二叉树的值存储在非叶结点中. 每个 (非空, 无标记) 二叉树类型的值要么是一个单结点 $\{\text{pt}\} = 1$, 要么等价于二叉树的有序配对 $B \times B = B^2$. 即 $B \xrightarrow{\sim} \{\text{pt}\} \sqcup B^2$.Theorem 2. Blass–Lawvere 定理 [blass-lawvere]
Theorem. Fiore–Leinster [fiore-leinster]
栈置换–二叉树同构 [stack-tree-isomorphism]
Definition 1. 栈置换 [stack-permutation]
Definition 2. Hille 编码 [hille-encode]
1
表示添加当前树节点的左子树. 例如 111
表示的树为 (⋅ (⋅ (⋅)))
.01
表示添加当前树节点的右子树. 例如 10101
表示的树为 (⋅ _ (⋅ _ (⋅)))
.01
前的 $k$ 个 0
, 这些 0
用于表示将当前树节点回溯到前 $k$ 层. 例如 11001
表示的树为 (⋅ (⋅) (⋅))
.1
和 0
, 并将栈置换对应的二进制序列称为栈编码. 对应的, 以 Hille 编码 刻画二叉树的构建.Example 3. $n=3$ [stack-permutation-000A]
def encode : Tree → String
| .node l r => "1" ++ encode l ++ encode r
| _ => "0"
110100100
这个编码出发, 无法直接恢复原本的
, 其正确的 Hille 编码应该为 1101000100
. 但是另一方面, 如果将序列 110100100
解释为栈的压入弹出操作, 即栈编码, 则可以得到正确的栈置换 2314
. 这就意味着, 当二叉树的节点个数 $n > 3$ 时, 存在二叉树使得其栈编码与 Hille 编码不同. 回忆二叉树和栈置换之间的双射关系, 这表明必然存在一套手续允许我们在两者之间互相转换, 下面我们将构造性地给出这个结果. 见 栈编码与 Hille 编码的等价性. 随后通过 相交率 解释, 为何中序遍历在 $n$ 不大情况下能够频繁得到正确的 Hille 编码.Proposition 4. 栈编码与 Hille 编码的等价性 [stack-permutation-000B]
0
, 当栈编码 $c$ 与二叉树 $b$ 的 Hille 编码 $h \in H$ 相同时, 对 $B$ 直接进行中序遍历便能得出正确的 Hille 编码.Proof. [stack-permutation-000C]
encode
算法就是 $h \circ g: B \to C$, 而预期的正确实现则是 $f$, 因此两者在结果上相差一个同构.Proposition 5. 相交数 [stack-permutation-000D]
UUDD
子序列的 Dyck 路径得到. 同时这也是从 $(0,0)$ 到 $(N,N)$ 不越过对角线且允许步长 $(1,k), (k,1), k \geqslant 1$ 的格路径的个数. 或者更简单地说, 是长度为 $N$ 的斜 Motzkin 路径的个数.Corollary 6. 相交率 [stack-permutation-000E]
Exegesis 7. 有效长度的上下界 [stack-permutation-000F]
0
. 我们将对此问题给出确切的回答.1
.
由于 此处 的讨论, 我们只需要验证 $n \geqslant 3$ 时 Hille 编码的有效长度至多是 $3n - 4$.Proof. [stack-permutation-000G]
1010101
$\cdots$, 其长度为 $2n - 1$.1101000100
按添加顺序对节点编号, 然后做中序遍历得到的是 2314
.综合微分法 [synthetic-differential]
Exegesis 1. 数值微分的误差 [synthetic-differential-000A]
Exegesis 2. 复步微分法 [complex-step]
Exegesis 3. 误差修正 [synthetic-differential-000C]
Definition 4. 对偶数 [dual-number]
Axiom 4.1. Kock–Lawvere [kock-lawvere]
Corollary. 所有函数都光滑 [kock-lawvere-000A]
无论是单纯接受这个 公理 还是认可该公理存在的舞台 $\mathcal{E}$, 其实都会导致完全相同的结果, 那就是 $\mathcal{E}$ 当中一般函数的性质发生了变化, 让所有的函数都变得光滑. 与之相对的, 这样的好性质所要求的代价是, $\mathcal{E}$ 当中不能使用经典逻辑中的选择公理、排中律、反证法等命题.
$\gdef\quads#1{\quad #1 \quad}$
$\gdef\str#1{{\footnotesize #1}}$
$\gdef\C{\mathbf{C}}$
$\gdef\spaces#1{~ #1 ~}$ 这样一来, 我们所说的 “将近似修正为严格等于” 就可以精确表示为 $$ \frac{\partial f}{\partial x} \quads= f(x+\varepsilon) ~ \str{中} ~ \varepsilon ~ \str{项的系数} $$ 复步微分法 的来源是完全解析的, 但其得到的微分方法却能代数地刻画. 正如我们可以考虑复数的 $z = a+b\sqrt{-1} \in \C$ 矩阵表示 $$
A \spaces= \begin{pmatrix}
a & -b \\
b & ~~~a \\
\end{pmatrix}
,\quad
\det A \spaces= (a+b\sqrt{-1})(a-b\sqrt{-1})
$$ 我们也可以构造 对偶数 $a + b \varepsilon \in R$ 的矩阵表示, 并自动得到微分运算的加法和乘法规则, 这可以被简单地视为 Moler 方法的矩阵版本. $$
A \spaces= \begin{pmatrix}
a & a' \\
0 & a \\
\end{pmatrix}
,\quad
\det A \spaces= (a+b\varepsilon)(a-b\varepsilon)
$$ $\gdef\Mat{\operatorname{Mat}}$
$\gdef\d{\operatorname{d}}$
$\gdef\Z{\mathbf{Z}}$
$\gdef\spaces#1{~ #1 ~}$ 设 $u, v \in R^R$, $n \in \Z$. 记 $A(u, u') = (\begin{smallmatrix} u & u' \\ 0 & u \end{smallmatrix})$. 从矩阵运算中立刻得到 对于 $e^{A(u,u')}$, 注意 $A(u, u') = A(u, 0) + A(0, u')$, 这里 $(A(0, u))^2 = 0$. 同样可以计算得到 $e^{A(u,u')} = A(e^u, 0) \cdot A(1, u') = A(e^u, e^u u')$. 而对于 $\log A(u,u')$ 我们直接展开为 $\sum_{k \ge 1}\frac{(-1)^{k+1}}{k} \cdot (A-1)^k$ 即可 验证. $\gdef\Mat{\operatorname{Mat}}$
$\gdef\spaces#1{~ #1 ~}$
$\gdef\d{\operatorname{d}}$
$\gdef\eqdef{\overset{\scriptscriptstyle\text{def}}{=}}$ 与 $\Mat_{2 \times 2}(R^R)$ 上的 运算 不同, 复合运算是只位于 $R^R$ 上的, 或者说 $\Mat_{2 \times 2}(R^R)$ 上并没有周知的复合运算. 为了自然地给出 $A: J^1(R, R) \to \Mat_{2 \times 2}(R^R)$ 上的复合, 这里 $J^1$ 是一阶 射流丛. 记 $\square(x)$ 为 $\square_x $, $A(u)$ 为 $A(u,u')$, 考虑显式应用的 $A(u)$, 即 $$
A(u)_x \spaces\eqdef \begin{pmatrix} u_x & u'_x \\ 0 & u_x \end{pmatrix} \spaces\in \Mat_{2 \times 2}(R), \quad x \in R
$$ 对于 $u: Y \to Z$, $v: X \to Y$. $A$ 上的复合 $A(u) \circ A(v)$ 可定义为 $A(u)_{v_x}$, $(v_x, v'_x) \in A(v)_x$. 我们来验证 $A(u) \circ A(v) = A(u \circ v)$. $$
\begin{aligned}
A(u)_{v_x}
&\spaces= \Big(u \cdot \frac{\partial A}{\partial u} + \frac{\d u}{\d x} \cdot \frac{\partial A}{\partial u'}\Big)\Big|_{v_x} \\
&\spaces= u(v_x) \cdot \frac{\partial A}{\partial u} + \frac{\d u(v_x)}{\d v_x} \frac{\d v_x}{\d x} \cdot \frac{\partial A}{\partial u'} \\
&\spaces= A(u(v(x)), u'(v(x))v'(x)) \\
\end{aligned}
$$Exegesis 4.2. 矩阵表示 [synthetic-differential-000D]
Example 4.3. 导出微分运算 [synthetic-differential-000B]
Exegesis 4.4. 链式法则 [synthetic-differential-000E]