HYPERGRAPH SEQUENCES AS A TOOL FOR SATURATION OF ULTRAPOWERS

作者：Malliaris M E^*

来源：Journal of Symbolic Logic, 2012, 77(1): 195-223.

Let T-1, T-2 be countable first-order theories, M-1 satisfies T-1, and D any regular ultrafilter on lambda >= N-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, D, if the ultrapower (M-2)lambda/D realizes all types over sets of size <= 2, then so must the ultrapower (M-1)lambda/D. In this paper, building on the author's prior work [12] [13] [14], 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 TP2 theory, and that maximality is implied by the density of certain graph edges (between components arising from Szemeredi-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 TP2 theory is flexible.

• 出版日期2012-3