The convergence of three notions of limit for finite structures
- Date: Wednesday 11 April 2018, 16:00 – 17:00
- Location: Mathematics Level 8, MALL 1, School of Mathematics
- Type: Logic, Seminars, Pure Mathematics
- Cost: Free
Alexander Kruckman, Indiana University, Bloomington. Part of the logic seminar series.
The (Rado) random graph R arises as a limit of finite graphs in at least three ways. First, R is the Fraïssé limit of the family of all finite graphs, the unique countable graph up to isomorphism which is universal and homogeneous for finite graphs. Second, it is pseudofinite: its first-order theory Th(R) is the logical limit (e.g. via an ultraproduct), of the first-order theories of a family of finite graphs, and in fact R is the unique countable model of this theory up to isomorphism. And third, it admits a random construction (the Erdős-Rényi construction on countably many vertices), which is naturally the limit of a uniform family of random constructions of finite graphs (the Erdős-Rényi construction on n vertices, for all n). Stronger, these random constructions of finite graphs witness pseudofiniteness, in the sense that every sentence in Th(R) is true with arbitrarily high probability in sufficiently large random finite structures.
I will explain how the strong agreement of these three limit notions (as in the case of the random graph) can be viewed as a consequence of higher-dimensional analogues of the amalgamation property in classes of finite structures. And in recent joint work with Cameron Hill, I will show when we have this sort of strong agreement, an analysis of the "random construction" (formally an invariant probability measure on the space of countable structures) can shed light on the model-theoretic properties of the limit. In particular, I will describe a generalization of de Finetti's theorem which is a useful tool in understanding invariant measures.