偏序序列变换规律再探

2021/7/20 23:21:49

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

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

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

偏序序列 U = (a) H [b],其中 H 为纯值对子序列,若 H = S1S2...Sh,其中 Si (i=1,...,h)为纯值对子序列,且满足以下条件:

I. F(Γ(Si)) = F(Si) - 1, i=1,...,h;

II. left(S1) ≥ 1;

III. left(Si) ≥ 2, i≠1;

IV. right(Si) ≥ 2, i≠h;

V. right(Sh) ≥ 1。

则称 H 从左至右被划分成 h 个堡垒子序列(简称堡垒)S1、S2、...、Sh 。相应引入:

堡垒数函数 forts(U) = forts(H) = h,堡垒函数 fort(U,i) = Si, i=1,...,forts(U),首堡垒函数 hfort(U) = S1尾堡垒函数 tfort(U) = Sh

再引入单次变换的跳变数函数 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 个序列 U1、U2、...、Un,满足 Ui >> Ui+1,i=1,...,n-1,且 Un 为规范序列,并记 gi = gap(Ui >> Ui+1),i=1,...,n-1。则有 gap(Uk) = Σgi: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) 单独划分为堡垒 S1,此时必有 h > 1,left(S1) = 1,rights(S1) = 2,符合条件,但是S2 的第一个值对为 [1,3),于是有 left(S2) = 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)

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

S1 = [1,3),S2 = [2,4),S3 = [3,1)[2,1)[1,5)[1,3),S4 = [4,2),S5 = [3,1)

