偏序序列变换规律再探

本文主要是介绍偏序序列变换规律再探，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

本篇是 偏序序列变换规律分析 的续篇。 

接下来，为进一步探索偏序序列连续变换的规律，引入堡垒子序列的概念：

偏序序列 U = (a) H [b]，其中 H 为纯值对子序列，若 H = S₁S₂...S_h，其中 S_i （i=1,...,h）为纯值对子序列，且满足以下条件：

I. F(Γ(S_i)) = F(S_i) - 1, i=1,...,h；

II. left(S₁) ≥ 1；

III. left(S_i) ≥ 2, i≠1；

IV. right(S_i) ≥ 2, i≠h；

V. right(S_h) ≥ 1。

则称 H 从左至右被划分成 h 个堡垒子序列（简称堡垒）S₁、S₂、...、S_h 。相应引入：

堡垒数函数 forts(U) = forts(H) = h，堡垒函数 fort(U,i) = S_i, i=1,...,forts(U)，首堡垒函数 hfort(U) = S₁，尾堡垒函数 tfort(U) = S_h。

再引入单次变换的跳变数函数 gap(U >> V) = F(U) - F(V) - 1，其中 V = Γ(U)。

由上述定义可知 gap(U >> V) = forts(U) - 1，gap(U) = gap(U >> V) + gap(V)，以及：

特性 12（跳变特性）：若有 n 个序列 U₁、U₂、...、U_n，满足 U_i >> U_i+1，i=1,...,n-1，且 Un 为规范序列，并记 g_i = gap(U_i >> U_i+1)，i=1,...,n-1。则有 gap(U_k) = Σg_{i:i=k,...,n-1}，k=1,...,n-2。

 

为探讨如何将一个偏序序列划分成若干个堡垒的问题，先考察几个例子。

例 1：U = [1,1)[1,1)

U 由两个 E 值对组成，E 值对的左界和右界均为 1，因此 只有 h = 1 的划分法，即 U 整体作为一个堡垒。

易知，当 U 为任意双一序列时，它都是作为整体被划分为一个堡垒，即forts(U) = 1，且有 left(U) = right(U) = 1。

例 2：U = [1,2)[1,3)[1,5)

这里 U 整体是一个左一序列。尝试把 第一个值对 [1,2) 单独划分为堡垒 S₁，此时必有 h > 1，left(S₁) = 1，rights(S₁) = 2，符合条件，但是S₂ 的第一个值对为 [1,3)，于是有 left(S₂) = 1，这与条件III 不符，故不能把第一个值对单独划分为堡垒，依此类推，容易得出 U 必须作为整体被划分为一个堡垒。

当 U 为任意一个左一序列时，可以推知，它都是作为整体被划分为一个堡垒，即forts(U) = 1，且有 left(U) = 1，right(U) ≥ 1。

当 U 为任意一个右一序列时，类似地可以推知，它都是作为整体被划分为一个堡垒，即forts(U) = 1，且有 right(U) = 1，left(U) ≥ 1。

例 3：U = [1,2)[1,3)[1,5)[4,1)[1,1)

 这里 U 是 LR 型序列，L = [1,2)[1,3)[1,5)，R = [4,1)[1,1)，left(L) = 1，right(L) = 5, left(R) = 4，right(R) = 1，易知 L 和 R 是 U 的两个堡垒，L 是左开右闭堡垒，R 是左闭右开堡垒。

例 4：U = [1,3)[2,4)[3,1)[2,1)[1,5)[1,3)[4,2)[3,1)

根据堡垒划分的定义，可以分解出以下几个堡垒：

S₁ = [1,3)，S₂ = [2,4)，S₃ = [3,1)[2,1)[1,5)[1,3)，S₄ = [4,2)，S₅ = [3,1)

其中打头的 S₁ 为左一序列，是左开右闭堡垒；末尾的 S₅ 为右一序列，是左闭右开堡垒；中间的 S₂、S₃、S₄ 都是全封闭的堡垒（即左右界都大于 1，一次变换后不会发生左析出或右析出），S2 和 S4 都是 I 型值对，S3 是 RL 型序列。

从上述几个示例可知，参与构成堡垒的子序列有以下几种：

