Logic Seminar

Matthew Harrison-TrainorVictoria University of Wellington
The Complexity of Descriptions

Tuesday, November 19, 2019 - 2:55pm
Malott 206

Most objects in mathematics, such as groups, graphs, or fields, consist of a set together with functions, relations, and constants on that set. We call such an object a structure. In computable structure theory, we study the complexity of countable structures using methods from computability theory as well as other areas of logic.

Given a particular countable structure, one can try to write down a description of the isomorphism type of that structure among all countable structures. For example, the order type of the rationals is the only countable linear order that is dense and has no endpoints. It turns out that every countable structure has such a description, called a Scott sentence, which can be written down in infinitary logic. The complexity of the simplest Scott sentence for a structure is a measure of the complexity of describing that structure; this is also tied to other measures of the complexity of that structure, for example the complexity of the automorphism orbits of the structure.

I will give an accessible introduction to the theory of Scott sentences and highlight a number of recent advances in the area.