Skip to main content
eScholarship
Open Access Publications from the University of California

Infinitary Limits of Finite Structures

  • Author(s): Kruckman, Alex
  • Advisor(s): Scanlon, Thomas
  • et al.
Abstract

We study three distinct ways of assigning infinitary limits to classes of finite structures. We are primarily concerned with logically motivated questions about these limit objects and their theories, as well as connections and analogies between them.

In the first part, we consider limits of sequences of finite structures which converge with respect to densities of quantifier-free formulas, generalizing the dense graph limits and similar structural limits studied in combinatorics. A convergent sequence determines, as a limit object, a certain kind of probability measure on the space of countable structures with domain $\omega$, which we call an ergodic structure. After developing the background theory, we take up the case of properly ergodic structures, which do not assign full measure to any single isomorphism class. The main result is a purely logical characterization of those theories in countable fragments of $L_{\omega_1,\omega}$ which arise as the theories of properly ergodic structures.

In the second part, we study categories consisting of finite structures and certain ``strong" embeddings between them. We identify a necessary and sufficient condition for the well-definedness of strong embeddings between infinite direct limits from the category. This allows us to develop the natural generalization of classical Fra\"iss e theory in this context, with a focus on topology and genericity, in the sense of Baire category, in the space of direct limits with domain $\omega$. We elaborate on an analogy between these generic limits and the measure limits in the first part, and we examine model-theoretic properties of generic limits.

In the third part, we take up logical limits, in the sense of ultraproducts and zero-one laws. In contrast to the first two parts, the limit theories here are always pseudofinite. We focus on countably categorical theories, which are essentially generic theories of small Fra\"iss e classes, and we show that higher amalgamation properties (disjoint $n$-amalgamation for all $n$) are sufficient to prove pseudofiniteness by a probabilistic argument. We examine relationships between pseudofiniteness, higher amalgamation, and model theoretic dividing lines, especially simplicity and NSOP$_1$. Our hope is that in ``purely combinatorial" situations, pseudofiniteness should always be explained by randomness, via higher amalgamation; in an attempt to isolate these situations, we define the class of primitive combinatorial theories.

Main Content
Current View