（1）左右界都等于 1 的左一或右一序列：称为全开放堡垒基，只能作为单一的全开放堡垒存在，即两边不能有邻接序列

（2）右界大于 1 的左一序列：称为左开放堡垒基，可作为单一的堡垒存在，也可作为最左侧的堡垒与其它堡垒并存

（3）左界大于 1 的右一序列：称为右开放堡垒基，可作为单一的堡垒存在，也可作为最右侧的堡垒与其它堡垒并存

（4）I 型值对：称为 I 型封闭堡垒基，简称 I 型堡垒基

（5）RL 型序列：称为 II 型封闭堡垒基，简称 II 型堡垒基

前三种堡垒基统称为开放堡垒基。I 型堡垒基和 II 型堡垒基统称为封闭堡垒基。一个封闭堡垒基可作为单一的堡垒存在，也可在任意位置作为堡垒与其它堡垒并存。

相应地，堡垒也可以按两端的界值的不同分为以下几类：

（1）左右界都为 1 的堡垒称作全开放堡垒

（2）左界为 1 右界大于 1 的堡垒称作左开放堡垒

（3）右界为 1 左界大于 1 的堡垒称作右开放堡垒

（4）左右界都大于 1 的堡垒称作封闭堡垒

上面几个例子都是一个堡垒基独立构成堡垒的情形，来看一个多个堡垒基构成一个堡垒的例子。

例 5：U = [1,3)[2,1)[5,1)[2,4)[3,1)[2,1)[1,5)[1,1)[1,3)[4,2)[1,1)[3,1)

这个例子是在例 4 的基础上加入了一些值对（如黄色标注部分）。

第一个堡垒依然是 S₁ = [1,3)，因为其后的值对的左界大于 1；

继续寻找右界大于 1 的值对，为 [2,4)，且随后的值对的左界大于 1，于是 S₂ = [2,1)[5,1)[2,4)，这个堡垒由一个右一序列 R（右开放堡垒基）和一个 I 型值对 W（I 型堡垒基）拼接而成，由前面的推论 gap(RW) = 0 可知 F(Γ(RW)) = F(RW) - 1，所以 S₂ 的确是满足定义要求的堡垒；

继续寻找右界大于 1 的值对，为 [1,5)，但是随后值对的左界为 1，继续寻找右界大于 1 的值对，为 [1,3)，且随后的值对 [4,2) 的左界大于 1，于是 S₃ = [3,1)[2,1)[1,5)[1,1)[1,3)，这个堡垒由一个 II 型堡垒基构成；

[4,2) 的右界大于 1，但是随后的值对 [1,1) 左界为1，继续往右寻找，[3,1) 已经是最末尾的值对，因此 S₄ = [4,2)[1,1)[3,1)，这个堡垒由一个 I 型堡垒基和一个全开放堡垒基拼接而成，由 [4,2)[1,1)[3,1) >> [3,1)[1,2)[3,1)[1] 知 F(Γ(S₄)) = F(S₄) - 1，所以 S₄ 的确是满足定义要求的堡垒。

从这个例子可以看出：

右开放堡垒基可以放到一个封闭堡垒的左侧，从而扩充成一个新的封闭堡垒，称为封闭堡垒的左侧扩充，如 [2,1)[5,1)[2,4)；同样左开放堡垒基可以放到一个封闭堡垒的右侧，从而扩充成一个新的封闭堡垒，称为封闭堡垒的右侧扩充，如 [2,4)[1,1)[1,5)；还可以从两侧同时扩充一个封闭堡垒，称为封闭堡垒的双侧扩充，如 [6,1)[2,1)[5,1)[2,4)[1,1)[1,5)[1,3)，由前面的推论 gap(RWL) = 0 可知 F(Γ(RWL)) = F(RWL) - 1，即扩充后的序列的确满足构成堡垒的条件 I。

而把一个全开放堡垒基放置在两个邻接的堡垒之间，则会连通成一个堡垒。如：[4,2)[1,1)[3,1) 以及 [4,2)[1,1)[3,1)[5,6)。

容易推知，为把 n 个堡垒连通成一个堡垒，只需在每两个相邻堡垒之间插入一个全开放堡垒基即可。

