PrSS的良序性 - 版本历史

2026年2月21日 (六) 14:41 Tabelog

2026-02-21T14:41:43Z

0100000000a7：0100000000a7移动页面PrSS 的良序性至PrSS的良序性：恢复

2026-02-20T09:37:33Z

←上一版本	2026年2月20日 (五) 17:37的版本
（没有差异）

Tabelog：Tabelog移动页面PrSS的良序性至PrSS 的良序性，不留重定向

2025-08-31T03:03:33Z

Tabelog移动页面PrSS的良序性至PrSS 的良序性，不留重定向

←上一版本	2025年8月31日 (日) 11:03的版本
（没有差异）

2025年8月31日 (日) 03:03 Tabelog

2025-08-31T03:03:10Z

←上一版本		2025年8月31日 (日) 11:03的版本
第1行：		第1行：
	== PrSS 没有无穷降链 ==		=== PrSS 没有无穷降链 ===

	首先我们将 [[初等序列系统\|PrSS]] 的每个合法表达式 <math>S</math> 对应于一个不超过 <math>\varepsilon_0</math> 的[[序数]] <math>F(S)</math>。然后我们证明 PrSS 表达式展开时，其对应的序数严格递减。于是就可以依据 <math>\varepsilon_0</math> 的[[良序\|良序性]]说明 PrSS 没有无穷降链。		首先我们将 [[初等序列系统\|PrSS]] 的每个合法表达式 <math>S</math> 对应于一个不超过 <math>\varepsilon_0</math> 的[[序数]] <math>F(S)</math>。然后我们证明 PrSS 表达式展开时，其对应的序数严格递减。于是就可以依据 <math>\varepsilon_0</math> 的[[良序\|良序性]]说明 PrSS 没有无穷降链。

第41行：		第40行：
	至此，PrSS 已经是一个合格的序数记号了。但我们不止于此，我们要给出判断 PrSS 表达式是否标准的方法，并证明 PrSS 标准式的序是字典序。		至此，PrSS 已经是一个合格的序数记号了。但我们不止于此，我们要给出判断 PrSS 表达式是否标准的方法，并证明 PrSS 标准式的序是字典序。

	== PrSS 标准表达式 ==		=== PrSS 标准表达式 ===

	PrSS 的极限基本列是 <math>(),(0),(0,1),(0,1,2),\cdots</math>。PrSS 的极限基本列的第 <math>n</math> 项是 <math>L_n=(0,1,2,\cdots,n-1)</math>。		PrSS 的极限基本列是 <math>(),(0),(0,1),(0,1,2),\cdots</math>。PrSS 的极限基本列的第 <math>n</math> 项是 <math>L_n=(0,1,2,\cdots,n-1)</math>。

第113行：		第111行：
	在第一节证明 PrSS 没有无穷降链时，我们使用了序数的良序性。如果想不依赖序数就证明 PrSS 没有无穷降链，参见知乎用户 www620 的证明<ref>https://zhuanlan.zhihu.com/p/13871622947</ref>。这个证明依赖本节的两个结论：PrSS 表达式展开时字典序变小、PrSS 标准式都是规范式。注意到本节的两个结论不依赖第一节，所以没有循环论证的问题。		在第一节证明 PrSS 没有无穷降链时，我们使用了序数的良序性。如果想不依赖序数就证明 PrSS 没有无穷降链，参见知乎用户 www620 的证明<ref>https://zhuanlan.zhihu.com/p/13871622947</ref>。这个证明依赖本节的两个结论：PrSS 表达式展开时字典序变小、PrSS 标准式都是规范式。注意到本节的两个结论不依赖第一节，所以没有循环论证的问题。

	== PrSS 标准式集的良序性 ==		=== PrSS 标准式集的良序性 ===

	上一节我们证明了 PrSS 合法表达式在展开过程中字典序变小，并由此得到了 PrSS 标准式的必要条件。这一节，我们证明字典序变小反过来也意味着可以展开得到，并由此得到 PrSS 标准式的充分条件。		上一节我们证明了 PrSS 合法表达式在展开过程中字典序变小，并由此得到了 PrSS 标准式的必要条件。这一节，我们证明字典序变小反过来也意味着可以展开得到，并由此得到 PrSS 标准式的充分条件。

第160行：		第157行：
	但我们不止于此。下一节，我们要证明 PrSS 标准式集[[良序\|序同构]]于 <math>\varepsilon_0</math>。		但我们不止于此。下一节，我们要证明 PrSS 标准式集[[良序\|序同构]]于 <math>\varepsilon_0</math>。

	== PrSS 标准式集的序型 ==		=== PrSS 标准式集的序型 ===

	为了证明 PrSS 标准式集[[良序\|序同构]]于 <math>\varepsilon_0</math>，我们要证明第一节定义的保序映射 <math>F</math> 是 PrSS 标准式集和 <math>\varepsilon_0</math> 之间的双射，结合 PrSS 标准式集的全序性，就能说明 <math>F</math> 是 PrSS 标准式集和 <math>\varepsilon_0</math> 之间的序同构。		为了证明 PrSS 标准式集[[良序\|序同构]]于 <math>\varepsilon_0</math>，我们要证明第一节定义的保序映射 <math>F</math> 是 PrSS 标准式集和 <math>\varepsilon_0</math> 之间的双射，结合 PrSS 标准式集的全序性，就能说明 <math>F</math> 是 PrSS 标准式集和 <math>\varepsilon_0</math> 之间的序同构。

