Scott Analysis of Discrete and Continuous Structures

Mathematicians study many different mathematical objects, and some of these objects are more complicated than others. Combining ideas from different areas of mathematical logic, from computability theory, descriptive set theory, and infinitary model theory, the Scott analysis is a way of measuring and understanding the complexity of mathematical objects. The Scott analysis is robust in the sense that it captures several different kinds of complexity that all coincide: the complexity of describing an object, the complexity of identifying two copies of an object, and the complexity of an object's internal structure. Though there remain many questions, the Scott analysis has now been well-developed for the case of discrete structures such as many structures appearing in algebra. More recently there has been increasing interest in studying continuous structures such as those appearing in analysis, a setting in which we do not have a robust Scott analysis, as there are further complication which do not arise in the discrete setting. This project will develop a robust Scott analysis in this continuous setting, including applications, while also further applying developing the Scott analysis in the more classical discrete setting. The long-term goals are to give a more rigorous and formal understanding of why certain mathematical questions are difficult or even impossible to solve, and what the barriers are to solving them. This project includes the training of undergraduate and graduate students.

Consider a discrete structure such as a graph, group, or Boolean algebra. The Scott analysis assigns to this structure an ordinal-valued Scott rank or more finely a Scott complexity. This is robust in the sense that it measures, simultaneously, the complexity of defining the automorphism orbits of the structure, the complexity of characterizing the structure up to isomorphism in infinitary logic, the Borel complexity of the set of copies of that structure in the topological space of all structures, and the computational complexity of building isomorphisms between copies of that structure. This project will develop such a theory in the continuous setting where the structures are metric or topological structures such as Banach spaces or manifolds. The main goal is to develop a bridge between syntactic characterizations in infinitary continuous logic and semantic characterizations in terms of computation or topology and descriptive set theory. Applications of this include studying how the Scott complexity of n-manifolds changes as n increases, or of studying the Scott complexity of Banach spaces and, for example, the impact of whether or not they have a Schauder basis. The project will also include further developments in the discrete setting, both in developing the theory at a finer level and in further applications.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

Award Number: 2452105
Principal Investigator: Matthew Harrison-Trainor
Funds Obligated: $109,999
State: IL