由序列两端的规范组不参与堡垒划分，有：

特性13（规范组不影响跳变数特性）：若 U = (a) V [b]，a ≥ 0，b ≥ 0，且 V 是纯值对序列。则有 gap(U) = gap(V)。

为方便起见，引入取纯函数 pure(U) = V，其中 V 是 U 去掉两端的规范组后的剩余序列。特性 13 即为：gap(U) = gap(pure(U))。

再引入左侧取纯函数 lpure(U) = V [b]，右侧取纯函数 rpure(U) = (a) V，U = (a) V [b]，a ≥ 0，b ≥ 0，且 V 是纯值对序列。

 

回顾特性 8：L = [1,q_t)...[1,q₂)[1,q₁) 和 R = [p₁,1)[p₂,1)...[p_s,1) 的拼接序列 LR 满足 gap(LR) = min{game(L), game(R)}。当接合位置的 q₁ 和 p₁ 都大于 1 ，即 right(L) > 1 且 left(R) > 1 时，LR 正好划分为两个堡垒，即左开放堡垒 L 和 右开放堡垒 R。

对于一个 LR 型序列，若 right(L) = 1 或 left(R) = 1，易知 L 与 R 的结合位置至少有一个 E 值对，这时称 LR 是连通的，否则称 LR 是不连通的。在堡垒划分时一个连通的 LR 型序列只能归属于同一个堡垒。

进一步来考察可生成偏序序列 V 的堡垒划分特性，由特性 13，只需考虑 V 是纯值对序列的情形。

易知 V 可分解为若干个左一序列和右一序列的交替拼接，因为 E 值对既可以归到左一序列又可以归到右一序列，为避免归类重叠，约定：若一个 E 值对没有左邻值对，则把这个 E 值对归到一个左一序列里；否则把这个 E 值对归到它的左邻值对所属的序列里。

一般地，V 可表示为：{R} {M} {L}

这里 {} 表示括起来的序列可以是 1 个，也可以是 0 个。但由于 V 是偏序序列，R、M、L 不能都为空序列。L 代表一个左一序列；R 代表一个右一序列，由上述的为了避免归类重叠而引入的约定法则可知 left(R) > 1；M 代表 k 个 LR 型序列从左至右拼接而成的序列，其形式为：

M = L₁R₁ L₂R₂ ... L_kR_k，k > 0，且 left(R_i) > 1, i=1,...,k。

具体而言，V 的一般形式可归结为 7 种，分别称为：L 型、R 型、RL 型、M 型、ML 型、RM 型和 RML 型序列。

L 型序列的示例：[1,1)[1,4)[1,3)、[1,1)、[1,3)[1,1)、[1,1)[1,1)、[1,1)[1,3)[1,1)。

R 型序列的示例：[5,1)[2,1)[6,1)、[3,1)[1,1)[1,1)。

RL 型序列的示例：[3,1)[1,1)[1,1)[1,3)[1,1)。

M 型序列的示例：[1,3)[4,1)[1,1)、[1,3)[1,2)[1,1)[4,1)[1,1)[1,5)[1,1)[1,3)[1,1)[8,1)[3,1)。

ML 型序列的示例：[1,3)[4,1)[1,1)[1,3)[1,2)[1,1)。

RM 型序列的示例：[3,1)[1,1)[1,3)[4,1)[1,1)。

RML 型序列的示例：[3,1)[1,1)[1,3)[4,1)[1,1)[1,4)[1,3)。

L 型、R 型、RL 型序列统称为泛 RL 型序列。

考察 M 型序列的堡垒划分。对 M = L₁R₁ L₂R₂ ... L_kR_k 从左至右划分为 t 个堡垒，记为 M = S₁S₂...S_t。

第一个堡垒 S₁ 的确定方法如下：

考察第一个 LR 型序列，若 L₁R₁ 是不连通的，则有 S₁ = L₁，确定完成；否则，考察下一个 LR 型序列，即若 L₂R₂ 是不连通的，则有 S₁ = L₁R₁L₂，确定完成；否则，考察下一个 LR 型序列，由 k 为有限数，总能确定 S₁，如果 M 中每个 LR 型序列都是连通的，则 M = S₁（即 t = 1）。

