pipette
ESEspañol

Cardinality of the K-cones below a non infinitely often -trivial

George Barmpalias, Lu Liu

Preprint

In the authors' words

Given a real , how many reals are there that are simpler (or equally simple) to describe than . With "simpler to describe" characterized by -complexity of initial segments (hence we call such with a solution to ), if is infinitely often -trivial (hence i.o. -trivial), then a simple counting argument shows that the number of solutions to is countable. If is non i.o. -trivial, then must it admit uncountably many solutions? Motivated by this question, we show that: (1) There is a non i.o. -trivial such that most of its solution is i.o. -trivial. i.e., Only countably many solution to are non i.o. -trivial. In particular, the cardinality of -degree of is countable. (2) There is a minimal pair of K-degree (meaning their common solutions are all -trivial) so that each of the pair is non i.o. -trivial, generalizing a result of Csima and Montalb\'an (where the pair is not required to be non i.o. -trivial but non -trivial). (3) There is a non i.o. -trivial whose complexity grows arbitrarily slow (in a weak sense: with a given unbounded and nondecreasing function) such that admits uncountably many solutions. (4) An ample excess lemma holds for non i.o. -trivial. Namely: for all non i.o. -trivial . Actually, this even holds for non i.o. --trivial with only depends on the universal prefix free machine. The same argument also gives a constant complexity return phenomenon for -trivial where this constant only depends on the universal prefix free machine.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.