On 0, 1-laws and asymptotics of definable sets in geometric Fraïssé classes. (English) Zbl 1385.03038
This paper studies the relationship between Fraïssé limits and limits obtained from logical zero-one laws. The main result is this, roughly stated:
Suppose that \(C\) is a Fraïssé class of finite structures having an additional ‘geometric’ property. Also, suppose that the theory \(T_C\) of the Fraïssé limit of \(C\) is the same as the set of almost sure sentences \(T_\mu\) with respect to some sequence of probability measures \(\mu_n\) on the structures of \(C\) with universe \(\{1,\ldots,n\}\) (so this assumes that \(C\) has a zero-one law). If the probility measures \(\mu_n\) have almost independent sampling, then there is a subclass \(D\) of \(C\) such that \(D\) is superrobust and a 1-dimensional asymptotic class and almost all members of \(C\) belong to \(D\) (more plainly, almost all members of \(C\) belong to a “nice” subclass of \(C\)).
Using results about superrobust and asymptotic classes, the author also derives that, under the same assumptions as above, \(T_C\) is supersimple and for every definable set \(X\) (of the generic model) the \(D\)-rank of \(X\) is bounded by the algebraic dimension of \(X\). Intuitively, the notion ‘almost independent sampling’ means that relations in structures of \(C\) are (with respect to the given probability measures) “mostly” independent. For background on asymptotic classes see for example [R. Elwes and D. Macpherson, Lond. Math. Soc. Lect. Note Ser. 350, 125–159 (2008; Zbl 1172.03020)].
Suppose that \(C\) is a Fraïssé class of finite structures having an additional ‘geometric’ property. Also, suppose that the theory \(T_C\) of the Fraïssé limit of \(C\) is the same as the set of almost sure sentences \(T_\mu\) with respect to some sequence of probability measures \(\mu_n\) on the structures of \(C\) with universe \(\{1,\ldots,n\}\) (so this assumes that \(C\) has a zero-one law). If the probility measures \(\mu_n\) have almost independent sampling, then there is a subclass \(D\) of \(C\) such that \(D\) is superrobust and a 1-dimensional asymptotic class and almost all members of \(C\) belong to \(D\) (more plainly, almost all members of \(C\) belong to a “nice” subclass of \(C\)).
Using results about superrobust and asymptotic classes, the author also derives that, under the same assumptions as above, \(T_C\) is supersimple and for every definable set \(X\) (of the generic model) the \(D\)-rank of \(X\) is bounded by the algebraic dimension of \(X\). Intuitively, the notion ‘almost independent sampling’ means that relations in structures of \(C\) are (with respect to the given probability measures) “mostly” independent. For background on asymptotic classes see for example [R. Elwes and D. Macpherson, Lond. Math. Soc. Lect. Note Ser. 350, 125–159 (2008; Zbl 1172.03020)].
Reviewer: Vera Koponen (Uppsala)
MSC:
03C13 | Model theory of finite structures |
03C15 | Model theory of denumerable and separable structures |
03C45 | Classification theory, stability, and related concepts in model theory |
05A16 | Asymptotic enumeration |