确定 S₁ 之后，M 中还有剩余的子序列没有被划分为堡垒，则继续用确定 S₁ 的方法依次去确定 S₂、...、S_t。

如果 t > 1，易知只有 St 是以一个 R型序列结尾的，且有 S_t = R_pL_p+1R_p+1...L_k-1R_k-1L_kR_k，p ≤ k（当 p = k 时，有 S_t = R_k），而 S_i = R_dL_d+1...R_q-1L_q，d ≥ 0，q > d，i ≠ t（当 d = 0 时，i = 1，且 R₀ 代表空序列，即有 S₁ = L₁R₁L₂R₂...L_q-1R_q-1L_q，当 q = 1 时，有 S₁ = L₁）。

考察 M 的首堡垒 S₁ = L₁R₁L₂R₂...L_q-1R_q-1L_q 的变换特性，其中的 q-1 个 LR 型序列都是连通的，由上述的 E 值对归属约定，可设 L_i = L'_iE, i=1,...,q-1，再设 L_q = [1,p₁)...[1,p_h)，于是 

S₁ = L'₁ER₁ L'₂ER₂ ... L'_q-1ER_q-1 L_q >> (1) L'₁R₁E L'₂R₂E ... L'_q-1R_q-1E L'_q

其中 L'_q = [1,p₁)...[1,p_h-1)

从 S₁ 到 Γ(S₁)，从效果上看，相当于每个连通的 L_iR_i 中 L_i 末尾的 E 被移到了 R_i 的末尾（i=1,...,q-1），其余的部分则简化为 L_q >> (1) L'_q。令 R'_i = R_iE, i=1,...,q-1，则 S₁ >> Γ(S₁) 可表达为

S₁ = L₁R₁L₂R₂...L_q-1R_q-1L_q >> (1) L'₁R'₁L'₂R'₂...L'_q-1R'_q-1L'_q 

不过，变换后不能保证 Γ(S₁) 依然是堡垒，因为不能每个 L'_iR'_i 依然都是连通的，事实上 Γ(S₁) 最多可能划分出 q-1 个堡垒。

  

特性 14（可生成偏序序列变换特性）：若一个可生成偏序序列 V = RML，R 是右一序列，L 是左一序列，则 gap(V) = gap(M)。

证明：把 ML 看成一个整体，先来证明 gap(RML) = gap(ML)。

对 M = L₁R₁ L₂R₂ ... L_kR_k 沿用上述方法从左至右划分为 t 个堡垒，即 M = S₁S₂...S_t，于是

ML = S₁ S₂ ... S_tL，RML = RS₁ S₂ ... S_tL

易知 ML 和 RML 也都相应被划分为 t 个堡垒，且有

fort(ML,i) = S_i, i=1,...,t-1，fort(ML,t) = S_tL

fort(RML,1) = RS₁，fort(RML,i) = S_i, i=2,...,t-1，fort(RML,t) = S_tL

即 RML 和 ML 除了首堡垒不同，其余堡垒都对应相同。

gap(ML >> Γ(ML)) = gap(RML >> Γ(RML)) = t-1

于是 gap(RML) = gap(ML) 等价于 gap(Γ(RML)) = gap(Γ(ML))

Γ(ML) = Γ(S₁) Γ(S₂) ... Γ(S_t-1)Γ(S_tL)

Γ(RML) = Γ(RS₁) Γ(S₂) ... Γ(S_t-1)Γ(S_tL)

以下分情形讨论：

1）若 t = 1，则 M 由 k 个连通的 LR 型序列组成，由上面分析，有

ML = L₁R₁...L_kR_kL >> (1) L'₁R'₁...L'_kR'_kL' 

RML = RL₁R₁...L_kR_kL >> (d)R'EL'₁R'₁...L'_kR'_kL' 

其中，L_i = L'_iE，R'_i = R_iE，(i=1,...,k)；且有 L >> (1)L' 以及 R >> (d)R'[1]（当 left(R) = 1 时，d = 1，否则 d = 0；特别地，当 R = E时，R' 为空序列）