第221行：		第217行：
	'''定理的证明''' 由引理1~4，<math>F</math>有逆映射<math>Seq</math>，且<math>Seq</math>保序。于是<math>Seq</math>(和其逆<math>F</math>)是 PrSS 标准式集与<math>\varepsilon_0</math>之间的序同构。		'''定理的证明''' 由引理1~4，<math>F</math>有逆映射<math>Seq</math>，且<math>Seq</math>保序。于是<math>Seq</math>(和其逆<math>F</math>)是 PrSS 标准式集与<math>\varepsilon_0</math>之间的序同构。

	证毕。		证毕。<references />
			[[分类:集合论相关]]
	[[分类:证明]]

Apocalypse：/* PrSS 标准式集的序型 */

2025-08-15T08:45:29Z

PrSS 标准式集的序型

@@ 第164行： / 第164行： @@
 为了证明 PrSS 标准式集[[良序|序同构]]于 <math>\varepsilon_0</math>，我们要证明第一节定义的保序映射 <math>F</math> 是 PrSS 标准式集和 <math>\varepsilon_0</math> 之间的双射，结合 PrSS 标准式集的全序性，就能说明 <math>F</math> 是 PrSS 标准式集和 <math>\varepsilon_0</math> 之间的序同构。
-【未完】
+'''定理'''
 [[分类:证明]]

Zhy137036：撤销Zhy137036（讨论）的修订版本1885

2025-08-15T05:38:36Z

撤销Zhy137036（讨论）的修订版本1885

←上一版本		2025年8月15日 (五) 13:38的版本
第49行：		第49行：
	一个 PrSS 表达式 <math>S</math> 是 '''PrSS 标准表达式'''（简称 '''PrSS 标准式'''），当且仅当存在 <math>n</math> 使得极限基本列的第 <math>n</math> 项 <math>L_n</math> 可以经过若干次展开得到 <math>S</math>。		一个 PrSS 表达式 <math>S</math> 是 '''PrSS 标准表达式'''（简称 '''PrSS 标准式'''），当且仅当存在 <math>n</math> 使得极限基本列的第 <math>n</math> 项 <math>L_n</math> 可以经过若干次展开得到 <math>S</math>。

	简单地说，标准式就是能从极限基本列展开得到的表达式。对于大部分的序数记号，存在合法但不标准的表达式。这些不标准的合法表达式往往也能对应于一个序数（例如上一节的映射 <math>F</math> 不要求表达式是标准的），但这将导致不同的合法表达式对应于同一个序数。对应于同一个序数的不同合法表达式，例如 <math>(0,1)</math> 和 <math>(0,0,1)</math> ~~都是对于于~~ <math>\omega</math> 的表达式，彼此之间无法展开成对方。这意味着合法表达式集不是全序，更不是良序。不同的标准表达式则不会对应于同一个序数，标准表达式集确实是良序的。		简单地说，标准式就是能从极限基本列展开得到的表达式。对于大部分的序数记号，存在合法但不标准的表达式。这些不标准的合法表达式往往也能对应于一个序数（例如上一节的映射 <math>F</math> 不要求表达式是标准的），但这将导致不同的合法表达式对应于同一个序数。对应于同一个序数的不同合法表达式，例如 <math>(0,1)</math> 和 <math>(0,0,1)</math> 都是对应于 <math>\omega</math> 的表达式，彼此之间无法展开成对方。这意味着合法表达式集不是全序，更不是良序。不同的标准表达式则不会对应于同一个序数，标准表达式集确实是良序的。

	在这一节，我们将给出 PrSS 标准式的必要条件。该条件实际上也是充分的，不过充分性将在下一节证明。在此之前，我们先来定义字典序的概念。		在这一节，我们将给出 PrSS 标准式的必要条件。该条件实际上也是充分的，不过充分性将在下一节证明。在此之前，我们先来定义字典序的概念。

	'''定义'''（字典序）		'''定义'''（字典序）

	设 <math>A</math> 是一个全序集，其上的全序是 <math>\le</math>。考虑两个数列 <math>S=(a_1,a_2,\cdots,a_n)</math> 和 <math>T=(b_1,b_2,\cdots,b_m)</math>，其中 <math>a_1,a_2,\cdots,a_n,b_1,b_2,\cdots,b_m\in A</math>。在字典序下，<math>S\le T</math> 当且仅当以下两条中的一条成立：		设 <math>A</math> 是一个全序集，其上的全序是 <math>\le</math>。考虑两个数列 <math>S=(a_1,a_2,\cdots,a_n)</math> 和 <math>T=(b_1,b_2,\cdots,b_m)</math>，其中 <math>a_1,a_2,\cdots,a_n,b_1,b_2,\cdots,b_m\in A</math>。在字典序下，<math>S\le T</math> 当且仅当以下两条中的一条成立：
	* 存在 <math>0\le k<\min\{n,m\}</math> 使得对任意 <math>i\in\{1,2,\cdots,k\}</math> 有 <math>a_i=b_i</math>，但 <math>a_{k+1}<b_{k+1}</math>；		* 存在 <math>0\le k<\min\{n,m\}</math> 使得对任意 <math>i\in\{1,2,\cdots,k\}</math> 有 <math>a_i=b_i</math>，但 <math>a_{k+1}<b_{k+1}</math>；
