Generically computable linear orderings

Abstract: 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: 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.

logic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic