Finite and Infinite Model Theory and Applications

Vassar College, Poughkeepsie NY

Investigators

Abstract

The project focuses on questions dealing with classes of finite structures, and variants and extensions of o-minimality. Most of the effort directed toward the study of finite structures involves asymptotic classes of finite structures, their infinite analogues (measurable structures), and robust classes of finite structures. Broadly speaking, this research has as its aim the development of a model theory for classes of finite structures that is in analogy with mainstream model theory for infinite structures. Other ongoing work involving finite models will solve a conjecture on the relative expressive power of two logics, which in particular will demonstrate that one of these logics cannot capture the polynomial time computational complexity class. The projected research devoted to problems about extensions of o-minimality concentrates on the continued development of a model theory for ordered structures of rank greater than one. Important foundational results already have been obtained and the proposed investigations build on these. Some of this work appears to have intriguing applications to preference and utility theory in mathematical economics, and possibly to other aspects of economic theory. Another aspect of the research to be undertaken dealing with extensions of o-minimality concerns questions arising from previous work on expansions of o-minimal structures whose definable open sets form an o-minimal reduct of the original structure. The research outlined above has as its foundation model theory, one of the principal subfields of mathematical logic. Model theorists study properties of familiar mathematical structures that can be expressed in a formal mathematical language such as predicate logic. This distinctive point of view can provide understanding and insights into such structures that otherwise could not be easily obtained. One of the two principal aspects of the project deals with classes of finite structures, that is, classes of mathematical structures whose domain consists of a finite set. Finite structures in general are central to computer science: any database can be interpreted as a finite structure in the sense in which they are studied in here, and a particular class of finite structures called finite fields are especially important in cryptology. The second major aspect of this project focuses on structures that include and behave in significant respects like the ordered field of real numbers, that is, the real numbers together with the polynomial and algebraic functions that are studied in calculus and describe a wide range of phenomena in the physical and life sciences, as well as in the more quantitative social sciences. Research arising from the model-theoretic point of view has deepened our understanding of familiar mathematical systems in such diverse areas of the mathematical sciences as the analysis and geometry of real functions, neural nets, relational database theory, and estimation theory in statistics. Some of the most intriguing applications of the proposed research relate to and unify within a single framework both the neoclassical theory of utility in economics and contingent valuation theory that has become prominent in environmental economics, for example. During the period of the award the principal investigator also intends to continue to direct the Vassar Science Scholars Program, an academic year science and mathematics outreach program for students from a local high school with inner city demographics which he initiated and has directed since its inception.