Pseudo-Finiteness of Combinatorial Theories

Wesleyan University, Middletown CT

Investigators

Abstract

Model theory is a branch of mathematical logic in which one can exploit the linguistic/formal description of a mathematical object to study the object itself. This object might be a single algebraic structure or a class of structures that share a common description (theory). In this project, the PI will study the phenomenon of pseudo-finiteness, in which every (finite) fragment of the description of an infinite object also describes a finite object -- even while the full description captures only infinite structures. In recent years, pseudo-finiteness has been exploited to prove theorems in finitary discrete mathematics and additive combinatorics. On the other hand, pseudo-finiteness has only been completely characterized in a small number of settings. Ax's characterization of pseudo-finite fields is probably the best known. Here, the PI intends to give such a characterization of pseudo-finiteness for theories that are "purely non-algebraic" -- theories that arise from classes of structures that are specifically of interest in discrete mathematics, such as classes of graphs and regular hypergraphs. In the very long term, one might expect to see applications of this research in network analysis, treating very large networks (i.e. graphs) like the internet and the human brain. Here are some more technical details. The project provides a detailed study of the phenomenon of pseudo-finiteness in what is called "combinatorial theories" -- countably-categorical theories with quantifier elimination and trivial algebraic closure operation. Such theories correspond immediately to commonly studied classes of finite structures from discrete mathematics, such as graphs (directed and undirected) and regular hypergraphs. In practice, it is quite difficult, if not impossible, to construct pseudo-finite combinatorial theories without appealing to probability theory in apparently essential ways: either the constructed theory is itself obtained from a 0,1-law or it is some sort of limit of such theories. Upon determining exactly what the appropriate limit processes are, the PI plans to show that this is, in fact, the only way to construct pseudo-finite combinatorial theories. A proof of this sort of claim will require a more or less complete understanding of 0,1-laws in this setting -- especially, connections and equivalences between conditional independence and higher amalgamation properties in classes of finite structures. In turn, this analysis seems to require deep exploration of connections between model theory, on one hand, and (for example) functional analysis and measure-theoretic probability on the other. Capturing pseudo-finite theories as limits of almost-sure theories will require development of an extensive technology for selecting/extracting well-behaved sub-classes inside of a given class of finite structures. 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.