W—度与T—度的结构差别（Ⅱ）

§1 介绍与基本概念最近,许多文章讨论r.e。集合的T-度与W-度之间的结构差别,例如Lerman和Remmel讨论USP性质以及UWP性质。1985年Downey证明每个度中都存在一个r.e。集合具有～USP和～UWP性质,并且猜想除contiguous度和完备度以外,所有度不包含具有USP(UWP)性质的r.e.集合。如果这样的话,contiguous集合具有的结构性质,具有USP性质的集合也应该具有。我们这里只讨论一种结构性质。Ambos,Spies和Fejer[ta]证明contiguous度在低度中     

wtt-度的 Nonbounding 定理

本文用“魔怪方法”证明了对任何一个低的 r.e.集 D,存在一个 r.e.集C,使得 D<_(wtt)C,且对任何 r.e.集 A,B,如果 A≤_(wtt)C,B≤_(wtt)C,A(?)_(wtt)D,B(?)_(wtt)D,则 deg(A)∩deg(B)≠(?).此处 deg(A),deg(B)分别表示 A,B 的 wtt-度.     

等度和不等度的结构及在P-T度下集合的分离性质

ξ0.引言 P=NP?是计算复杂性中的主要问题。自从Cook和Karp引进P-T归约和P-T度的概念后,人们在这方面作了大量研究。另外,Baker,Gill和Solovay证明了存在集合A和B,使得P(A)=NP(A)和P(B)≠NP(B),从而开始了相对复杂性的研究。最近,杨竞辉将P-T度结构和相对复杂性结合起来,提出等度和不等度的概念,并得到了一些结果。本文在此基础上,进一步讨论等度和不等度的结构。     

递归集的k-1-度上半格的不可补性与不可分配性

我们在[11]中证明了多项式时间强图灵归约≤_(sn)T 与多项式时间多一归≤_(pm)有表现在完全集上的本质差别,在本文中我们证明了递归集的≤_(sn)T-归约约度上半格〈(?)_k~1;≤〉不可分配,籍此得〈(?)_k~1;≤〉与〈(?)_m~p;≤〉不同构.这表明此二种归约有表现在其度结构上的差别.此外,使用对角线技术我们还证明了〈(?)_k~1;≤〉的某些初始片段不可补.     

每一个Cappable度都有ω个两两组成最小对的r.e.度与之组成最小对

本文证明了,对任意Cappable度α-deg(W_i),b=deg(W_i)可以一致地找到r.e.度c=deg(W_(f(i,f)))使得a∩ c=b∩c=0这里f(x,y)是一个递归函数.进而,本文证明了,对任意Cappable度a=deg(W_e),ω个r.e.度b_i=deg(W_(f(e,t)))可以一致地找到,使得a∩b_i=0,i∈ω.这里f(x,y)也是递归函数.在证明中用到了Lachlan提出的树形构造和gap-cogap方法.要确定真路径f,需要0的外部信息源.     

有关递归不可分集的几个结果

本文在递归不可分理论方面得到一些结果。 1.对任意给定的非递归r.e.度,均存在r.e.集,A是有丝分裂集且可分裂的两集可要求为递归不可分的r.e.集。 2.对任意高r.e.集C和任意非递归r.e.集D,均存在递归不可分的r.e.集A,B满足A其高度,B具低度,C≤_TA,φ<_TB≤_TD。 3.存在r.e.集A,B,C,D满足(1)A,B递归不可分且形成极小对,(2)A\B,A\D,C\B,C\D,(3)A<_TC,B<_TD,(4)A,B具低度,(5)C,D具高度。     

在d-r.e.度结构中真d-r.e.分支度的弱稠密性 *

证明了对任意r.e .度v相似文献   

递归可枚举度的强分解定理

本文将证明,对任 r.e.度(?),存在 r.e.度(?),(?),(?),和(?)使得(?)<(?),(?)<(?),(?)<(?)≤(?),(?)∪(?)=(?),(?)∩(?)=(?)且对任 r.e.度(?),如果(?),那么(?)∩(?).这结果的一个立即推论是,对任 r.e.度(?),存在(?)<(?)使[(?)]中一切(?)-cappable 度不作成理想.同时可推出:对任 r.e.度(?),存在 r.e.度(?),(?)和(?)使得(?)∪(?)=(?),(?)∩(?)=(?)且对任 r.e.度(?)有(?).这是 r.e.度分解的一个临界性结果.     

关于极限引理的一些应用

本文首先推广定义 n-可加速集,给出 n-非可加集与 n-低度之间的关系.证明 r.e.度(?)使得存在 r.e.n-可加速集 A≡_n(?)当且仅当(?)~(n)>(?)~(n).然后运用极限引理到 H_n 的描述中,证明 r.e.度(?)包含一个 n-极大集 A≡_n(?)当且仅当(?)∈H_n,i.,e.(?)~(n)≥(?)~(n+1)且(?)∈H_n 当且仅当存在一个度≤(?)的函数 f,n-do-minate 每个递归函数.     

低R.E度上D.R.E.度的非稠密性

本文用 O′′′优先损害方法证明了在 d.r e.度中任何低的递归可枚举度 l 之上存在一个非稠密区间,即存在 d.r.e.度 d,l相似文献   

低R.E度上D.R.E.度的非稠密性

本文用O(?)优先损害方法证明了d.r e.度中任何低的递归可枚举度ι之上存在一个非稠密区间,即存在d.r.e.度d,ι相似文献   

