康托尔定理是否具有自动性？

### 康托尔定理是否具有自动性？ 在数学领域，康托尔定理以及自动结构的研究一直是重要的课题。本文将深入探讨康托尔定理在自动结构中的表现，以及自动结构相关的一些性质。 #### 1. 自动结构与康托尔定理概述 在经典模型理论中，康托尔定理指出任何可数线性序 $(L, ≤)$ 都同构于有理数集的某个子集，即“有理数是通用的”。而在有效模型理论中，关注点转移到了经典模型理论的计算内容上，只考虑递归的线性序 $(L, ≤)$，并询问在合适的有理数编码下，对应的有理数子集 $X$ 是否可判定。当进一步将 $L$、$≤$ 和 $X$ 限制到特定复杂度类 $C$ 时，就进入了复杂度理论模型理论的范畴。 Khoussainov 和 Nerode 发起了对自动结构的研究，这里的复杂度类 $C$ 是正则语言集。自动结构与有限自动机密切相关，有限自动机的丰富理论是理解这一领域的核心。例如，有限自动机的补运算和投影运算表明任何自动结构的一阶理论都是可判定的，这也意味着 Presburger 算术以及下推自动机配置图带传递闭包的一阶理论的可判定性。 研究自动结构的一条重要思路是识别所有自动结构并研究可定义性问题。Delhommé、Goranko 和 Knapik 证明了一大类自动线性序与他们对有理数的规范表示的正则子集是序同构的，并猜想这对所有自动线性序都成立，但本文的定理 5.4 推翻了这一猜想。 #### 2. 相关定义 - **卷积定义**：对于字母表 $\Sigma$，令 $\Sigma_{\perp} = \Sigma \cup \{\perp\}$（其中 $\perp \notin \Sigma$）。两个单词 $u = a_1a_2 \cdots a_n$ 和 $v = b_1b_2 \cdots b_m$ 在 $\Sigma$ 上的卷积 $u \otimes v$ 定义为 $u \otimes v = (a'_1, b'_1)(a'_2, b'_2) \cdots (a'_k, b'_k) \in (\Sigma^2_{\perp})^*$，其中 $k = \max(m, n)$，且 \[ a'_i = \begin{cases} a_i & \text{如果 } i \leq n \\ \perp & \text{否则} \end{cases} \quad b'_i = \begin{cases} b_i & \text{如果 } i \leq m \\ \perp & \text{否则} \end{cases} \] 对于二元关系 $R \subseteq (\Sigma^*)^2$，$R^{\otimes} = \{u \otimes v | (u, v) \in R\}$ 表示 $R$ 的卷积；对于（部分）映射 $f: \Sigma^* \to \Sigma^*$，$f^{\otimes}$ 表示 $f$ 的图像的卷积。 - **自动表示定义**：自动表示是一个元组 $(L, R_0, \cdots, R_n)$，其中 $L \subseteq \Gamma^*$ 且 $R_i \subseteq (\Gamma^*)^2$，使得 $L$ 和 $(R_i)^{\otimes}$ 都是正则语言。如果一个结构存在同构的自动表示，则称该结构是自动的。 - **有理数的自动表示**：从现在起，令 $\Sigma = \{0, 1\}$。对于 $u, v \in \Sigma^*$，定义 $u \prec v$ 当且仅当 $(u \wedge v)0$ 是 $u$ 的前缀或 $(u \wedge v)1$ 是 $v$ 的前缀，其中 $u \wedge v$ 表示 $u$ 和 $v$ 的最大公共前缀。关系 $\prec$ 是传递且反对称的，即 $\sqsubseteq = (\prec \cup =)$ 是 $\Sigma^*$ 上的线性序。由于对于任何 $v \in \Sigma^*$ 都有 $v0 \prec v \prec v1$，它没有端点，且是稠密的，因此 $(\Sigma^*, \sqsubseteq)$ 同构于 $(Q, \leq)$，并且 $\sqsubseteq^{\otimes}$ 是正则的，所以 $(\Sigma^*, \sqsubseteq)$ 是 $(Q, \leq)$ 的一个自动表示。 #### 3. $(\Sigma^*, \sqsubseteq)$ 的自动自同构 在研究 $(\Sigma^*, \sqsubseteq)$ 的自动自同构之前，需要先了解两个辅助性质： - **引理 2.1**：设 $h \in \Sigma^*$，则集合 $h\Sigma^*$ 在 $(\Sigma^*, \sqsubseteq)$ 中是凸的。 - **引理 2.2**：设 $a \in \Sigma^*$ 和 $n \in N$，则集合 $X = a0\Sigma^* \cup \{a\} \cup a10^n\Sigma^*$ 在 $(\Sigma^*, \sqsubseteq)$ 中是凸的。 接下来构造自动自同构 $g_{a,n}: \Sigma^* \to \Sigma^*$，定义如下： \[ g_{a,n}(x) = \begin{cases} a & \text{如果 } x = a10^n \\ a0 & \text{如果 } x = a \\ a10^nz & \text{如果 } x = a10^n1z \\ a01z & \text{如果 } x = a10^n0z \\ a00z & \text{如果 } x = a0z \\ x & \text{否则} \end{cases} \] - **证明 $g_{a,n}$ 是自动自同构**： - **满射性**：$g_{a,n}$ 的支撑集（即 $g_{a,n}(w) \neq w$ 的单词 $w \in \Sigma^*$ 的集合）为 $\{a\} \cup \{a10^n\} \cup a10^n1\Sigma^* \cup a10^n0\Sigma^* \cup a0\Sigma^*$，其像集为 $\{a\} \cup a10^n\Sigma^* \cup \{a0\} \cup a01\Sigma^* \cup a00\Sigma^*$，$g_{a,n}$ 将其支撑集映射到自身，所以是满射的。 - **单射性**：只需检查它在支撑集上的作用是单射的，$\{a10^n, a\}$ 单射地映射到 $\{a, a0\}$，$a10^n1\Sigma^*$ 映射到 $a10^n\Sigma^*$，$a10^n0\Sigma^*$ 映射到 $a01\Sigma