记 X = lpure(Γ(ML))，即 X = L'₁R'₁...L'_kR'_kL'，易知 gap(Γ(ML)) = gap(X)

记 Y = Γ(RML)，若 X 被划分为 a 个堡垒：X₁...X_a，则由 Y = R'EX 可知，Y 也一定被划分为 a 个堡垒：Y₁...Y_a，且有 Y₁ = R'EX₁，Y_i = X_i, i=2,...,a

gap(X >> Γ(X)) = gap(Y >> Γ(Y)) = a-1

于是 gap(RML) = gap(ML) 等价于 gap(Γ(Y)) = gap(Γ(X))

若 a = 1，易知 Y 和 X 的堡垒划分关系和上面 t = 1 时 RML 和 ML 的堡垒划分关系是一样的，可以同上面一样往下推进；

若 a > 1，则有

X₁ = L'₁R'₁...L'_q-1R'_q-1L'_q，1 ≤ q ≤ k（当 q = 1 时，X₁ = L'₁）

Y₁ = R'EX₁ = R'EL'₁R'₁...L'_q-1R'_q-1L'_q，1 ≤ q ≤ k（当 q = 1 时，X₁ = L'₁）

记 X' = Γ(X)，Y' = Γ(Y)，则

X' = Γ(X₁)Γ(X₂) ... Γ(X_a)

Y' = Γ(Y₁)Γ(X₂) ... Γ(X_a)

由 X₁ 是堡垒知，X₁ 中的 q-1 个 LR 型序列都是连通的，于是有

Γ(X₁)  = (1) L''₁R''₁...L''_q-1R''_q-1L''_q，

Γ(Y₁) = Γ(R'EX₁) = Γ(R'E) Γ(X₁) = (d)R''[1] Γ(X₁)

= (d)R''EL''₁R''₁...L''_q-1R''_q-1L''_q