第82行：		第83行：
	对表达式 <math>S=(a_1,a_2,\cdots,a_n)</math> 的长度 <math>n</math> 归纳定义。		对表达式 <math>S=(a_1,a_2,\cdots,a_n)</math> 的长度 <math>n</math> 归纳定义。

	<math>n=0</math> 时，<math>S=()</math> 是 PrSS 规范式。		若 <math>n=0</math>，则 <math>S=()</math> 是 PrSS 规范式。

	<math>n>0</math> 且 <math>S</math> 中仅有首项是零，则 <math>S</math> 是 PrSS 规范式当且仅当 <math>(a_2-1,a_3-1,\cdots,a_n-1</math> 是 PrSS 规范式。		若 <math>n>0</math> 且 <math>S</math> 中仅有首项是零，则 <math>S</math> 是 PrSS 规范式当且仅当 <math>(a_2-1,a_3-1,\cdots,a_n-1)</math> 是 PrSS 规范式。

	<math>n>0</math> 且 <math>S</math> 中有 <math>r>1</math> 项是零，设 <math>a_{k_1}=a_{k_2}=\cdots=a_{k_r}=0</math>，其中 <math>1=k_1<k_2<\cdots<k_r<k_{r+1}=n+1</math>，令 <math>S_i=(a_{k_i},a_{k_i+1},\cdots,a_{k_{i+1}-1})</math>。则 <math>S</math> 是 PrSS 规范式当且仅当 <math>S_1,S_2,\cdots,S_r</math> 都是 PrSS 规范式且按字典序 <math>S_1\ge S_2\ge\cdots\ge S_r</math>。		若 <math>n>0</math> 且 <math>S</math> 中有 <math>r>1</math> 项是零，设 <math>a_{k_1}=a_{k_2}=\cdots=a_{k_r}=0</math>，其中 <math>1=k_1<k_2<\cdots<k_r<k_{r+1}=n+1</math>，令 <math>S_i=(a_{k_i},a_{k_i+1},\cdots,a_{k_{i+1}-1})</math>。则 <math>S</math> 是 PrSS 规范式当且仅当 <math>S_1,S_2,\cdots,S_r</math> 都是 PrSS 规范式且按字典序 <math>S_1\ge S_2\ge\cdots\ge S_r</math>。

	PrSS 规范式是本文临时定义的，并不是通用术语。PrSS 规范式实际上等价于 PrSS 标准式。		PrSS 规范式是本文临时定义的，并不是通用术语。PrSS 规范式实际上等价于 PrSS 标准式。
第124行：		第125行：
	'''证明'''		'''证明'''

	定义一种特殊的展开函数 <math>E</math>：设 PrSS 表达式 <math>U</math> ~~的展开式为~~ <math>U_0,U_1,U_2,\cdots</math>。若存在 <math>i</math> 使得按字典序 <math>U_i\ge S</math>，则取 <math>k=\min\{i\mid U_i\ge S\}</math> 并定义 <math>E(U)=U_k</math>。如果对任意 <math>i</math> 都有按字典序 <math>U_i<S</math>，则取 <math>E(U)=U</math>。如果 <math>U</math> 是后缀表达式，则取 <math>U_0=U_1=\cdots</math> 为 <math>U</math> 的前驱表达式。特殊地，如果 <math>U</math> 是零表达式，则 <math>E(U)=U</math>。		定义一种特殊的展开函数 <math>E</math>：设 PrSS 表达式 <math>U</math> 的基本列为 <math>U_0,U_1,U_2,\cdots</math>。若存在 <math>i</math> 使得按字典序 <math>U_i\ge S</math>，则取 <math>k=\min\{i\mid U_i\ge S\}</math> 并定义 <math>E(U)=U_k</math>。如果对任意 <math>i</math> 都有按字典序 <math>U_i<S</math>，则取 <math>E(U)=U</math>。如果 <math>U</math> 是后缀表达式，则取 <math>U_0=U_1=\cdots</math> 为 <math>U</math> 的前驱表达式。特殊地，如果 <math>U</math> 是零表达式，则 <math>E(U)=U</math>。

	从 <math>E</math> 的定义不难看出，如果按字典序 <math>U\ge S</math>，则按字典序 <math>E(U)\ge S</math>。令 <math>T_0=T</math>，<math>T_{n+1}=E(T_n)</math>。因为按字典序 <math>T>S</math>，所以对任意 <math>i</math> 都有按字典序 <math>T_i\ge S</math>。		从 <math>E</math> 的定义不难看出，如果按字典序 <math>U\ge S</math>，则按字典序 <math>E(U)\ge S</math>。令 <math>T_0=T</math>，<math>T_{n+1}=E(T_n)</math>。因为按字典序 <math>T>S</math>，所以对任意 <math>i</math> 都有按字典序 <math>T_i\ge S</math>。
第130行：		第131行：
	而第一节已经证明 PrSS 不存在无穷降链，所以存在 <math>k</math> 使得 <math>T_k=T_{k+1}=\cdots</math>。讨论一下不难得到，这时有两种可能：		而第一节已经证明 PrSS 不存在无穷降链，所以存在 <math>k</math> 使得 <math>T_k=T_{k+1}=\cdots</math>。讨论一下不难得到，这时有两种可能：

	# <math>T_k=S</math>。		* <math>T_k=S</math>。
	# <math>T_k>S</math>，但 <math>T_k</math> ~~的展开式都按字典序小于~~ <math>S</math>。进一步讨论还可以看出，这种情况下 <math>T_k</math> 一定是极限表达式。		* 按字典序 <math>T_k>S</math>，但 <math>T_k</math> 的基本列的每一项都按字典序小于 <math>S</math>。进一步讨论还可以看出，这种情况下 <math>T_k</math> 一定是极限表达式。

	~~前一种情况命题已经成立，我们只需要用反证法证明后一种情况不存在即可。~~		前一种情况命题已经成立，只需要用反证法证明后一种情况不存在即可。

	若存在，设 <math>T_k</math> 的好部是 <math>G</math>，坏部是 <math>B</math>，末项是 <math>L</math>，坏根是 <math>L-1</math>，则 <math>T_k=(G,B,L)</math>，而 <math>T_k</math> 的展开式形如 <math>(G,B,B,\cdots)</math>。		若存在，设 <math>T_k</math> 的好部是 <math>G</math>，坏部是 <math>B</math>，末项是 <math>L</math>，坏根是 <math>L-1</math>，则 <math>T_k=(G,B,L)</math>，而 <math>T_k</math> 的展开式形如 <math>(G,B,B,\cdots)</math>。
第152行：		第153行：

	设 <math>S</math> 是 PrSS 规范式。存在 <math>n</math> 使得 <math>T=(0,1,2,\cdots,n-1)</math> 按字典序大于 <math>S</math>。根据上一个定理，<math>T</math> 可以展开成 <math>S</math>，所以 <math>S</math> 是 PrSS 标准式。		设 <math>S</math> 是 PrSS 规范式。存在 <math>n</math> 使得 <math>T=(0,1,2,\cdots,n-1)</math> 按字典序大于 <math>S</math>。根据上一个定理，<math>T</math> 可以展开成 <math>S</math>，所以 <math>S</math> 是 PrSS 标准式。

			证毕。

	至此，我们证明了 PrSS 没有无穷降链、PrSS 标准式集的序是字典序，而字典序是全序，所以 PrSS 标准式集上的序是良序。		至此，我们证明了 PrSS 没有无穷降链、PrSS 标准式集的序是字典序，而字典序是全序，所以 PrSS 标准式集上的序是良序。

2025年8月15日 (五) 05:36 Zhy137036

2025-08-15T05:36:33Z

←上一版本		2025年8月15日 (五) 13:36的版本
第49行：		第49行：
	一个 PrSS 表达式 <math>S</math> 是 '''PrSS 标准表达式'''（简称 '''PrSS 标准式'''），当且仅当存在 <math>n</math> 使得极限基本列的第 <math>n</math> 项 <math>L_n</math> 可以经过若干次展开得到 <math>S</math>。		一个 PrSS 表达式 <math>S</math> 是 '''PrSS 标准表达式'''（简称 '''PrSS 标准式'''），当且仅当存在 <math>n</math> 使得极限基本列的第 <math>n</math> 项 <math>L_n</math> 可以经过若干次展开得到 <math>S</math>。

	简单地说，标准式就是能从极限基本列展开得到的表达式。对于大部分的序数记号，存在合法但不标准的表达式。这些不标准的合法表达式往往也能对应于一个序数（例如上一节的映射 <math>F</math> 不要求表达式是标准的），但这将导致不同的合法表达式对应于同一个序数。对应于同一个序数的不同合法表达式，例如 <math>(0,1)</math> 和 <math>(0,0,1)</math> ~~都是对应于~~ <math>\omega</math> 的表达式，彼此之间无法展开成对方。这意味着合法表达式集不是全序，更不是良序。不同的标准表达式则不会对应于同一个序数，标准表达式集确实是良序的。		简单地说，标准式就是能从极限基本列展开得到的表达式。对于大部分的序数记号，存在合法但不标准的表达式。这些不标准的合法表达式往往也能对应于一个序数（例如上一节的映射 <math>F</math> 不要求表达式是标准的），但这将导致不同的合法表达式对应于同一个序数。对应于同一个序数的不同合法表达式，例如 <math>(0,1)</math> 和 <math>(0,0,1)</math> 都是对于于 <math>\omega</math> 的表达式，彼此之间无法展开成对方。这意味着合法表达式集不是全序，更不是良序。不同的标准表达式则不会对应于同一个序数，标准表达式集确实是良序的。

	在这一节，我们将给出 PrSS 标准式的必要条件。该条件实际上也是充分的，不过充分性将在下一节证明。在此之前，我们先来定义字典序的概念。		在这一节，我们将给出 PrSS 标准式的必要条件。该条件实际上也是充分的，不过充分性将在下一节证明。在此之前，我们先来定义字典序的概念。

	'''定义'''（字典序）		'''定义'''（字典序）

	设 <math>A</math> 是一个全序集，其上的全序是 <math>\le</math>。考虑两个数列 <math>S=(a_1,a_2,\cdots,a_n)</math> 和 <math>T=(b_1,b_2,\cdots,b_m)</math>，其中 <math>a_1,a_2,\cdots,a_n,b_1,b_2,\cdots,b_m\in A</math>。在字典序下，<math>S\le T</math> 当且仅当以下两条中的一条成立：		设 <math>A</math> 是一个全序集，其上的全序是 <math>\le</math>。考虑两个数列 <math>S=(a_1,a_2,\cdots,a_n)</math> 和 <math>T=(b_1,b_2,\cdots,b_m)</math>，其中 <math>a_1,a_2,\cdots,a_n,b_1,b_2,\cdots,b_m\in A</math>。在字典序下，<math>S\le T</math> 当且仅当以下两条中的一条成立：
	* 存在 <math>0\le k<\min\{n,m\}</math> 使得对任意 <math>i\in\{1,2,\cdots,k\}</math> 有 <math>a_i=b_i</math>，但 <math>a_{k+1}<b_{k+1}</math>；		* 存在 <math>0\le k<\min\{n,m\}</math> 使得对任意 <math>i\in\{1,2,\cdots,k\}</math> 有 <math>a_i=b_i</math>，但 <math>a_{k+1}<b_{k+1}</math>；
第83行：		第82行：
	对表达式 <math>S=(a_1,a_2,\cdots,a_n)</math> 的长度 <math>n</math> 归纳定义。		对表达式 <math>S=(a_1,a_2,\cdots,a_n)</math> 的长度 <math>n</math> 归纳定义。

	若 <math>n=0</math>，则 <math>S=()</math> 是 PrSS 规范式。		<math>n=0</math> 时，<math>S=()</math> 是 PrSS 规范式。

	若 <math>n>0</math> 且 <math>S</math> 中仅有首项是零，则 <math>S</math> 是 PrSS 规范式当且仅当 <math>(a_2-1,a_3-1,\cdots,a_n-1)</math> 是 PrSS 规范式。		<math>n>0</math> 且 <math>S</math> 中仅有首项是零，则 <math>S</math> 是 PrSS 规范式当且仅当 <math>(a_2-1,a_3-1,\cdots,a_n-1</math> 是 PrSS 规范式。

	若 <math>n>0</math> 且 <math>S</math> 中有 <math>r>1</math> 项是零，设 <math>a_{k_1}=a_{k_2}=\cdots=a_{k_r}=0</math>，其中 <math>1=k_1<k_2<\cdots<k_r<k_{r+1}=n+1</math>，令 <math>S_i=(a_{k_i},a_{k_i+1},\cdots,a_{k_{i+1}-1})</math>。则 <math>S</math> 是 PrSS 规范式当且仅当 <math>S_1,S_2,\cdots,S_r</math> 都是 PrSS 规范式且按字典序 <math>S_1\ge S_2\ge\cdots\ge S_r</math>。		<math>n>0</math> 且 <math>S</math> 中有 <math>r>1</math> 项是零，设 <math>a_{k_1}=a_{k_2}=\cdots=a_{k_r}=0</math>，其中 <math>1=k_1<k_2<\cdots<k_r<k_{r+1}=n+1</math>，令 <math>S_i=(a_{k_i},a_{k_i+1},\cdots,a_{k_{i+1}-1})</math>。则 <math>S</math> 是 PrSS 规范式当且仅当 <math>S_1,S_2,\cdots,S_r</math> 都是 PrSS 规范式且按字典序 <math>S_1\ge S_2\ge\cdots\ge S_r</math>。

	PrSS 规范式是本文临时定义的，并不是通用术语。PrSS 规范式实际上等价于 PrSS 标准式。		PrSS 规范式是本文临时定义的，并不是通用术语。PrSS 规范式实际上等价于 PrSS 标准式。
第110行：		第109行：

	证毕。		证毕。

			在第一节证明 PrSS 没有无穷降链时，我们使用了序数的良序性。如果想不依赖序数就证明 PrSS 没有无穷降链，参见知乎用户 www620 的证明<ref>https://zhuanlan.zhihu.com/p/13871622947</ref>。这个证明依赖本节的两个结论：PrSS 表达式展开时字典序变小、PrSS 标准式都是规范式。注意到本节的两个结论不依赖第一节，所以没有循环论证的问题。

	== PrSS 标准式集的良序性 ==		== PrSS 标准式集的良序性 ==
第123行：		第124行：
	'''证明'''		'''证明'''

	定义一种特殊的展开函数 <math>E</math>：设 PrSS 表达式 <math>U</math> ~~的基本列为~~ <math>U_0,U_1,U_2,\cdots</math>。若存在 <math>i</math> 使得按字典序 <math>U_i\ge S</math>，则取 <math>k=\min\{i\mid U_i\ge S\}</math> 并定义 <math>E(U)=U_k</math>。如果对任意 <math>i</math> 都有按字典序 <math>U_i<S</math>，则取 <math>E(U)=U</math>。如果 <math>U</math> 是后缀表达式，则取 <math>U_0=U_1=\cdots</math> 为 <math>U</math> 的前驱表达式。特殊地，如果 <math>U</math> 是零表达式，则 <math>E(U)=U</math>。		定义一种特殊的展开函数 <math>E</math>：设 PrSS 表达式 <math>U</math> 的展开式为 <math>U_0,U_1,U_2,\cdots</math>。若存在 <math>i</math> 使得按字典序 <math>U_i\ge S</math>，则取 <math>k=\min\{i\mid U_i\ge S\}</math> 并定义 <math>E(U)=U_k</math>。如果对任意 <math>i</math> 都有按字典序 <math>U_i<S</math>，则取 <math>E(U)=U</math>。如果 <math>U</math> 是后缀表达式，则取 <math>U_0=U_1=\cdots</math> 为 <math>U</math> 的前驱表达式。特殊地，如果 <math>U</math> 是零表达式，则 <math>E(U)=U</math>。

	从 <math>E</math> 的定义不难看出，如果按字典序 <math>U\ge S</math>，则按字典序 <math>E(U)\ge S</math>。令 <math>T_0=T</math>，<math>T_{n+1}=E(T_n)</math>。因为按字典序 <math>T>S</math>，所以对任意 <math>i</math> 都有按字典序 <math>T_i\ge S</math>。		从 <math>E</math> 的定义不难看出，如果按字典序 <math>U\ge S</math>，则按字典序 <math>E(U)\ge S</math>。令 <math>T_0=T</math>，<math>T_{n+1}=E(T_n)</math>。因为按字典序 <math>T>S</math>，所以对任意 <math>i</math> 都有按字典序 <math>T_i\ge S</math>。
第129行：		第130行：
	而第一节已经证明 PrSS 不存在无穷降链，所以存在 <math>k</math> 使得 <math>T_k=T_{k+1}=\cdots</math>。讨论一下不难得到，这时有两种可能：		而第一节已经证明 PrSS 不存在无穷降链，所以存在 <math>k</math> 使得 <math>T_k=T_{k+1}=\cdots</math>。讨论一下不难得到，这时有两种可能：

	* <math>T_k=S</math>。		# <math>T_k=S</math>。
	* 按字典序 <math>T_k>S</math>，但 <math>T_k</math> ~~的基本列的每一项都按字典序小于~~ <math>S</math>。进一步讨论还可以看出，这种情况下 <math>T_k</math> 一定是极限表达式。		# <math>T_k>S</math>，但 <math>T_k</math> 的展开式都按字典序小于 <math>S</math>。进一步讨论还可以看出，这种情况下 <math>T_k</math> 一定是极限表达式。

	~~前一种情况命题已经成立，只需要用反证法证明后一种情况不存在即可。~~		前一种情况命题已经成立，我们只需要用反证法证明后一种情况不存在即可。

	若存在，设 <math>T_k</math> 的好部是 <math>G</math>，坏部是 <math>B</math>，末项是 <math>L</math>，坏根是 <math>L-1</math>，则 <math>T_k=(G,B,L)</math>，而 <math>T_k</math> 的展开式形如 <math>(G,B,B,\cdots)</math>。		若存在，设 <math>T_k</math> 的好部是 <math>G</math>，坏部是 <math>B</math>，末项是 <math>L</math>，坏根是 <math>L-1</math>，则 <math>T_k=(G,B,L)</math>，而 <math>T_k</math> 的展开式形如 <math>(G,B,B,\cdots)</math>。
第152行：		第153行：
	设 <math>S</math> 是 PrSS 规范式。存在 <math>n</math> 使得 <math>T=(0,1,2,\cdots,n-1)</math> 按字典序大于 <math>S</math>。根据上一个定理，<math>T</math> 可以展开成 <math>S</math>，所以 <math>S</math> 是 PrSS 标准式。		设 <math>S</math> 是 PrSS 规范式。存在 <math>n</math> 使得 <math>T=(0,1,2,\cdots,n-1)</math> 按字典序大于 <math>S</math>。根据上一个定理，<math>T</math> 可以展开成 <math>S</math>，所以 <math>S</math> 是 PrSS 标准式。

	~~证毕。~~		至此，我们证明了 PrSS 没有无穷降链、PrSS 标准式集的序是字典序，而字典序是全序，所以 PrSS 标准式集上的序是良序。

	~~因此，一个~~ PrSS ~~表达式是标准式当且仅当它是规范式。PrSS 标准式集上由展开定义的序是字典序。~~

	== PrSS ~~标准式集序同构于 <math>\varepsilon_0</math> ==~~

	~~前面几节我们证明了~~ PrSS ~~没有无穷降链、PrSS 标准式集的序是字典序，而字典序是全序，所以 PrSS 标准式集上的序是良序。~~		但我们不止于此。下一节，我们要证明 PrSS 标准式集[[良序\|序同构]]于 <math>\varepsilon_0</math>。

	~~但我们不止于此，我们还要证明~~ PrSS ~~标准式集[[良序\|序同构]]于 <math>\varepsilon_0</math>。~~		== PrSS 标准式集的序型 ==

	~~为此，我们要证明第一节定义的保序映射~~ <math>F</math> 是 PrSS 标准式集和 <math>\varepsilon_0</math> 之间的双射，结合 PrSS 标准式集的全序性，就能说明 <math>F</math> 是 PrSS 标准式集和 <math>\varepsilon_0</math> 之间的序同构。		为了证明 PrSS 标准式集[[良序\|序同构]]于 <math>\varepsilon_0</math>，我们要证明第一节定义的保序映射 <math>F</math> 是 PrSS 标准式集和 <math>\varepsilon_0</math> 之间的双射，结合 PrSS 标准式集的全序性，就能说明 <math>F</math> 是 PrSS 标准式集和 <math>\varepsilon_0</math> 之间的序同构。

	【未完】		【未完】

	[[分类:证明]]		[[分类:证明]]

2025年8月7日 (四) 10:38 Zhy137036

2025-08-07T10:38:28Z

←上一版本		2025年8月7日 (四) 18:38的版本
第111行：		第111行：
	证毕。		证毕。

	== PrSS ~~标准式集的序是字典序~~ ==		== PrSS 标准式集的良序性 ==

	上一节我们证明了 PrSS 合法表达式在展开过程中字典序变小，并由此得到了 PrSS 标准式的必要条件。这一节，我们证明字典序变小反过来也意味着可以展开得到，并由此得到 PrSS 标准式的充分条件。		上一节我们证明了 PrSS 合法表达式在展开过程中字典序变小，并由此得到了 PrSS 标准式的必要条件。这一节，我们证明字典序变小反过来也意味着可以展开得到，并由此得到 PrSS 标准式的充分条件。
第156行：		第156行：
	因此，一个 PrSS 表达式是标准式当且仅当它是规范式。PrSS 标准式集上由展开定义的序是字典序。		因此，一个 PrSS 表达式是标准式当且仅当它是规范式。PrSS 标准式集上由展开定义的序是字典序。

	== PrSS ~~标准式集的良序性~~ ==		== PrSS 标准式集序同构于 <math>\varepsilon_0</math> ==

	前面几节我们证明了 PrSS 没有无穷降链、PrSS 标准式集的序是字典序，而字典序是全序，所以 PrSS 标准式集上的序是良序。		前面几节我们证明了 PrSS 没有无穷降链、PrSS 标准式集的序是字典序，而字典序是全序，所以 PrSS 标准式集上的序是良序。

2025年8月7日 (四) 10:33 Zhy137036

2025-08-07T10:33:40Z

显示更改

Zhy137036：未完

2025-08-04T05:00:46Z

未完

新页面

== PrSS 没有无穷降链 ==

首先我们将 [[初等序列系统|PrSS]] 的每个合法表达式 <math>S</math> 对应于一个不超过 <math>\varepsilon_0</math> 的[[序数]] <math>F(S)</math>。然后我们证明 PrSS 表达式展开时，其对应的序数严格递减。于是就可以依据 <math>\varepsilon_0</math> 的[[良序|良序性]]说明 PrSS 没有无穷降链。

'''第一步'''：将 PrSS 的每个合法表达式对应于一个不超过 <math>\varepsilon_0</math> 的序数。

对 PrSS 表达式的长度归纳定义。

任取 PrSS 合法表达式 <math>S=(a_1,a_2,\cdots,a_n)</math>。

若 <math>n=0</math>，则 <math>F(S)=0<\varepsilon_0</math>。

若 <math>n>0</math>，分两种情况讨论：

* 若 <math>\forall i\in\{2,3,\cdots,n\},a_i\neq 0</math>，则取 <math>T=(a_2-1,a_3-1,\cdots,a_n-1)</math>。 不难验证，<math>T</math> 是合法的 PrSS 表达式，且 <math>T</math> 的长度比 <math>S</math> 的长度短。令 <math>F(S)=\omega^{F(T)}</math>。 因为 <math>F(T)<\varepsilon_0</math>，所以 <math>F(S)<\varepsilon_0</math>。
* 否则，设 <math>S</math> 中有 <math>r</math> 项为零，且 <math>a_{k_1}=a_{k_2}=\cdots=a_{k_r}=0</math>，其中 <math>1=k_1<k_2<k_3<\cdots<k_r<k_{r+1}=n+1</math>。 取 <math>S_i=(a_{k_i},a_{k_i+1},\cdots,a_{k_{i+1}-1}),\quad i=1,2,\cdots,r</math>，不难验证 <math>S_1,S_2,\cdots,S_r</math> 都是合法的 PrSS 表达式，且它们的长度都比 <math>S</math> 短。 令 <math>F(S)=F(S_1)+F(S_2)+\cdots+F(S_r)</math>。 因为 <math>F(S_1),F(S_2),\cdots,F(S_r)<\varepsilon_0</math>，所以 <math>F(S)<\varepsilon_0</math>。

'''第二步'''：证明 PrSS 表达式展开时，其对应的序数严格递减。

对 PrSS 表达式的长度归纳证明。

任取 PrSS 表达式 <math>S=(a_1,a_2,\cdots,a_n)</math>。

若 <math>n=0</math>，则 <math>S</math> 无法展开。下面讨论 <math>n>0</math> 的情况。

若 <math>a_n=0</math>，则 <math>S</math> 的展开式（前驱表达式）是 <math>T=(a_1,a_2,\cdots,a_{n-1})</math>。分为两种情况讨论：

* 若 <math>\forall i\in\{2,3,\cdots,n\},a_i\neq 0</math>，则 <math>S=(0)</math>，<math>F(S)=1</math>，<math>T=()</math>，<math>F(T)=0</math>，<math>F(T)<F(S)</math>。
* 否则，设 <math>S</math> 中有 <math>r</math> 项为零，且 <math>a_{k_1}=a_{k_2}=\cdots=a_{k_r}=0</math>，其中 <math>1=k_1<k_2<k_3<\cdots<k_r=n<k_{r+1}=n+1</math>。 取 <math>S_i=(a_{k_i},a_{k_i+1},\cdots,a_{k_{i+1}-1}),\quad i=1,2,\cdots,r</math>，则 <math>F(S)=F(S_1)+F(S_2)+\cdots+F(S_r)</math>。 注意到 <math>S_r=(0)</math>，<math>F(S_r)=1</math>，所以 <math>F(T)=F(S_1)+F(S_2)+\cdots+F(S_{r-1})</math>，所以 <math>F(S)=F(T)+1>F(T)</math>。

若 <math>a_n\neq 0</math>，分为三种情况讨论：

* 若 <math>S</math> 中有不止一项是零。 设 <math>S</math> 中有 <math>r>1</math> 项为零，且 <math>a_{k_1}=a_{k_2}=\cdots=a_{k_r}=0</math>，其中 <math>1=k_1<k_2<k_3<\cdots<k_r<k_{r+1}=n+1</math>。 取 <math>S_i=(a_{k_i},a_{k_i+1},\cdots,a_{k_{i+1}-1}),\quad i=1,2,\cdots,r</math>，则 <math>F(S)=F(S_1)+F(S_2)+\cdots+F(S_r)</math>。 设 <math>S</math> 的坏根为 <math>a_x</math>。不难看出，<math>x\ge k_r</math>。 设 <math>S_r</math> 的基本列的第 <math>p</math> 项是 <math>V_p</math>。由 PrSS 展开规则，<math>S</math> 的基本列的第 <math>p</math> 项是 <math>U_p=(S_1,S_2,\cdots,S_{r-1},V_p)</math>。 因为 <math>S_r</math> 的长度比 <math>S</math> 短，根据归纳假设，有 <math>F(V_p)<F(S_r)</math>。 设 <math>V_p=(b_1,b_2,\cdots,b_m)</math> 中有 <math>s</math> 项为零，且 <math>b_{l_1}=b_{l_2}=\cdots=b_{l_s}=0</math>，其中 <math>1=l_1<l_2<l_3<\cdots<l_s<l_{s+1}=m+1</math>。 取 <math>T_i=(b_{l_i},b_{l_i+1},\cdots,b_{l_{i+1}-1}),\quad i=1,2,\cdots,s</math>，则 <math>F(V_p)=F(T_1)+F(T_2)+\cdots+F(T_s)</math>。 所以 <math display="block">\begin{aligned}F(U_s)\,&=F(S_1)+F(S_2)+\cdots+F(S_{r-1})+F(T_1)+F(T_2)+\cdots+F(T_s)\\&=F(S_1)+F(S_2)+\cdots+F(S_{r-1})+(F(T_1)+F(T_2)+\cdots+F(T_s))\\&=F(S_1)+F(S_2)+\cdots+F(S_{r-1})+F(V_s)\\&<F(S_1)+F(S_2)+\cdots+F(S_{r-1})+F(S_r)\\&=F(S)\end{aligned}</math>
* 若 <math>S</math> 中仅有首项为零，且末项为 <math>a_n=1</math>。 令 <math>T_1=(a_1,a_2,\cdots,a_{n-1})</math>。由 PrSS 展开规则，不难看出 <math>S</math> 的基本列的第 <math>p</math> 项是 <math>U_p=(T_1,T_1,\cdots,T_1)</math>，其中有 <math>p</math> 个 <math>T_1</math>。 显然 <math>n\ge 2</math>，所以 <math>F(T_1)>0</math>。 那么 <math>F(U_p)=F(T_1)+F(T_1)+\cdots+F(T_1)=F(T_1)\times p<F(T_1)\times\omega</math>。 令 <math>T_2=(a_2-1,a_3-1,\cdots,a_n-1)</math>，则 <math>F(S)=\omega^{F(T_2)}</math>。 令 <math>T_3=(a_2-1,a_3-1,\cdots,a_{n-1}-1)</math>，则 <math>F(T_1)=\omega^{F(T_3)}</math>。 因为 <math>a_n-1=0</math>，所以 <math>F(T_2)=F(T_3)+1</math>，所以 <math>F(S)=\omega^{F(T_2)}=\omega^{F(T_3)+1}=\omega^{F(T_3)}\times\omega=F(T_1)\times\omega>F(U_p)</math>。
* 若 <math>S</math> 中仅有首项为零，且末项为 <math>a_n\neq 1</math>。 令 <math>T=(a_2-1,a_3-1,\cdots,a_n-1)</math>，因为 <math>a_n-1\neq 0</math>，所以 <math>T</math> 是极限表达式。 设 <math>T</math> 的基本列的第 <math>k</math> 项是 <math>T_k=(b_1,b_2,\cdots,b_{m_k})</math>，则由 PrSS 展开规则可以看出 <math>S</math> 的基本列的第 <math>k</math> 项是 <math>S_k=(0,b_1+1,b_2+1,\cdots,b_{m_k}+1)</math>。 根据归纳假设有 <math>F(T_k)<F(T)</math>，所以 <math>F(S_k)=\omega^{F(T_k)}<\omega^{F(T)}=F(S)</math>。

== PrSS 标准表达式 ==

== PrSS 标准式集的序是字典序 ==

== PrSS 标准式集的良序性 ==

这一节，我们不仅要最终证明 PrSS 标准式集是良序的，还要证明它[[良序|序同构]]于 <math>\varepsilon_0</math>。

为此，我们首先证明上一节所述字典序是全序，结合第一节所证 PrSS 没有无穷降链，就能说明 PrSS 标准式集是良序的。

接下来，我们证明第一节定义的保序映射 <math>F</math> 是 PrSS 标准式集和 <math>\varepsilon_0</math> 之间的双射，结合 PrSS 标准式集的全序性，就能说明 <math>F</math> 是 PrSS 标准式集和 <math>\varepsilon_0</math> 之间的序同构。

[[分类:证明]]

PrSS的良序性 - 版本历史

2026年2月21日 (六) 14:41 Tabelog

0100000000a7：​0100000000a7移动页面PrSS 的良序性至PrSS的良序性：​恢复

Tabelog：​Tabelog移动页面PrSS的良序性至PrSS 的良序性，不留重定向