Computability Theory: Constructive Applications of the Lefthanded Local Lemma and Characterizations of Some Classes of Cohesive Powers

Abstract

The Lovász local lemma (LLL) is a technique from combinatorics for proving existential results. There are many different versions of the LLL. One of them, the lefthanded local lemma, is particularly well suited for applications to two player games. There are also constructive and computable versions of the LLL. The chief object of this thesis is to prove an effective version of the lefthanded local lemma and to apply it to effectivise constructions of non-repetitive sequences.

The second goal of this thesis is to categorize some classes of cohesive powers. We completely describe both the isomorphism types of cohesive powers of equivalence structures and injection structures, as well as clarify the relationship between these cohesive powers and their original structures. We also describe the finite condensation of cohesive powers of computable copies of the integers as a linear order by cohesive sets whose complement are computably enumerable.

Finally, we investigate the possibility of decomposing problems in the Weihrauch degrees into a product of first order part and second order part. We give a preliminary result in this direction.

Abstract prepared by Daniel Mourad.

E-mail: [email protected]

URL: https://daniel-mourad.scholar.uconn.edu/wp-content/uploads/sites/2530/2023/06/ThesisFinalWithRevisions-2.pdf