其中，L'_i = L''_iE，R''_i = R'_iE，(i=1,...,q-1)；且有 L'_q >> (1)L''_q 以及 R'E >> (d)R''[1]（当 left(R'E) = 1 时，d = 1，否则 d = 0；特别地，当 R' 为空序列，R'' 也为空序列）

记 X'_i = Γ(X_i)，Y'_i = Γ(Y_i)，i=1,...,a，易知：

X' = X'₁ X'₂ ... X'_a，Y' = Y'₁ X'₂ ... X'_a

即 X' 和 Y' 只在打头的序列 X'₁ 和 Y'₁ 上不同，且从上面可知，pure(Y'₁) = R''E pure(X'₁) ，从而有

pure(Y') = R''E pure(X') 

于是，若 pure(X') 被划分为 b 个堡垒，则 pure(Y') 同样会被划分为 b 个堡垒，即有

gap(RML) = gap(ML) 等价于 gap(Y') = gap(X')，又等价于 gap(pure(Y')) = gap(pure(X'))，又等价于 gap(Γ(pure(Y'))) = gap(Γ(pure(X')))

再往下无论 b = 1 还是 b > 1都可以按上述相应的方法继续变换下去，并得到新的等价等式。但这个变换过程不会无限进行下去，因为 F(ML) 是有限制，而 ω(ML) ≤ F(ML)，同理 ω(RML) 也是有限值。

综上分析可知，从 ML 和 RML 开始，每经历一次变换后得到的两个新序列，它们的堡垒划分总具有上述的对等性。从而总有 gap(RML) = gap(ML) 成立。

2）若 t > 1，再往后只需沿用上面处理 a > 1 的情形采用的方法，同样可以得以进行下去，并得到新的等价等式。

综上，便有 gap(RML) = gap(ML) 成立。

需要指出的是 ω(ML) < ω(RML)，即 ML 比 RML 经历更少的变换次数成为规范序列，但依然有 gap(RML) = gap(ML) 成立，实际上当 ML 经若干次变换后成为泛 RL 型序列 R_xL_x 时，RML 也一定经同样次数的变换后成为泛 RL 型序列 R_yL_y，尽管 F(R_yL_y) > F(R_xL_x)，但总有 g(R_yL_y) = g(R_xL_x) = 0。

由此再去梳理上面的证明过程，会发现 “若 pure(X') 被划分为 b 个堡垒，则 pure(Y') 同样会被划分为 b 个堡垒” 是有缺陷的，即没有考虑到 b = 0 的情形。这里补充一下：

在经多次变换（不妨记为 c 次）后一定会出现 pure(X'^.c.') 为空序列的情况（即 ML 经 c 次变换后成为规范序列），这时 b = 0，而 pure(Y'^.c.') = R'^.c.'E 会被划分为 1 个堡垒。此时 pure(Y'^.c.') 是一个 R 型序列，满足 gap(pure(X'^.c.')) = gap(pure(Y'^.c.')) = 0。

以上证明了 gap(RML) = gap(ML)。类似地方法可以进一步证明 gap(ML) = gap(M)。

 

为具象化，考察一个具体例子：

R = [7,1)[1,1)[3,1)，M= [1,2)[1,5)[1,1)[4,1)[3,1) [1,5)[1,1)[4,1)[2,1)，L = [1,2)[1,1)[1,5)

ML = [1,2)[1,5)[1,1)[4,1)[3,1) [1,5)[1,1)[4,1)[2,1) [1,2)[1,1)[1,5)   ① // forts = 1

 >> (1) [1,2)[1,5)[4,1)[3,1)E [1,5)[4,1)[2,1)E [1,2)[1,1)[1,4)   ② // forts = 3，gap(② >> ③) = 2

 >> (2) [1,2)[1,4)[3,1)[3,1)E² [1,4)[3,1)[2,1)E² [1,2)[1,1)[1,3)  ③ // forts = 3，gap(③ >> ④) = 2

 >> (3) [1,2)[1,3)[2,1)[3,1)E³ [1,3)[2,1)[2,1)E³ [1,2)[1,1)[1,2)  ④ // forts = 3，gap(④ >> ⑤) = 2

 >> (4) [1,2)[1,2)[1,1)[3,1)E⁴ [1,2)[1,1)[2,1)E⁴ [1,2)[1,1)[1,1)  ⑤ // forts = 1

 >> (5) [1,2)[1,2)[3,1)E⁵ [1,2)[2,1)E⁵ [1,2)[1,1) [1]  ⑥ // forts = 3，gap(⑥ >> ⑦) = 2

 >> (6) [1,2)[1,1)[2,1)E⁶ [1,1)[1,1)E⁶ [1,2) [2]  ⑦ // forts = 1

 >> (7) [1,2)[2,1)E¹⁴ [1,1)[1,1) [2]  ⑧ // forts = 2，gap(⑧ >> ⑨) = 1

 >> (8) [1,1)[1,1)E¹⁴ [1,1)[1,1) [3]  ⑨ 

由上述 ML 的连续变换过程可以看出，8 次变换后得到序列 ⑨ = (8) E¹⁸ [3]，pure(⑨) 是双一序列，之后的每次变换的跳变数都为 0，于是 gap(ML) = 2+2+2+2+1 = 9。

RML = [7,1)[1,1)[3,1)[1,2)[1,5)[1,1)[4,1)[3,1) [1,5)[1,1)[4,1)[2,1) [1,2)[1,1)[1,5)   ①' // forts = 1

 >> [6,1)E[3,1)E [1,2)[1,5)[4,1)[3,1)E [1,5)[4,1)[2,1)E [1,2)[1,1)[1,4)   ②' // forts = 3，gap(②' >> ③') = 2

 >> [5,1)E[3,1)E² [1,2)[1,4)[3,1)[3,1)E² [1,4)[3,1)[2,1)E² [1,2)[1,1)[1,3)  ③' // forts = 3，gap(③' >> ④') = 2

 >> [4,1)E[3,1)E³ [1,2)[1,3)[2,1)[3,1)E³ [1,3)[2,1)[2,1)E³ [1,2)[1,1)[1,2)  ④' // forts = 3，gap(④' >> ⑤') = 2

 >> [3,1)E[3,1)E⁴ [1,2)[1,2)E[3,1)E⁴ [1,2)E[2,1)E⁴ [1,2)[1,1)[1,1)  ⑤' // forts = 1

 >> [2,1)E[3,1)E⁵ [1,2)[1,2)[3,1)E⁵ [1,2)[2,1)E⁵ [1,2)[1,1) [1]  ⑥' // forts = 3，gap(⑥' >> ⑦') = 2

 >> E²[3,1)E⁶ [1,2)[1,1)[2,1)E⁶ [1,1)[1,1)E⁶ [1,2) [2]  ⑦' // forts = 1

 >> (1) E[3,1)E⁷ [1,2)[2,1)E¹⁴ [1,1)[1,1) [2]  ⑧' // forts = 2，gap(⑧' >> ⑨') = 1

 >> (2) [3,1)E⁸ [1,1)[1,1)E¹⁴ [1,1)[1,1) [3]  ⑨'

由上述 RML 的连续变换过程可以看出，8 次变换后得到序列 ⑨' = (2) [3,1)E²⁶ [3]，pure(⑨') 是 R 型序列，之后的每次变换的跳变数都为 0，于是 gap(RML) = 2+2+2+2+1 = 9。

