Logic Seminar

Barbara Csima, University of Waterloo

Measuring complexity of structures via their Scott Sentences

Scott’s Isomorphism Theorem shows that each countable structure can be uniquely defined, up to isomorphism, by a sentence of infinitary logic, now known as the Scott Sentence of the structure. The complexity of a structure’s Scott Sentence can then be viewed as a measure of complexity of the structure. In this talk, we will discuss the relationship of Scott complexity with other measures of complexity, as well as discuss the Scott Complexity of certain structures.

MC 5403