Pseudofiniteness and measurability of the everywhere infinite forest

Abstract: A structure M is said to be pseudofinite if every first-order sentence that is true in M has a finite model, or equivalently, if M is elementarily equivalent to an ultraproduct of finite structures. For this kind of structures, the fundamental theorem of ultraproducts ( Los' Theorem) provides a powerful connection between finite and infinite sets, which can sometimes be used to prove qualitative properties of large finite structures using combinatorial methods applied to non-standard cardinalities of definable sets.

The concept of measurable structures was defined by Macpherson and Steinhorn in [2] as a method to study infinite structures with strong conditions of finiteness and definability for the sizes of definable sets. The most notable examples are the ultraproducts of asymptotic classes of finite structures (e.g., the class of finite fields or the class of finite cyclic groups). Measurable structures are supersimple of finite SU-rank, but recent generalizations of this concept are more flexible and allow the presence of structures whose SU-rank is possibly infinite.

The everywhere infinite forest is the theory of an acyclic graph G such that every vertex has infinite degree. It is a well-known example of an omega-stable theory of infinite rank. In this talk we will take this structure as a motivating example to introduce all the concepts mentioned above, showing that it is pseudofinite and giving a precise description of the sizes of their definable sets. In particular, these results provide a description of forking and U-rank for the infinite everywhere forest in terms of certain pseudofinite dimensions, and also show that it is a generalized measurable structure that can be presented as the ultraproduct of a multidimensional exact class of finite graphs. These results are joint work with Melissa Robles, and can be found in [1].

References:

[1] Darío García and Melissa Robles. Pseudofiniteness and measurability of the everywhere infinite forest. Available at arXiv: arxiv.org/pdf/2309.00991.pdf

[2] Dugald Macpherson and Charles Steinhorn. One-dimensional asymptotic classes of finite structures, Transactions of the American Mathematical Society, vol. 360 (2008)

combinatoricslogicprobability

Audience: researchers in the topic

---

Online logic seminar

Series comments: Description: Seminar on all areas of logic

---