等价E-紧致度量空间上的迪尼定理

理论计算机科学电子笔记120（2005）73-82www.elsevier.com/locate/entcsE-紧致度量空间上的E-等价Dini加茂博康1部奈良女子大学理学部信息情报科学研究科日本奈良摘要本文证明了在等价紧致度量空间上，若实值函数的可计算序列逐点单调收敛于可计算函数，则该序列等价一致收敛于该函数.这是迪尼定理的一个简化版本关键词：Dini1介绍如果紧致空间上的一列实值连续函数逐点单调收敛到一个连续函数，则该序列一致收敛到该函数。它被称为迪尼从可计算性的观点出发，问题是：我们是否能将Dini本文在度量空间的情形下给出了这个问题的一个肯定回答，更确切地说，给出了一个定理：如果一个可计算的实值函数序列在一个连续紧度量空间上，1电子邮件地址：wd@ics.nara-wu.ac.jp1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2004.06.03574H. Kamo/Electronic Notes in Theoretical Computer Science 120（2005）73KS∈ S1n单调逐点收敛到一个可计算函数，则序列一致收敛到该函数。同时，如果一个可计算的实数序列单调收敛到一个可计算的实数，那么这个序列也单调收敛到这个实数。这就是所谓的单调收敛定理[6]。本文的主要定理不仅是Dini定理的推广，单调收敛定理推广到等价紧度量空间上的实值连续函数。单调收敛定理被认为是我们定理在C（{0}）上的一个特例，C（{ 0}）是 所有的实值连续函数在一个singlton。2预赛对 于 一 个 关 系 S<$X1×···×Xm×Y1×···×Yn 和 一 个 元 组 （ x1 ， . ， xm ）∈X1×···×Xm，则集合{（y1，.，y n）∈Y1×·· ·×Y n|（x1，.，x m，y1，.，yn）∈S}表示为S（x1，.，x m）。我们固定了一些标准的元组函数和相应的投影函数，关于N。 ... 表示n元组函数.(-)n表示核心，响应第k个投影函数。我们经常识别一个n元组序列（xk1，.，kn），其序列化（x（k）n，...，（k）n）k∈N。我们使用Pour-El和Richards在[6]中使用的关于实数和实函数的可计算性的术语和符号以下四个定义是由Yasugi，Mori和Tsujii在[9]中引入的。定义2.1设（M，d）是度量空间。一个集合Mω是（M，d）上的一个可计算结构，如果以下三个条件成立。(i) 如果（xn），（yn），则（d（xn，ynJ））n，nJ构成一个可计算的实数二重序列。(ii) 若（xn）∈ S且σ：N→N是递归函数，则（xσ（n））∈S.(iii) 如果（xn ，k）∈S，（ xjn ）∈Mω ，且nd（xn ，k）∈N，则（ XNJ）∈E∈N当k→ ∞时，则（xjn）∈ S.S中的一个元素称为M中的一个可计算序列。定义2.2具有可计算结构（M，d，S）的度量空间是等价全有界的，如果存在可计算序列（el）∈ S和递归函数γ：N→N，使得γ（i）M ={e 1|l ∈ N}和（εi∈N）M =B（el，1/2 i）.l=零H. Kamo/Electronic Notes in Theoretical Computer Science 120（2005）7375S⊂|SS→l=零γiMKKKL2我K（M，d，）是等价紧的，如果它是等价全有界的，且d是完备度量.定义2.3设（M，d，）是具有可计算结构的度量空间。 子集KM是M的等价紧子集，如果（K，dK，K ω）是等价紧度量空间。换句话说，K是（M，d，S）的一个等价紧子集，它是（M，d）的一个紧子集，并且存在一个可计算序列（el）∈ S和一个递归函数γ：N→N，使得γ（i）K ={e 1|l ∈ N}和（εi∈N）K ∈B（el，1/2 i）.l=零定义2.4设（M，d，S）是等价紧度量空间。一个函数序列（fn）fn：MR是可计算的，如果下面两个条件成立.(i) 对于M中的任何可计算序列（xk），（fn（xk））n，k形成实数的可计算序列。(ii) （E-一致连续性）存在递归函数α：N2→N使得对任意n，j∈N和任意x，y∈M，d（x，y）<1/2 α（n，j）= π |f n（x）− f n（y）|<1/2 j.一个函数f：M→R是一个可计算函数，如果（f）n∈N，其所有元素都等于f的序列是一个可计算函数序列定义2.4（ii）中的递归函数α称为（fn）的有效连续模3等效Dini首先，我们展示了两个命题，没有关于可计算性的假设。命题3.1设（M，d）是度量空间。设K∈M是一个非空紧子集，（el）∈Mω，γ：N→N使得K ={el|l∈N}和（εi）K ∈B（el，1/2）.然后，对于任意有限个开球序列（B（x k，r k））k=0，.，m，以下成立：KB（x，r）<$k（i）（i≤γ（i））（k≤m）d（x，e）+1k=0fn（x），我们得到fn（el）−1/ 2j>c−r。所得到的两个不等式的合取意味着（n，c，r，l，α（n，j））∈S.因此，x∈B（el，1/ 2i），对于某些（l，i）∈S（n，c，r）。这说明[（ii）（i）]（序列可计算性）假设（xk）。从（ii），我们获得|1/ 2 <$（n，c，1 / 2，l，i）∈ S <$d（x k，el）1 / 2 ].|<1/2⇐⇒ (∃l)(∃i)[(n, c, 1/2, l, i) ∈ S ∧ d (x k, e l) <1/2].因此{（n，k，j，c）∈N×N×N×Q||f n（x k）−c|<1/2 j}是一个递归可重集。同时，（n）（k）（j）（cQ）fn（xk）c1/ 2j成立，因为Q在R中稠密。因此，存在一个可计算的有理数三元序列（c n，k，j），使得（nn）（nk）（nj）|f n（x k）−c n，k，j|<1/2 j，即，（fn（xk））n，k是可计算的双实数序列。（等价一致连续）利用命题3.2，我们得到：B（el，1/ 2i）=lJ，iJ∈N，d（el，elJ）+2/2iJ1/2iB（e lJ，1/2）。显然d（el，ELJ）+ 2/ 2ij 1/ 2i是l，i，LJ，IJ的递归可重谓词。<同样清楚的是，（l）（i）（lJ）（iJ）d（el，elJ）+ 2/ 2iJ 1/ 2i成立。<因此存在H. Kamo/Electronic Notes in Theoretical Computer Science 120（2005）7379递归函数σ，ρ：N3→N使得对任意l，i∈N，{（l，i，lJ，iJ）∈ N × N × N × N |d（e l，e lJ）+2/2 iJ<1/2 i}={（l，i，σ（l，i，k），ρ（l，i，k））|k ∈ N}。80H. Kamo/Electronic Notes in Theoretical Computer Science 120（2005）73Jρ（n，j，k）j+1j+1B（eσ（σJ（n，j，（k）2），ρJ（n，j，（k）2），（k）2），1/ 2112）的情况。112因此，对于任何l，i∈N，∞B（el，1/ 2i）=B（eσ（l，i，k），1/ 2ρ（l，i，k））（1）k=0和（εk）d（el，e σ（l，i，k））+ 2/2 ρ（l，i，k）<1/2 i.（二）由于S是一个递归可重集，所以{（n，j，l，i，c）∈N×N×N×N×Q| （n，c，1/2 j+1，l，i）∈ S}. 另一方面，由于M =c∈Qfn−1（（c−1/2j+1，c+1/2j+1）），它保持t帽M=B（e l，1/2 i）。c∈Q（l，i）∈S（n，c，1/ 2j+1）因此（n）（nj）（nl）（ni）（nc∈Q）（n，c，1/ 2j+1，l，i）∈S.因此，存在递归函数σJ，ρJ： N3→N和一个可计算的有理数三元序列（cn，j，k）使得对任意n，j∈N，{（n，j，l，i，c）∈ N × N × N × Q|（n，c，1/2 j+1，l，i）∈ S}={（n，j，σJ（n，j，k），ρJ（n，j，k），c n，j，k）|k ∈ N}。对于任何n，j∈N，∞M=B（eσJ（n，j，k），1/ 2ρJ（n，j，k））（3）k=0和（k）f n（B（e σJ（n，j，k），1/2））<$（c n，j，k−1/2，c n，j，k+1/2）.（4）从（1）和（3），我们得到∞ρ（σJ（n，j，（k）2），ρJ（n，j，（k）2），（k）2）k=0应用引理3.3得出存在递归函数γ：N2→N，使得M=H. Kamo/Electronic Notes in Theoretical Computer Science 120（2005）7381B（eσ（σJ（n，j，（k）2），ρJ（n，j，（k）2），（k）2），1/ 2112）的情况。112γ（n，j）ρ（σJ（n，j，（k）2），ρJ（n，j，（k）2），（k）2）k=0M=82H. Kamo/Electronic Notes in Theoretical Computer Science 120（2005）7311111111121121112设α：N2→N是一个递归函数，定义为α（n，j）=maxρ（σJ（n，j，（k）2），ρJ（n，j，（k）2），（k）2）.k≤γ（n，j）1 1 2设点x，y∈M满足d（x，y）1/ 2α（n，j）.< 那么存在着一些k≤γ（n，j），使得ρ（σJ（n，j，（k）2），ρJ（n，j，（k）2），（k）2）d（x，eσ（σJ（n，j，（k）2），ρJ（n，j，（k）2））1/ 2<112.1 1 2有了这样的k，d（x，eσJ（n，j，（k）2））≤d（eσJ（n，j，（k）2），eσ（σJ（n，j，（k）2），ρJ（n，j，（k）2））+d（x，eσ（σJ（n，j，（k）2），ρJ（n，j，（k）2），（k）2））ρ（σJ（n，j，（k）2），ρJ（n，j，（k）2），（k）2）

下载后可阅读完整内容，剩余1页未读，立即下载