其中打头的 S1 为左一序列,是左开右闭堡垒;末尾的 S5 为右一序列,是左闭右开堡垒;中间的 S2、S3、S4 都是全封闭的堡垒(即左右界都大于 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 的基础上加入了一些值对(如黄色标注部分)。

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

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

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

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

从这个例子可以看出:

右开放堡垒基可以放到一个封闭堡垒的左侧,从而扩充成一个新的封闭堡垒,称为封闭堡垒的左侧扩充,如 [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,qt)...[1,q2)[1,q1) 和 R = [p1,1)[p2,1)...[ps,1) 的拼接序列 LR 满足 gap(LR) = min{game(L), game(R)}。当接合位置的 q1 和 p1 都大于 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 = L1R1 L2R2 ... LkRk,k > 0,且 left(Ri) > 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 = L1R1 L2R2 ... LkRk 从左至右划分为 t 个堡垒,记为 M = S1S2...St

第一个堡垒 S1 的确定方法如下:

考察第一个 LR 型序列,若 L1R1 是不连通的,则有 S1 = L1,确定完成;否则,考察下一个 LR 型序列,即若 L2R2 是不连通的,则有 S1 = L1R1L2,确定完成;否则,考察下一个 LR 型序列,由 k 为有限数,总能确定 S1,如果 M 中每个 LR 型序列都是连通的,则 M = S1(即 t = 1)。

确定 S1 之后,M 中还有剩余的子序列没有被划分为堡垒,则继续用确定 S1 的方法依次去确定 S2、...、St

如果 t > 1,易知只有 St 是以一个 R型序列结尾的,且有 St = RpLp+1Rp+1...Lk-1Rk-1LkRk,p ≤ k(当 p = k 时,有 St = Rk),而 Si = RdLd+1...Rq-1Lq,d ≥ 0,q > d,i ≠ t(当 d = 0 时,i = 1,且 R0 代表空序列,即有 S1 = L1R1L2R2...Lq-1Rq-1Lq,当 q = 1 时,有 S1 = L1)。

考察 M 的首堡垒 S1 = L1R1L2R2...Lq-1Rq-1Lq 的变换特性,其中的 q-1 个 LR 型序列都是连通的,由上述的 E 值对归属约定,可设 Li = L'iE, i=1,...,q-1,再设 Lq = [1,p1)...[1,ph),于是 

S1 = L'1ERL'2ER... L'q-1ERq-1 Lq >> (1) L'1R1E L'2R2E ... L'q-1Rq-1E L'q

其中 L'q = [1,p1)...[1,ph-1)

从 S1 到 Γ(S1),从效果上看,相当于每个连通的 LiRi 中 Li 末尾的 E 被移到了 Ri 的末尾(i=1,...,q-1),其余的部分则简化为 Lq >> (1) L'q。令 R'i = RiE, i=1,...,q-1,则 S1 >> Γ(S1) 可表达为

S1 = L1R1L2R2...Lq-1Rq-1Lq >> (1) L'1R'1L'2R'2...L'q-1R'q-1L'q 

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

  

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

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

对 M = L1R1 L2R2 ... LkRk 沿用上述方法从左至右划分为 t 个堡垒,即 M = S1S2...St,于是

ML = SS... StL,RML = RSS... StL

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

fort(ML,i) = Si, i=1,...,t-1,fort(ML,t) = StL

fort(RML,1) = RS1,fort(RML,i) = Si, i=2,...,t-1,fort(RML,t) = StL

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

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

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

Γ(ML) = Γ(S1) Γ(S2) ... Γ(St-1)Γ(StL)

Γ(RML) = Γ(RS1) Γ(S2) ... Γ(St-1)Γ(StL)

以下分情形讨论:

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

ML = L1R1...LkRkL >> (1) L'1R'1...L'kR'kL' 

RML = RL1R1...LkRkL >> (d)R'EL'1R'1...L'kR'kL' 

其中,Li = L'iE,R'i = RiE,(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'1R'1...L'kR'kL',易知 gap(Γ(ML)) = gap(X)

记 Y = Γ(RML),若 X 被划分为 a 个堡垒:X1...Xa,则由 Y = R'EX 可知,Y 也一定被划分为 a 个堡垒:Y1...Ya,且有 Y1 = R'EX1,Yi = Xi, 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,则有

X1 = L'1R'1...L'q-1R'q-1L'q,1 ≤ q ≤ k(当 q = 1 时,X1 = L'1

Y1 = R'EX1 = R'EL'1R'1...L'q-1R'q-1L'q,1 ≤ q ≤ k(当 q = 1 时,X1 = L'1

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

X' = Γ(X1)Γ(X2) ... Γ(Xa)

Y' = Γ(Y1)Γ(X2) ... Γ(Xa)

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

Γ(X1)  = (1) L''1R''1...L''q-1R''q-1L''q

Γ(Y1) = Γ(R'EX1) = Γ(R'E) Γ(X1) = (d)R''[1] Γ(X1)

= (d)R''EL''1R''1...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 = Γ(Xi),Y'i = Γ(Yi),i=1,...,a,易知:

X' = X'1 X'2 ... X'a,Y' = Y'1 X'2 ... X'a

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

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 型序列 RxLx 时,RML 也一定经同样次数的变换后成为泛 RL 型序列 RyLy,尽管 F(RyLy) > F(RxLx),但总有 g(RyLy) = g(RxLx) = 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)E2 [1,4)[3,1)[2,1)E2 [1,2)[1,1)[1,3)  ③ // forts = 3,gap(③ >> ④) = 2

 >> (3) [1,2)[1,3)[2,1)[3,1)E3 [1,3)[2,1)[2,1)E3 [1,2)[1,1)[1,2)  ④ // forts = 3,gap(④ >> ⑤) = 2

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

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

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

 >> (7) [1,2)[2,1)E14 [1,1)[1,1) [2]  ⑧ // forts = 2,gap(⑧ >> ⑨) = 1

 >> (8) [1,1)[1,1)E14 [1,1)[1,1) [3]  ⑨ 

由上述 ML 的连续变换过程可以看出,8 次变换后得到序列 ⑨ = (8) E18 [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)E2 [1,2)[1,4)[3,1)[3,1)E2 [1,4)[3,1)[2,1)E2 [1,2)[1,1)[1,3)  ③' // forts = 3,gap(③' >> ④') = 2

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

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

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

 >> E2[3,1)E6 [1,2)[1,1)[2,1)E6 [1,1)[1,1)E6 [1,2) [2]  ⑦' // forts = 1

 >> (1) E[3,1)E7 [1,2)[2,1)E14 [1,1)[1,1) [2]  ⑧' // forts = 2,gap(⑧' >> ⑨') = 1

 >> (2) [3,1)E8 [1,1)[1,1)E14 [1,1)[1,1) [3]  ⑨'

由上述 RML 的连续变换过程可以看出,8 次变换后得到序列 ⑨' = (2) [3,1)E26 [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)。

 



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


扫一扫关注最新编程教程