Hypergraph sequences as a tool for saturation of ultrapowers. (English) Zbl 1247.03048

Malliaris, M. E.

J. Symb. Log. 77, No. 1, 195-223 (2012).

Summary: Let \(T_{1}, T_{2}\) be countable first-order theories, \(M_{i} \models T_{i}\), and \(\mathcal D\) any regular ultrafilter on \(\lambda \geq \aleph _{0}\). A longstanding open problem of Keisler asks when \(T_{2}\) is more complex than \(T_{1}\), as measured by the fact that for any such \(\lambda, \mathcal D\), if the ultrapower (\(M_{2})^{\lambda }/\mathcal D\) realizes all types over sets of size \(\leq \lambda \), then so must the ultrapower (\(M_{1})^{\lambda }/\mathcal D\). In this paper, building on the author’s prior work, we show that the relative complexity of first-order theories in Keisler’s sense is reflected in the relative graph-theoretic complexity of sequences of hypergraphs associated to formulas of the theory. After reviewing prior work on Keisler’s order, we present the new construction in the context of ultrapowers, give various applications to the open question of the unstable classification, and investigate the interaction between theories and regularizing sets. We show that there is a minimum unstable theory, a minimum TP\(_{2}\) theory, and that maximality is implied by the density of certain graph edges (between components arising from Szemerédi-regular decompositions) remaining bounded away from \(0,1\). We also introduce and discuss flexible ultrafilters, a relevant class of regular ultrafilters which reflect the sensitivity of certain unstable (non-low) theories to the sizes of regularizing sets, and prove that any ultrafilter which saturates the minimal TP\(_{2}\) theory is flexible.

MSC:

03C20	Ultraproducts and related constructions
05C65	Hypergraphs

Keywords:

countable first-order theories; regular ultrafilter; ultrapower; sequences of hypergraphs; unstable classification

References:

[1]	J. Baker and K. Kunen Limits in the uniform ultrafilters , Transactions of the American Mathematical Society , vol. 353(2001), no. 10, pp. 4083-4093. · Zbl 0972.54019 · doi:10.1090/S0002-9947-01-02843-4
[2]	S. Buechler Lascar strong types in some simple theories , Journal of Symbolic Logic, vol. 64(1999), no. 2, pp. 817-824. · Zbl 0930.03035 · doi:10.2307/2586503
[3]	W. Comfort and S. Negrepontis The theory of ultrafilters , Springer-Verlag,1974.
[4]	A. Dow Good and ok ultrafilters , Transactions of the American Mathematical Society , vol. 290(1985), no. 1, pp. 145-160. · doi:10.1090/S0002-9947-1985-0787959-4
[5]	M. Džamonja and S. Shelah On \(\triangleleft^\ast\)-maximality , Annals of Pure and Applied Logic , vol. 125(2004), pp. 119-158. · Zbl 1040.03029 · doi:10.1016/j.apal.2003.11.001
[6]	I. Farah, B. Hart, and D. Sherman Model theory of operator algebras II : model theory,2010, family
[7]	V. Guingona On uniform definability of types over finite sets ,2010, family · Zbl 1255.03039 · doi:10.2178/jsl/1333566634
[8]	H. J. Keisler Ultraproducts which are not saturated , Journal of Symbolic Logic, vol. 32(1967), pp. 23-46. · Zbl 0162.01501 · doi:10.2307/2271240
[9]	S. Kochen Ultraproducts in the theory of models , Annals of Mathematics. Second Series , vol. 74(1961), no. 2, pp. 221-261. · Zbl 0132.24602 · doi:10.2307/1970235
[10]	J. Komlós and M. Simonovitz Szemerédi’s regularity lemma and its applications in graph theory , Combinatorics, Paul Erdős is eighty. Volume 2, Bolyai Society Mathematical Studies, Budapest,1996, pp. 295-352. · Zbl 0851.05065
[11]	K. Kunen Ultrafilters and independent sets , Transactions of the American Mathematical Society , vol. 172(1972), pp. 299-306. · Zbl 0263.02033 · doi:10.2307/1996350
[12]	M. Malliaris Realization of \(\varphi\)-types and Keisler’s order , Annals of Pure and Applied Logic , vol. 157(2009), pp. 220-224. · Zbl 1159.03022 · doi:10.1016/j.apal.2008.09.008
[13]	—- The characteristic sequence of a first-order formula , Journal of Symbolic Logic, vol. 75(2010), no. 4, pp. 1415-1440. · Zbl 1220.03019 · doi:10.2178/jsl/1286198155
[14]	—- Edge distribution and density in the characteristic sequence , Annals of Pure and Applied Logic , vol. 162(2010), no. 1, pp. 1-19. · Zbl 1225.03035 · doi:10.1016/j.apal.2010.06.009
[15]	S. Shelah Simple unstable theories , Annals of Mathematical Logic , vol. 19(1980), pp. 177-203. · Zbl 0489.03008 · doi:10.1016/0003-4843(80)90009-1
[16]	—- Classification theory and the number of non-isomorphic models , revised ed., North-Holland,1990. · Zbl 0713.03013
[17]	—- The universality spectrum: Consistency for more classes , Combinatorics: Paul Erdős is eighty. Volume 1, Bolyai Society Mathematical Studies, Budapest,1993, pp. 403-420. · Zbl 0805.03020
[18]	—- Toward classifying unstable theories , Annals of Pure and Applied Logic , vol. 80(1996), pp. 229-255. · Zbl 0874.03043 · doi:10.1016/0168-0072(95)00066-6
[19]	S. Shelah and A. Usvyatsov More on \({\mathrm SOP}_1\) and \({\mathrm SOP}_2\) , Annals of Pure and Applied Logic , vol. 155(2008), no. 1, pp. 16-31. · Zbl 1154.03015 · doi:10.1016/j.apal.2008.02.003