Logic Seminar

Matthew Harrison-TrainorUniversity of Waterloo
Some computable structure theory of finitely generated structures

Wednesday, October 18, 2017 - 4:00pm
Malott 206

Every countable structure has a sentence of infinitary logic, called a Scott sentence, which describes it up to isomorphism among countable structures. We can characterize the complexity of a structure by the complexity of the simplest description of that structure. A finitely generated structure always has a $\Sigma^0_3$ description. We show that there is a finitely generated group which has no simpler description. The proof of this leads us to talk about notions of universality for finitely generated structures. Finitely generated groups are universal, but finitely generated fields are not. By this, we mean that for every finitely generated structure, there is a finitely generated group which has the same computability-theoretic properties; but the same is not true for finitely generated fields. We apply the results of this investigation to pseudo Scott sentences.