Logic Seminar-Cohesive Powers of Directed Pseudoforests

Time: Wednesday, April 26

11:00 am – 12:00 noon

Place: Rome 350

Speaker:  Keshav Srinivasan, GWU

Title: Cohesive Powers of Directed Pseudoforests

Abstract: We consider a computability-theoretic product construction for structures. We start with infinitely but countably many uniformly computable structures and in their direct product consider partial computable sequences modulo a fixed cohesive set. A cohesive set is an infinite set of natural numbers that cannot be split into two infinite subsets by any computably enumerable set. Hence, the elements of the cohesive product are the equivalence classes of partial computable sequences, and in some cases computable ones. In particular, we study products that are powers of a single computable structure. We focus on directed pseudoforests, a type of directed graph which can be thought of as a set endowed with a partial function. As a special case we study partial injection structures, whose cohesive powers we classify up to isomorphism in many cases. The isomorphism problem for directed pseudoforests in general is Turing-undecidable, but we still obtain partial characterizations of the properties of their cohesive powers.