1 Introduction
Classification theory is a line of research in model theory, started essentially by Shelah, in which we define and study dividing lines that differentiate classes of theories in order to understand their complexity and behavior. One of the first dividing lines, introduced by Shelah, is stability (see Definition 2.1), defined as a generalization of Morley’s notion of totally transcendental theories. Stable theories can be characterized by the absence of a local combinatorial property on definable sets (Order Property, See Definition 2.1, (1)). As shown by Shelah, the presence of this local property (the theory is said to be unstable in this case) implies bad structural behaviors of the theory. For instance
Theorem (Shelah,[Reference Shelah20]).
If T is unstable and
$\lambda> |T| + \aleph _0$
, then T has exactly
$2^\lambda $
non-isomorphic models of size
$\lambda $
.
On the other hand, the assumption of stability provides methods and tools to analyze and understand this class of theories. The rich framework provided by stability led researchers to try to extend these methodologies outside stability, defining more and more dividing lines and giving structure to the universe of first-order theories.
Two prototypical examples of unstable theories, dense linear orders without endpoints and the theory of the random graph, led to the definition of two incomparable extensions of the class of stable theories whose intersection characterizes it:
$\mathrm {NIP}$
and
$\mathrm {NSOP}$
(see Definition 2.1 and Fact 2.2). In order to study the existence of saturated elementary extensions of models of first-order theories, Shelah (in [Reference Shelah21]) isolated a class of theories, extending stability, called simple theories (omitting the tree property, see Definition 2.1, (4)). Simple theories were then intensely studied by Hrushovski, Chatzidakis, Pillay, Kim et al. (see, e.g., [Reference Chatzidakis and Hrushovski2, Reference Hrushovski and Pillay9, Reference Kim11, Reference Kim and Pillay13, Reference Kim and Pillay14]), showing that, with the assumption of omitting the tree property, many typically stability-theoretic tools behave correctly and are useful in this enlarged framework. A plethora of dividing lines has been defined, along with great developments regarding the classes of theories that are characterized by them, making classification theory a rich and exciting line of research in model theory.
Many of these dividing lines are defined, similarly to stability, by the absence of specific configurations of definable sets. In this paper, abstracting the essential and combinatorial nature of these properties, we introduce the concept of patterns of consistency and inconsistency (see Definition 3.1) in order to give a general framework for talking about dividing lines. This concept was first defined by Shelah in with a different notation and more recently appeared in in a fashion similar to ours.
Patterns essentially describe abstract configurations of finite collections of sets by asserting conditions about the emptiness (or not) of their intersections. A formula exhibits a pattern in a theory if there are parameters in a model of the theory such that the sets defined by the formula and the parameters satisfy the conditions described by the pattern (see Definition 3.2). In this sense, we can capture the combinatorial properties that define dividing lines by exhibition of patterns (a similar approach to ours can be found in [Reference Guingona and Hill8]). In Section 3, we define all the notions relative to patterns and describe this general framework for dividing lines.
On the wild side of every previously considered dividing line, two notions of maximal complexity for a complete first-order theory have been defined: Cooper’s property
$1$
(see [Reference Cooper7]) and “an extreme condition of the form of unstability” called Straight Maximality (
$\mathrm {SM}$
) defined by Shelah [Reference Shelah24]. In Section 4, we show that these two notions are equivalent and fit in the framework of exhibition of patterns. Indeed, these two properties are characterized by the existence of a formula exhibiting all the exhibitable (see Definition 3.2) patterns. We kept a name similar to Shelah’s for this property (Straight up Maximality).
One of the main approaches in classification theory, as we described above, is to extend nice properties and tools on the tame side of some dividing line to a wider class of theories. Here we reverse the approach and start from the worst (in some sense) combinatorial property that a complete first-order theory can have and study how theories behave when we weaken this bad property. Using this methodology, in Section 5, we define weakenings of
$\mathrm {SM}$
by requesting the presence of a formula exhibiting a smaller collection of patterns, guided by the examples of previously defined properties of formulas. For instance, both
$\mathrm {OP}$
and
$\mathrm {IP}$
do not require any inconsistency conditions. We thus define Consistency Maximality (
$\mathrm {CM}$
, see Definition 5.10) by requiring the existence of a formula realizing all the patterns without inconsistency conditions. We show that
$\mathrm {CM}$
is equivalent to
$\mathrm {IP}$
(even at the level of formulas), giving a different perspective to this well-known property. Other dividing lines, such as
$\mathrm {TP}$
,
$\mathrm {TP}_1$
, and
$\mathrm {TP}_2$
(see Definition 2.1, (4)–(6)), can be characterized by realizing patterns in which the negation of the formula is not involved. Using this observation, we define a collection of patterns (positive patterns, see Definition 5.1) and a weaker version of
$\mathrm {SM}$
, called Positive Maximality (
$\mathrm {PM}$
, see Definition 5.2) by requesting the existence of a formula exhibiting all the positive patterns. In particular, all the properties that can be characterized by realization of positive patterns are implied by
$\mathrm {PM}$
. Since our characterization of
$\mathrm {SOP}$
uses patterns that are not positive, a natural question is the following
Question. Is there a positive maximal
$\mathrm {NSOP}$
theory?
In Section 5, we answer positively to the above question by finding an example of an
$\mathrm {NSOP}_4$
(see Definition 2.1, (
$7_4$
)) positive maximal theory (see Example 5.7). In particular, this shows that neither
$\mathrm {SOP}$
nor
$\mathrm {SOP}_n$
for
$n \geq 4$
(see Definition 2.1, (
$7_n$
)) can be characterized through positive patterns. We point out that, in [Reference Kaplan, Ramsey and Simon10, Lemma 7.3], Kaplan, Ramsey, and Simon proved a characterization of
$\mathrm {SOP}_3$
which can be obtained by exhibition of positive patterns.
In Section 6, by putting restraints on the size of the inconsistency conditions in positive patterns, we define a collection of properties
$(\mathrm {PM}^{(k)})_{1<k<\omega }$
(see Definition 6.1), weaker than
$\mathrm {PM}$
but still strong enough to imply all the classical positive dividing lines. We show that, at the level of theories,
$\mathrm {PM}^{(k+1)}$
implies
$\mathrm {PM}^{(k)}$
(see Proposition 6.5) and we give
$\mathrm {NSOP}_4$
,
$\mathrm {PM}^{(k)}$
and
$\mathrm {NPM}^{(k+1)}$
examples showing that the above implication is strict (see Example 6.13). We show that
$\mathrm {PM}^{(k)}$
is equivalent to the realization (in some sense) of every finite k-hypergraph and can be witnessed by a (generic ordered k-hypergraph)-indexed generalized indiscernible. The k-independence property (
$\mathrm {IP}_k$
) is a higher-arity version of
$\mathrm {IP}$
introduced by Shelah. In [Reference Chernikov, Palacin and Takeuchi3], Chernikov, Palacin, and Takeuchi showed the equivalence of
$\mathrm {NIP}_k$
with the collapse of the above kind of generalized indiscernibles. This led the way for showing the following result.
Theorem (See 6.11).
For every
$0<k<\omega $
, if T is
$\mathrm {PM}^{(k+1)}$
, then T has
$\mathrm {IP}_k$
.
The notions of maximality introduced in this paper as essentially given by binary properties. The above result shows, in particular, that the binary notion of positive maximality (PM) implies all the k-ary versions of
$\mathrm {IP}$
(at each step of the way). We also point out that there are examples of simple
$\mathrm {IP}_k$
theories, and thus
$\mathrm {PM}^{(k+1)}$
is not equivalent to
$\mathrm {IP}_k$
.
Many questions arise about these notions of maximality, the behavior of classes of theories defined by them and their relations with previously defined dividing lines. For instance, which of the standard examples of
$\mathrm {SOP}_3$
but
$\mathrm {NSOP}$
theories are
$\mathrm {PM}$
(or
$\mathrm {PM}^{(k)}$
for some
$1<k<\omega $
)? Is there an
$\mathrm {SOP}_3$
but
$\mathrm {NSOP}$
and
$\mathrm {NPM}^{(2)}$
theory? If not, we would have that
$\mathrm {NSOP} \cap \mathrm {NPM}^{(2)} = \mathrm {NSOP}_3$
; this would imply the collapse of the
$\mathrm {SOP}_n$
hierarchy inside
$\mathrm {NTP}_2$
.
2 Preliminaries
Unless otherwise stated, in what follows T is a complete first-order
$\mathcal {L}$
-theory,
$\mathcal {U} \models T$
is a monster model. Whenever we state the existence of some tuples, we mean tuples of elements from
$\mathcal {U}$
and every set is a small (of cardinality less then the saturation of
$\mathcal {U}$
) subset of
$\mathcal {U}$
. Frequently we work with partitioned formulas
$\varphi (x;y)$
in which the free variables are divided into object variables and parameters variables (the variables x and
$y,$
respectively). Moreover, whenever we write
$x,y,z,\dots $
for variables we mean tuples of variables (not necessarily singletons) and, as a notation, we write
$\mathcal {U}^x,\mathcal {U}^y,\mathcal {U}^z,\dots $
for the set of tuples of elements of
$\mathcal {U}$
that can be plugged in for
$x,y,z,\dots ,$
respectively. By convention, particularly when dealing with the class of finite models of a theory in a relational language, we allow the empty structure. This simplifies the proof that a class of finite structures is a Fraïssé class (see Examples 5.7 and 6.13). We note that the results are easily seen to still be true even when we exclude the empty structure.
2.1 Dividing lines
We recall the definition of some of the properties defining dividing lines in the universe of first-order theories. Most of these properties were introduced by Shelah in [Reference Shelah19] and [Reference Shelah22]. For the definitions and a bird’s-eye view of the universe, we refer to [Reference Conant4].
Definition 2.1. A partitioned formula
$\varphi (x;y)$
has
-
(1) the order property (
$\mathrm {OP}$
) if there are tuples
$(a_ib_i)_{i<\omega }$
such that
$$\begin{align*}\models \varphi(a_i;b_j) \iff i<j\end{align*}$$
-
(2) the independence property (
$\mathrm {IP}$
) if there are tuples
$(a_i)_{i<\omega }$
and
$(b_I)_{I \subseteq \omega }$
such that
$$\begin{align*}\models \varphi(a_i;b_I) \iff i \in I\end{align*}$$
-
(3) the strict-order property (
$\mathrm {SOP}$
) if there are tuples
$(b_i)_{i<\omega }$
such that
$$\begin{align*}\models \exists x (\varphi(x;b_j) \land \neg\varphi(x;b_i)) \iff i < j\end{align*}$$
-
(4) the k-tree property (k-
$\mathrm {TP}$
) if there exist tuples
$(b_\eta )_{\eta \in \omega ^{<\omega }}$
such that-
• paths are consistent: for all
$f \in \omega ^\omega $
, we have that
$\{\varphi (x;b_{f|i}) \ : \ i <\omega \}$
is consistent, and -
• levels are k-inconsistent: for all
$\eta \in \omega ^{<\omega }$
,
$\{\varphi (x;b_{\eta \frown i}) \ : \ i<\omega \}$
is k-inconsistent (i.e., every subset of size k is inconsistent).
It has the tree property (
$\mathrm {TP}$
) if it has k-
$\mathrm {TP}$
for some
$1<k<\omega $
-
-
(5) the tree property of the first kind (
$\mathrm {TP}_1$
) if there are tuples
$(b_{\eta })_{\eta \in \omega ^{<\omega }}$
such that-
• paths are consistent: for all
$f \in \omega ^\omega $
, we have that
$\{\varphi (x;b_{f|i}) \ : \ i<\omega \}$
is consistent, and -
• incomparable elements are inconsistent: for all incomparable
$\eta ,\mu \in \omega ^{<\omega }$
, we have that
$\{\varphi (x;b_\eta ),\varphi (x;b_\mu )\}$
is inconsistent.
-
-
(6) the k-tree property of the second kind (k-
$\mathrm {TP}_2$
) if there are tuples
$(b_i^j)_{i,j<\omega }$
such that-
• paths are consistent: for every
$f \in \omega ^\omega $
, we have that
$\{\varphi (x;b_{i}^{f(i)}) \ : \ i<\omega \}$
is consistent, and -
• rows are k-inconsistent: for each
$i<\omega $
,
$\{\varphi (x;b_i^j) \ : \ j<\omega \}$
is k-inconsistent.
It has the tree property of the second kind (
$\mathrm {TP}_2$
) if it has k-
$\mathrm {TP}_2$
for some
$1<k<\omega $
. -
-
(7 n ) n-strong order property
$(\mathrm {SOP}_n)$
for some
$n\geq 3$
, if
$|x| = |y|$
and there are
$(a_i)_{i<\omega }$
such that for all
$i<j$
, we have
$\varphi (a_i;a_j)$
and the set is inconsistent.
$$\begin{align*}\{\varphi(x_1;x_2),\varphi(x_2;x_3),\dots,\varphi(x_{n-1},x_n),\varphi(x_n,x_1)\}\end{align*}$$
A complete first-order theory T is
-
• stable if no formula has
$\mathrm {OP}$
in T. It is said to be unstable otherwise. -
• simple if no formula has
$\mathrm {TP}$
in T. -
•
$Np$
if no formula has p in T, where
$p \in \{\mathrm {IP},\mathrm {SOP},\mathrm {TP}_1,\mathrm {TP}_2, \mathrm {SOP}_n\}$
; otherwise, we say that T has p. For instance, T is
$\mathrm {NIP}$
if no formula has
$\mathrm {IP}$
in T; if there is a formula with
$\mathrm {IP}$
in T, we say that T has
$\mathrm {IP}$
.
The reader can find a diagram of known relations and implications between these properties below.
Fact 2.2. The following relations hold for properties of complete first-order theories.
-
• Stable =
$\mathrm {NIP} \cap \mathrm {NSOP}$
. -
• Simple =
$\mathrm {NTP}_1 \cap \mathrm {NTP}_2$
.
Proof. For the proofs of the above we refer to [Reference Casanovas1, Reference Conant5, Reference Kim and Kim12], and [Reference Shelah19].
2.2 Generalized indiscernibles
We review the basic definitions and notions around generalized indiscernibles, introduced by Shelah in [Reference Shelah19] and developed by Scow in [Reference Scow17, Reference Scow18].
Definition 2.3. Fix a language
$\mathcal {L}'$
,
$\mathcal {L}'$
-structures I and
$J,$
and tuples
$b_i = f(i)$
,
$c_j = g(j)$
of some fixed length
$\ell $
for some
$f\colon I \to \mathcal {U}^\ell $
and
$g\colon J \to \mathcal {U}^\ell $
.
-
(1) We say that
$(b_i)_{i \in I}$
is an I-indexed generalized indiscernible (or just I-indiscernible) if for all
$n<\omega $
and for all
$\bar {i} = i_0,\dots ,i_{n-1}$
and
$\bar {j} = j_0,\dots ,j_{n-1}$
from I, we have
$$\begin{align*}\mathrm{qftp}_{\mathcal{L}'}(\bar{i}) = \mathrm{qftp}_{\mathcal{L}'}(\bar{j}) \Rightarrow \mathrm{tp}_{\mathcal{L}}(b_{\bar{i}}) = \mathrm{tp}_{\mathcal{L}}(b_{\bar{j}}).\end{align*}$$
-
(2) We say that
$(b_i)_{i \in I}$
is based on
$(c_j)_{j \in J}$
if for any finite set of formulas
$\Sigma $
, for any
$n<\omega $
and any tuple
$\bar {i} = i_0\dots i_{n-1}$
from
$I,$
there is a tuple
$\bar {j} = j_0\dots j_{n-1}$
from J with
$\mathrm {qftp}_{\mathcal {L}'}(\bar {i}) = \mathrm {qftp}_{\mathcal {L}'}(\bar {j})$
, such that
$$\begin{align*}\mathrm{tp}_\Sigma(b_{\bar{i}}) = \mathrm{tp}_\Sigma(c_{\bar{j}}).\end{align*}$$
-
(3) We say that I has the modeling property if given any
$(c_i)_{i \in I}$
there exists an I-indiscernible
$(b_i)_{i \in I}$
based on
$(c_i)_{i \in I}$
.
Fact 2.4 (Stretching indiscernibles, see [Reference Scow18]).
Let I be an
$\mathcal {L}'$
-structure,
$(b_i)_{i \in I} I$
-indiscernible. Then, for any
$\mathcal {L}'$
-structure J with
$\mathrm {age}(J) \subseteq \mathrm {age}(I)$
, we can find J-indiscernible
$(c_j)_{j \in J}$
based on
$(b_i)_{i \in I}$
.
In her thesis [Reference Scow18], Scow showed a profound connection between Ramsey classes (see, e.g., [Reference Scow18, Definition 3.2.6]) and the modeling property for generalized indiscernibles.
Fact 2.5. Let I be a structure in a finite relational language and
$\mathcal {K} = \mathrm {age}(I)$
. Then
$\mathcal {K}$
is a Ramsey class if and only if I has the modeling property.
Fact 2.6. Let
$k\geq 2$
. Applying the “main theorem” in [Reference Nešetřil and Rödl16], we have that the class of finite ordered k-hypergraphs is a Ramsey class. By Fact 2.5, the generic ordered k-hypergraph has the modeling property.
3 Patterns of consistency and inconsistency
In this section, we want to describe a general framework for talking about combinatorial properties defining dividing lines. We start with a visual representation of some of the properties of formulas defined in Definition 2.1.
The OP for a formula
$\varphi (x;y)$
can be represented as follows: there are
$(b_i)_{i<\omega }$
from
$ \mathcal {U}^y$
such that, for each
$i<\omega ,$
we have
where the dashed lines represent
$\neg \varphi $
and the solid lines represent
$\varphi $
. Similarly, the IP can be visualized as follows: there are
$(b_i)_{i<\omega }$
from
$\mathcal {U}^y$
such that for every
$X\subseteq \omega $
(circled elements below):
A new element of complexity is added for describing the SOP: there is
$(b_i)_{i<\omega }$
from
$\mathcal {U}^y$
such that for all
$i<\omega ,$
we have
We see that the these properties are realized by satisfying consistency (
$\exists x$
) or inconsistency (
$\neg \exists x$
) requests on positive (solid line, i.e.,
$\varphi $
) or negative (dashed line, i.e.,
$\neg \varphi $
) instances of the formula
$\varphi (x;y)$
on subsets of the set of parameters. We are now ready to define patterns as pairs
$(\mathcal {C},\mathcal {I})$
where
$\mathcal {C}$
and
$\mathcal {I}$
will be sets of conditions of the form
$(X^+,X^-)$
; the conceptual correspondence should be
$$ \begin{align*} &\mathcal{C} \longleftrightarrow \exists x &X^+ \longleftrightarrow \varphi\\ &\mathcal{I} \longleftrightarrow \neg \exists x &X^- \longleftrightarrow \neg \varphi. \end{align*} $$
Definition 3.1. Fix
$n<\omega $
. An n-pattern (of consistency and inconsistency) is a pair
$(\mathcal {C},\mathcal {I})$
where
$\mathcal {C},\mathcal {I} \subseteq \mathcal {P}(n) \times \mathcal {P}(n) \setminus \{(\emptyset ,\emptyset )\}$
.
A pair
$(X^+,X^-)$
in
$\mathcal {C}$
(resp., in
$\mathcal {I}$
) is called a consistency (resp., inconsistency) condition, or just condition, of the pattern
$(\mathcal {C},\mathcal {I})$
.
Definition 3.2. Let
$\varphi (x;y)$
be a partitioned formula, let
$n<\omega $
and let
$(\mathcal {C},\mathcal {I})$
be an n-pattern. We say that
$\varphi (x;y)$
exhibits (or realizes) the pattern
$(\mathcal {C},\mathcal {I})$
(in T) if there is
$B = (b_i)_{i<n}$
from
$\mathcal {U}^y$
such that
-
(i) For all
$\mathcal {A} = (A^+,A^-) \in \mathcal {C}$
the partial
$\varphi $
-type is consistent, and
$$\begin{align*}p_{\mathcal{A}}^B(x) = \{\varphi(x;b_i) \ : \ i\in A^+\}\cup\{\neg \varphi(x;b_j) \ : \ j \in A^-\}\end{align*}$$
-
(ii) for all
$\mathcal {Z} = (Z^+,Z^-) \in \mathcal {I}$
, the partial
$\varphi $
-type is inconsistent.
$$\begin{align*}p_{\mathcal{Z}}^B(x) = \{\varphi(x;b_i) \ : \ i \in Z^+\}\cup\{\neg \varphi(x;b_j) \ : \ j \in Z^-\}\end{align*}$$
In the next proposition, we show how to characterize some of the dividing lines using exhibition of patterns.
Proposition 3.3. Let
$\varphi (x;y)$
be a partitioned formula. Then
-
(1)
$\varphi (x;y)$
has
$\mathrm {OP}$
if and only if, for all
$n<\omega $
, the formula
$\varphi (x;y)$
exhibits the n-pattern
$(\mathcal {C}_n,\mathcal {I}_n)$
where
$$\begin{align*}\mathcal{C}_n = \{(\{i,i+1,\dots ,n-1\},\{0,\dots ,i-1\}) \ : \ i<n\}\end{align*}$$
$$\begin{align*}\mathcal{I}_n = \emptyset.\end{align*}$$
-
(2)
$\varphi (x;y)$
has
$\mathrm {IP}$
if and only if, for all
$n<\omega $
, the formula
$\varphi (x;y)$
exhibits the n-pattern
$(\mathcal {C}_n,\mathcal {I}_n)$
where
$$\begin{align*}\mathcal{C}_n = \{(X,n\setminus X) \ : \ X \subseteq n\}\end{align*}$$
$$\begin{align*}\mathcal{I}_n = \emptyset.\end{align*}$$
-
(3)
$\varphi (x;y)$
has
$\mathrm {SOP}$
if and only if, for all
$n<\omega $
, the formula
$\varphi (x;y)$
exhibits the n-pattern
$(\mathcal {C}_n,\mathcal {I}_n)$
where
$$\begin{align*}\mathcal{C}_n = \{(\{i+1\},\{i\}) \ : \ i<n-1\}\end{align*}$$
$$\begin{align*}\mathcal{I}_n = \{(\{i\},\{i+1\}) \ : \ i<n-1\}.\end{align*}$$
-
(4) For
$1<k<\omega $
,
$\varphi (x;y)$
has k-
$\mathrm {TP}$
if and only if, for all
$n<\omega $
, the formula
$\varphi (x;y)$
exhibits the
$n^{<n}$
-pattern
$(\mathcal {C}_n,\mathcal {I}_n)$
where
$$\begin{align*}\mathcal{C}_n = \{(\text{ path}_i,\emptyset) \ : \ i \in n^n\}\end{align*}$$
where
$$\begin{align*}\mathcal{I}_n = \{(\{i_0,\dots ,i_{k-1}\},\emptyset) \ : \ i_0,\dots ,i_{k-1} \text{ children of the same node}\}\end{align*}$$
$\{path_i \ : \ i\in n^n\}$
is the collection of all the paths in the tree
$n^{<n}$
.
-
(5)
$\varphi (x;y)$
has
$\mathrm {TP}_1$
if and only if, for all
$n<\omega $
, the formula
$\varphi (x;y)$
exhibits the
$n^{<n}$
-pattern
$(\mathcal {C}_n,\mathcal {I}_n)$
where
$$\begin{align*}\mathcal{C}_n = \{(\text{ path}_i,\emptyset) \ : \ i \in n^n\}\end{align*}$$
with a similar notation as above.
$$\begin{align*}\mathcal{I}_n = \{(\{i,j\},\emptyset) \ : \ i,j \text{ are incomparable elements in the tree } n^{<n}\}\end{align*}$$
-
(6) For
$1<k<\omega $
,
$\varphi (x;y)$
has k-
$\mathrm {TP}_2$
if and only if, for all
$n<\omega $
, the formula
$\varphi (x;y)$
exhibits the
$n^2$
-pattern
$(\mathcal {C}_n,\mathcal {I}_n)$
where
$$\begin{align*}\mathcal{C}_n = \{(\text{ path}_i,\emptyset) \ : \ i \in n^n\}\end{align*}$$
Here, by a path in
$$\begin{align*}\mathcal{I}_n = \{(\{i_0,\dots ,i_{k-1}\},\emptyset) \ : \ i_0,\dots ,i_{k-1} \text{ are on the same row }\}.\end{align*}$$
$n^2$
, we mean a function
$f\colon n \to n, $
i.e., a choice of one element per row in the array
$n^2$
.
Proof. The characterization is clear. We get the usual definitions of the properties using compactness.
The above proposition shows that exhibition of patterns gives a general framework for talking about dividing lines in first-order theories. There are some exceptions. For instance, it is not clear whether the
$\mathrm {SOP}_n$
hierarchy, for
$n\geq 4$
, can be characterized using pattern exhibition. There exists a characterization of
$\mathrm {SOP}_3$
[Reference Kaplan, Ramsey and Simon10, Lemma 7.3] that can be described through patterns. We also want to point out that, in the above proposition,
$\mathrm {SOP}$
is the only property that is described using both consistency and inconsistency condition on both positive and negative instances of the formula.
Definition 3.4. We say that an n-pattern
$(\mathcal {C},\mathcal {I})$
is exhibitable if there is a theory T and a formula
$\varphi (x;y)$
such that
$\varphi $
exhibits
$(\mathcal {C},\mathcal {I})$
in T.
There are “syntactical reasons” that make a pattern not exhibitable; with the next definition, we want to exclude those reasons from the picture.
Definition 3.5. Fix
$n<\omega $
. A reasonable n-pattern (of consistency and inconsistency) is an n-pattern such that
-
(i) For all
$(Z^+,Z^-) \in \mathcal {I}$
and for all
$(Y^+,Y^-) \in \mathcal {C}$
, we have that
$Z^\epsilon \not \subseteq Y^\epsilon $
for some
$\epsilon \in \{+,-\}$
. -
(ii) For all
$(A^+,A^-) \in \mathcal {C}$
,
$A^+ \cap A^- = \emptyset $
. -
(iii) For all
$(Z^+,Z^-) \in \mathcal {I}$
,
$Z^+ \cap Z^- = \emptyset $
.
Remark 3.6. In the above definition, a failure of condition (iii) doesn’t really make a pattern not exhibitable; however, an inconsistency condition
$(Z^+,Z^-)$
for which
$Z^+ \cap Z^- \neq \emptyset $
doesn’t add any meaningful request to the pattern and thus we avoid it. We also want to point out that “reasonability” does not imply “exhibitability”. For example, a pattern in which
$\mathcal {I}$
contains both
$(\{0\},\emptyset )$
and
$(\emptyset ,\{0\})$
is not exhibitable.
Even assuming reasonability, deciding whether a pattern is exhibitable or not is a complex problem. More precisely, let
$\mathrm {PSAT}$
be the following decision problem: given
$n<\omega $
and a reasonable n-pattern
$(\mathcal {C},\mathcal {I})$
, is
$(\mathcal {C},\mathcal {I})$
exhibitable?
Proposition 3.7. The decision problem
$\mathrm {PSAT}$
is
$\mathrm {NP}$
-complete.
The idea of the proof is to first provide a more concrete characterization of exhibitability and then show how to reduce
$\mathrm {PSAT}$
to
$\mathrm {SAT}$
(the Boolean satisfiability probelm) and vice-versa. The complete proof of the above will appear in the author’s Ph.D. thesis.
Definition 3.8. Fix
$n<\omega $
. An n-pattern
$(\mathcal {C},\mathcal {I})$
is called condition complete, or just complete, if each one of its conditions is of the form
$(X,n\setminus X)$
.
Remark 3.9. Every complete pattern
$(\mathcal {C},\mathcal {I})$
with
$\mathcal {C} \cap \mathcal {I} = \emptyset $
is reasonable.
Remark 3.10. As a justification for the above nomenclature, consider that, given any n-pattern
$(\mathcal {C},\mathcal {I})$
and a formula
$\varphi (x;y)$
exhibiting it with witnesses
$B = (b_i)_{i<n}$
, each condition
$(X^+,X^-)$
is associated with a
$\varphi $
-type over B:
$$\begin{align*}p_{X^+,X^-}^B(x) = \{\varphi(x;b_i) \ : \ i \in X^+\} \cup \{\neg \varphi(x;b_j) \ : \ j \in X^-\}\end{align*}$$
that is asked to be consistent or inconsistent based on where the condition lies (in
$\mathcal {C}$
or in
$\mathcal {I,}$
respectively). Saying that a pattern is complete is saying that those types corresponding to conditions are all complete
$\varphi $
-types over B.
Definition 3.11. An n-pattern
$(\mathcal {C},\mathcal {I})$
is called fully complete if it is complete,
$\mathcal {C} \neq \emptyset $
and every condition of the form
$(X, n\setminus X)$
is either in
$\mathcal {C}$
or in
$\mathcal {I}$
but not both.
Proposition 3.12. Every fully complete pattern is exhibitable.
Proof. We actually show something stronger: there is a theory T and a formula
$\varphi $
such that, for every
$n<\omega $
and fully complete n-pattern,
$\varphi $
exhibits it.
Let T be the theory of infinite atomic Boolean algebras in the language
$\mathcal {L} = \{\cup ,\cap , (-)^c,0,1\}$
, work in a model
$\mathcal {B}$
, let
$\psi (x;y) = \mathrm {At}(x) \land x \leq y$
and define
$$\begin{align*}\varphi(x;yw_0w_1) = (\psi(x;y) \land w_0=w_1)\lor(\neg \psi(x;y) \land w_0 \neq w_1),\end{align*}$$
where
$\mathrm {At}(x)$
is the formula saying that x is an atom. Fix
$n<\omega $
and a fully complete n-pattern
$(\mathcal {C},\mathcal {I})$
. Enumerate
$\mathcal {C} = \{(A_j,n\setminus A_j) \ : \ j<k\}$
. Since the pattern is fully complete,
$\mathcal {C} \neq \emptyset $
, so
$k \geq 1$
. Moreover, let
$a_0,\dots ,a_{k-1}$
be k distinct atoms of
$\mathcal {B}$
.
First, assume that
$(\emptyset ,n) \notin \mathcal {I}$
. Let c any element of
$\mathcal {B}$
and, for each
$i<n$
, define
$$\begin{align*}b_i = \bigcup\{a_j \ : \ j<k, i \in A_j\}\end{align*}$$
and
$c_i^0 = c_i^1 = c$
. We claim that
$(b_ic_i^0c_i^1)_{i<n}$
witness the exhibition of
$(\mathcal {C},\mathcal {I})$
by
$\varphi $
. Indeed, let
$j<k$
and consider the condition
$(A_j,n \setminus A_j) \in \mathcal {C}$
. We have that
$i \in A_j$
if and only if
$a_j \leq b_i$
if and only if
$a_j \models \mathrm {At}(x) \land x \leq b_i$
if and only if
$a_j \models \varphi (x;b_ic_i^0c_i^1)$
. This holds for every
$j<k$
and thus any consistency condition is satisfied. Let
$(Z,n\setminus Z) \in \mathcal {I}$
. By assumption
$Z \neq \emptyset $
. Assume, toward contradiction, that there is
$a \in \mathcal {U}^x$
, such that
$\models \varphi (a;b_ic_i^0c_i^1)$
if and only if
$i \in Z$
. Since
$Z \neq \emptyset $
, there is at least one i such that a is an atom below
$b_i$
. Thus there exists
$j<k$
such that
$a = a_j$
. But now
$i \in Z$
if and only if
$\models \varphi (a_j;b_ic_i^0c_i^1)$
if and only if
$a_j \leq b_i$
if and only if
$i \in A_j$
. Thus
$Z = A_j$
and
$(Z,n\setminus Z) \in \mathcal {C}$
. Contradiction. Thus, in the case that
$(\emptyset ,n) \notin \mathcal {I}$
, we are done.
Assume now that
$(\emptyset ,n) \in \mathcal {I}$
. Fix two distinct elements of the model
$c,c'$
and for
$i<n$
,
$i \notin A_0$
, define
$$\begin{align*}b_i = \bigcup\{a_j \ : \ j<k, i \in A_j\} \quad \text{ and take } c_i^0 = c = c_i^1. \end{align*}$$
For
$i \in A_0$
, define
$$\begin{align*}b_i = \bigcup\{a_j \ : \ j<k, i \notin A_j\} \quad \text{ and take } c_i^0 = c \neq c' = c_i^1. \end{align*}$$
Let
$B = (b_ic_i^0c_i^1)_{i<n}$
. Fix
$(A_j,n\setminus A_j) \in \mathcal {C}$
and suppose
$j \neq 0$
. If
$i \in n \setminus A_0$
, we have
$$\begin{align*}a_j \models \varphi(x;b_i\bar{c_i}) \iff \mathrm{At}(a_j) \land (a_j \leq b_i) \iff a_j \leq b_i \iff i \in A_j \setminus A_0.\end{align*}$$
If
$i \in A_0$
, we have
$$\begin{align*}a_j \models \varphi(x;b_i\bar{c_i}) \iff \neg \mathrm{At}(a_j) \lor (a_j \not \leq b_i)\end{align*}$$
$$\begin{align*}\iff a_j \not \leq b_i \iff a_j \leq b_i^c = (\bigcup_{i \notin A_j} a_j)^c = \bigcap_{i \notin A_j}a_j^c \iff i \in A_j.\end{align*}$$
Hence, if
$(A_j, n \setminus A_j) \neq (A_0,n\setminus A_0)$
,
$a_j \models p_{A_j,n \setminus A_j}^B(x)$
. Consider now
$(A_0,n \setminus A_0)$
and fix an element b that is not an atom. Then, if
$i \in A_0$
, since
$b \models \neg \mathrm {At}(x)$
,
$b \models \varphi (x;b_icc')$
. If
$i \notin A_0$
, then, since
$b \not \models \mathrm {At}(x) $
,
$b \models \neg \varphi (x;b_icc)$
. Thus, we showed that each consistency condition is satisfied.
Fix now
$(Z,n\setminus Z) \in \mathcal {I}$
. First assume that
$Z = \emptyset $
; we want to show that for any
$a \in \mathcal {B}$
, there is
$i<n$
such that
$a \models \varphi (x;b_i\bar {c}_i)$
. If
$a \notin \mathrm {At}(\mathcal {B})$
, then
$a \models \neg \mathrm {At}(x)$
and hence
$a \models \varphi (x;b_i,cc')$
for any
$i \in A_0$
. If
$a \in \mathrm {At}(\mathcal {B}) \setminus (a_j)_{0<j<k}$
, then
$a \not \leq b_i$
for
$i \in A_0$
and hence
$a \models \varphi (x;b_icc')$
. If
$a = a_j \neq a_0$
, then
$a_j \models \varphi (x;b_icc)$
for
$i \in A_j$
(note that
$A_j \neq \emptyset $
since
$(\emptyset ,n) \in \mathcal {I}$
). Hence
$p_{(\emptyset ,n)}^B(x)$
is inconsistent.
Assume
$Z \neq \emptyset $
and suppose that there is
$a \in \mathcal {B}$
such that
$$\begin{align*}a \models \varphi(x;b_i\bar{c}_i) \iff i \in Z.\end{align*}$$
If a is not one of the
$(a_j)_{j<k}$
, then
$a \models \varphi (x;b_i\bar {c}_i) \iff i \in A_0$
and hence
$A_0 = Z$
. Contradiction.
If
$a = a_j$
for some
$0<j<k$
, then
$a=a_j \models \varphi (x;b_i\bar {c}_i) \iff i \in A_j$
and hence
$A_j = Z$
. Contradiction. If
$a = a_0$
, then if
$i \in A_0$
then
$a_0 = a \not \leq b_i$
and hence
$a \models \varphi (x;b_icc')$
; on the other hand, if
$i \notin A_0$
, then
$a_0 = a \not \leq b_i$
and hence
$a\not \models \varphi (x;b_icc) $
. Hence
$Z = A_0$
. Contradiction. Hence
$p_{(Z,n\setminus Z)}^B(x)$
is inconsistent.
In conclusion, for every
$n<\omega $
,
$\varphi $
exhibits every fully complete n-pattern.
Remark 3.13. In the above proof, we gave an example of a formula
$\varphi $
that, in a theory T, exhibits, for every
$n<\omega $
, every fully complete n-pattern. In the next proposition, we will show that any exhibitable pattern can be extended (in some sense) to a fully complete pattern. Thus, the above proof gives an example of a theory T and a formula
$\varphi $
such that for any
$n<\omega $
and any exhibitable n-pattern,
$\varphi $
exhibits it. This property is what, in the next section, we will call Straight up Maximality (similar to Shelah’s nomenclature from [Reference Shelah24]); thus the theory of infinite atomic Boolean algebras is an example of a straight up maximal theory.
Proposition 3.14. Fix
$n<\omega $
and let
$(\mathcal {C},\mathcal {I})$
any exhibitable n-pattern. Then, there exists a fully complete n-pattern
$(\mathcal {C}',\mathcal {I}')$
such that, if a formula exhibits
$(\mathcal {C}',\mathcal {I}')$
, then it exhibits
$(\mathcal {C},\mathcal {I})$
.
Proof. Since
$(\mathcal {C},\mathcal {I})$
is exhibitable, there is a theory T, a formula
$\varphi (x;y)$
and parameter
$B = (b_i)_{i<n}$
such that
$\varphi $
exhibits
$(\mathcal {C},\mathcal {I})$
in T with B. As a convention for this proof, a complete
$\varphi $
-type over B is not necessarily consistent. Let
$\mathrm {Con}(\varphi ,B)$
be the set of complete consistent
$\varphi $
-types over B and, similarly, let
$\mathrm {Inc}(\varphi ,B)$
be the set of complete inconsistent
$\varphi $
-types over B. To each complete
$\varphi $
-type p, we can associate a condition
$(X_p,n\setminus X_p)$
where
$X_p = \{i < n \ : \ \varphi (x;b_i) \in p\}$
. Define
$$\begin{align*}\mathcal{C}' = \{(A_p,n \setminus A_p) \ : \ p \in \mathrm{Con}(\varphi,B)\}\end{align*}$$
$$\begin{align*}\mathcal{I}' = \{(Z_p,n \setminus Z_p) \ : \ p \in \mathrm{Inc}(\varphi,B)\}.\end{align*}$$
Suppose
$\psi (x;y)$
exhibits
$(\mathcal {C}',\mathcal {I}')$
in T with
$B' = (b_i')_{i<n}$
.
Given
$(A^+,A^-) \in \mathcal {C}$
, since
$\varphi (x;y)$
exhibits
$(\mathcal {C},\mathcal {I})$
with B, we have that
$p_{(A^+,A^-)}^{B,\varphi }(x)$
is consistent and thus it is contained in some
$p \in \mathrm {Con}(\varphi ,B)$
. Thus, there is
$(A,n\setminus A) \in \mathcal {C}'$
such that
$(A^+,A^-) \subseteq (A,n \setminus A)$
. Since
$p_{(A,n\setminus A)}^{B',\psi }(x)$
is consistent, it must be that
$p_{(A^+,A^-)}^{B',\psi }(x)$
is consistent too.
Let
$(Z^+,Z^-) \in \mathcal {I}$
and assume, toward contradiction, that
$p_{(Z^+,Z^-)}^{B',\psi }(x)$
is realized by some
$a \in \mathcal {U}^x$
. By the choice of
$\varphi $
and B, we have that
$p_{(Z^+,Z^-)}^{B,\varphi }(x)$
is inconsistent; thus, for any
$X \subseteq n$
such that
$(Z^+,Z^-) \subseteq (X,n \setminus X)$
, we have that
$(X,n \setminus X) \in \mathcal {I}'$
. But now
$\mathrm {tp}^\psi (a/B')$
gives us a set
$X \subseteq n$
such that
$(Z^+,Z^-) \subseteq (X,n\setminus X)$
which is in
$\mathcal {I}'$
and the corresponding type has a realization. Contradiction.
4 Notions of maximality
In this section, we define a notion of maximal complexity for first-order theories by requesting the exhibition (by a single formula) of all the exhibitable patterns.
Definition 4.1. A formula
$\varphi (x;y)$
is Straight up Maximal (or just
$\mathrm {SM}$
) if, for every
$n<\omega $
and for every exhibitable n-pattern
$(\mathcal {C},\mathcal {I})$
,
$\varphi (x;y)$
exhibits
$(\mathcal {C},\mathcal {I})$
. A theory T is
$\mathrm {SM}$
if there is a formula which is
$\mathrm {SM}$
; otherwise, we say that T is
$\mathrm {NSM}$
.
Other notions of maximality were previously defined by Shelah [Reference Shelah24] and Cooper [Reference Cooper7]. We will see how both of them agree with our notion of maximality and we will give some examples of theories which present/omit this property.
4.1 Shelah’s maximality
In [Reference Shelah24], Shelah defined “an extreme condition of the form of unstability” called Straight Maximality.
Definition 4.2. A formula
$\varphi (x;y)$
is Shelah-
$\mathrm {SM}$
(Shelah’s straight maximal) if for every
$n<\omega $
and for every non-empty
$\mathscr {F} \subseteq 2^n$
there are
$b_0,\dots ,b_{n-1} \in \mathcal {U}^y$
such that: Given
$f \in 2^n$
,
$f \in \mathscr {F}$
if and only if there is
$a \in \mathcal {U}^x$
such that for every
$i<n$
,
$\models \varphi (a;b_i) \iff f(i) =1$
.
We can characterize the above property using patterns.
Proposition 4.3. A formula
$\varphi (x;y)$
is Shelah-
$\mathrm {SM}$
if and only if
$\varphi (x;y)$
exhibits every fully complete pattern.
Proof. Assume
$\varphi $
is Shelah-
$\mathrm {SM}$
, fix
$n<\omega $
and let
$(\mathcal {C},\mathcal {I})$
a fully complete n-pattern. Define
$\mathscr {F} = \{\mathrm {char}(X) \ : \ (X,n\setminus X) \in \mathcal {C}\} \subseteq 2^n$
where
$\mathrm {char}(X)\colon n \to 2$
is the characteristic function of
$X \subseteq n$
. Since
$\mathcal {C} \neq \emptyset $
(given that the pattern is fully complete), we have that
$\mathscr {F}$
is not empty. Let
$B = \{b_0,\dots ,b_{n-1}\}$
given by Shelah-
$\mathrm {SM}$
. Now, fix a condition
$(Y^+,Y^-) = (Y,n\setminus Y) \in \mathcal {C}$
. This corresponds to a function
$f\colon n \to 2$
,
$f \in \mathscr {F}$
, such that
$f(i) = 1$
if and only if
$i \in Y$
. Hence there is
$a \in \mathcal {U}^x$
such that
$\models \varphi (a;b_i)$
if and only if
$f(i) = 1$
if and only if
$i \in X$
; thus a witness the consistency of
$p_{Y^+,Y^-}^B(x)$
. Now, given a condition of inconsistency
$(Z^+,Z^-) = (Z,n\setminus Z) \in \mathcal {I}$
, if there was
$a \in \mathcal {U}^x$
such that
$\models \varphi (a;b_i)$
if and only if
$i \in Z$
if and only if
$\mathrm {char}(Z)(i) = 1$
, we would have that
$\mathrm {char}(Z) \in \mathscr {F}$
; but it’s not. Contradiction. Hence the type
$p_{Z^+,Z^-}^B(x)$
is inconsistent. This shows that
$\varphi $
exhibits
$(\mathcal {C},\mathcal {I})$
. In conclusion (of the proof of this direction),
$\varphi $
exhibits every fully complete pattern.
On the other hand, assume that
$\varphi $
exhibits every fully complete pattern. Given
$n<\omega $
and
$\emptyset \neq \mathscr {F} \subseteq 2^n$
, define the
$n $
-pattern.
$(\mathcal {C},\mathcal {I})$
as follows:
$$\begin{align*}\mathcal{C} = \{(f^{-1}(\{1\}), f^{-1}(\{0\})) \ : \ f \in \mathscr{F}\}\end{align*}$$
$$\begin{align*}\mathcal{I} = \{(f^{-1}(\{1\}), f^{-1}(\{0\})) \ : \ f \in 2^n \setminus \mathscr{F}\}.\end{align*}$$
Clearly this is a fully complete pattern. Along the lines of the proof of the previous part, it’s clear that a witness
$B = \{b_0,\dots ,b_{n-1}\}$
of the exhibition of
$(\mathcal {C},\mathcal {I})$
by
$\varphi $
is also a witness of
$\varphi $
being Shelah-
$\mathrm {SM}$
.
Proposition 4.4. A formula is Shelah-
$\mathrm {SM}$
if and only if it is
$\mathrm {SM}$
.
Proof. Let
$\varphi (x;y)$
be an
$\mathrm {SM}$
formula, i.e., it realizes every exhibitable pattern. Since every fully complete pattern is exhibitable,
$\varphi $
exhibits every fully complete pattern. Hence
$\varphi $
is Shelah-
$\mathrm {SM}$
by Proposition 4.3.
On the other hand, assume that
$\varphi (x;y)$
is Shelah-
$\mathrm {SM}$
; then it realizes every fully complete pattern. Given an exhibitable pattern
$(\mathcal {C},\mathcal {I})$
, by Proposition 3.14, there is a fully complete pattern
$(\mathcal {C}',\mathcal {I}')$
such that, if a formula realizes
$(\mathcal {C}',\mathcal {I}')$
then it realizes
$(\mathcal {C},\mathcal {I})$
. Since
$\varphi $
realizes every fully complete pattern, it realizes every exhibitable pattern. In conclusion, it is
$\mathrm {SM}$
.
4.2 Cooper’s maximality
In [Reference Cooper7], Cooper defined a condition called
$1$
, requesting the existence of a formula which defines, in some sense, all the possible Venn diagrams. They then proved that this property implies every other property of this kind. For more details about the background and the maximality property, we refer to [Reference Cooper7].
Definition 4.5 (Cooper [Reference Cooper7]).
-
• A property of formulas is any sequence
$\rho = (\rho _i)_{i<\omega }$
of consistent quantifier free (q.f.) formulas of
$\mathrm {BA}$
(the theory of Boolean algebras with the language
$\mathcal {L} = \{0,1,(-)^c,\cup ,\cap \}$
). -
• If
$\varphi (x,y)$
is a formula of a complete theory T and
$\psi (z)$
is a q.f. formula of
$\mathrm {BA}$
, we say that
$\varphi (x,y)$
admits
$\psi (z)$
in T if for some
$$\begin{align*}\mathcal{P}(\mathcal{M}^x) \models \psi(\varphi(\mathcal{M},a_0),\dots ,\varphi(\mathcal{M},a_{|z|-1}))\end{align*}$$
$\mathcal {M} \models T $
and some
$a_0,\dots ,a_{|z|-1} \in \mathcal {M}^x,$
i.e., there is some model of T and parameters such that, in the power set of the set of tuples of the model (of the right length) viewed as a Boolean algebra, the
$\varphi $
-definable sets given by the parameters satisfy
$\psi $
. Otherwise we say that
$\varphi (x,y)$
omits
$\psi (z)$
in T.
-
• If
$\rho $
is a property of formulas, we say that a formula
$\varphi (x,y)$
of a complete theory T admits
$\rho $
in T if there exists a strictly increasing sequence
$\alpha \in \omega ^\omega $
such that
$\varphi (x,y)$
admits
$\rho _{\alpha (i)}$
in T for every
$i<\omega $
. Otherwise we say that
$\varphi (x,y)$
omits
$\rho $
in T. Moreover we say that T admits
$\rho $
if there exists
$\varphi (x,y)$
of T such that
$\varphi (x,y)$
admits
$\rho $
in T. Otherwise T omits
$\rho $
.
Cooper’s notion of maximality (property
$1$
) is a property of formulas (as in Definition 4.5) which implies all the other properties of formulas. In order to define
$1$
, Cooper started with an enumeration of all the consistent q.f. formulas of
$\mathrm {BA}$
, say
$\{\psi _i \ : \ i <\omega \}$
, and defined
$$\begin{align*}\rho_i = \bigwedge_{j<i} \psi_i.\end{align*}$$
Finally,
$1$
is defined as the property of formulas
$(\rho _i)_{i<\omega }$
.
The next definition gives us a more explicit equivalent (at the level of theories) version of property
$1$
.
Definition 4.6 (Cooper [Reference Cooper7]).
For each
$0<n<\omega ,$
we define the property
$1^{(n)}$
as follows.
A formula
$\varphi (x,y)$
admits
$1^{(n)}$
in some complete theory T if for arbitrarily large
$n\leq m <\omega $
there are
$(b_i)_{i<m}$
in some model
$\mathcal {U}^y$
such that
-
(i) for any
$l\leq m$
and for any
$X \in \mathcal {P}(m)$
with
$|X| = l$
there is
$b_X$
such that
$$\begin{align*}\bigcup_{i \in X}\varphi(\mathcal{U},b_i) = \varphi(\mathcal{U},b_X),\end{align*}$$
-
(ii) for any
$Y \in \mathcal {P}(m)$
$$\begin{align*}\bigcap_{i \in Y}\varphi(\mathcal{U},b_i) = \emptyset \text{ if and only if } |Y|>n.\end{align*}$$
In other words,
$\varphi (x,y)$
admits
$1^{(n)}$
if and only if for arbitrarily large
$n\leq m <\omega $
there are
$m\ \varphi $
-definable sets such that the union of any
$l\leq m $
is still
$\varphi $
-definable but the intersection of any
$l\leq m$
of them is non-empty if and only if
$l \leq n$
.
Fact 4.7 (Cooper [Reference Cooper7]).
If T is a complete theory and
$0<n<\omega $
, the following hold
-
(1) If some formula
$\varphi (x,y)$
of T admits
$1^{(n)}$
in T then some formula
$\psi (x,z)$
of T admits
$1^{(1)}$
in T. -
(2) If some formula
$\psi (x,z)$
of T admits
$1^{(1)}$
in T, then some formula
$\chi (x,w)$
of T admits
$1$
in T.
Remark 4.8. The above fact shows that, at the level of theories, admitting the property
$1^{(n)}$
implies admitting the property
$1^{(1)}$
which, in turn, implies admitting the property
$1$
. Moreover, since each
$1^{(n)}$
can be described as a property of formulas and each property of formulas is implied by
$1$
, we have that, at the level of theories, each
$1^{(n)}$
is a different characterization of
$1$
.
Definition 4.9. A complete theory T is Cooper maximal if there is a formula which admits
$1$
(equivalently
$1^{(n)}$
) in T.
We are now ready to prove that Cooper’s maximality coincides with straight up maximality.
Proposition 4.10. Let T be a complete theory. T is Cooper maximal if and only if T is
$\mathrm {SM}$
.
Proof. Assume T is
$\mathrm {SM}$
and let
$\varphi (x;y)$
be the
$\mathrm {SM}$
formula witnessing it.
Claim. For each
$n<\omega ,$
there are
$(b_i)_{i<n}$
such that
$$\begin{align*}\varphi(\mathcal{U},b_i)\cap \varphi(\mathcal{U},b_j) = \emptyset \text{ for all }i\neq j < n\end{align*}$$
for each
$X \subseteq n$
, there is
$b_X$
such that
$$\begin{align*}\varphi(\mathcal{U},b_X) = \bigcup_{i \in X}\varphi(\mathcal{U},b_i). \end{align*}$$
Equivalently,
$\varphi (x;y)$
admits
$1^{(1)}$
.
Proof of the Claim:
Since
$\varphi (x;y)$
is
$\mathrm {SM}$
, it realizes every fully complete n-patterns and these patterns can be described by pairs
$(C,I)$
where
$C,I \subseteq \mathcal {P}(n)$
with
$C \cap I = \emptyset $
. Let
$n< \omega $
and consider the following
$2^n$
-pattern:
$$\begin{align*}C = \{\uparrow \{i\} \ : \ i<n\}\end{align*}$$
$$\begin{align*}I = \mathcal{P}(2^n) \setminus C\end{align*}$$
where
$\uparrow \{i\} = \{X \subseteq n \ : \ i \in X\}$
. Clearly
$I \cap C = \emptyset $
. Let
$(b_X)_{X \subseteq n}$
be the parameters given by
$\mathrm {SM}$
with this pattern. First notice that
$\varphi (\mathcal {U},b_{\{i\}}) \cap \varphi (\mathcal {U},b_{\{j\}}) = \emptyset $
. Indeed, suppose
$a \models \varphi (x,b_{\{i\}}) \land \varphi (x,b_{\{j\}})$
. Let
$A = \{\{k\} \subseteq n \ : \ a \models \varphi (x,b_{\{k\}}) \}$
. Since
$A \in I$
we have that the
$\varphi $
-type of a over
$(b_X)_{X \subseteq n}$
is inconsistent; contradiction.
Let
$X \subseteq n$
. We want to show that
$$\begin{align*}\varphi(\mathcal{U},b_X) = \bigcup_{i \in X} \varphi(\mathcal{U},b_{\{i\}})\end{align*}$$
Let
$a \models \varphi (x,b_{\{i\}})$
for some
$i \in X$
. Since
$\mathcal {P}(n)\setminus X \in I$
, it is inconsistent to be in
$\varphi (\mathcal {U},b_{\{i\}})$
but not in
$\varphi (\mathcal {U},b_X)$
; hence
$a \in \varphi (\mathcal {U},b_X)$
. If
$a \models \varphi (x,b_X)$
. Since
$\{X\} \in I$
, it is inconsistent to be in
$\varphi (\mathcal {U},b_X)$
but not in all the
$\varphi (x,b_{\{i\}})$
, hence there is
$i \in X$
such that
$a \in \varphi (\mathcal {U},b_{\{i\}})$
.
The claim shows that, if
$\varphi (x;y)$
is
$\mathrm {SM}$
, then it admits
$1^{(1)}$
. By Fact 4.7, there is a formula admitting
$1$
and thus T is Cooper maximal.
Assume now that T is Cooper maximal and let
$\varphi (x;y)$
admitting
$1$
. Since
$1$
is the strongest property of formulas, it is enough to prove that
$\mathrm {SM}$
can be described as a property of formulas. Indeed
$\mathrm {SM}$
is a property of formulas described by:
$$\begin{align*}\rho_m := \bigwedge_{n<m} \bigwedge_{\substack{(\mathcal{C},\mathcal{I}) \\ \text{ exhibitable }n\text{-p}}}( \bigwedge_{(Y^+,Y^-) \in \mathcal{C}}(\bigcap_{i\in Y^+}x_i \cap \bigcap_{j\in Y^{-}} (n \setminus x_j)) \neq 0 )\end{align*}$$
$$\begin{align*}\land \bigwedge_{(Z^+,Z^-) \in \mathcal{I}} (\bigcap_{i\in Z^+}x_i \cap \bigcap_{j\in Z^{-}} (n \setminus x_j)) = 0 ).\end{align*}$$
This shows that, if T is Cooper maximal, then it is
$\mathrm {SM}$
.
Remark 4.11. We want to point out that the above equivalence is only at the level of theories. Indeed, while a formula admitting
$1$
is
$\mathrm {SM}$
, if a formula is
$\mathrm {SM}$
, it admits
$1^{(1)}$
and thus (by Fact 4.7) there is a (possibly different) formula admitting 1.
4.3 Examples of
$\mathrm {SM}$
theories
Example 4.12 (Infinite atomic Boolean algebra).
In Proposition 3.12, we showed that the theory T of infinite atomic Boolean algebras is
$\mathrm {SM}$
by showing a formula that exhibits every exhibitable pattern. We now prove again this result using Cooper’s characterization of
$\mathrm {SM}$
(see Fact 4.7 and Proposition 4.10): It is enough to find a formula with
$1^{(1)}$
, i.e., a formula
$\varphi (x;y)$
such that, for any
$n<\omega $
there are
$(b_i)_{i<n}$
such that
-
•
$\varphi (\mathcal {U};b_i) \cap \varphi (\mathcal {U};b_j) = \emptyset $
for all
$i<j<n$
, and -
• for each
$X \subseteq n$
, there is
$b_X$
such that
$$\begin{align*}\varphi(\mathcal{U};b_X) = \bigcup_{i \in X} \varphi(\mathcal{U};b_i).\end{align*}$$
Work in some model
$\mathcal {B}$
. Let
$\mathrm {At}(x)$
be the formula saying that x is an atom and consider the formula
$$\begin{align*}\varphi(x;y) = \mathrm{At}(x) \land x \leq y.\end{align*}$$
Fix
$n<\omega $
and choose
$(b_i)_{i<n}$
such that
$\mathrm {At}(b_i)$
and
$b_i \neq b_j$
for
$i<j<n$
. Now
$\varphi (x;b_i) \land \varphi (x;b_j)$
is inconsistent for
$i<j<n$
. Moreover, if
$X \subseteq n$
, let
$b_X := \bigcup _{i \in X} b_i$
; then
$$\begin{align*}\varphi(\mathcal{B};b_X) = \bigcup\{b_i : b_i \leq b_X \land i<n\} = \bigcup_{i \in X} \varphi(\mathcal{B};b_i).\end{align*}$$
In conclusion
$\varphi (x;y)$
has
$1^{(1)}$
and thus T is
$\mathrm {SM}$
.
Non-example 4.13 (Atomless Boolean algebras).
Consider the theory T of atomless Boolean algebras in the language
$\mathcal {L} = \{\cup ,\cap ,\neg ,0,1\}$
. In [Reference Cooper7], Cooper proved that T does not admit
$1$
and thus, by Proposition 4.10, it is not
$\mathrm {SM}$
.
In the next section, we will show that, in T, the formula
$\varphi (x;y) = 0 \neq x \leq y$
exhibits every pattern
$(\mathcal {C},\mathcal {I})$
in which, for every
$(X^+,X^-) \in \mathcal {C} \cup \mathcal {I}$
,
$X^- = \emptyset $
(see Definition 5.1 and Remark 5.3). Thus,
$\varphi (x;y)$
is an example of what, in the next section, we will call a positive maximal formula (
$\mathrm {PM}$
formula, see Definition 5.2). Although being
$\mathrm {PM}$
,
$\varphi (x;y)$
does not exhibit every exhibitable pattern. For example, consider the
$3$
-pattern
$(\mathcal {C},\mathcal {I})$
defined by
$$\begin{align*}\mathcal{C} = \{(\{0\},\emptyset),(\{1\},\emptyset)\}\end{align*}$$
$$\begin{align*}\mathcal{I} = \{(\{0,1\},\emptyset),(\{0\},\{2\}),(\{1\},\{2\}),(\{2\},\{0,1\})\}.\end{align*}$$
This pattern describes three sets
$A_0,A_1,A_2$
with the conditions that
$A_0 \neq \emptyset \neq A_1$
,
$A_0 \cap A_1 = \emptyset ,$
and
$A_2 = A_0 \cup A_1$
. This pattern is clearly exhibitable (in any theory with models of size at least
$2$
, by the formula
$x = y_0 \lor x = y_1$
). On the other hand, it is easy to see that the formula
$\varphi (x;y) = 0\neq x \leq y$
does not exhibit it in T. We point out that this does not prove that T is not
$\mathrm {SM}$
; it just shows that
$\varphi (x;y)$
is not
$\mathrm {SM}$
.
Example 4.14 (Skolem arithmetic).
Skolem arithmetic is the first-order theory of the structure
$(\mathbb N,\cdot )$
. First of all, we observe that we can define the number
$1$
, the divisibility relation and the set of prime numbers:
-
•
$\mathrm {One}(x) = \forall y (x \cdot y = y)$
. -
•
$x|y = \exists z (y = x \cdot z)$
-
•
$P(x) = \neg \mathrm {One}(x) \land \forall y (y|x \to (\mathrm {One}(y) \lor y=x)).$
To show that this theory is
$\mathrm {SM}$
we use Cooper’s characterization of
$\mathrm {SM}$
showing a formula
$\varphi (x;y)$
with
$1^{(1)}$
. Define
$\varphi (x;y) = P(x) \land x|y$
and enumerate the prime numbers
$P(\mathbb N) = \{p_i \ : \ i<\omega \}$
. Fix
$n< \omega $
and for each
$i<n$
let
$b_i = p_i$
. Now, for
$i<j<n$
,
$\varphi (\mathbb N,b_i) \cap \varphi (\mathbb N,b_j) = \{p_i\} \cap \{p_j\} = \emptyset $
. Moreover, given
$X \subseteq n$
, take
$b_X = \prod _{i \in X}p_i$
. We have
$$\begin{align*}\varphi(\mathbb N,b_X) = \{p_i \ : \ i \in X\} = \bigcup_{i \in X}\{p_i\} = \bigcup_{i \in X}\varphi(\mathbb N,b_i).\end{align*}$$
In conclusion, Skolem arithmetic is
$\mathrm {SM}$
.
A similar argument shows that the first-order theory of
$(\mathbb Z,+, \cdot ,0,1)$
is
$\mathrm {SM}$
.
Since all the previous examples of
$\mathrm {SM}$
theories are not
$\omega $
-categorical, we now construct an
$\omega $
-categorical
$\mathrm {SM}$
theory.
Example 4.15 (
$\omega $
-categorical
$\mathrm {SM}$
theory).
Consider the complete theory of the two-sorted structure
$(2^\omega ,\mathrm {CLOP}(2^\omega ))$
in the language of Boolean algebras for the second sort and a binary relational symbol interpreted as the membership relation between a point of the Cantor space and one of its clopen sets.
In order to prove
$\omega $
-categoricity, we present this example as the complete theory of a Fraïssé limit of a class of finite models of a universal theory
$T_0$
, coding the two sorts with unary predicates. Consider the language
$\mathcal {L} = \{S,B,R\}\cup \mathcal {L}_{\mathrm {BA}}$
where
$\mathcal {L}_{\mathrm {BA}} = \{\cap , \cup , (-)^c,0,1\}$
is the language of Boolean algebras, S and B are unary predicates and R is a binary relation. For each
$\mathcal {L}_{\mathrm {BA}}$
term
$t(\bar {y})$
define an
$\mathcal {L}$
-formula
$\psi _t(x,\bar {y})$
as follows:
-
• If t is a variable y then
$\psi _t(x,y) = R(x,y)$
. -
• if t is
$1$
then
$\psi _t(x)$
is
$x=x$
. -
• if
$t_1(\bar {y})$
,
$t_2(\bar {y}')$
are terms, then
$\psi _{t_1 \cap t_2}(x,\bar {y}\bar {y}') = \psi _{t_1}(x,\bar {y}) \land \psi _{t_2}(x,\bar {y}')$
. -
• If
$t(\bar {y}) = (t'(\bar {y}))^c$
then
$\psi _{t}(x,\bar {y}) = \neg \psi _{t'}(x,\bar {y})$
.
Since
$0$
and
$\cup $
are definable from the other symbols, we can assume that the term t does not contain them.
Notice that, given an atomic
$\psi \in \mathcal {L}_{\mathrm {BA}}$
,
$\psi $
is of the form
$t_1(\bar {y}) = t_2(\bar {y}')$
for some
$\mathcal {L}_{\mathrm {BA}}$
-terms.
Consider the following
$\mathcal {L}$
-theory
$T_0$
:
-
(A 1) S and B partition the universe.
-
(A 2)
$R \subseteq S \times B$
. -
(A 3)
$B \models T_{BA}$
, i.e., B is a Boolean algebra. -
(A 4 t 1, t 2 ) For
$\mathcal {L}_{BA}$
-terms
$t_1(\bar {y})$
and
$t_2(\bar {y}')$
, we have
$$\begin{align*}(\forall \bar{y}\bar{y}' \in B)( t_1(\bar{y}) = t_2(\bar{y}') \rightarrow (\forall x \in S)(\psi_{t_1}(x,\bar{y})\leftrightarrow \psi_{t_2}(x,\bar{y}'))).\end{align*}$$
We claim that the class
$\mathcal {K} := Mod_{<\omega }(T_0)$
(i.e., the class of finite models of
$T_0$
) is a Fraïssé class and the theory of its limit is
$\mathrm {SM}$
. Intuitively, each structure in
$\mathcal {K}$
can be described as follows: we have a set S, a Boolean algebra
$B,$
and a relation R between the two disjoint subsets. The axiom scheme
$(A_4^{t_1,t_2})$
makes sure that we have a homomorphism of Boolean algebras
$$\begin{align*}h\colon B \to \mathcal{P}(S)\end{align*}$$
$$\begin{align*}b \mapsto R(S,b).\end{align*}$$
Thus, we have a realization of a homomorphic image of B as R-definable (over B) subsets of S.
To show that
$\mathcal {K}$
is a Fraïssé class, we need to show that
$\mathcal {K}$
has
$\mathrm {HP}$
,
$\mathrm {JEP}$
, and
$\mathrm {AP}$
and it is uniformly locally finite, i.e., there exists
$f\colon \omega \to \omega $
that bounds the size of structures in
$\mathcal {K}$
with respect to the number of their generators. First of all, since
$T_0$
is universal, we have that
$\mathcal {K}$
is closed under substructures (i.e.,
$\mathcal {K}$
has
$\mathrm {HP}$
). Moreover, since the structure
$(\emptyset ,\{0,1\})$
is an initial object in
$\mathcal {K}$
(i.e., it embeds uniquely in every structure in
$\mathcal {K}$
), we have that
$\mathrm {JEP}$
is implied by
$\mathrm {AP}$
.
Consider the function
$f \colon \omega \to \omega $
defined as
$f(n) = n+2^{2^n}$
. Now, given
$C \leq A \in \mathcal {K}$
with
$C = \langle C_{gen}\rangle $
,
$C_{gen} = \{s_0,\dots ,s_{l-1},b_0,\dots ,b_{k-1}\}$
and
$l+k=n$
, it’s easy to see that
$|C| \leq l + 2^{2^k} \leq f(n)$
. Thus
$\mathcal {K}$
is uniformly locally finite. It remains to show that
$\mathcal {K}$
has
$\mathrm {AP}$
.
Lemma 4.16. Given
$A,A' \in \mathcal {K}$
, there is an embedding
$A \to A'$
if and only if there is an embedding of Boolean algebras
$B(A) \to B(A')$
and a surjective homomorphism of Boolean algebras
$\mathcal {P}(S(A')) \to \mathcal {P}(S(A))$
such that the following commutes:
where
$h_A$
and
$h_{A'}$
are the Boolean algebra homomorphisms given by
$b \mapsto R(S,b)$
.
Proof. Suppose we have an embedding
$A \to A'$
. In particular, we have an embedding of Boolean algebras
$F \colon B(A) \to B(A')$
and an inclusion
$S(A) \subseteq S(A')$
such that for every
$s \in S(A)$
,
$R(s,b)$
if and only if
$R(s,F(b))$
. By taking
$X \mapsto X \cap S(A)$
, we have a surjective homomorphism of Boolean algebras
$\mathcal {P}(S(A')) \twoheadrightarrow \mathcal {P}(S(A))$
. Therefore, given
$b \in B(A)$
, we have
$$\begin{align*}h_{A'}(F(b)) \cap S(A) = R(S(A'),F(b)) \cap S(A) = R(S(A),b) = h_A(b)\end{align*}$$
Conversely, given the above diagram, we have a Boolean algebra embedding
$B(A) \to B(A')$
and by Stone duality, we get an injection
$S(A) \to S(A')$
. Commutativity of the diagram implies that the relation R is preserved by this pair of maps and thus we have an embedding of
$\mathcal {L}$
-structures
$A \to A'$
.
Remark 4.17. Using the proof of the above lemma, one could show an equivalence between the category
$\mathcal {K}$
with
$\mathcal {L}$
-embeddings and the comma category of the functors
$$\begin{align*}(\mathrm{FinBA},\mathrm{BA}\text{-}\mathrm{emb}) \xrightarrow[]{\mathrm{id}}(\mathrm{FinBA},\mathrm{BA}\text{-}\mathrm{hom}) \xleftarrow[]{\mathcal{P}} (\mathrm{FinSet}^{\mathrm{op}},\mathrm{injections}).\end{align*}$$
In particular, the data of an embedding of Boolean algebras
$B(A) \to B(A')$
together with a surjective Boolean algebra homomorphism
$\mathcal {P}(S(A')) \to \mathcal {P}(S(A)) $
, not only guarantees the existence of an
$\mathcal {L}$
-embedding, but it characterizes such embedding.
Proposition 4.18.
$\mathcal {K}$
has
$\mathrm {AP}$
.
Proof. Consider the following amalgamation problem in
$\mathcal {K}$
:
By our previous lemma, this translates to the following diagram with commutative squares:
Applying Stone duality, we get the following diagram in the category of finite sets, maintaining commutativity:
Performing the pullback and pushout (in the category of finite sets), we get
Now,
$S_1 \times _{S_0}S_2 = \{(a,b) \in S_1 \times S_2 \ : \ g_1(a) = g_2(b)\}$
and the functions
$p_i \colon S_1 \times _{S_0} S_2 \to S_i$
are the projections. Without loss of generality, we consider
$i,i',j,j'$
inclusions of sets. We want to define a function
$$\begin{align*}h\colon S(C)\sqcup_{S(A)}S(C') \to S_1 \times_{S_0}S_2\end{align*}$$
such that
$f_1 = p_1 \circ h \circ j$
and
$f_2 = p_2 \circ h \circ j'$
. Given
$x \in S(A)$
, define
$h(x) = (f_1(x),f_2(x))$
; since the outer paths are the same,
$(f_1(x),f_2(x)) \in S_1 \times _{S_0}S_2$
. Now, given
$x \in S(C)$
, since
$p_1$
is surjective, pick
$b \in S_2$
such that
$(f_1(x),b) \in S_1 \times _{S_0}S_2$
and define
$h(x) = (f_1(x),b)$
. Similarly, for
$x \in S(C')$
, since
$p_2$
is surjective, define
$h(x) = (a,f_2(x))$
for some
$a \in S_1$
such that
$(a,f_2(x)) \in S_1 \times _{S_0}S_2$
. It is easy to check that
$f_1 = p_1 \circ h \circ j$
and
$f_2 = p_2 \circ h \circ j'$
.
Dually, we get a Boolean algebra
$B(D) = \mathcal {P}(S_1 \times _{S_0}S_2)$
that solves the amalgamation problem
$B(A) \to B(C)$
and
$B(A) \to B(C')$
and a set
$S(D)$
with a homomorphism
$B(D) \to \mathcal {P}(S(D))$
. Using the lemma and commutativity of squares, we get a solution
$(B(D),S(D))$
to the initial amalgamation problem. In conclusion,
$\mathcal {K}$
has
$\mathrm {AP}$
.
Let T be the first-order theory of the Fraïssé limit of
$\mathcal {K}$
. We show that T is
$\mathrm {SM}$
. By Fact 4.7 and Proposition 4.10, it is enough to show that T has
$1^{(1)}$
. Let
$\varphi (x;y) = R(x,y)$
. Fix
$n<\omega $
and consider the finite model A of
$T_0$
given by
$B(A) = \mathcal {P}(n)$
and
$S(B) = n$
with
$R(i,X)$
if and only if
$i \in X$
. Now, for each
$i<n$
, define
$b_i = b_{\{i\}}$
. Clearly,
$R(A,b_i) \cap R(A,b_j) = R(n,b_i)\cap R(n,b_j) = \{i\} \cap \{j\} = \emptyset $
for all
$i<j<n$
. Moreover, given
$X \subseteq n$
, we have that
$$\begin{align*}R(A,b_X) = R(n,b_X) = X = \bigcup_{i \in X}\{i\} = \bigcup_{i \in X}R(A,b_i).\end{align*}$$
Embedding A into
$\mathcal {M}$
(by universality of
$\mathcal {M}$
), the above properties are preserved. Thus
$R(x,y)$
is
$\mathrm {SM}$
in T.
We can give an explicit description of the Fraïssé limit as follows: Let
$\mathcal {M} = (S(\mathcal {M}),B(\mathcal {M})) = (\omega ,\mathcal {B})$
where
$\mathcal {B}$
is the countable atomless Boolean algebra. By Stone duality, we know that there is an isomorphism of Boolean algebras
$\mathcal {B} \xrightarrow {g} \mathrm {CLOP}(2^\omega )$
. Moreover, let
$f\colon \omega \to 2^\omega $
such that the image of f is a countable dense subset of the Cantor space and define
$R(x,y)$
as follows:
$$\begin{align*}\mathcal{M} \models R(n,b) \text{ iff } f(n) \in g(b).\end{align*}$$
Note that, since
$2^\omega $
is totally disconnected, for every
$n \neq m$
in
$\omega ,$
there exists
$b_{n}^m \in \mathcal {B}$
such that
$\mathcal {M} \models R(n,b) \land \neg R(m,b)$
. Using this, one can check that the extension properties hold in
$\mathcal {M}$
and thus show that it is the desired Fraïssé limit.
5 Weakenings of
$\mathrm {SM}$
Now that we have established the worst (in some sense) combinatorial binary property that a complete first-order theory can have, we identify subcollections of the set of exhibitable patterns which are enough to describe some of the properties of formulas previously considered. From that, we define other notions of maximality realizing the patterns in those subcollections.
5.1 Positive maximality
The tree properties defining simple,
$\mathrm {NTP}_1$
and
$\mathrm {NTP}_2$
theories can be described by patterns in which the negation of the formula is not involved. More precisely, we can characterize tree properties by exhibiting patterns in which, for every condition
$(X^+,X^-) \in \mathcal {C} \cup \mathcal {I}$
, the set
$X^-$
is empty (see Proposition 3.3). This observation leads the way for the concepts and results described in this subsection.
Definition 5.1. Fix
$n<\omega $
. A positive n-pattern is a pattern
$(\mathcal {C},\mathcal {I})$
such that for every condition
$(X^+,X^-) \in \mathcal {C} \cup \mathcal {I}$
, we have that
$X^- = \emptyset $
.
We can now define the notion of
$\mathrm {PM}$
by requesting the exhibition of all reasonable (see Definition 3.5) positive patterns.
Definition 5.2. A formula
$\varphi (x;y)$
is positive maximal (
$\mathrm {PM}$
), if for every
$n<\omega $
and every reasonable positive n-pattern
$(\mathcal {C},\mathcal {I})$
, the formula
$\varphi $
exhibits
$(\mathcal {C},\mathcal {I})$
.
Remark 5.3. Notice that we didn’t require (as in
$\mathrm {SM}$
) to realize every exhibitable pattern since every reasonable positive pattern is exhibitable. Let’s show this by giving an example of a
$\mathrm {PM}$
theory. Let
$T = \mathrm {Th}(\mathcal {B})$
where
$\mathcal {B}$
is an infinite Boolean algebra with an atomless element. We claim that the formula
$\varphi (x;y) = 0 \neq x \leq y$
is
$\mathrm {PM}$
. The existence of an atomless element implies the existence of a sequence
$(a_i)_{i<\omega }$
of non-zero elements below the atomless element such that
$a_i \cap a_j = 0$
for every
$i<j<\omega $
. Fix
$n<\omega $
and fix a reasonable positive n-pattern
$(\mathcal {C},\mathcal {I})$
. If
$\mathcal {C} = \emptyset $
, take
$b_i = 0$
for every
$i<n$
; since
$\varphi (x;b_i) = \bot $
for every i, we get that every inconsistency condition will be satisfied. Assume
$\emptyset \neq \mathcal {C} = \{(Y_j,\emptyset ) \ : \ j <k\} $
. For each
$i<n$
, define
$$\begin{align*}b_i = \bigcup_{i \in Y_j}a_j.\end{align*}$$
Fix
$\tilde {j}<k$
. Then, if
$i \in Y_{\tilde {j}}$
we have that
$$\begin{align*}0\neq a_{\tilde{j}} \leq \bigcup_{i \in Y_j}a_j = b_i\end{align*}$$
hence
$\{\varphi (x;b_i) \ : \ i \in Y_{\bar {j}}\}$
is consistent. Fix now
$(Z,\emptyset ) \in \mathcal {I}$
and suppose, toward contradiction, that there is
$a \in \mathcal {B}$
such that for every
$i \in Z$
,
$a \models \varphi (x;b_i)$
. This means that
$$\begin{align*}0 \neq a \leq \bigcap_{i \in Z}\bigcup_{i \in Y_j}a_j = \bigcup_{\substack{f\colon Z \to k,\\ (\forall i \in Z)(i \in Y_{f(i)}) }}\bigcap_{i \in Z} a_{f(i).}\end{align*}$$
If the above union is
$0 \in \mathcal {B}$
, then
$0 \neq a \leq 0$
; contradiction. If it is not empty, this means that there is
$f\colon Z \to k$
, with for all
$i\in Z, i \in Y_{f(i)}$
, such that
$\bigcap _{i \in Z}a_{f(i)} \neq 0$
. Since all the
$a_j$
are pairwise disjoint, this can only happen if f is constant, hence there is a
$j<k$
such that for all
$i \in Z$
,
$a_j$
appears in the above union, i.e., there is a
$j<k$
such that for all
$i\in Z$
,
$i \in Y_j$
; thus
$Z \subseteq Y_j$
contradicting reasonableness. In conclusion, this theory is
$\mathrm {PM}$
(despite being
$\mathrm {NSM}$
, see Remark 4.13) and hence every reasonable positive n-pattern is exhibitable.
Remark 5.4. Since every reasonable positive pattern is, in particular, an exhibitable pattern, if a formula
$\varphi (x;y)$
is
$\mathrm {SM}$
, then
$\varphi (x;y)$
is also
$\mathrm {PM}$
.
We now prove a characterization of
$\mathrm {PM}$
at the level of formulas. This equivalence will give us a concrete subfamily of the collection of all reasonable positive patterns which is enough to exhibit PM.
Proposition 5.5. A formula
$\varphi (x;y)$
is
$\mathrm {PM}$
if and only if, for every
$n<\omega $
, there is
$(b_X)_{X \subseteq n}$
such that, for any family of subsets of n,
$\emptyset \neq Z \in \mathcal {P}(\mathcal {P}(n))$
, the partial
$\varphi $
-type
$$\begin{align*}\{\varphi(x;b_Y) \ : \ Y \in Z\} \text{ is consistent if and only if }\bigcap Z \neq \emptyset.\end{align*}$$
Proof. Assume
$\varphi (x;y)$
is
$\mathrm {PM}$
. Fix
$n<\omega $
and consider the following reasonable positive
$2^n$
-pattern:
$$\begin{align*}\mathcal{C} = \{(Z,\emptyset) \ : \ Z \subseteq 2^n \text{ such that } \bigcap Z \neq \emptyset\}\end{align*}$$
$$\begin{align*}\mathcal{I} = \{(Z,\emptyset) \ : \ Z \subseteq 2^n \text{ such that }\bigcap Z = \emptyset\},\end{align*}$$
where we identify each
$Z \subseteq 2^n$
as a family of subsets of n. By
$\mathrm {PM}$
, there is
$(b_i)_{i<2^n} = (b_X)_{X \subseteq n}$
such that, for every
$(Z,\emptyset ) \in \mathcal {C}$
, i.e., for every
$Z \subseteq 2^n$
such that
$\bigcap Z \neq \emptyset $
, the type
$\{\varphi (x;b_i) \ : \ i \in Z\} = \{\varphi (x;b_Y) \ : \ Y \in Z\}$
is consistent and, for every
$(Z, \emptyset ) \in \mathcal {I}$
, i.e., for every
$Z \subseteq 2^n$
such that
$\bigcap Z = \emptyset $
, the type
$\{\varphi (x;b_Y) \ : \ Y \in Z \}$
is inconsistent.
Assume now that
$\varphi (x;y)$
has the above property; fix
$n<\omega $
and let
$(\mathcal {C},\mathcal {I})$
be a reasonable positive n-pattern. By the above property, let
$(b_X)_{X \subseteq n}$
as above. We can assume that
$\mathcal {C} \neq \emptyset $
(otherwise, take
$b_i = b_\emptyset $
for all
$i<n$
). Hence let
$\mathcal {C} = \{(Y_i,\emptyset ) \ : \ i <k\}$
. For any
$i<n$
define
$$\begin{align*}b_i = b_{\{j<k \ : \ i \in Y_j\}.}\end{align*}$$
Fix
$(Y_{\tilde {j}},\emptyset ) \in \mathcal {C}$
. To show that
$\{\varphi (x;b_i) \ : \ i \in Y_{\tilde {j}}\}$
is consistent, by the above property, it is enough to show that
$$\begin{align*}\bigcap_{i \in Y_{\tilde{j}}}\{j<k \ : \ i \in Y_j\} \neq \emptyset.\end{align*}$$
For every
$i \in Y_{\tilde {j}}$
,
$\tilde {j}$
is one of the
$j<k$
such that
$i \in Y_{\tilde {j}}$
, thus
$\tilde {j} \in \bigcap _{i \in Y_{\tilde {j}}}\{j<k \ : \ i \in Y_j\}$
.
Assume now that
$(Z, \emptyset ) \in \mathcal {I}$
and that, toward contradiction, there is
$a \in \mathcal {U}^x$
such that for all
$i \in Z$
, we have that
$a \models \varphi (x;b_i),$
i.e.,
$$\begin{align*}\{\varphi(x;b_i) \ : \ i \in Z\} = \{\varphi(x;b_{\{j<k \ : \ i \in Y_j\}}) \ : \ i \in Z\} \text{ is consistent.}\end{align*}$$
By the above property, this is equivalent to
$$\begin{align*}\emptyset \neq \bigcap_{i \in Z}\{j<k \ : \ i \in Y_j\}. \end{align*}$$
Take
$j<k$
in the above intersection. Then, for every
$i \in Z$
,
$i \in Y_j$
contradicting reasonability of the pattern.
Remark 5.6. In [Reference Cooper7], Cooper defined a property of formulas (named vp) that closely resembles the above characterization of
$\mathrm {PM}$
. It is easy to check that, using Proposition 5.5,
$\mathrm {PM}$
is equivalent to Cooper’s vp, even at the level of formulas.
As pointed out above, some dividing lines can be defined through realizations of reasonable positive patterns. In particular,
$\mathrm {TP}_2$
is given by positive patterns and hence
$\mathrm {PM}$
implies
$\mathrm {TP}_2$
and a fortiori
$\mathrm {IP}$
and
$\mathrm {OP}$
. As described above,
$\mathrm {SOP}$
is not given by positive patterns; hence, a natural question is the following: Is there an
$\mathrm {NSOP}$
and
$\mathrm {PM}$
theory?
We answer positively to the above question showing an example.
Example 5.7 (A positive maximal
$\mathrm {NSOP}_{4}$
theory).
Let
$\mathcal {L} = \{P,O,R,(E_k)_{0<k<\omega }\}$
where
$\mathrm {ar}(P) = \mathrm {ar}(O) = 1$
,
$\mathrm {ar}(R) = 2$
and for any
$k<\omega $
,
$\mathrm {ar}(E_k) = k$
. Let
$T_0$
be the following
$\mathcal {L}$
-theory:
-
(A 1)
$P,O$
partition the universe. -
(A 2 k )
$E_k \subseteq O^k$
is irreflexive. -
(A 3 )
$R \subseteq P \times O$
. -
(A 4 k )
$\forall y_0\dots y_{k-1}\forall x(E_k(\bar {y}) \to \neg \bigwedge _{i<k}R(x,y_i) ).$
Let
$\mathcal {K} = \{A \ : \ A \models T_0 \text { and } A \text { is finite}\}$
. We claim that
$\mathcal {K}$
is a Fraïssé class with free amalgamation.
Since
$T_0$
is
$\forall $
-axiomatized, the class of models of
$T_0$
(in particular the class of its finite models) is closed under taking substructures. Thus
$\mathcal {K}$
has
$\mathrm {HP}$
. Since we allow the empty structure to be a model of
$T_0$
, it’s enough to prove
$\mathrm {AP}$
to get
$\mathrm {JEP}$
for free.
Proposition 5.8. The class
$\mathcal {K}$
has the amalgamation property.
Proof. Consider the amalgamation problem
$(A,B_i,f_i)_{i<2}$
in
$\mathcal {U}$
where
$f_i\colon A \to B_i$
are embeddings.
We define an
$\mathcal {L}$
-structure C as follows: The universe of C is partitioned by
$P^C = (P^{B_0} \setminus P^A) \sqcup P^{B_1}$
and
$O^C = (O^{B_0} \setminus O^A) \sqcup O^{B_1}$
. The interpretation of R and
$E_k$
is the induced one (with no other relations holding). In particular there is no relation
$E_k$
holding between elements of
$O^{B_0}$
and
$O^{B_1}$
inside C.
Clearly C solves the amalgamation problem. We need to show that
$C \models T_0$
.
Clearly C satisfies the axioms (and axiom schemes)
$A_1$
,
$(A_2^k)_{k<\omega }$
and
$(A_3^k)_{k<\omega }$
. It remains to show that, for each
$k<\omega $
,
$C \models (A_4^k)$
. So, fix
$k<\omega $
, fix
$c_0\dots c_{k-1} \in O^C$
and
$a \in P^C$
. Moreover, assume that
$E_k(\bar {c})$
holds. We need to show that
$a \models \neg \bigwedge _{i<k}R(x;c_i)$
. Since
$E_k$
is induced, we have that either
$\bar {c} \in (O^{B_0})^k$
or
$\bar {c} \in (O^{B_1})^k$
, but not both. Without loss of generality,
$\bar {c} \in (O^{B_1})^k$
. Now, either
$a \in P^{B_0} \setminus P^A$
xor
$a \in P^{B_1}$
. In the first case, since
$\bar {c} \in P^{B_1}$
and R is the induced one, we have that
$\models \neg R(a,c_i)$
for every
$i<k$
and hence
$a \models \neg \bigwedge _{i<k}R(x;c_i)$
. In the second case, since
$B_1 \models T_0$
,
$a \models \neg \bigwedge _{i<k}R(x;c_i)$
. In conclusion
$C \models (A_4^k)$
and hence
$\mathcal {K}$
has
$AP$
.
Note that, in the above proof, C is the free amalgam of
$B_0$
and
$B_1$
over A. Hence
$\mathcal {K}$
is closed under free amalgamation (we refer to [Reference Conant6], Definition 3.1, and Example 3.2).
Since
$\mathcal {K}$
is a Fraïssé class, let
$\mathcal {M}$
be its limit and let
$T_{\mathcal {M}} = \mathrm {Th}(\mathcal {M})$
. Since
$\mathcal {K}$
is closed under free amalgamation, we have that
$T_{\mathcal {M}}$
is
$\mathrm {NSOP}_4$
(see [Reference Conant6, Theorem 1.1]) and in particular
$\mathrm {NSOP}$
.
Proposition 5.9.
$T_{\mathcal {M}}$
is
$\mathrm {PM}$
.
Proof. We claim that the formula
$R(x;y)$
is
$\mathrm {PM}$
. Let
$n<\omega $
and fix
$\mathcal {P} = (\mathcal {C},\mathcal {I})$
a reasonable positive n-pattern, where
$$\begin{align*}\mathcal{C} = \{(Y_0,\emptyset),\dots ,(Y_{l-1},\emptyset)\} \text{ and } \mathcal{I} = \{(Z_0,\emptyset),\dots ,(Z_{h-1},\emptyset)\}.\end{align*}$$
Define the structure
$A_{\mathcal {P}}$
as follows: The universe of
$A_{\mathcal {P}}$
is given by
$P^{A_{\mathcal {P}}} \cup O^{A_{\mathcal {P}}} = \{a_i \ : \ i < l\} \cup \{b_i \ : \ i<n\}$
. We interpret R by
$R(a_i;b_j)$
holds if and only if
$i \in Y_j$
and, for
$k<\omega $
, we define
$E_k$
as follows:
$ E_k(b_{i_0},\dots ,b_{i_{k-1}})$
holds if and only if
$k = |Z_j|$
for some
$j < h $
and
$\{i_0,\dots ,i_{k-1}\} = Z_j$
. First of all, by definition of reasonable pattern (see Definition 3.5), there is no
$(Z,\emptyset ) \in \mathcal {I}$
such that
$(Z,\emptyset ) \subseteq (Y,\emptyset )$
(coordinatewise) for some
$(Y,\emptyset ) \in \mathcal {C}$
. This ensures that the witness for
$\{R(x,b_i) \ : \ i \in Y\}$
doesn’t conflict with the relation
$E_{k}$
for
$k<|Y|$
and the axiom
$(A_4^k)$
. Thus, we have that
$A_{\mathcal {P}} \models T_0$
. Hence there is an embedding of
$f\colon A_{\mathcal {P}} \to \mathcal {M}$
. Let
$B = \{f(b_i) \ : \ i < n\}$
. It’s clear that
$R(x;y)$
exhibits the pattern
$\mathcal {P}$
as witnessed by B.
As we showed, this example is actually an
$\mathrm {NSOP}_4$
and
$\mathrm {PM}$
theory. This means that no
$\mathrm {SOP}_n$
,
$n\geq 4$
, can be described by positive patterns. It is still open whether
$\mathrm {SOP}_n$
, for
$n \geq 4$
, can be described through (non-positive) patterns (even though, since
$\mathrm {SM}$
implies
$\mathrm {SOP}$
which in turn implies
$\mathrm {SOP}_n$
, we have
$\mathrm {SM}$
implies every
$\mathrm {SOP}_n$
).
Again, we remark that
$\mathrm {SOP}_3$
was characterized by Kaplan, Ramsey, and Simon [Reference Kaplan, Ramsey and Simon10, Lemma 7.3] in a way that can be described using positive patterns.
5.2 Consistency maximality
While tree properties can be characterized by positive patterns, some properties of formulas, such as
$\mathrm {OP}$
and
$\mathrm {IP}$
, do not need any inconsistency conditions, i.e., the patterns
$(\mathcal {C},\mathcal {I})$
needed to get these properties have
$\mathcal {I} = \emptyset $
(see Proposition 3.3). It is thus natural to define the following property.
Definition 5.10. We say that a formula
$\varphi (x;y)$
is consistency maximal (
$\mathrm {CM}$
) if, for every
$n<\omega $
and every reasonable (consistency) n-pattern
$(\mathcal {C},\emptyset )$
,
$\varphi $
exhibits
$(\mathcal {C},\emptyset )$
.
Remark 5.11. Note that we didn’t ask for a
$\mathrm {CM}$
formula to realize every exhibitable pattern of the form
$(\mathcal {C},\emptyset )$
since every such pattern is exhibitable. To see this, we give an example of a
$\mathrm {CM}$
formula.
Consider the theory T of the random graph. Recall that this is a countable graph characterized (up to isomorphism) by the following property.
For any
$A,B$
finite disjoint subsets of vertices, there exists a vertex v such that
$$\begin{align*}\models E(v,a) \text{ for every }a \in A\end{align*}$$
$$\begin{align*}\models \neg E(v,b) \text{ for every }b \in B,\end{align*}$$
where E is the edge relation.
Let
$\varphi (x;y) = E(x;y)$
, fix
$n<\omega $
, a reasonable n-pattern
$(\mathcal {C},\emptyset )$
and n distinct vertices
$b_0,\dots ,b_{n-1}$
. Then, for every condition
$(A^+,A^-) \in \mathcal {C}$
, by the above property characterizing the random graph, there is v such that
$$\begin{align*}v \models \{\varphi(x;b_i) \ : \ i \in A^+\} \cup \{\neg \varphi(x;b_i) \ : \ i \in A^-\}.\end{align*}$$
Hence
$\varphi (x;y)$
exhibits
$(\mathcal {C},\emptyset )$
. In conclusion
$\varphi (x;y)$
is
$\mathrm {CM}$
.
We prove that
$\mathrm {CM}$
is a weakening of
$\mathrm {PM}$
.
Proposition 5.12. If a formula
$\varphi (x;y)$
is
$\mathrm {PM}$
then
$\varphi (x;y)$
is
$\mathrm {CM}$
.
Proof. Let
$n<\omega $
and let
$(\mathcal {C},\emptyset )$
be a reasonable n-pattern. Define the positive
$2n$
-pattern
$$\begin{align*}\mathcal{C}' := \{(A^+ \cup (n+A^-), \emptyset)\ : \ (A^+,A^-)\in \mathcal{C}\}\end{align*}$$
$$\begin{align*}\mathcal{I}' = \{(\{i,i+n\},\emptyset) \ : \ i<n\},\end{align*}$$
where
$n+A^- = \{n+i \ : \ i \in A^-\}$
. Note that, since
$A^+ \cap A^- = \emptyset $
, the positive pattern
$(\mathcal {C}',\mathcal {I}')$
is reasonable. Since
$\varphi (x;y)$
is positive maximal, there are
$b_0,\dots ,b_{n-1},b_{n},\dots ,b_{2n-1}$
witnessing that
$\varphi $
exhibits
$(\mathcal {C}',\mathcal {I}')$
. We claim that
$b_0,\dots ,b_{n-1}$
witness that
$\varphi $
exhibits
$(\mathcal {C},\emptyset )$
. Let
$(A^+,A^-) \in \mathcal {C}$
. Then
$$\begin{align*}\{\varphi(x;b_i) \ : \ i \in A^+ \cup (n+A^-)\} \text{ is consistent.}\end{align*}$$
Let a be a realization of it and let
$i \in A^-$
. If, toward contradiction,
$a \models \varphi (x;b_i)$
, then, by the choice of a,
$a \models \varphi (x;b_i)\land \varphi (x;b_{n+i})$
which is inconsistent. Hence, for each
$i \in A^-$
,
$a \models \neg \varphi (x;b_i)$
. This shows that
$$\begin{align*}\{\varphi(x;b_i) \ : \ i \in A^+\} \cup \{\neg \varphi(x;b_j) \ : \ j \in A^-\} \text{ is consistent.}\end{align*}$$
Hence,
$\varphi $
exhibits
$(\mathcal {C},\emptyset )$
. In conclusion,
$\varphi $
is
$\mathrm {CM}$
.
We now give an example of an
$\mathrm {NPM}$
but
$\mathrm {CM}$
theory, showing that the implication in Proposition 5.12 is strict.
Example 5.13. Again, consider the theory T of the random graph. It is well known that this theory is simple (
$\mathrm {NTP}$
); moreover we proved that it is
$\mathrm {CM}$
. If T was
$\mathrm {PM}$
, then, since
$\mathrm {TP}$
can be realized through positive patterns, T would have
$\mathrm {TP}$
, contradicting the simplicity of the theory.
We now prove that this weaker notion of maximality (
$\mathrm {CM}$
) is actually equivalent to the IP. Recall that a formula
$\varphi (x;y)$
has
$\mathrm {IP}$
if, by definition, there are tuples
$(a_i)_{i<\omega }$
and
$(b_I)_{I \subseteq \omega }$
such that
$$\begin{align*}\models \varphi(a_i;b_I) \iff i \in I. \end{align*}$$
By compactness, this is equivalent to having, for every
$n<\omega $
, an nth approximation of the above property.
Proposition 5.14. A formula
$\varphi (x;y)$
is
$\mathrm {CM}$
if and only if it has
$\mathrm {IP.}$
Proof. We will actually prove that
$\varphi (x;y)$
is
$\mathrm {CM}$
if and only if
$\varphi ^{\mathrm {opp}}(y;x)$
has
$\mathrm {IP}$
. On the other hand, it’s well-known that a formula has
$\mathrm {IP}$
if and only if the opposite formula has
$\mathrm {IP}$
(see, e.g., [Reference Casanovas1]).
Suppose
$\varphi (x;y)$
is
$\mathrm {CM}$
. Fix
$n<\omega $
and consider the pattern
$$\begin{align*}\mathcal{C} = \{(X,n\setminus X) \ : \ X \in \mathcal{P}(n)\}\end{align*}$$
$$\begin{align*}\mathcal{I} = \emptyset.\end{align*}$$
Since this is a consistency pattern,
$\varphi (x,y)$
exhibits it; let
$B=(b_i)_{i<n}$
be a witness. For any
$X \in \mathcal {P}(n) = \mathcal {C}$
, let
$a_X$
a realization of
$p_{X,n\setminus X}^B(x)$
. Then,
$$\begin{align*}\models \varphi^{\mathrm{opp}}(b_i,a_X) \iff \models\varphi(a_X,b_i) \iff i \in X.\end{align*}$$
Hence, for every
$n<\omega $
,
$\varphi ^{\mathrm {opp}}(y;x)$
has an nth approximation of
$\mathrm {IP}$
. By compactness,
$\varphi ^{\mathrm {opp}}(y;x)$
has
$\mathrm {IP}$
.
Assume now that
$\varphi ^{\mathrm {opp}}(y;x)$
has
$\mathrm {IP}$
. Take
$(b_i)_{i<\omega }$
and
$(a_I)_{I \subseteq \omega }$
witnessing it. Fix a reasonable n-pattern
$(\mathcal {C},\emptyset )$
. Then, for any condition
$(A^+,A^-) \in \mathcal {C}$
, we have that
$$\begin{align*}a_{A^+} \models \{\varphi^{\mathrm{opp}}(b_i;x) \ : \ i \in A^+\} \cup \{\varphi^{\mathrm{opp}}(b_i;x) \ : \ i \notin A^+, i<n\}.\end{align*}$$
Since
$A^- \subseteq n \setminus A^+$
, we have
$$\begin{align*}\{\varphi^{\mathrm{opp}}(b_i;x) \ : \ i \in A^+\} \cup \{\varphi^{\mathrm{opp}}(b_i;x) \ : \ i \notin A^+\} \supseteq \end{align*}$$
$$\begin{align*}\{\varphi^{\mathrm{opp}}(b_i;x) \ : \ i \in A^+\} \cup \{\varphi^{\mathrm{opp}}(b_i;x) \ : \ i \in A^-\}. \end{align*}$$
Which in turn equals to
$$\begin{align*}\{\varphi(x;b_i) \ : \ i \in A^+\} \cup \{\varphi(x;b_i) \ : \ i \in A^-\}. \end{align*}$$
Hence
$p_{A^+,A^-}^B(x)$
is consistent and hence
$\varphi (x;y)$
is
$\mathrm {CM}$
.
Remark 5.15. Given the above equivalence, we have an alternative proof of Proposition 5.12:
Since
$\mathrm {TP}_2$
can be realized by positive patterns, if
$\varphi (x;y)$
is
$\mathrm {PM}$
, then
$\varphi (x;y)$
has
$\mathrm {TP}_2$
which in turn implies
$\mathrm {IP}$
(see Fact 2.2) which, by Proposition 5.14, is equivalent to
$\mathrm {CM}$
.
6 The
$\mathrm {PM}^{(k)}$
hierarchy
Natural weakenings of
$\mathrm {PM}$
can be obtained by restricting the size of possible sets of inconsistencies. Some combinatorial properties that can be defined in terms of inconsistency sets of size
$>2$
, such as k-
$\mathrm {TP}$
and k-
$\mathrm {TP}_2$
, turn out to be equivalent, at the level of theories, to their counterparts with inconsistency sets of size
$2$
(
$2$
-
$\mathrm {TP}$
and
$2$
-
$\mathrm {TP}_2$
). In contrast, by weakening
$\mathrm {PM}$
restricting the size of possible sets of inconsistencies, we get a strict hierarchy of properties
$(\mathrm {PM}^{(k)})_{1<k<\omega }$
.
Definition 6.1. Let
$1<k<\omega $
. A formula
$\varphi (x;y)$
is
$\mathrm {PM}^{(k)}$
if for all
$n<\omega $
and for every reasonable positive n-pattern
$(\mathcal {C},\mathcal {I})$
with for all
$(Z^+,\emptyset ) \in \mathcal {I}$
,
$|Z^+| = k$
,
$\varphi (x;y)$
exhibits
$(\mathcal {C},\mathcal {I})$
. We say that a theory T is
$\mathrm {PM}^{(k)}$
if there is a
$\mathrm {PM}^{(k)}$
formula. Otherwise we say T is
$\mathrm {NPM}^{(k)}$
.
Remark 6.2. We don’t consider
$\mathrm {PM}^{(0)}$
and
$\mathrm {PM}^{(1)}$
since every theory is
$\mathrm {PM}^{(0)}$
and
$\mathrm {PM}^{(1)}$
. For
$\mathrm {PM}^{(0)}$
, fix a tuple
$a \in \mathcal {U}^x$
and take the formula
$$\begin{align*}\varphi(x;y) = (x=y).\end{align*}$$
Since we excluded conditions of the form
$(\emptyset ,\emptyset )$
from the definition of patterns,
$\mathcal {I} = \emptyset $
and thus
$\varphi (x;y)$
is asked to exhibit positive patterns of the form
$(\mathcal {C},\emptyset )$
. Fix
$n<\omega $
and an n-pattern as above. Define
$b_i =a $
for all
$i<n$
; then, for any condition
$(A^+,\emptyset ) \in \mathcal {C}$
$$\begin{align*}\bigwedge_{i \in A^+} (x=a) \text{ is consistent, witnessed by }a.\end{align*}$$
For
$\mathrm {PM}^{(1)}$
, fix
$a\neq b$
and consider the formula
$$\begin{align*}\varphi(x;y) = (y = a) \land (x=x).\end{align*}$$
Fix
$n<\omega $
and a reasonable positive n-pattern
$(\mathcal {C},\mathcal {I})$
with for all
$(Z^+,\emptyset )$
,
$|Z^+| = 1$
. For all i such that there is a condition
$(\{i\},\emptyset ) \in \mathcal {I}$
, define
$b_i = b$
. Otherwise, define
$b_i = a$
. Then, for
$(A^+,\emptyset ) \in \mathcal {C}$
, since pattern are reasonable, for all
$i \in A^+$
,
$b_i = a$
and thus
$$\begin{align*}\bigwedge_{i<n}(a=a)\land (x=x) \text{ is consistent.} \end{align*}$$
For
$(\{i\},\emptyset ) \in \mathcal {I}$
,
$b_i = b \neq a$
and thus
$$\begin{align*}\varphi(x;b_i) = (a=b) \land (x=x) \text{ is inconsistent.}\end{align*}$$
In conclusion, we disregard
$\mathrm {PM}^{(0)}$
and
$\mathrm {PM}^{(1)}$
since they are not very sensible notions.
We can characterize the
$\mathrm {PM}^{(k)}$
properties by “realizations of hypergraphs”.
Proposition 6.3.
$\varphi (x;y)$
is
$\mathrm {PM}^{(k)}$
if and only if for every finite k-hypergraph
$(n,E)$
,
$\varphi $
realizes
$(n,E)$
, i.e., there are
$(b_i)_{i<n}$
such that
-
(i) for any
$i_0,\dots ,i_{k-1} \in n$
with
$\neg E(i_0,\dots ,i_{k-1})$
, we have and
$$\begin{align*}\{\varphi(x;b_{i_j}) \ : \ j<k\} \text{ is inconsistent}\end{align*}$$
-
(ii) for any clique
$\{i_0,\dots ,i_{l-1}\} \subseteq n$
$$\begin{align*}\{\varphi(x;b_{i_j}) \ : \ j<l\} \text{ is consistent.}\end{align*}$$
Proof. Suppose
$\varphi (x;y)$
is
$\mathrm {PM}^{(k)}$
. Let
$(n,E) be$
a finite k-hypergraph. Consider the positive n-pattern
$(\mathcal {C},\mathcal {I})$
where
$$\begin{align*}\mathcal{C} := \{(\{i_0,\dots ,i_{l-1}\},\emptyset) \ : \ \{i_0,\dots ,i_{l-1}\}\text{ is a clique}\}\end{align*}$$
$$\begin{align*}\mathcal{I} :=\{(\{i_0,\dots ,i_{k-1}\},\emptyset) \ : \ \neg E(i_0,\dots ,i_{k-1})\}.\end{align*}$$
Since no non-hyperedge can be a subset of a clique, this is a reasonable pattern. By
$\mathrm {PM}^{(k)}$
,
$\varphi $
exhibits
$(\mathcal {C},\mathcal {I})$
and thus there are
$(b_i)_{i<n}$
witnessing it. It’s easy to see that, with these parameters,
$\varphi $
realizes
$(n,E)$
.
Assume now that
$\varphi (x;y)$
realizes every k-hypergraph. Let
$n<\omega $
and let
$(\mathcal {C},\mathcal {I}) be$
a positive n-pattern with for all
$(Z^+,\emptyset ) \in \mathcal {I}$
,
$|Z^+| = k$
. Consider the graph
$(n,E)$
where
$E(i_0,\dots ,i_{k-1})$
holds if and only if
$(\{i_0,\dots ,i_{k-1}\},\emptyset ) \notin \mathcal {I}$
. Since
$\varphi (x;y)$
realizes every finite k-hypergraph, there are
$(b_i)_{i<n}$
witnessing it. Now, given
$(A^+,\emptyset ) \in \mathcal {C}$
, since the pattern is reasonable, every k-element subset B of
$A^+$
is such that
$(B,\emptyset ) \notin \mathcal {I}$
, thus
$A^+$
forms a clique in
$(n,E)$
and therefore
$$\begin{align*}\{\varphi(x;b_i) \ : \ i \in A^+\} \text{ is consistent.}\end{align*}$$
On the other hand, given
$(\{i_0,\dots ,i_{k-1}\},\emptyset ) \in \mathcal {I}$
, we have
$\neg E(i_0,\dots ,i_{k-1})$
and thus
$$\begin{align*}\{\varphi(x;b_{i_j}) \ : \ j<k\} \text{ is inconsistent.}\end{align*}$$
Thus
$\varphi $
exhibits
$(\mathcal {C},\mathcal {I})$
.
Proposition 6.4. If
$\varphi (x;y)$
is
$\mathrm {PM}^{(k)}$
, then
$\varphi (x;y)$
realizes the generic k-hypergraph. Moreover, the parameters may be chosen to be (generic ordered k-hypergraph)-indiscernibles.
Proof. Apply compactness and the modeling property (which ordered k-hypergraphs have by Fact 2.6).
Proposition 6.5. For every
$1<k<\omega $
, if
$\varphi (x;y)$
is
$\mathrm {PM}^{(k+1)}$
, then
$\psi (x;y_0\dots y_{k}) = \bigwedge _{i<k+1}\varphi (x;y_i)$
is
$\mathrm {PM}^{(k)}$
.
Proof. Assume
$\varphi (x;y)$
has
$\mathrm {PM}^{(k+1)}$
. Consider the formula
$$\begin{align*}\psi(x;y_0\dots y_{k}) = \bigwedge_{i<k+1}\varphi(x;y_i).\end{align*}$$
We want to show that
$\psi $
is
$\mathrm {PM}^{(k)}$
. Let
$n<\omega $
and let
$(n,E)$
be a finite k-hypergraph. Define a
$(k+1)$
-hypergraph
$(\tilde {V},\tilde {E})$
as follows:
-
(i) For each
$i < n$
, take
$k+1$
new vertices
$K_i = v_i^0,\dots ,v_i^{k}$
with
$\tilde {E}(v_i^0,\dots ,v_i^k)$
. -
(ii) For each hyperedge
$i_0,\dots ,i_{k-1}$
in
$(n,E)$
, make
$K_{i_0}\dots K_{i_{k-1}}$
into a
$\tilde {E}$
-clique. -
(iii) No other hyperedge is present.
Now,
$(\tilde {V},\tilde {E})$
is a
$(k+1)$
-hypergraph, thus by
$\mathrm {PM}^{(k+1)}$
, there are
$(b_v)_{v \in \tilde {V}}$
realizing it. Let
${i_0,\dots ,i_{k-1}}$
a non-hyperedge in
$(n,E)$
. This implies that
$(K_{i_j})_{j<k}$
doesn’t form an
$\tilde {E}$
-clique and hence
$\{\varphi (x;b_v) \ : \ v \in \bigcup _{j<k}K_{i_j}\}$
is inconsistent. Thus
$$\begin{align*}\{\psi(x;\bar{b}_{K_{i_j}}) \ : \ j<k\} \text{ is inconsistent.}\end{align*}$$
If
$i_0,\dots ,i_{l-1}$
is a clique in
$(n,E)$
, then
$(K_{i_j})_{j<l}$
forms a clique in
$(\tilde {V},\tilde {E})$
and thus
$\{\varphi (x;b_v) \ : \ v \in \bigcup _{j<l}K_{i_j}\}$
is consistent; this shows that
$$\begin{align*}\{\varphi(x;\bar{b}_{K_j}) \ : \ j<l\}\end{align*}$$
is consistent. In conclusion,
$\psi (x;y_0\dots y_{k})$
realizes
$(n,E)$
and hence
$\psi $
is
$\mathrm {PM}^{(k)}$
.
Definition 6.6. A theory is
-
(i)
$\mathrm {PM}^{(\infty )}$
if there are formulae
$(\varphi _k(x_k;y_k))_{1<k<\omega }$
such that for all
$1<k<\omega, \varphi _k(x_k;y_k)$
is
$\mathrm {PM}^{(k)}$
. -
(ii)
$UPM^{(\infty )}$
(Uniformly
$\mathrm {PM}^{(\infty )}$
) if there is a formula
$\varphi (x;y)$
with
$\mathrm {PM}^{(k)}$
for all
$1<k<\omega $
.
Remark 6.7. Clearly, at the level of theories, for all
$2<k<\omega ,$
we have
$$\begin{align*}\mathrm{PM} \Rightarrow \mathrm{UPM}^{(\infty)} \Rightarrow \mathrm{PM}^{(\infty)} \Rightarrow \dots \Rightarrow \mathrm{PM}^{(k+1)} \Rightarrow \mathrm{PM}^{(k)} \Rightarrow \dots \Rightarrow \mathrm{PM}^{(2).}\end{align*}$$
We will show that the implication
$\mathrm {PM}^{(k+1)} \Rightarrow \mathrm {PM}^{(k)}$
is strict for every
$1<k<\omega $
.
Question 6.8. Is there a
$\mathrm {PM}^{(\infty )}$
but
$\mathrm {NUPM}^{(\infty )}$
theory? Similarly, is there a
$\mathrm {UPM}^{(\infty )}$
but
$\mathrm {NPM}$
theory?
Definition 6.9. Fix
$n<\omega $
. A relational language
$\mathcal {L}$
is n-ary if, for every
$R \in \mathcal {L}$
,
$\mathrm {ar}(R) \leq n$
. An
$\mathcal {L}$
-theory T is n-ary if
-
(i)
$\mathcal {L}$
is n-ary, and -
(ii) T has
$\mathrm {QE}$
.
Remark 6.10. We could have defined a theory to be n-ary if it is interdefinable with a theory satisfying the conditions in Definition 6.9; on the other hand, all the properties that we are considering here are preserved under interdefinability and thus we don’t actually lose any generality.
In [Reference Chernikov, Palacin and Takeuchi3], Chernikov, Palacin, and Takeuchi studied higher arity versions of
$\mathrm {IP}$
, firstly introduced by Shelah, called
$\mathrm {IP}_k$
(
$0<k<\omega $
). In particular, they characterized
$\mathrm {NIP}_k$
in terms of the collapse of ordered
$(k+1)$
-hypergraphs indiscernibles to order-indiscernibles. Using this characterization, we get the following result.
Theorem 6.11. For any
$0<k<\omega $
,
$\mathrm {PM}^{(k+1)}$
implies
$\mathrm {IP}_k$
.
Proof. Fix
$0<k<\omega $
. By [Reference Chernikov, Palacin and Takeuchi3, Theorem 5.4], it’s enough to exhibit a (generic ordered
$(k+1)$
-hypergraph)-indiscernible that is not order indiscernible. Suppose
$\varphi (x;y)$
is
$\mathrm {PM}^{(k+1)}$
. By Ramsey and compactness, we can find
$(b_h)_{h \in H} (H,<,E)$
-indiscernible witnessing it, where
$(H,<, E)$
is the generic ordered
$(k+1)$
-hypergraph. Let
$h_0<h_1<\dots <h_{k+1} \in H$
such that
$$\begin{align*}\models E(h_0\dots h_k) \land \neg E(h_1\dots h_{k+1}).\end{align*}$$
By
$\mathrm {PM}^{(k+1)},$
we have
$$\begin{align*}\models \exists x \bigwedge_{i<k+1}\varphi(x;b_{h_i}) \land \neg \exists x \bigwedge_{0<i<k+2} \varphi(x;b_{h_i})\end{align*}$$
and thus, even if the order type of
$h_0<\dots <h_k$
is the same as the one of
$h_1<\dots <h_{k+1}$
, we have
$$\begin{align*}\mathrm{tp}((b_{h_i})_{i<k+1}) \neq \mathrm{tp}((b_{h_i})_{0<i<k+2})\end{align*}$$
In conclusion,
$(b_h)_{h \in H}$
is not order indiscernible and thus some formula has
$\mathrm {IP}_k$
.
Alternative Proof.
Suppose
$\varphi (x;y)$
is
$\mathrm {PM}^{(k+1)}$
. Then, by Proposition 6.3 and compactness, the formula
$$\begin{align*}\psi(y_0,\dots ,y_{k}) =\exists x \bigwedge_{i<k+1}\varphi(x;y_i)\end{align*}$$
encodes every
$(k+1)$
-hypergraph; in particular, it has
$\mathrm {IP}_k$
(see [Reference Chernikov, Palacin and Takeuchi3, Proposition 5.2]).
Corollary 6.12. Any k-ary theory is
$\mathrm {NPM}^{(k+1)}$
.
Proof. From [Reference Chernikov, Palacin and Takeuchi3, Example 2.2], we have that k-ary theories are
$\mathrm {NIP}_k$
. By Theorem 6.11, k-ary theories are
$\mathrm {NPM}^{(k+1)}$
.
We now construct examples of theories with
$\mathrm {PM}^{(k)}$
but not
$\mathrm {PM}^{(k+1)}$
for all
$k\geq 2$
. This will show that the implication
$\mathrm {PM}^{(k+1)} \Rightarrow PM^{(k)}$
is strict. We give a uniform recipe to build
$\mathrm {PM}^{(k)} \mathrm {NPM}^{(k+1)}$
theories.
Example 6.13 (
$\mathrm {PM}^{(k)} \mathrm {NPM}^{(k+1)}$
theory).
Fix
$1<k<\omega $
and consider the language
$\mathcal {L}_k = \{O,P,R,E_k\}$
where
$P,O$
are unary predicates, R is a binary predicate, and
$E_k$
is a k-ary predicate. Consider the
$\mathcal {L}_k$
-theory
$T_0$
axiomatized as follows:
-
(A 1)
$P,O$
partition the universe. -
(A 2)
$E_k \subseteq P^k$
and
$(P,E_k)$
is a k-hypergraph. -
(A 3)
$R \subseteq O \times P.$
-
(A 4)
$\forall v_0\dots v_{k-1}\forall x(\bigwedge _{i<k}R(x,v_i) \to \neg E_k(\bar {v})).$
Let
$\mathcal {K} = \{A \models T_0\ : \ |A| < \aleph _0 \}$
. Similarly to the proof of Proposition 5.8, it can be shown that
$\mathcal {K}$
is a Fraïssé class closed under free-amalgamation. Let
$\mathcal {M}_k$
be the Fraïssé limit. Intuitively
$\mathcal {M}_k$
has two disjoint sets (O,P),
$(P(\mathcal {M}_k),E_k)$
is the generic k-hypergraph and
$O(\mathcal {M}_k)$
is the set of witnesses for the consistency along R of independent sets and the inconsistency along R of k-hyperedges. In particular,
$T_k:= \mathrm {Th}(\mathcal {M}_k)$
is
$\mathrm {PM}^{(k)}$
(witnessed by R),
$\omega $
-categorical,
$\mathrm {NSOP}_4$
(see [Reference Conant6, Theorem 1.1]) and eliminates quantifiers. Moreover, by Corollary 6.12,
$T_k$
is
$\mathrm {NPM}^{(k+1)}$
.
We now consider a well-known theory and see how it relates with this hierarchy.
Example 6.14 (Generic triangle-free graph).
Let
$\mathcal {L} = \{e\}$
where e is a binary relation and let
$\mathcal {K}$
be the class of finite triangle-free graphs. It can be shown that
$\mathcal {K}$
is a Fraïssé class; let
$\mathcal {H}$
be its limit and let
$T_{\mathcal {H}} = \mathrm {Th}(\mathcal {H})$
.
Proposition 6.15.
$T_{\mathcal {H}}$
is
$\mathrm {PM}^{(2)}$
.
Proof. We claim that the formula
$\varphi (x;yz) = e(x,y) \land e(x,z)$
is
$\mathrm {PM}^{(2)}$
. Let
$n<\omega $
and let
$(V,E)$
any finite graph an n vertices. Construct the graph
$(\tilde {V},\tilde {E})$
as follows: Replace each vertex
$v \in V$
with two vertices
$b_vc_v$
with
$\neg b_v \tilde {E}c_v$
. Whenever
$\{v,w\} \notin E$
, make a new edge between
$\{b_v,c_w\} \in \tilde {E}$
and no other edges.
Claim.
$(\tilde {V},\tilde {E})$
is triangle-free.
Proof of the Claim:
As a notation, given a graph and a vertex v, we write
$N(v)$
for the graph neighborhood of
$v,$
i.e., the set of all the vertices in the graph that are connected by an edge to v. Suppose, toward contradiction, that there is a triangle
$a \tilde {E} a' \tilde {E}a" \tilde {a} $
. Since there’s no edge between
$b_v$
and
$c_v$
for every v, there must be
$v_0,v_1,v_2$
, such that the triangle is among
$(b_{v_i}c_{v_i})_{i<3}$
. Suppose that
$b_{v_0}$
is in the triangle. But
$N(b_{v_0}) = \{c_{v_1},c_{v_2}\}$
and
$\neg c_{v_1} \tilde {E} c_{v_2}$
, contradiction. Then it must be the case that
$c_{v_0}$
is in the triangle. But
$N(c_{v_0}) = \{b_{v_1},b_{v_2}\}$
and
$\neg b_{v_1}\tilde {E}b_{v_2}$
. Contradiction. Thus
$(\tilde {V},\tilde {E})$
is triangle-free.
Since
$(\tilde {V},\tilde {E})$
is a finite triangle-free graph, it can be embedded in
$\mathcal {H}$
. Now, let
$\{v,w\} \notin E$
. Then, if there is a vertex a such that
$$\begin{align*}a \models \varphi(x;b_vc_v) \land \varphi(x;b_wc_w) = (e(x,b_v) \land e(x,c_v)) \land ((e(x,b_w) \land e(x,c_w)).\end{align*}$$
Then
$a,b_v,c_w$
form a triangle; contradiction. On the other hand, if
$v_0,\dots ,v_{n-1}$
is a clique, then
$(b_{v_i}c_{v_i})_{i<n}$
is an independent set of vertices and hence, by the extension property of
$\mathcal {H}$
, there is a vertex a such that
$a \models \bigwedge _{i<n} e(x,b_{v_i}) \land e(x,c_{v_i})$
and thus
$$\begin{align*}\{\varphi(x;b_{v_i}c_{v_i}) \ : \ i<n\} \text{ is consistent.}\end{align*}$$
In conclusion
$\varphi (x;y)$
is
$\mathrm {PM}^{(2)}$
. Thus, by definition,
$T_{\mathcal {H}}$
is
$\mathrm {PM}^{(2)}$
.
Moreover, since
$T_{\mathcal {H}}$
is a binary theory, by Corollary 6.12,
$T_{\mathcal {H}}$
is
$\mathrm {NPM}^{(3)}$
.
Acknowledegments
This work is part of the author’s Ph.D. dissertation in progress. The author would like to sincerely thank Alex Kruckman for his guidance, valuable help, and fruitful discussions. Furthermore, the exciting environment of the Wesleyan University logic group played an important role in this project, in particular, the encouragement and the helpful conversations the author had with Cameron Hill, Rehana Patel, and Alex Van Abel. Finally, the author would like to thank the anonymous referee for their useful comments and corrections.
