Source-linked AI summary
A characterization of the finite model property for $\omega$-categorical theories
Vera Koponen
TL;DR
The paper asks when a complete ω-categorical theory has the finite model property and what finite structures can serve as bases for random expansions with a first-order convergence law. It characterizes the property through classes of finite structures and reports a remaining open direction for a related FSMP characterization.
Problem
The paper asks when a complete ω-categorical theory has FMP and what finite base structures must satisfy for random expansions to have a chance at a first-order convergence law.
Source: §1 · pp. 1–2Method
It characterizes FMP through a class of finite structures with specified partial-closure behavior and uses an extension property to transfer definable n-independence criteria.
Source: §1 · pp. 1–2Results
A complete ω-categorical T has FMP if and only if it consists of sentences true in every sufficiently large member of a class C satisfying assumptions 2.1, 2.16, and 2.23.
Source: §3 · p. 10Takeaways & Limitations
The characterization offers a guideline for assessing whether concrete ω-categorical theories have FMP and informs the study of suitable random-expansion base sequences.
Source: §1 · pp. 1–2The paper leaves unproved the converse direction of the proposed FSMP characterization using a class C with the hereditary property for closed substructures.
Source: §3 · p. 12
Abstract
from arXiv · showhide
A first-order theory $T$ has the {\em finite model property} if every first-order sentence that is implied by $T$ has a finite model. We give a characterization of when a complete $\omega$-categorical theory $T$ has the finite model property. The characterization makes it possible to transfer stability theoretic results in [29] to certain classes of finite structures. This approach also gives information concerning properties that a sequence of finite ``base structures'' of ever larger size must have in order for its random expansions to a larger vocabulary to have a chance to satisfy a convergence law for first-order logic.
1. Introduction
After defining FMP and FSMP and their finite-search and order-property implications, the introduction presents a closure-based characterization for complete ω-categorical theories and connects it to finite classes and random expansions.
1. Introduction
- FMP supplies finite models for consequences and rules out consequences expressing that all models are infinite or that a formula has the strict order property.Source: §1 · p. 1
- Although prior work established FSMP for several ω-categorical classes, FMP remains unknown for the triangle-free graph Fraïssé limit and some Hrushovski-style structures.Source: §1 · p. 1
- For a complete ω-categorical theory, FMP is characterized by its being exactly the sentences true in every sufficiently large member of a finite-structure class with suitable partial-closure behavior.Source: §1 · p. 1
- The characterization also informs what properties increasingly large finite base structures need for their random expansions to have a chance at a first-order convergence law.Source: §1 · p. 2
- An extension property relative to partial closure yields n-independence in sufficiently large class members, with symmetry criteria tied to the exchange property for elements of n-rank 1.Source: §1 · p. 2
Basic notation and terminology.
- A closure operator is extensive, monotone, and idempotent; closure types compare generated substructures through isomorphisms preserving closure dependencies.Source: Basic notation and terminology · p. 3
2. Finite structures with a partial closure operator
Section 2 studies classes of finite structures with definable, bounded partial closure, showing how closure types and hereditary closure properties shape the first-order behavior of their limit theories, including when those theories have the finite model property. Under a multiextension assumption, the limit model’s closure operator coincides with algebraic closure.
2.1. Finite structures with a partial closure operator.
- Assumption 2.1 requires sufficiently large structures to have a partial closure operator with bounded closure sizes and first-order definability.The assumptions also constrain closure behavior through monotonicity and idempotence when the iterated closure is defined.Source: §2.1 · p. 3
- For each tuple length, finitely many closure types uniquely classify tuples up to closure equivalence in all sufficiently large members of C.Each tuple realizes exactly one of the types, and matching types characterize closure-equivalent tuples across structures.Source: §2.1 · p. 5
- Every first-order formula holding in arbitrarily large members of C is eventually characterized by finitely many closure types.The proof reduces Boolean connectives directly and existential quantification using boundedness or the extension property for unbounded types.Source: §2.1 · pp. 6–7
- If all sufficiently large structures have the same empty-tuple closure type, every first-order sentence is eventually either true throughout C or false throughout C.This zero-one law also supplies sufficient conditions for 0-or-1 convergence of sentences when structures are randomly expanded from singleton base classes.Source: §2.1 · p. 7
2.2. The limit theory.
- Under stable empty-tuple closure, the eventual theory TC is ω-categorical and has the finite model property.Every formula is equivalent in TC to a finite disjunction of closure types.Source: §2.2 · p. 8
- Every model of TC carries a closure operator defined by the formulas ξk, and this closure is contained in algebraic closure.Source: §2.2 · p. 8
2.2. The limit theory
- For each tuple in a model of TC, exactly one closure type applies, and two tuples have the same closure type exactly when they satisfy the same such type.Source: §2.2 · p. 8
- With the hereditary property for closed substructures, every finite substructure A of a model of TC satisfying clM(A) = A is isomorphic to a member of C.The property requires each closed substructure B of a member of C to have an isomorphic copy in C.Source: §2.2 · p. 9
- If C has the hereditary property for closed substructures, then its limit theory TC has the finite model property.The proof uses bounded closures of finite tuples to find a finite closed substructure satisfying each sentence in TC.Source: §2.2 · p. 9
- Under the multiextension property, the closure operator on any model M of TC equals algebraic closure: clM(A) = aclM(A).The assumption supplies arbitrarily many realizations of each relevant unbounded closure type, so elements outside clM(A) are not algebraic over A.Source: §2.2 · pp. 9–10
3. Characterization of FMP for ω-categorical theories
Theorem 3.1 characterizes the finite model property for complete ω-categorical theories through classes of finite structures. When T has the FMP, formulas consistent with T also admit a closure-type normal form.
Theorem 3.1
- T has the FMP exactly when it is the set of sentences true in every sufficiently large member of a finite-structure class C satisfying Assumptions 2.1, 2.16, and 2.23.Conversely, such a class C implies that T has the FMP.Source: §3 · pp. 10, 12
- For every formula consistent with T, there are closure types whose finite disjunction is equivalent to it in all models of T.For T, closure types use formulas ξ_k to express membership in the algebraic closure of the other variables.Source: §3 · pp. 10, 12
Proof of Theorem 3.1
- The proof identifies T with the theory of sentences eventually true in C by showing that countable models of T and that theory are isomorphic.The isomorphism is built by back-and-forth using matching closure types.Source: §3 · pp. 11–12
Remark 3.2
- The paper leaves open whether the FMP characterization extends to an equivalence for the finite submodel property when C also has the hereditary property for closed substructures.The stated sufficient direction follows from Theorem 2.22, but the converse is not proved.Source: §3 · p. 12
4. Independence in a class of finite structures
The section transfers n-independence from the ω-categorical theory T to sufficiently large structures in C. It describes the finite-structure relation using bounded closure conditions for n=0 and rank and definable equivalence relations for n>0.
4. Independence in a class of finite structures
- The eventual theory T is complete and ω-categorical, and its n-independence relation is defined on finite subsets of models of T.In the finite structures, the transferred relation is expressed by formulas on tuples.Source: §4 · pp. 12–13
4.1. Transfering ⌣|n from models of T to members of C.
- For every fixed m, sufficiently large S∈C inherit properties (2)–(6) of n-independence for subsets of size at most m.The transfer is stated for all A, B, C, D⊆S of cardinality at most m.Source: §4.1 · p. 13
- For each m, model-theoretic exchange up to κ(m) implies symmetry up to m, yielding the corresponding bounded symmetry condition in sufficiently large members of C.The exchange condition is stated for rank-1 elements; the finite-structure implication is expressed by first-order sentences.Source: §4.1 · pp. 13–14
4.2. The case n = 0.
- For fixed i, sufficiently large A∈C define ⌣|0 on sequences of length at most i in terms of cl_A.In the tree example, the condition compares the parts of cl_A(a) outside cl_A(c) and cl_A(bC).Source: §4.2 · p. 15
4.3. The case n > 0.
- When each E_i is equality, the generalized ξ formula is equivalent in models of T to ξ_k.This identifies the special case where the tuples are not passed to quotient classes.Source: §4.3 · p. 16
- For n>0, rank-at-least-α is characterized by witnesses involving ∅-definable equivalence relations and their classes, viewed as imaginary elements.The equivalence classes used in the construction are treated as imaginary elements.Source: §4.3 · pp. 15–16
- For n>0, failure of independence is characterized by a rank threshold for a over b that no longer holds after adjoining c, with the threshold bounded in terms of T and |a|.The rank threshold can be witnessed using ∅-definable equivalence relations on tuples.Source: §4.3 · pp. 16–17