ScholarBank@NUShttps://scholarbank.nus.edu.sgThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Thu, 12 Sep 2024 06:02:32 GMT2024-09-12T06:02:32Z50241- The members of thin and minimal ?<inf>1</inf>0 classes, their ranks and Turing degreeshttps://scholarbank.nus.edu.sg/handle/10635/123266Title: The members of thin and minimal ?<inf>1</inf>0 classes, their ranks and Turing degrees
Authors: Downey, Rod G.; Wu, Guohua; Yang, Yue
Thu, 01 Jan 2015 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1232662015-01-01T00:00:00Z
- There exists a maximal 3-C.E. enumeration degreehttps://scholarbank.nus.edu.sg/handle/10635/104372Title: There exists a maximal 3-C.E. enumeration degree
Authors: Cooper, S.B.; Li, A.; Sorbi, A.; Yang, Y.
Abstract: We construct an incomplete 3-c.e. enumeration degree which is maximal among then-c.e. enumeration degrees for everyn with 3 ≤ n ≤ ω. Consequently then-c.e. enumeration degrees are not dense for any suchn. We show also that no lown-c.e. e-degree can be maximal among then-c.e. e-degrees, for 2 ≤ n ≤ ω. © 2003 Hebrew University.
Mon, 01 Dec 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1043722003-12-01T00:00:00Z
- Properly Σ 2 minimal degrees and 0″ complementationhttps://scholarbank.nus.edu.sg/handle/10635/103979Title: Properly Σ 2 minimal degrees and 0″ complementation
Authors: Cooper, S.B.; Lewis, A.E.M.; Yang, Y.
Abstract: We show that there exists a properly Σ 2 minimal (Turing) degree b, and moreover that b can be chosen to join with 0′ to 0″ - so that b is a 0″ complement for every degree a such that 0′ ≤ a < 0″. © 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.
Sat, 01 Jan 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1039792005-01-01T00:00:00Z
- Properly Σ2 0 enumeration degrees and the high/low hierarchyhttps://scholarbank.nus.edu.sg/handle/10635/103980Title: Properly Σ2 0 enumeration degrees and the high/low hierarchy
Authors: Giorgi, M.; Sorbi, A.; Yang, Y.
Abstract: We show that there exist downwards properly Σ2 0 (in fact noncuppable) e-degrees that are not high. We also show that every high e-degree bounds a noncuppable e-degree. © 2006, Association for Symbolic Logic.
Fri, 01 Dec 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1039802006-12-01T00:00:00Z
- Π11-conservation of combinatorial principles weaker than Ramsey's theorem for pairshttps://scholarbank.nus.edu.sg/handle/10635/104487Title: Π11-conservation of combinatorial principles weaker than Ramsey's theorem for pairs
Authors: Chong, C.T.; Slaman, T.A.; Yang, Y.
Abstract: We study combinatorial principles weaker than Ramsey's theorem for pairs over the RCA 0 (recursive comprehension axiom) system with σ20-bounding. It is shown that the cohesiveness (COH), ascending and descending sequence (ADS), and chain/antichain (CAC) principles are all Π11-conservative over σ20-bounding. In particular, none of these principles proves σ20-induction. © 2012 Elsevier Ltd.
Wed, 20 Jun 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1044872012-06-20T00:00:00Z
- Σ2 induction and infinite injury priority arguments, Part II Tame Σ2 coding and the jump operatorhttps://scholarbank.nus.edu.sg/handle/10635/104488Title: Σ2 induction and infinite injury priority arguments, Part II Tame Σ2 coding and the jump operator
Authors: Chong, C.T.; Yang, Y.
Mon, 15 Sep 1997 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1044881997-09-15T00:00:00Z
- Diamond embeddings into the enumeration degreeshttps://scholarbank.nus.edu.sg/handle/10635/104557Title: Diamond embeddings into the enumeration degrees
Authors: Sorbi, A.; Wu, G.; Yang, Y.
Abstract: We show that the diamond lattice can be embedded into the Σ02 enumeration degrees preserving 0 and 1, with atoms one high and ∏01, and the other one low. © 2010 Cambridge University Press.
Fri, 01 Oct 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1045572010-10-01T00:00:00Z
- The minimal e-degree problem in fragments of Peano arithmetichttps://scholarbank.nus.edu.sg/handle/10635/104316Title: The minimal e-degree problem in fragments of Peano arithmetic
Authors: Arslanov, M.M.; Chong, C.T.; Cooper, S.B.; Yang, Y.
Abstract: We study the minimal enumeration degree (e-degree) problem in models of fragments of Peano arithmetic (PA) and prove the following results: in any model M of Σ2 induction, there is a minimal enumeration degree if and only if M is a nonstandard model. Furthermore, any cut in such a model has minimal e-degree. By contrast, this phenomenon fails in the absence of Σ2 induction. In fact, whether every Σ2 cut has minimal e-degree is independent of the Σ2 bounding principle. © 2004 Elsevier B.V. All rights reserved.
Sat, 01 Jan 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1043162005-01-01T00:00:00Z
- The jump of a Σn-cuthttps://scholarbank.nus.edu.sg/handle/10635/104309Title: The jump of a Σn-cut
Authors: Chong, C.T.; Yang, Y.
Abstract: Let n≥1. We study the proof-theoretic strength of jump classes of the Turing degrees from the point of view of fragments of Peano arithmetic. By investigating the jump of a Σn definable cut in a model of Δn-induction, we show that over the base theory PA- + Δn-induction, the existence of a non-trivial lown Turing degree is equivalent to Σn-induction. © 2007 London Mathematical Society.
Fri, 01 Jun 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1043092007-06-01T00:00:00Z
- The existence of high nonbounding degrees in the difference hierarchyhttps://scholarbank.nus.edu.sg/handle/10635/104292Title: The existence of high nonbounding degrees in the difference hierarchy
Authors: Chong, C.T.; Li, A.; Yang, Y.
Abstract: We study the jump hierarchy of d.c.e. Turing degrees and show that there exists a high d.c.e. degree d which does not bound any minimal pair of d.c.e. degrees. © 2005 Elsevier B.V. All rights reserved.
Wed, 01 Mar 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1042922006-03-01T00:00:00Z
- On differences among elementary theories of finite levels of Ershov hierarchieshttps://scholarbank.nus.edu.sg/handle/10635/104599Title: On differences among elementary theories of finite levels of Ershov hierarchies
Authors: Yang, Y.; Yu, L.
Abstract: We study the differences among elementary theories of finite levels of Ershov hierarchies. We also give a brief survey on the current state of this area. Some questions are raised. © Springer-Verlag Berlin Heidelberg 2006.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1045992006-01-01T00:00:00Z
- Selection by recursively enumerable setshttps://scholarbank.nus.edu.sg/handle/10635/104624Title: Selection by recursively enumerable sets
Authors: Merkle, W.; Stephan, F.; Teutsch, J.; Wang, W.; Yang, Y.
Abstract: For given sets A, B and Z of natural numbers where the members of Z are z0, z1,⋯ in ascending order, one says that A is selected from B by Z if A(i) = B(zi) for all i. Furthermore, say that A is selected from B if A is selected from B by some recursively enumerable set, and that A is selected from B in n steps iff there are sets E0, E1,⋯, En such that E0 = A, En = B, and Ei is selected from Ei+1 for each i < n. The following results on selections are obtained in the present paper. A set is ω-r.e. if and only if it can be selected from a recursive set in finitely many steps if and only if it can be selected from a recursive set in two steps. There is some Martin-Löf random set from which any ω-r.e. set can be selected in at most two steps, whereas no recursive set can be selected from a Martin-Löf random set in one step. Moreover, all sets selected from Chaitin's Ω in finitely many steps are Martin-Löf random. © Springer-Verlag Berlin Heidelberg 2013.
Tue, 01 Jan 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1046242013-01-01T00:00:00Z
- Bounding computably enumerable degrees in the Ershov hierarchyhttps://scholarbank.nus.edu.sg/handle/10635/102949Title: Bounding computably enumerable degrees in the Ershov hierarchy
Authors: Li, A.; Wu, G.; Yang, Y.
Abstract: Lachlan observed that any nonzero d.c.e. degree bounds a nonzero c.e. degree. In this paper, we study the c.e. predecessors of d.c.e. degrees, and prove that given a nonzero d.c.e. degree a, there is a c.e. degree b below a and a high d.c.e. degree d > b such that b bounds all the c.e. degrees below d. This result gives a unified approach to some seemingly unrelated results. In particular, it has the following two known theorems as corollaries: (1) there is a low c.e. degree isolating a high d.c.e. degree [S. Ishmukhametov, G. Wu, Isolation and the high/low hierarchy, Arch. Math. Logic 41 (2002) 259-266]; (2) there is a high d.c.e. degree bounding no minimal pairs [C.T. Chong, A. Li, Y. Yang, The existence of high nonbounding degrees in the difference hierarchy, Ann. Pure Appl. Logic 138 (2006) 31-51]. © 2005 Elsevier B.V. All rights reserved.
Tue, 01 Aug 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1029492006-08-01T00:00:00Z
- Bounding and nonbounding minimal pairs in the enumeration degreeshttps://scholarbank.nus.edu.sg/handle/10635/102948Title: Bounding and nonbounding minimal pairs in the enumeration degrees
Authors: Cooper, S.B.; Li, A.; Sorbi, A.; Yang, Y.
Abstract: We show that every nonzero Δ2 0 e-degree bounds a minimal pair. On the other hand, there exist ∑2 0 e-degrees which bound no minimal pair. © 2005, Association for Symbolic Logic.
Thu, 01 Sep 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1029482005-09-01T00:00:00Z
- On the role of the collection principle for ∑2 0 -formulas in second-order reverse mathematicshttps://scholarbank.nus.edu.sg/handle/10635/103836Title: On the role of the collection principle for ∑2 0 -formulas in second-order reverse mathematics
Authors: Chong, C.T.; Lempp, S.; Yang, Y.
Abstract: We show that the principle PART from Hirschfeldt and Shore is equivalent to the ∑2 0 -Bounding principle B∑2 0 over RCA0, answering one of their open questions. Furthermore, we also fill a gap in a proof of Cholak, Jockusch and Slaman by showing that D2 2 implies B∑2 0 and is thus indeed equivalent to Stable Ramsey's Theorem for Pairs (SRT2 2 ). This also allows us to conclude that the combinatorial principles IPT 2 2 , SPT2 2 and SIPT2 2 defined by Dzhafarov and Hirst all imply B∑2 0 and thus that SPT2 2 and SIPT2 2 are both equivalent to SRT2 2 as well. Our proof uses the notion of a bi-tame cut, the existence of which we show to be equivalent, over RCA0, to the failure of B∑2 0 © 2009 American Mathematical Society.
Mon, 01 Mar 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1038362010-03-01T00:00:00Z
- On Σ1-structural differences among finite levels of the Ershov hierarchyhttps://scholarbank.nus.edu.sg/handle/10635/103858Title: On Σ1-structural differences among finite levels of the Ershov hierarchy
Authors: Yang, Y.; Yu, L.
Abstract: We show that the structure ℛ of recursively enumerable degrees is not a Σ1-elementary substructure of script Dn, where script Dn (n > 1) is the structure of n-r.e. degrees in the Ershov hierarchy. © 2006, Association for Symbolic Logic.
Fri, 01 Dec 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1038582006-12-01T00:00:00Z
- On the definable ideal generated by nonbounding c.e. degreeshttps://scholarbank.nus.edu.sg/handle/10635/103786Title: On the definable ideal generated by nonbounding c.e. degrees
Authors: Yu, L.; Yang, Y.
Abstract: Let [NB]1 denote the ideal generated by nonbounding c.e. degrees and NCup the ideal of noncuppable c.e. degrees. We show that both [NB] 1 ∩ NCup and the ideal generated by nonbounding and noncuppable degrees are new, in the sense that they are different from M, [NB]1 and NCup - the only three known definable ideals so far. © 2005, Association for Symbolic Logic.
Tue, 01 Mar 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1037862005-03-01T00:00:00Z
- Iterated trees and fragments of arithmetichttps://scholarbank.nus.edu.sg/handle/10635/103449Title: Iterated trees and fragments of arithmetic
Authors: Yang, Y.
Wed, 01 Mar 1995 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1034491995-03-01T00:00:00Z
- A rank one cohesive sethttps://scholarbank.nus.edu.sg/handle/10635/102742Title: A rank one cohesive set
Authors: Downey, R.G.; Yue, Y.
Abstract: In this paper, we prove that there is a Π0 1 class in 2ω with a unique nonrecursive member, with that member a cohesive set. This solves an open question from Cenzer (1993). The proof uses the Δ0 3 method in the context of the construction of a Π0 1 class. © 1994.
Fri, 15 Jul 1994 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1027421994-07-15T00:00:00Z
- A join theorem for the computably enumerable degreeshttps://scholarbank.nus.edu.sg/handle/10635/102663Title: A join theorem for the computably enumerable degrees
Authors: Jockusch Jr., C.G.; Li, A.; Yang, Y.
Abstract: It is shown that for any computably enumerable (c.e.) degree w, if w ≠ 0, then there is a c.e. degree a such that (a ∨ w)′ = a″ = 0″ (so a is low 2 and a ∨ w is high). It follows from this and previous work of P. Cholak, M. Groszek and T. Slaman that the low and low 2 c.e. degrees are not elementarily equivalent as partial orderings.
Thu, 01 Jul 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1026632004-07-01T00:00:00Z
- ∑2 induction and infinite injury priority arguments, part III: Prompt sets, minimal pairs and shoenfield's conjecturehttps://scholarbank.nus.edu.sg/handle/10635/102602Title: ∑2 induction and infinite injury priority arguments, part III: Prompt sets, minimal pairs and shoenfield's conjecture
Authors: Chong, C.T.; Qian, L.; Slaman, T.A.; Yang, Y.
Abstract: We prove that in every B∑2 model (one satisfies ∑2 collection axioms but not ∑2 induction), every recursively enumerable (r.e.) set is either prompt or recursive. Consequently, over the base theory ∑2 collection, the existence of r.e. minimal pairs is equivalent to ∑2 induction. We also refute Shoenfield's Conjecture in B∑2 models.
Mon, 01 Jan 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1026022001-01-01T00:00:00Z
- ∑2 Induction and infinite injury priority argument, Part I: Maximal sets and the jump operatorhttps://scholarbank.nus.edu.sg/handle/10635/102601Title: ∑2 Induction and infinite injury priority argument, Part I: Maximal sets and the jump operator
Authors: Chong, C.T.; Yang, Y.
Tue, 01 Sep 1998 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1026011998-09-01T00:00:00Z
- Computable categoricity and the Ershov hierarchyhttps://scholarbank.nus.edu.sg/handle/10635/103019Title: Computable categoricity and the Ershov hierarchy
Authors: Khoussainov, B.; Stephan, F.; Yang, Y.
Abstract: In this paper, the notions of Fα-categorical and Gα-categorical structures are introduced by choosing the isomorphism such that the function itself or its graph sits on the α-th level of the Ershov hierarchy, respectively. Separations obtained by natural graphs which are the disjoint unions of countably many finite graphs. Furthermore, for size-bounded graphs, an easy criterion is given to say when it is computable-categorical and when it is only G2-categorical; in the latter case it is not Fα-categorical for any recursive ordinal α. © 2008 Elsevier B.V. All rights reserved.
Sat, 01 Nov 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1030192008-11-01T00:00:00Z
- High minimal pairs in the enumeration degreeshttps://scholarbank.nus.edu.sg/handle/10635/104572Title: High minimal pairs in the enumeration degrees
Authors: Sorbi, A.; Wu, G.; Yang, Y.
Abstract: The natural embedding of the Turing degrees into the enumeration degrees preserves the jump operation, and maps isomorphically the computably enumerable Turing degrees onto the π0 1 enumeration degrees. The embedding does not preserve minimal pairs, though, unless one of the two sides is low. In particular it is known that there exist high minimal pairs of c.e. Turing degrees that do not embed to minimal pairs of e-degrees. We show however that high minimal pairs of π0 1 e-degrees do exist. © Springer-Verlag Berlin Heidelberg 2009.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1045722009-01-01T00:00:00Z