收缩临界6连通图的6度顶点

利用断片的性质,改进了齐恩凤,齐登记等的研究结果,得到了收缩临界6-连通图中6度点的性质的新结果:设x是G中任意一点,设A是一个x-原子,记N_A=T_A,N(x)∩T_A≠Φ,则A∩T_A中有与x相邻的6度点或两点的距离为2.     

集合的概念与运算

集合是数学中的重要概念之一,在中学数学竞赛中,许多本质上属于代数、几何、数论、组合的问题都可以用集合的观点和方法来解决,局部与整体的观点是其思想实质.一般地,某些指定的对象集中在一起就成为一个集合,集合中的每个对象叫做这个集合的元素.常用描述法表示集合,S={x|x具有性质P}表示所有具有性质P的对象组成的集合S.集合的运算中,除了交、并运算外,还有补运算和差运算.对于A、B两个集合,由所有属于A但不属于B的元素构成的集合称为A关于B的差集,记作A\B,即A\B={x|x∈A,且x B}关于集合的运算满足如下关系式:(1)交换律:A∩B=B∩A…     

一道2019年斯坦福大学数学竞赛题的多解及推广

<正>题目已知集合S={1,2,3,4,5,6,7,8},A,B均为集合S的子集.试问共有多少个不同的集合对(A,B),使得A是B的真子集?本题难度不大,但讨以从多个角度进行思考,进而推广到更一般的情况.解法1设集合A有k个元素(k=0,1,2,3,4,5,6,7),则集合B的个数为2~(8-k)-1.因此,满足题目条件的集合对(A,B)的个数为:     

集合与简易逻辑

1.1　集合的概念及元素的特征内容概述1.集合通常用列举法、描述法表示 ,有时还用特定记号法、图示法、区间法来表示 .2 .非空集合中的元素具备确定性、互异性、无序性等特征 .3.含有 n个元素的集合共有 C0n C1n C2n … Cnn =2 n个子集 ,2 n - Cnn=2 n- 1个真子集 ,2 n -C0n - Cnn =2 n - 2个非空真子集 .4 .两个集合的交、并、补运算方法是定义法、韦恩图法、数轴法 .两个易错的常用的习题结论是CU( A∩ B) =( CUA)∪ ( CUB) ,CU( A∪ B) =( CUA)∩ ( CUB) .5 .运算特例 :( 1) CAA = ,　 CA =A,CU( CUA) =A,　 A∩…     

极小k边连通图的一个极值问题

本文只讨论单纯图。所有符号的意义均同于[2]。依照[1]给出定义 如图 G=(V,E)具有性质:λ(G)=k,而对(?)e∈E 均有λ(G-e)=k-1,则称 G 为极小 k 边连通图。设已给图 G=(V,E),如果 A,B(?)V,且 A∩B=φ,则记[A,B]={xy↓x∈A,y∈B,xy∈E}。如果 S(?)E,|S|=k,且 G-S=G_1 U G_2 V(G_1)∩V(G_2)=φ,V(G_1)≠φ,     

保持算子乘积谱函数的映射

设A和B为无限维复Banach空间上的标准算子代数,记ΔR(·)为下列谱函数之一σR(·),σRl(·),σRr(·),σRl(·)∩σRr(·),(a)σR(·),ησR(·),σRp(·),σRc(·),σRap(·),σRs(·),σRap(·)∩σRs(·),σRp(·)∩σRc(·),σRp(·)∪σRc(·),其中R=A或B.证明了A和B之间的每个保持算子Jordan三乘积(算子乘积)之谱函数ΔR(·)的满射φ必有形式φ=επ,其中ε是1的立方根(1的平方根)而π或者是A和B之间的代数同构,或者是代数反同构.也获得不定度规空间上的标准算子代数之间保持算子斜乘积之谱函数的映射的完全刻画.     

关于2可逆的置换可分环（英文）

环R称为可分环,如果对任何有限生成投射右R-模A和B,AA≌AB≌BBA≌B.假设R是置换可分环,其中2可逆,a-a~3∈R正则,证明了a∈R单位正则当且仅当R(1-a~2)R=Rr(a)=e(a)R.环R中元素a称为特殊clean元,如果有幂等元e∈R使得a-e∈R可逆,而且aR∩eR=0.进一步,证明了a∈R是特殊clean元,如果aR/ar(a~2),R/(aR+r(a))投射,而且R(a-a~3)R=Rar(a~2)=e(a~2)aR.由此推广了正则可分环中相关结论.     

与小魔群B有共同本原置换表示次数的有限群

本文研究小魔群B的极大子群的指数对群的结构的影响.设G是有限群,πt(G)和πt(B)分别表示G和B的极大子群的指数集,s26=[BM11].设πt(B)∩πt(G)≠φ,对任意s∈πt(B)∩πt(G),如果s≠s26,那么G与B或As同态;如果s=s26,那么G与B或A1(s26-1)或As同态.     

浅淡公式rkAB＝rkB—dim（R（B）∩N（A）的应用

本文的目的是给出有关矩阵乘积的秩的一个等式.然后据此研究一系列秩数问题.定理若矩阵A与B可乘,则rkAB=rkB—(dimR(B)∩N(A)) (1) =rkA—dim(R(A′)∩N(B′)) (1′)其中R(B)是B的值域,N(A)是A的零空间;rkA记A的秩,dimR(B)记只(B)的维数.