Logic Colloquium 2024


David Gonzalez

University of California, Berkeley

Talks at this conference:

  Tuesday, 15:20, J222

Generically computable linear orderings

W. Calvert, D, Cenzer and V. Harizanov introduced notions of generic computability for structures that are stratified by the computable ordinals. In a recent collaboration with these authors we examined these notions in the context of linear orderings. Our main results contrast one another. We show that every linear ordering has a 1-generically computable copy. On the other hand, we have that the set of linear orderings with a n-generically computable copy for \(n>1\) is as complicated as possible: \(\mathbf{\Sigma}_1^1\)-complete. This talk will put these results in context and describe the new, more structural approach we took to this problem. In particular, I will describe these results through the lens of a surprising connection with Ramsey-like properties.