|
Organizers |
Relative randomness and cardinality
by
George Barmpalias
Victoria University
We show that for every D02 set B, MLR ⊆ MLRB iff the class {A | MLRB ⊆ MLRA} is countable (where MLRX denotes the class of Martin-Löf random numbers relative to X and MLR = MLR∅). It follows that D02 is the largest arithmetical class with this property, and if {A | MLRB ⊆ MLRA} is uncountable it contains a perfect P01 set P of reals.
Date received: October 23, 2007
Continuity of capping in EbT
by
Paul Brodhead
University of Florida
Coauthors: Angsheng Li (Chinese Academy of Sciences),
Weilin Li (Chinese Academy of Sciences)
For sets A, B ⊆ w, we say that A is bounded Turing reducible to B if A is Turing reducible to B with use bounded by a computable function. We study the continuity properties of the c.e. bT-degrees. We show that for any c.e. bT-degree b ≠ 0, 0', there is a c.e. bT-degree a > b such that for any c.e. bT-degree x, b∧x=0 iff a∧x=0. This is the first continuity property of the c.e. bT-degrees.
Date received: November 1, 2007
Representation of Computably Enumerable e-Random Reals
by
Cristian S. Calude
University of Auckland
Coauthors: Nicholas J. Hay
If x = 0.x1x2 ... is c.e. random, then clearly x0 = 0.x1 0 x2 0 ... is at least 1/2-random. Is x0 exactly 1/2-random? Can we obtain x0 in a natural way, i.e. as halting probability of a "weak" type of universal prefix-free machine?
The talk will present some representability results for c.e. e-random reals which were introduced and studied by Tadaki, Staiger, Calude, Terwijn, Merkle, Nies and Reinmann. We will use the techniques developed by Calude, Hertling, Khoussainov, Wang, and Slaman.
Date received: October 15, 2007
A P11 uniformization principle for reals
by
Chi Tat Chong
National University of Singapore
Coauthors: Liang Yu, Department of Mathematics, Nanjing University, China
We present a P11 uniformization principle and illustrate its applications to various problems, including the existence of P11 maximal chains of Turing degrees, P11 thin maximal antichains of Turing degrees, as well as Martin's conjecture on degree invariant functions.
Date received: October 31, 2007
Linear Orders with Distinguished Function Symbol
by
Barbara F. Csima
University of Waterloo
Coauthors: Douglas Cenzer, Bakhadyr Khoussainov
We consider certain linear orders with a function on them, and discuss for which types of functions the resulting structure is or is not computably categorical. Particularly, we consider computable copies of the rationals with a fixed-point free automorphism, and also w with a non-decreasing function.
Date received: November 1, 2007
Solovay pairs and supercompacteness
by
Qi Feng
National University of Singapore/Chinese Academy of Sciences)
We shall present a new characteristic of supercompact cardinals using Solovay pairs and study related matters.
Date received: November 21, 2007
Truth table reducibility and Schnorr triviality
by
Johanna Franklin
National University of Singapore
Coauthors: Frank Stephan
In this work, we study the relationship between truth table reducibility and Schnorr triviality. The standard notion of lowness for Schnorr randomness in the Turing degrees does not coincide with Schnorr triviality. Here, we study a new notion, which provides further evidence that Schnorr triviality is most naturally considered in the truth table degrees.
We develop a notion of tt-low for Schnorr random and show that it is equivalent to Schnorr triviality as well as several other properties. We are then able to use these properties to show that, among other things, the Schnorr trivial reals form an ideal in the truth table degrees. We also rule out the weak truth table degrees as a natural degree structure for Schnorr triviality, since here, as in the Turing degrees, the Schnorr trivial reals are not closed downward.
This work is joint with Frank Stephan.
Date received: September 20, 2007
Working above totally omega-c.e. degrees using strong reducibilities
by
Noam Greenberg
Victoria University
Coauthors: George Barmpalias and Rod Downey
We characterise the c.e. degrees which are not totally omega-c.e. as those that contain c.e. sets which are not wtt-reducible to hypersimple sets; equivalently, to ranked sets. We also give a characterisation of the c.e. array computable degrees in terms of computable Lipschitz reductions to random c.e. reals.
Date received: October 30, 2007
Atomic Models and Genericity
by
Denis R. Hirschfeldt
University of Chicago
Coauthors: Richard A. Shore and Theodore A. Slaman
The Atomic Model Theorem states that every complete, consistent, atomic theory in a countable language has a countable atomic model. I will present recent results on the computability theoretic and reverse mathematical strength of this result, and its connections with a certain P01 genericity principle.
Date received: October 30, 2007
Chains and antichains in (weakly) stable posets
by
Carl G. Jockusch, Jr.
Department of Mathematics, University of Illinois at Urbana-Champaign, 1409 W. Green Street, Urbana, IL 61801 USA
Coauthors: Bart Kastermans (University of Wisconsin),
Steffen Lempp (University of Wisconsin),
Manuel Lerman (University of Connecticut),
Reed Solomon (University of Connecticut)
Hirschfeldt and Shore [1] introduced the notion of stability for partial orderings (or posets). We introduce the notion of weak stability for posets, which is arguably more natural than stability. Namely, an infinite poset is weakly stable if each of its elements either lies below all but finitely many elements, or above all but finitely many elements, or is incomparable with all but finitely many elements. We study the complexity of infinite chains and antichains in stable and weakly stable infinite computable posets, emphasizing results on the existence of infinite chains and antichains which are computable, low, or P01. We also obtain a related result in Reverse Mathematics and simplify the proofs of some results on linear orderings in [1].
Reference
[1] Denis R. Hirschfeldt and Richard A. Shore, Combinatorial principles weaker than Ramsey's Theorem for Pairs, J. Symbolic Logic 72, 2007, 171-206.
Date received: October 26, 2007
Kolmogorov Complexity, Computable Categoricity, and Frasse Limits
by
Bakhadyr Khoussainov
University of Auckland/Cornell University
Coauthors: Pavel Semukhin and Frank Stephan
We answer the following long standing open question (since the early 80s): does there exist a non-countably categorical w-saturated structure with exactly one computable isomorphism type?
We motivate the question, give a brief background, and provide our positive solution to the question. We explain the uses of Kolmogorov complexity and Frasse limits in our construction of the desired structure. Kolmogorov complexity is used to build a special type of uniform family of computably enumerable sets. Frasse limits are used to code the family into the structure. We also say why the standard codings known in computable model theory can not be applied in building the desired structure.
Date received: November 20, 2007
Infinite subsets of random sets of integers
by
Bjørn Kjos-Hanssen
University of Hawaii at Manoa
For all randomness notions between weak 2-randomness and weak 1-randomness, and with respect to any Bernoulli measure, there is an infinite subset of a random set of integers that computes no random set of integers.
To obtain this, we design a probability distribution P on the collection of all closed sets of reals, so that P satisfies (1) and (2). Then we apply (3).
(1) Whenever C is random according to P, each member of C computes an infinite subset of a random set of integers.
(2) Each real of sufficiently high effective Hausdorff dimension is a member of some C that is random according to P.
(3) (N. Greenberg, J. Miller) There is a real of arbitrarily high effective Hausdorff dimension that computes no random set of integers.
Date received: October 30, 2007
On the Back-and-Forth relation on Boolean Algebras
by
Antonio Montalban
University of Chicago
Coauthors: Kenneth Harris
The objective of this paper is to provide a good undesrtaing of the structure of the n-back-and-forth-equivalence classes of Boolean algebras, and the n-backand-forth relations between them. As an application, we obtain a characterization of the relatively intrinsically Sigma-0-n relations of Boolean algebras as existential formulas over a finite set of relations.
Date received: October 30, 2007
Strong Jump Traceability and Beyond
by
Ng, Keng Meng
Victoria University of Wellington
A set is low if it is computationally weak when used as an oracle. We study various notions of lowness. In particular we look at strong jump traceability, which is a variant of c.e. traceability. These reals are all superlow in the c.e. case, and by relativizing the notion of strong jump traceablility, we show that there is a subclass of the c.e. K-trivials with no promptly simple members. We look at various other properties of this new class of reals, which are all very weak in terms of their computational power.
Date received: October 28, 2007
Borel presentable structures
by
Andre Nies
University of Auckland
Coauthors: G Hjorth, B Khoussainov, A Montalban
Traditionally, effectivity is studied for countable structures.
Borel structures in contrast allow us to develop a theory of effectivity for the
equally natural uncountable structures, such as the field of real numbers.
After some initial work by Friedman (1979), the forthcoming paper entitled:
from automatic structures to Borel structures?? by Khoussainov, Hjorth, Montalban
and myself has revived the subject by applying Borel structures to solve a well-known
question on Buechi presentable structures; see Section 5 of Nies' Bull. Symb.
Logic paper ?Describing Groups??, Sept 2007. We show that there is a Buechi presentable
structure without an injective Borel representation. Further, there exists a Rabin
presentable structure that is not Borel.
Date received: November 1, 2007
Effective Capacitability and Dimension of Measures
by
Jan Reimann
University of California, Berkeley
We introduce the notion of effective capacitability and show that every Hausdorff random real is effectively capacitable. This yields a useful characterization of effective dimension. We relate effective capacitability to dimension notions for measures.
Date received: October 31, 2007
On Universal Computably Enumerable Prefix Codes
by
Ludwig Staiger
Martin-Luther-Universität Halle-Wittenberg, Institut für Informatik, D-06099 Halle (Saale), Germany
Coauthors: Cristian S. Calude
We study computably enumerable (c.e.) prefix codes which are capable of coding all positive integers in an optimal way up to a fixed constant: these codes will be called universal. We prove various characterisations of these codes including the following one: a c.e. prefix code is universal iff it contains the domain of a universal self-delimiting Turing machine. Finally, we study various properties of these codes from the points of view of computability, maximality, and density.
Date received: October 12, 2007
Sets of nonrandom numbers
by
Frank Stephan
National University of Singapore, Departments of Mathematics and Computer Science
Let C and H denote the plain and prefix-free Kolmogorov complexity, respectively. Then the sets NRC of nonrandom numbers with respect to C has neither a maximal nor an r-maximal superset. The set of NRH of nonrandom numbers with respect to H has an r-maximal but no maximal superset. Thus the lattices of recursively enumerable supersets (modulo finite sets) of NRC and NRH are not isomorphic. Further investigations deal with the related set NRW of all numbers x which are the maximum of some r.e. set with an index e < x. Friedman originally asked whether NRW is Turing equivalent to K and Davie provided a positive answer for many acceptable numberings. Later Teutsch asked the related question whether one can choose the underlying acceptable numbering such that NRW is either an r.e. or co-r.e. set. A negative answer is provided to this question and the position of NRW in the difference-hierarchy is provided: one can choose the underlying numbering such that NRW is a co-2-r.e. set but NRW is never a 2-r.e. set. Furthermore, if the underlying numbering is a Kolmogorov numbering, then NRW is an omega-r.e. set but not an n-r.e. set for any natural number n.
Date received: September 17, 2007
Definable Determinacy and Second Order Number Theory
by
Hugh Woodin
UC Berkeley
Definable Determinacy is the assertion that all definable sets are determined (no parameters). The base theory is Second Order Number Theory and so Definable Determinacy is an axiom scheme. The basic problem is to compute the consistency strength of this theory. This in turn leads to some interesting questions about the combinatorics associated to Woodin cardinals.
Date received: October 30, 2007
On the complexity of the successivity relation in computable linear orderings
by
Guohua Wu
Nanyang Technological University
Coauthors: Rod Downey, Steffen Lempp
In this paper, we prove that if a computable linear ordering A has infinitely many successivities, then there is a computable linear ordering B such that B is isomorphic to A, and the set of successivities in B, Succ(B), is Turing complete.
Date received: October 30, 2007