对比 RML 和 ML 的连续变换，可以直观地看到 R 及其每次变换的结果都只是一个右开放堡垒基，只有右侧为空序列时它才能构成唯一的堡垒，否则只能从左侧去加入一个堡垒。同样，对比 ML 和 M 的连续变换，也有类似结论。M 的连续变换过程这里不再详细展开了。

 

特性 15：R 是任意右一序列，L 是任意左一序列，U 是任意纯值对序列，则 gap(RUL) = gap(U)。

本特性是对特性 14 的扩展。

证明：若 U 中不含有 I 型值对，则由特性 14 知命题成立。因而只需考虑 U 中含有 I 型值对的情形。

易知 forts(RU) = forts(U)，即有

gap(RU >> Γ(RU)) = gap(U >> Γ(U))    ①

设 U >> (a) V [b]，a = 0,1，b = 0,1，V 为纯值对序列。

由特性 9 知 V 是可生成偏序序列。再设 R >> (c) R' [1]，c = 0,1。

若 a = 1，则有 RU >> (c) R'EV [b]

由特性 13 和 14，有

gap(Γ(U)) = gap(V) = gap(R'EV) = gap(Γ(RU))

结合 ① 便有 gap(RU) = gap(U)。

若 a = 0，则必有 left(U) > 1，可记 V = [p,1)V'，即有 RU >> (c) R' [p+1,1)V' [b]

由特性 13 和 14，有

gap(Γ(U)) = gap(V) = gap(V') = gap(R' [p+1,1)V') = gap(Γ(RU))

结合 ① 便有 gap(RU) = gap(U)。

综上，有 gap(RU) = gap(U)，由 U 的一般性有 gap(RUL) = gap(UL)。

用类似的方法可证明 gap(UL) = gap(U)。

 

以下证明特性 10：

任意改变纯值对序列 U 的左界或右界值，得到的序列 V 必然满足 gap(U) = gap(V)。

证明：若 U 只含有一个值对，即 U = [p,q)，由于 gap(U) = 0 可知结论显然成立。现假定 U = [p,q)X，X 为纯值对序列。记 M = [p+1,q)X，N = [1,q)X，来证明 gap(M) = gap(N)。

当 q = 1 时，由特性 15 显然有 gap(M) = gap(N) = gap(X)。

当 q > 1 时，M = [p+1,q)X >> [p,1)[1,q-1) Γ(X)，N = [1,q)X >> (1)[1,q-1)Γ(X)

对比 Γ(M) 和 Γ(N) 可知，gap(M >> Γ(M)) = gap(N >> Γ(N))；而由特性 15 又有

gap(Γ(M)) = gap([1,q-1)Γ(X)) = gap(Γ(N))，于是有 gap(M) = gap(N)。

综上证得：对任意的 纯值对序列 X 以及任意 p > 0，q > 0，总有 gap([p+1,q)X) = gap([1,q)X)。即任意改变纯值对序列 U 的左界值，得到的序列 V 必然满足 gap(U) = gap(V)。

同样的方法可以证明：任意改变纯值对序列 U 的右界值，得到的序列 V 必然满足 gap(U) = gap(V)。

 

这篇关于偏序序列变换规律再探的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！