A walk on the wild side:
Notions of maximality in first-order theories

Michele Bailetti

(Date: September 28, 2024.)

Abstract.

In the classification of complete first-order theories, many dividing lines have been defined in order to understand the complexity and the behavior of some classes of theories. In this paper, using the concept of patterns of consistency and inconsistency, we describe a general framework to study dividing lines and we introduce a notion of maximal complexity by requesting the presence of all the exhibitable patterns of definable sets. Weakening this notion, we define new properties (Positive Maximality and the $PM_{k}$ hierarchy) and prove some results about them. In particular, we show that $PM_{k+1}$ theories are not $k$ -dependent.

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,[19]).

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: $NIP$ and $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 [20]) 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, B. Kim et al (See, e.g., [8, 10, 13, 12, 2]), 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 [22] (Definition 5.17) with a different notation and more recently appeared in [14] (Definition 6.2) 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. 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 [7]) and “an extreme condition of the form of unstability” called Straight Maximality ( $SM$ ) defined by Shelah ([23]). 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 $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 $OP$ and $IP$ do not require any inconsistency conditions. We thus define Consistency Maximality ( $CM$ , see Definition 5.10) by requiring the existence of a formula realizing all the patterns without inconsistency conditions. We show that $CM$ is equivalent to $IP$ (even at the level of formulas), giving a different perspective to this well-known property. Other dividing lines, such as $TP$ , $TP_{1}$ and $TP_{2}$ (See Definition 2.1, (4),(5),(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 $SM$ , called Positive Maximality ( $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 $PM$ . Since our characterization of $SOP$ uses patterns that are not positive, a natural question is the following:

Question 1.1.

Is there a positive maximal $NSOP$ theory?

In Section 5, we answer positively to the above question by finding an example of a $NSOP_{4}$ (See Definition 2.1,( $7_{4}$ )) positive maximal theory (See Example 5.7). In particular, this shows that neither $SOP$ nor $SOP_{n}$ for $n\geq 4$ (See Definition 2.1,( $7_{n}$ )) can be characterized through positive patterns. We point out that, in [9] (Lemma 7.3), Kaplan, Ramsey and Simon proved a characterization of $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 $(PM_{k})_{1<k<\omega}$ (See Definition 6.1), weaker than $PM$ but still strong enough to imply all the classical positive dividing lines. We show that, at the level of theories, $PM_{k+1}$ implies $PM_{k}$ (See Proposition 6.5) and we give $NSOP_{4}$ , $PM_{k}$ and $NPM_{k+1}$ examples showing that the above implication is strict (See Example 6.13). We show that $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 ( $IP_{k}$ ) is a higher-arity version of $IP$ introduced by Shelah. In [3], Chernikov, Palacin and Takeuchi showed the equivalence of $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 $PM_{k+1}$ , then $T$ has $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 implies all the $k$ -ary versions of $IP$ (at each step of the way). We also point out that there are examples of simple $IP_{k}$ theories, and thus $PM_{k+1}$ is not equivalent to $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 $SOP_{3}$ but $NSOP$ theories are $PM$ (or $PM_{k}$ for some $1<k<\omega$ )? Is there a $SOP_{3}$ but $NSOP$ and $NPM_{2}$ theory? If not, we would have that $NSOP\cap NPM_{2}=NSOP_{3}$ ; this would imply the collapse of the $SOP_{n}$ hierarchy inside $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,...$ 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},...$ for the set of tuples of elements of $\mathcal{U}$ that can be plugged in for $x,y,z,...$ respectively.

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 [18] and [21]. For the definitions and a bird’s-eye view of the universe we refer to [4].

Definition 2.1.

A partitioned formula $\varphi(x;y)$ has

(1)

the order property ( $OP$ ) if there are tuples $(a_{i}b_{i})_{i<\omega}$ such that

$\models\varphi(a_{i};b_{j})\iff i<j$
(2)

the independence property ( $IP$ ) if there are tuples $(a_{i})_{i<\omega}$ and $(b_{I})_{I\subseteq\omega}$ such that

$\models\varphi(a_{i};b_{I})\iff i\in I$
(3)

the strict-order property ( $SOP$ ) if there are tuples $(b_{i})_{i<\omega}$ such that

$\models\exists x(\varphi(x;b_{j})\land\neg\varphi(x;b_{i}))\iff i<j$
(4)
the $k$ -tree property ( $k$ - $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 ( $TP$ ) if it has $k$ - $TP$ for some $1<k<\omega$
(5)
the tree property of the first kind ( $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$ - $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 ( $TP_{2}$ ) if it has $k$ - $TP_{2}$ for some $1<k<\omega$ .
( $7_{n}$ )

$n$ -strong order property $(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

$\{\varphi(x_{1};x_{2}),\varphi(x_{2};x_{3}),...,\varphi(x_{n-1},x_{n}),\varphi(x_{n},x_{1})\}$

is inconsistent.

A complete first-order theory $T$ is

•

stable if no formula has $OP$ in $T$ . It is said to be unstable otherwise.
•

simple if no formula has $TP$ in $T$ .
•

$Np$ if no formula has $p$ in $T$ , where $p\in\{IP,SOP,TP_{1},TP_{2},SOP_{n}\}$ ; otherwise, we say that $T$ has $p$ . For instance, $T$ is $NIP$ if no formula has $IP$ in $T$ ; if there is a formula with $IP$ in $T$ , we say that $T$ has $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 = $NIP\cap NSOP$ .
•

Simple = $NTP_{1}\cap NTP_{2}$ .

Proof.

For the proofs of the above we refer to [1], [5], [11] and [18]. ∎

2.2. Generalized indiscernibles

We review the basic definitions and notions around generalized indiscernibles, introduced by Shelah in [18] and developed by Scow in [17, 16].

Definition 2.3.

Fix a language $\mathcal{L}^{\prime}$ , $\mathcal{L}^{\prime}$ -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},...,i_{n-1}$ and $\bar{j}=j_{0},...,j_{n-1}$ from $I$ , we have

qftp_{\mathcal{L}^{\prime}}(\bar{i})=qftp_{\mathcal{L}^{\prime}}(\bar{j})\Rightarrow tp_{\mathcal{L}}(b_{\bar{i}})=tp_{\mathcal{L}}(b_{\bar{j}})

(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}...i_{n-1}$ from $I$ there is a tuple $\bar{j}=j_{0}...j_{n-1}$ from $J$ with $qftp_{\mathcal{L}^{\prime}}(\bar{i})=qftp_{\mathcal{L}^{\prime}}(\bar{j})$ , such that

$tp_{\Sigma}(b_{\bar{i}})=tp_{\Sigma}(c_{\bar{j}})$
(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 [17]).

Let $I$ be an $\mathcal{L}^{\prime}$ -structure, $(b_{i})_{i\in I}$ $I$ -indiscernible. Then, for any $\mathcal{L}^{\prime}$ -structure $J$ with $age(J)\subseteq age(I)$ , we can find $J$ -indiscernible $(c_{j})_{j\in J}$ based on $(b_{i})_{i\in I}$ .

In her thesis ([17]), Scow showed a profound connection between Ramsey classes (See, e.g., [17], 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}=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 [15], 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 order property $(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 red dashed lines represent $\neg\varphi$ and the green lines represent $\varphi$ . Similarly, the independence property $(IP)$ can be visualized as follows: there are $(b_{i})_{i<\omega}$ from $\mathcal{U}^{y}$ such that for every ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X}\subseteq\omega$

A new element of complexity is added for describing the strict-order property $(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 (green line i.e. $\varphi$ ) or negative (red 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

	$\displaystyle\mathcal{C}\longleftrightarrow\exists x$	$\displaystyle X^{+}\longleftrightarrow\varphi$
	$\displaystyle\mathcal{I}\longleftrightarrow\neg\exists x$	$\displaystyle X^{-}\longleftrightarrow\neg\varphi$

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 a $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

$p_{\mathcal{A}}^{B}(x)=\{\varphi(x;b_{i})\ :\ i\in A^{+}\}\cup\{\neg\varphi(x;b_{j})\ :\ j\in A^{-}\}$

is consistent, and
(ii)

for all $\mathcal{Z}=(Z^{+},Z^{-})\in\mathcal{I}$ , the partial $\varphi$ -type

$p_{\mathcal{Z}}^{B}(x)=\{\varphi(x;b_{i})\ :\ i\in Z^{+}\}\cup\{\neg\varphi(x;b_{j})\ :\ j\in Z^{-}\}$

is inconsistent.

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 $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

$\mathcal{C}_{n}=\{(\{i,i+1,...,n-1\},\{0,...,i-1\})\ :\ i<n\}$

$\mathcal{I}_{n}=\emptyset$
(2)

$\varphi(x;y)$ has $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

$\mathcal{C}_{n}=\{(X,n\setminus X)\ :\ X\subseteq n\}$

$\mathcal{I}_{n}=\emptyset$
(3)

$\varphi(x;y)$ has $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

$\mathcal{C}_{n}=\{(\{i+1\},\{i\})\ :\ i<n-1\}$

$\mathcal{I}_{n}=\{(\{i\},\{i+1\})\ :\ i<n-1\}$
(4)

For $1<k<\omega$ , $\varphi(x;y)$ has $k$ - $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

$\mathcal{C}_{n}=\{(\text{ path}_{i},\emptyset)\ :\ i\in n^{n}\}$

$\mathcal{I}_{n}=\{(\{i_{0},...,i_{k-1}\},\emptyset)\ :\ i_{0},...,i_{k-1}\text{ children of the same node}\}$

where $\{path_{i}\ :\ i\in n^{n}\}$ is the collection of all the paths in the tree $n^{<n}$ .
(5)

$\varphi(x;y)$ has $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

$\mathcal{C}_{n}=\{(\text{ path}_{i},\emptyset)\ :\ i\in n^{n}\}$

$\mathcal{I}_{n}=\{(\{i,j\},\emptyset)\ :\ i,j\text{ are incomparable elements in the tree }n^{<n}\}$

with a similar notation as above.
(6)

For $1<k<\omega$ , $\varphi(x;y)$ has $k$ - $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

$\mathcal{C}_{n}=\{(\text{ path}_{i},\emptyset)\ :\ i\in n^{n}\}$

$\mathcal{I}_{n}=\{(\{i_{0},...,i_{k-1}\},\emptyset)\ :\ i_{0},...,i_{k-1}\text{ are on the same row }\}$

Here, by a path in $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 $SOP_{n}$ hierarchy, for $n\geq 4$ , can be characterized using pattern exhibition. There exists a characterization of $SOP_{3}$ ([9], Lemma 7.3) that can be described through patterns.

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 $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 $PSAT$ is $NP$ -complete.

The proof of the above will appear in the author’s PhD thesis.

Definition 3.8.

Fix $n<\omega$ . A $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$ :

p_{X^{+},X^{-}}^{B}(x)=\{\varphi(x;b_{i})\ :\ i\in X^{+}\}\cup\{\neg\varphi(x;b_{j})\ :\ j\in X^{-}\}

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.

A $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)=At(x)\land x\leq y$ and define

\varphi(x;yw_{0}w_{1})=(\psi(x;y)\land w_{0}=w_{1})\lor(\neg\psi(x;y)\land w_{0}\neq w_{1})

where $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},...,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

b_{i}=\bigcup\{a_{j}\ :\ j<k,i\in A_{j}\}

and $c_{i}^{0}=c_{i}^{1}=c$ . We claim that $(b_{i}c_{i}^{0}c_{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 At(x)\land x\leq b_{i}$ if and only if $a_{j}\models\varphi(x;b_{i}c_{i}^{0}c_{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_{i}c_{i}^{0}c_{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_{i}c_{i}^{0}c_{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^{\prime}$ and for $i<n$ , $i\notin A_{0}$ , define

b_{i}=\bigcup\{a_{j}\ :\ j<k,i\in A_{j}\}\quad\text{ and take }c_{i}^{0}=c=c_{i}^{1}

For $i\in A_{0}$ , define

b_{i}=\bigcup\{a_{j}\ :\ j<k,i\notin A_{j}\}\quad\text{ and take }c_{i}^{0}=c\neq c^{\prime}=c_{i}^{1}

Let $B=(b_{i}c_{i}^{0}c_{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

a_{j}\models\varphi(x;b_{i}\bar{c_{i}})\iff At(a_{j})\land(a_{j}\leq b_{i})\iff a_{j}\leq b_{i}\iff i\in A_{j}\setminus A_{0}

If $i\in A_{0}$ , we have

a_{j}\models\varphi(x;b_{i}\bar{c_{i}})\iff\neg At(a_{j})\lor(a_{j}\not\leq b_{i})

\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}

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 At(x)$ , $b\models\varphi(x;b_{i}cc^{\prime})$ . If $i\notin A_{0}$ , then, since $b\not\models At(x)$ , $b\models\neg\varphi(x;b_{i}cc)$ . 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 At(\mathcal{B})$ , then $a\models\neg At(x)$ and hence $a\models\varphi(x;b_{i},cc^{\prime})$ for any $i\in A_{0}$ . If $a\in 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_{i}cc^{\prime})$ . If $a=a_{j}\neq a_{0}$ , then $a_{j}\models\varphi(x;b_{i}cc)$ 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

a\models\varphi(x;b_{i}\bar{c}_{i})\iff i\in Z

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_{i}cc^{\prime})$ ; 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_{i}cc)$ . 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 [23]); 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}^{\prime},\mathcal{I}^{\prime})$ such that, if a formula exhibits $(\mathcal{C}^{\prime},\mathcal{I}^{\prime})$ , 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 parameters $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 $Con(\varphi,B)$ be the set of complete consistent $\varphi$ -types over $B$ and, similarly, let $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

\mathcal{C}^{\prime}=\{(A_{p},n\setminus A_{p})\ :\ p\in Con(\varphi,B)\}

\mathcal{I}^{\prime}=\{(Z_{p},n\setminus Z_{p})\ :\ p\in Inc(\varphi,B)\}

Suppose $\psi(x;y)$ exhibits $(\mathcal{C}^{\prime},\mathcal{I}^{\prime})$ in $T$ with $B^{\prime}=(b_{i}^{\prime})_{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 Con(\varphi,B)$ . Thus, there is $(A,n\setminus A)\in\mathcal{C}^{\prime}$ such that $(A^{+},A^{-})\subseteq(A,n\setminus A)$ . Since $p_{(A,n\setminus A)}^{B^{\prime},\psi}(x)$ is consistent, it must be that $p_{(A^{+},A^{-})}^{B^{\prime},\psi}(x)$ is consistent too.

Let $(Z^{+},Z^{-})\in\mathcal{I}$ and assume, toward contradiction, that $p_{(Z^{+},Z^{-})}^{B^{\prime},\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}^{\prime}$ . But now $tp^{\psi}(a/B^{\prime})$ gives us a set $X\subseteq n$ such that $(Z^{+},Z^{-})\subseteq(X,n\setminus X)$ which is in $\mathcal{I}^{\prime}$ 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 $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 $SM$ if there is a formula which is $SM$ ; otherwise we say that $T$ is $NSM$ .

Other notions of maximality were previously defined by Shelah ([23]) and Cooper ([7]). 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 [23], Shelah defined “an extreme condition of the form of unstability” called Straight Maximality.

Definition 4.2.

A formula $\varphi(x;y)$ is Shelah- $SM$ (Shelah’s Straight maximal) if for every $n<\omega$ and for every non-empty $\mathscr{F}\subseteq 2^{n}$ there are $b_{0},...,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- $SM$ if and only if $\varphi(x;y)$ exhibits every fully complete pattern.

Proof.

Assume $\varphi$ is Shelah- $SM$ , fix $n<\omega$ and let $(\mathcal{C},\mathcal{I})$ a fully complete $n$ -pattern. Define $\mathscr{F}=\{char(X)\ :\ (X,n\setminus X)\in\mathcal{C}\}\subseteq 2^{n}$ where $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},...,b_{n-1}\}$ given by Shelah- $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 $char(Z)(i)=1$ , we would have that $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

\mathcal{C}=\{(f^{-1}(\{1\}),f^{-1}(\{0\}))\ :\ f\in\mathscr{F}\}

\mathcal{I}=\{(f^{-1}(\{1\}),f^{-1}(\{0\}))\ :\ f\in 2^{n}\setminus\mathscr{F}\}

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},...,b_{n-1}\}$ of the exhibition of $(\mathcal{C},\mathcal{I})$ by $\varphi$ is also a witness of $\varphi$ being Shelah- $SM$ . ∎

Proposition 4.4.

A formula is Shelah- $SM$ if and only if it is $SM$ .

Proof.

Let $\varphi(x;y)$ be a $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- $SM$ by Proposition 4.3.

On the other hand, assume that $\varphi(x;y)$ is Shelah- $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}^{\prime},\mathcal{I}^{\prime})$ such that, if a formula realizes $(\mathcal{C}^{\prime},\mathcal{I}^{\prime})$ then it realizes $(\mathcal{C},\mathcal{I})$ . Since $\varphi$ realizes every fully complete pattern, it realizes every exhibitable pattern. In conclusion, it is $SM$ . ∎

4.2. Cooper’s maximality

In [7], 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 [7].

Definition 4.5 (Cooper, [7]).

•

A property of formulas is any sequence $\rho=(\rho_{i})_{i<\omega}$ of consistent quantifier free (q.f.) formulas of $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 $BA$ , we say that $\varphi(x,y)$ admits $\psi(z)$ in $T$ if

$\mathcal{P}(\mathcal{M}^{x})\models\psi(\varphi(\mathcal{M},a_{0}),...,\varphi(\mathcal{M},a_{|z|-1}))$

for some $\mathcal{M}\models T$ and some $a_{0},...,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 $BA$ , say $\{\psi_{i}\ :\ i<\omega\}$ , and defined

\rho_{i}=\bigwedge_{j<i}\psi_{i}

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, [7]).

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

$\bigcup_{i\in X}\varphi(\mathcal{U},b_{i})=\varphi(\mathcal{U},b_{X})$
(ii)

for any $Y\in\mathcal{P}(m)$

$\bigcap_{i\in Y}\varphi(\mathcal{U},b_{i})=\emptyset\text{ if and only if }|Y|>n$

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, [7]).

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 $SM$ .

Proof.

Assume $T$ is $SM$ and let $\varphi(x;y)$ be the $SM$ formula witnessing it.

Claim for each $n<\omega$ there are $(b_{i})_{i<n}$ such that

\varphi(\mathcal{U},b_{i})\cap\varphi(\mathcal{U},b_{j})=\emptyset\text{ for all }i\neq j<n

for each $X\subseteq n$ , there is $b_{X}$ such that

\varphi(\mathcal{U},b_{X})=\bigcup_{i\in X}\varphi(\mathcal{U},b_{i})

Equivalently, $\varphi(x;y)$ admits $1^{(1)}$ .

Proof of the Claim: Since $\varphi(x;y)$ is $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:

C=\{\uparrow\{i\}\ :\ i<n\}

I=\mathcal{P}(2^{n})\setminus C

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 $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

\varphi(\mathcal{U},b_{X})=\bigcup_{i\in X}\varphi(\mathcal{U},b_{\{i\}})

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\}})$ . $\blacksquare$

The claim shows that, if $\varphi(x;y)$ is $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 $SM$ can be described as a property of formulas. Indeed $SM$ is a property of formulas described by:

\rho_{m}:=\bigwedge_{n<m}\bigwedge_{\begin{subarray}{c}(\mathcal{C},\mathcal{I})\\ \text{ exhibitable $n$-p}\end{subarray}}(\bigwedge_{(Y^{+},Y^{-})\in\mathcal{C}}(\bigcap_{i\in Y^{+}}x_{i}\cap\bigcap_{j\in Y^{-}}(n\setminus x_{j}))\neq 0)

\land\bigwedge_{(Z^{+},Z^{-})\in\mathcal{I}}(\bigcap_{i\in Z^{+}}x_{i}\cap\bigcap_{j\in Z^{-}}(n\setminus x_{j}))=0)

This shows that, if $T$ is Cooper maximal, then it is $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 $SM$ , if a formula is $SM$ , it admits $1^{(1)}$ and thus (by Fact 4.7) there is a (possibly different) formula admitting $1$ .

4.3. Examples of $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 $SM$ by showing a formula that exhibits every exhibitable pattern. We now prove again this result using Cooper’s characterization of $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

$\varphi(\mathcal{U};b_{X})=\bigcup_{i\in X}\varphi(\mathcal{U};b_{i})$

Work in some model $\mathcal{B}$ . Let $At(x)$ be the formula saying that $x$ is an atom and consider the formula

\varphi(x;y)=At(x)\land x\leq y

Fix $n<\omega$ and choose $(b_{i})_{i<n}$ such that $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

\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})

In conclusion $\varphi(x;y)$ has $1^{(1)}$ and thus $T$ is $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 [7], Cooper proved that $T$ does not admit $1$ and thus, by Proposition 4.10, it is not $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:

•

$One(x)=\forall y(x\cdot y=y)$ .
•

$x|y=\exists z(y=x\cdot z)$
•

$P(x)=\neg One(x)\land\forall y(y|x\to(One(y)\lor y=x))$

To show that this theory is $SM$ we use Cooper’s characterization of $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

\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})

In conclusion, Skolem arithmetic is $SM$ .

A similar argument shows that the first-order theory of $(\mathbb{Z},+,\cdot,0,1)$ is $SM$ .

Since all the previous examples of $SM$ theories are not $\omega$ -categorical, we now construct an $\omega$ -categorical $SM$ theory.

Example 4.15 ( $\omega$ -categorical $SM$ theory).

Consider the language $\mathcal{L}=\{S,B,R\}\cup\mathcal{L}_{BA}$ where $\mathcal{L}_{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}_{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}^{\prime})$ are terms, then $\psi_{t_{1}\cap t_{2}}(x,\bar{y}\bar{y}^{\prime})=\psi_{t_{1}}(x,\bar{y})\land\psi_{t_{2}}(x,\bar{y}^{\prime})$ .
•

If $t(\bar{y})=(t^{\prime}(\bar{y}))^{c}$ then $\psi_{t}(x,\bar{y})=\neg\psi_{t^{\prime}}(x,\bar{y})$ .

Since $0$ and $\cup$ are definable from the other symbols, we can assume that the term $t$ does not contain them.

Now, given an atomic $\psi\in\mathcal{L}_{BA}$ , $\psi$ is of the form $t_{1}(\bar{y})=t_{2}(\bar{y}^{\prime})$ . Define

\tilde{\psi}(x,\bar{y}\bar{y}^{\prime})=\psi_{t_{1}}(x,\bar{y})\leftrightarrow\psi_{t_{1}}(x,\bar{y}^{\prime})

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}^{\psi}$ )

For any $\psi(\bar{y})\in\mathcal{L}_{BA}^{at}$ , we have

$(\forall\bar{y}\in B)(\psi(\bar{y})\rightarrow(\forall x\in S)\tilde{\psi}(x,\bar{y}))$

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 $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 sorts. The axiom scheme $(A_{4}^{\psi})_{\psi\in\mathcal{L}_{BA}^{at}}$ makes sure that we have a homomorphism of Boolean algebras

h\colon B\to\mathcal{P}(S)

b\mapsto R(S,b)

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 $HP$ , $JEP$ , $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 $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 $JEP$ is implied by $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=<C_{gen}>$ , $C_{gen}=\{s_{0},...,s_{l-1},b_{0},...,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 $AP$ .

Lemma 4.16.

Given $A,A^{\prime}\in\mathcal{K}$ , there is an embedding $A\to A^{\prime}$ if and only if there is an embedding of Boolean algebras $B(A)\to B(A^{\prime})$ and a surjective homomorphism of Boolean algebras $\mathcal{P}(S(A^{\prime}))\to\mathcal{P}(S(A))$ such that the following commutes

where $h_{A}$ and $h_{A^{\prime}}$ are the Boolean algebra homomorphisms given by $b\mapsto R(S,b)$ .

Proof.

Suppose we have an embedding $A\to A^{\prime}$ . In particular we have a embedding of Boolean algebras $F\colon B(A)\to B(A^{\prime})$ and an inclusion $S(A)\subseteq S(A^{\prime})$ 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 an surjective homomorphism of Boolean algebras $\mathcal{P}(S(A^{\prime}))\twoheadrightarrow\mathcal{P}(S(A))$ . Therefore, given $b\in B(A)$ , we have

h_{A^{\prime}}(F(b))\cap S(A)=R(S(A^{\prime}),F(b))\cap S(A)=R(S(A),b)=h_{A}(b)

Conversely, given the above diagram, we have a Boolean algebra embedding $B(A)\to B(A^{\prime})$ and by Stone duality, we get an injection $S(A)\to S(A^{\prime})$ . 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^{\prime}$ . ∎

We now prove that $\mathcal{K}$ has $AP$ . 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^{\prime},j,j^{\prime}$ inclusions of sets. We want to define a function

h\colon S(C)\sqcup_{S(A)}S(C^{\prime})\to S_{1}\times_{S_{0}}S_{2}

such that $f_{1}=p_{1}\circ h\circ j$ and $f_{2}=p_{2}\circ h\circ j^{\prime}$ . 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^{\prime})$ , 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^{\prime}$ .

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^{\prime})$ 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 $AP$ .

Let $T$ be the first-order theory of the Fraïssé limit of $\mathcal{K}$ . We show that $T$ is $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

R(A,b_{X})=R(n,b_{X})=X=\bigcup_{i\in X}\{i\}=\bigcup_{i\in X}R(A,b_{i})

Embedding $A$ into $\mathcal{M}$ (by universality of $\mathcal{M}$ ), the above properties are preserved. Thus $R(x,y)$ is $SM$ in $T$ .

We can give an explicit description of the Fraïssé limit as follows: Let $\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}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:

\mathcal{M}\models R(n,b)\text{ iff }f(n)\in g(b)

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 $SM$

Once 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, $NTP_{1}$ and $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 positive maximality ( $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 ( $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 $SM$ ) to realize every exhibitable pattern since every reasonable positive pattern is exhibitable. Let’s show this by giving an example of a $PM$ theory. Let $T=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 $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

b_{i}=\bigcup_{i\in Y_{j}}a_{j}

Fix $\tilde{j}<k$ . Then, if $i\in Y_{\tilde{j}}$ we have that

0\neq a_{\tilde{j}}\leq\bigcup_{i\in Y_{j}}a_{j}=b_{i}

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

0\neq a\leq\bigcap_{i\in Z}\bigcup_{i\in Y_{j}}a_{j}=\bigcup_{\begin{subarray}{c}f\colon Z\to k,\\ (\forall i\in Z)(i\in Y_{f(i)})\end{subarray}}\bigcap_{i\in Z}a_{f(i)}

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 $PM$ (despite being $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 $SM$ , then $\varphi(x;y)$ is also $PM$ .

We now prove a characterization of $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 positive maximality.

Proposition 5.5.

A formula $\varphi(x;y)$ is $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

\{\varphi(x;b_{Y})\ :\ Y\in Z\}\text{ is consistent if and only if }\bigcap Z\neq\emptyset

Proof.

Assume $\varphi(x;y)$ is $PM$ . Fix $n<\omega$ and consider the following reasonable positive $2^{n}$ -pattern

\mathcal{C}=\{(Z,\emptyset)\ :\ Z\subseteq 2^{n}\text{ such that }\bigcap Z\neq\emptyset\}

\mathcal{I}=\{(Z,\emptyset)\ :\ Z\subseteq 2^{n}\text{ such that }\bigcap Z=\emptyset\}

where we identify each $Z\subseteq 2^{n}$ as a family of subsets of $n$ . By $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

b_{i}=b_{\{j<k\ :\ i\in Y_{j}\}}

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

\bigcap_{i\in Y_{\tilde{j}}}\{j<k\ :\ i\in Y_{j}\}\neq\emptyset

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.

\{\varphi(x;b_{i})\ :\ i\in Z\}=\{\varphi(x;b_{\{j<k\ :\ i\in Y_{j}\}})\ :\ i\in Z\}\text{ is consistent.}

By the above property, this is equivalent to

\emptyset\neq\bigcap_{i\in Z}\{j<k\ :\ i\in Y_{j}\}

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 [7], Cooper defined a property of formulas (named vp) that closely resembles the above characterization of $PM$ . It is easy to check that, using Proposition 5.5, $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, $TP_{2}$ is given by positive patterns and hence $PM$ implies $TP_{2}$ and a fortiori $IP$ and $OP$ . As described above, $SOP$ is not given by positive patterns; hence, a natural question is the following: Is there a $NSOP$ and $PM$ theory?

We answer positively to the above question showing an example:

Example 5.7 (A positive maximal $NSOP_{(4)}$ theory).

Let $\mathcal{L}=\{P,O,R,(E_{k})_{0<k<\omega}\}$ where $ar(P)=ar(O)=1$ , $ar(R)=2$ and for any $k<\omega$ , $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}$
$(A_{3})$

$R\subseteq P\times O$
$(A_{4}^{k})$

$\forall y_{0}...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$ 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 $HP$ . Since we allow the empty structure to be a model of $T_{0}$ , it’s enough to prove $AP$ to get $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}...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 [6], 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}}=Th(\mathcal{M})$ . Since $\mathcal{K}$ is closed under free amalgamation, we have that $T_{\mathcal{M}}$ is $NSOP_{4}$ (See [6], Theorem 1.1) and in particular $NSOP$ .

Proposition 5.9.

$T_{\mathcal{M}}$ is $PM$ .

Proof.

We claim that the formula $R(x;y)$ is $PM$ . Let $n<\omega$ and fix $\mathcal{P}=(\mathcal{C},\mathcal{I})$ a reasonable positive $n$ -pattern, where

\mathcal{C}=\{(Y_{0},\emptyset),...,(Y_{l-1},\emptyset)\}\text{ and }\mathcal{I}=\{(Z_{0},\emptyset),...,(Z_{h-1},\emptyset)\}

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}},...,b_{i_{k-1}})$ holds if and only if $k=|Z_{j}|$ for some $j<h$ and $\{i_{0},...,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 a $NSOP_{4}$ and $PM$ theory. This means that no $SOP_{n}$ , $n\geq 4$ , can be described by positive patterns. It is still open whether $SOP_{n}$ , for $n\geq 4$ , can be described through (non-positive) patterns (even though, since $SM$ implies $SOP$ which in turn implies $SOP_{n}$ , we have $SM$ implies every $SOP_{n}$ ).

Again, we remark that $SOP_{3}$ was characterized by Kaplan, Ramsey and Simon ([9], 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 $OP$ and $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 ( $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 $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 $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

\models E(v,a)\text{ for every $a\in A$}

\models\neg E(v,b)\text{ for every $b\in B$ }

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},...,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

v\models\{\varphi(x;b_{i})\ :\ i\in A^{+}\}\cup\{\neg\varphi(x;b_{i})\ :\ i\in A^{-}\}

Hence $\varphi(x;y)$ exhibits $(\mathcal{C},\emptyset)$ . In conclusion $\varphi(x;y)$ is $CM$ .

We prove that $CM$ is a weakening of $PM$ .

Proposition 5.12.

If a formula $\varphi(x;y)$ is $PM$ then $\varphi(x;y)$ is $CM$ .

Proof.

Let $n<\omega$ and let $(\mathcal{C},\emptyset)$ be a reasonable $n$ -pattern. Define the positive $2n$ -pattern

\mathcal{C}^{\prime}:=\{(A^{+}\cup(n+A^{-}),\emptyset)\ :\ (A^{+},A^{-})\in\mathcal{C}\}

\mathcal{I}^{\prime}=\{(\{i,i+n\},\emptyset)\ :\ i<n\}

where $n+A^{-}=\{n+i\ :\ i\in A^{-}\}$ . Note that, since $A^{+}\cap A^{-}=\emptyset$ , the positive pattern $(\mathcal{C}^{\prime},\mathcal{I}^{\prime})$ is reasonable. Since $\varphi(x;y)$ is positive maximal, there are $b_{0},...,b_{n-1},b_{n},...,b_{2n-1}$ witnessing that $\varphi$ exhibits $(\mathcal{C}^{\prime},\mathcal{I}^{\prime})$ . We claim that $b_{0},...,b_{n-1}$ witness that $\varphi$ exhibits $(\mathcal{C},\emptyset)$ . Let $(A^{+},A^{-})\in\mathcal{C}$ . Then

\{\varphi(x;b_{i})\ :\ i\in A^{+}\cup(n+A^{-})\}\text{ is consistent.}

Let $a$ 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

\{\varphi(x;b_{i})\ :\ i\in A^{+}\}\cup\{\neg\varphi(x;b_{j})\ :\ j\in A^{-}\}\text{ is consistent.}

Hence, $\varphi$ exhibits $(\mathcal{C},\emptyset)$ . In conclusion $\varphi$ is $CM$ . ∎

We now give an example of a $NPM$ but $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 ( $NTP$ ); moreover we proved that it is $CM$ . If $T$ was $PM$ , then, since $TP$ can be realized through patterns, $T$ would have $TP$ , contradicting the simplicity of the theory.

We now prove that this weaker notion of maximality ( $CM$ ) is actually equivalent to the Independence Property $(IP)$ . Recall that a formula $\varphi(x;y)$ has $IP$ if, by definition, there are tuples $(a_{i})_{i<\omega}$ and $(b_{I})_{I\subseteq\omega}$ such that

\models\varphi(a_{i};b_{I})\iff i\in I

By compactness, this is equivalent to having, for every $n<\omega$ , a $n$ th approximation of the above property.

Proposition 5.14.

A formula $\varphi(x;y)$ is $CM$ if and only if it has $IP$

Proof.

We will actually prove that $\varphi(x;y)$ is $CM$ if and only if $\varphi^{opp}(y;x)$ has $IP$ . On the other hand, it’s well-known that a formula has $IP$ if and only if the opposite formula has $IP$ (See, e.g., [1]).

Suppose $\varphi(x;y)$ is $CM$ . Fix $n<\omega$ and consider the pattern

\mathcal{C}=\{(X,n\setminus X)\ :\ X\in\mathcal{P}(n)\}

\mathcal{I}=\emptyset

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,

\models\varphi^{opp}(b_{i},a_{X})\iff\models\varphi(a_{X},b_{i})\iff i\in X

Hence, for every $n<\omega$ , $\varphi^{opp}(y;x)$ has a $n$ th approximation of $IP$ . By compactness, $\varphi^{opp}(y;x)$ has $IP$ .

Assume now that $\varphi^{opp}(y;x)$ has $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

a_{A^{+}}\models\{\varphi^{opp}(b_{i};x)\ :\ i\in A^{+}\}\cup\{\varphi^{opp}(b_{i};x)\ :\ i\notin A^{+},i<n\}

Since $A^{-}\subseteq n\setminus A^{+}$ , we have

\{\varphi^{opp}(b_{i};x)\ :\ i\in A^{+}\}\cup\{\varphi^{opp}(b_{i};x)\ :\ i\notin A^{+}\}\supseteq

\{\varphi^{opp}(b_{i};x)\ :\ i\in A^{+}\}\cup\{\varphi^{opp}(b_{i};x)\ :\ i\in A^{-}\}

Which in turn equals to

\{\varphi(x;b_{i})\ :\ i\in A^{+}\}\cup\{\varphi(x;b_{i})\ :\ i\in A^{-}\}

Hence $p_{A^{+},A^{-}}^{B}(x)$ is consistent and hence $\varphi(x;y)$ is $CM$ . ∎

Remark 5.15.

Given the above equivalence, we have an alternative proof of Proposition 5.12:

Since $TP_{2}$ can be realized by positive patterns, if $\varphi(x;y)$ is $PM$ , then $\varphi(x;y)$ has $TP_{2}$ which in turn implies $IP$ (See Fact 2.2) which, by Proposition 5.14, is equivalent to $CM$ .

6. The $PM_{k}$ hierarchy

Natural weakenings of $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$ - $TP$ and $k$ - $TP_{2}$ , turn out to be equivalent, at the level of theories, to their counterparts with inconsistency sets of size $2$ ( $2$ - $TP$ and $2$ - $TP_{2}$ ). In contrast, by weakening $PM$ restricting the size of possible sets of inconsistencies, we get a strict hierarchy of properties $(PM_{k})_{1<k<\omega}$ .

Definition 6.1.

Let $1<k<\omega$ . A formula $\varphi(x;y)$ is $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 $PM_{k}$ if there is a $PM_{k}$ formula. Otherwise we say $T$ is $NPM_{k}$ .

Remark 6.2.

We don’t consider $PM_{0}$ and $PM_{1}$ since (almost) every theory is $PM_{0}$ and $PM_{1}$ . For $PM_{0}$ , fix a tuple $a\in\mathcal{U}^{x}$ and take the formula

\varphi(x;y)=(x=y)

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}$

\bigwedge_{i\in A^{+}}(x=a)\text{ is consistent, witnessed by $a$}

For $PM_{1}$ , fix $a\neq b$ and consider the formula

\varphi(x;y)=(y=a)\land(x=x)

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

\bigwedge_{i<n}(a=a)\land(x=x)\text{ is consistent.}

For $(\{i\},\emptyset)\in\mathcal{I}$ , $b_{i}=b\neq a$ and thus

\varphi(x;b_{i})=(a=b)\land(x=x)\text{ is inconsistent.}

In conclusion, we disregard $PM_{0}$ and $PM_{1}$ since they are not very sensible notions.

We can characterize the $PM_{k}$ properties by “realizations of hypergraphs”:

Proposition 6.3.

$\varphi(x;y)$ is $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},...,i_{k-1}\in n$ with $\neg E(i_{0},...,i_{k-1})$ , we have

$\{\varphi(x;b_{i_{j}})\ :\ j<k\}\text{ is inconsistent}$

and
(ii)

for any clique $\{i_{0},...,i_{l-1}\}\subseteq n$

$\{\varphi(x;b_{i_{j}})\ :\ j<l\}\text{ is consistent.}$

Proof.

Suppose $\varphi(x;y)$ is $PM_{k}$ . Let $(n,E)$ a finite $k$ -hypergraph. Consider the positive $n$ -pattern $(\mathcal{C},\mathcal{I})$ where

\mathcal{C}:=\{(\{i_{0},...,i_{l-1}\},\emptyset)\ :\ \{i_{0},...,i_{l-1}\}\text{ is a clique }\}

\mathcal{I}:=\{(\{i_{0},...,i_{k-1}\},\emptyset)\ :\ \neg E(i_{0},...,i_{k-1})\}

Since no non-hyperedge can be a subset of a clique, this is a reasonable pattern. By $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})$ a positive $n$ -pattern with for all $(Z^{+},\emptyset)\in\mathcal{I}$ , $|Z^{+}|=k$ . Consider the graph $(n,E)$ where, $E(i_{0},...,i_{k-1})$ holds if and only if $(\{i_{0},...,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

\{\varphi(x;b_{i})\ :\ i\in A^{+}\}\text{ is consistent.}

On the other hand, given $(\{i_{0},...,i_{k-1}\},\emptyset)\in\mathcal{I}$ , we have $\neg E(i_{0},...,i_{k-1})$ and thus

\{\varphi(x;b_{i_{j}})\ :\ j<k\}\text{ is inconsistent.}

Thus $\varphi$ exhibits $(\mathcal{C},\mathcal{I})$ . ∎

Proposition 6.4.

If $\varphi(x;y)$ is $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 $PM_{k+1}$ , then $\psi(x;y_{0}...y_{k})=\bigwedge_{i<k+1}\varphi(x;y_{i})$ is $PM_{k}$ .

Proof.

Assume $\varphi(x;y)$ has $PM_{k+1}$ . Consider the formula

\psi(x;y_{0}...y_{k})=\bigwedge_{i<k+1}\varphi(x;y_{i})

We want to show that $\psi$ is $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},...,v_{i}^{k}$ with $\tilde{E}(v_{i}^{0},...,v_{i}^{k})$ .
(ii)

for each hyperedge $i_{0},...,i_{k-1}$ in $(n,E)$ , make $K_{i_{0}}...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 $PM_{k+1}$ , there are $(b_{v})_{v\in\tilde{V}}$ realizing it. Let ${i_{0},...,i_{k-1}}$ a non-hyperedge in $(n,E)$ . This implies that $(K_{i_{j}})_{j<k}$ doesn’t form a $\tilde{E}$ -clique and hence $\{\varphi(x;b_{v})\ :\ v\in\bigcup_{j<k}K_{i_{j}}\}$ is inconsistent. Thus

\{\psi(x;\bar{b}_{K_{i_{j}}})\ :\ j<k\}\text{ is inconsistent.}

If $i_{0},...,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

\{\varphi(x;\bar{b}_{K_{j}})\ :\ j<l\}

is consistent. In conclusion $\psi(x;y_{0}...y_{k})$ realizes $(n,E)$ and hence $\psi$ is $PM_{k}$ . ∎

Definition 6.6.

A theory is

(i)

$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 $PM_{k}$ .
(ii)

$UPM_{\infty}$ (Uniformly $PM_{\infty}$ ) if there is a formula $\varphi(x;y)$ with $PM_{k}$ for all $1<k<\omega$ .

Remark 6.7.

Clearly, at the level of theories, for all $2<k<\omega$ we have

PM\Rightarrow UPM_{\infty}\Rightarrow PM_{\infty}\Rightarrow...\Rightarrow PM_{k+1}\Rightarrow PM_{k}\Rightarrow...\Rightarrow PM_{2}

We will show that the implication $PM_{k+1}\Rightarrow PM_{k}$ is strict for every $1<k<\omega$ .

Question 6.8.

Is there a $PM_{\infty}$ but $NUPM_{\infty}$ theory? Similarly, is there a $UPM_{\infty}$ but $NPM$ theory?

Definition 6.9.

Fix $n<\omega$ . A relational language $\mathcal{L}$ is $n$ -ary if, for every $R\in\mathcal{L}$ , $ar(R)\leq n$ . An $\mathcal{L}$ -theory $T$ is $n$ -ary if

(i)

$\mathcal{L}$ is $n$ -ary, and
(ii)

$T$ has $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 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 [3], Chernikov, Palacin and Takeuchi studied higher arity versions of $IP$ , firstly introduced by Shelah, called $IP_{k}$ ( $0<k<\omega$ ). In particular, they characterized $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$ , $PM_{k+1}$ implies $IP_{k}$ .

Proof.

Fix $0<k<\omega$ . By Theorem 5.4 in [3], it’s enough to exhibit a (generic ordered $(k+1)$ -hypergraph)-indiscernible that is not order indiscernible. Suppose $\varphi(x;y)$ is $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}<...<h_{k+1}\in H$ such that

\models E(h_{0}...h_{k})\land\neg E(h_{1}...h_{k+1})

By $PM_{k+1}$ we have

\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}})

and thus, even if the order type of $h_{0}<...<h_{k}$ is the same as the one of $h_{1}<...<h_{k+1}$ , we have

tp((b_{h_{i}})_{i<k+1})\neq tp((b_{h_{i}})_{0<i<k+2}

In conclusion $(b_{h})_{h\in H}$ is not order indiscernible and thus some formula has $IP_{k}$ . ∎

Corollary 6.12.

Any $k$ -ary theory is $NPM_{k+1}$ .

Proof.

From [3], Example 2.2, we have that $k$ -ary theories are $NIP_{k}$ . By 6.11, $k$ -ary theories are $NPM_{k+1}$ . ∎

We now construct examples of theories with $PM_{k}$ but not $PM_{k+1}$ for all $k\geq 2$ . This will show that the implication $PM_{k+1}\Rightarrow PM_{k}$ is strict. We give a uniform recipe to build $PM_{k}$ $NPM_{k+1}$ theories.

Example 6.13 ( $PM_{k}$ $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}...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}:=Th(\mathcal{M}_{k})$ is $PM_{k}$ (witnessed by $\neg R$ ), $\omega$ -categorical, $NSOP_{4}$ (See [6], Theorem 1.1) and eliminates quantifiers. Moreover, by Corollary 6.12, $T_{k}$ is $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}}=Th(\mathcal{H})$ .

Proposition 6.15.

$T_{\mathcal{H}}$ is $PM_{2}$ .

Proof.

We claim that the formula $\varphi(x;yz)=e(x,y)\land e(x,z)$ is $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_{v}c_{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^{\prime}\tilde{E}a^{\prime\prime}\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. $\blacksquare$

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

a\models\varphi(x;b_{v}c_{v})\land\varphi(x;b_{w}c_{w})=(e(x,b_{v})\land e(x,c_{v}))\land((e(x,b_{w})\land e(x,c_{w}))

Then $a,b_{v},c_{w}$ form a triangle; contradiction. On the other hand, if $v_{0},...,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

\{\varphi(x;b_{v_{i}}c_{v_{i}})\ :\ i<n\}\text{ is consistent.}

In conclusion $\varphi(x;y)$ is $PM_{2}$ . Thus, by definition, $T_{\mathcal{H}}$ is $PM_{2}$ . ∎

Moreover, since $T_{\mathcal{H}}$ is a binary theory, by Corollary 6.12, $T_{\mathcal{H}}$ is $NPM_{3}$ .

Acknowledgements

This work is part of the author’s PhD 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.

References

Casanovas [2011] Enrique Casanovas. NIP formulas and theories. Model theory Seminar notes, 2011.
Chatzidakis and Hrushovski [1999] Zoé Chatzidakis and Ehud Hrushovski. Model theory of difference fields. Trans. Amer. Math. Soc., 351(8):2997–3071, 1999. ISSN 0002-9947,1088-6850. doi: 10.1090/S0002-9947-99-02498-8. URL https://doi.org/10.1090/S0002-9947-99-02498-8.
Chernikov et al. [2019] Artem Chernikov, Daniel Palacin, and Kota Takeuchi. On $n$ -dependence. Notre Dame J. Form. Log., 60(2):195–214, 2019. ISSN 0029-4527,1939-0726. doi: 10.1215/00294527-2019-0002. URL https://doi.org/10.1215/00294527-2019-0002.
[4] Gabriel Conant. Map of the universe. URL https://www.forkinganddividing.com/.
Conant [2012] Gabriel Conant. Dividing lines in unstable theories. 2012.
Conant [2017] Gabriel Conant. An axiomatic approach to free amalgamation. J. Symb. Log., 82(2):648–671, 2017. ISSN 0022-4812,1943-5886. doi: 10.1017/jsl.2016.42. URL https://doi.org/10.1017/jsl.2016.42.
Cooper [1982] Glen R. Cooper. On complexity of complete first-order theories. Z. Math. Logik Grundlagen Math., 28(2):93–136, 1982. ISSN 0044-3050. doi: 10.1002/malq.19820280802. URL https://doi.org/10.1002/malq.19820280802.
Hrushovski and Pillay [1994] Ehud Hrushovski and Anand Pillay. Groups definable in local fields and pseudo-finite fields. Israel J. Math., 85(1-3):203–262, 1994. ISSN 0021-2172,1565-8511. doi: 10.1007/BF02758643. URL https://doi.org/10.1007/BF02758643.
Kaplan et al. [2024] Itay Kaplan, Nicholas Ramsey, and Pierre Simon. Generic stability independence and treeless theories. Forum Math. Sigma, 12:Paper No. e49, 27, 2024. ISSN 2050-5094. doi: 10.1017/fms.2024.35. URL https://doi.org/10.1017/fms.2024.35.
Kim [1998] Byunghan Kim. Forking in simple unstable theories. J. London Math. Soc. (2), 57(2):257–267, 1998. ISSN 0024-6107,1469-7750. doi: 10.1112/S0024610798005985. URL https://doi.org/10.1112/S0024610798005985.
Kim and Kim [2011] Byunghan Kim and Hyeung-Joon Kim. Notions around tree property 1. Ann. Pure Appl. Logic, 162(9):698–709, 2011. ISSN 0168-0072,1873-2461. doi: 10.1016/j.apal.2011.02.001. URL https://doi.org/10.1016/j.apal.2011.02.001.
Kim and Pillay [1997] Byunghan Kim and Anand Pillay. Simple theories. volume 88, pages 149–164. 1997. doi: 10.1016/S0168-0072(97)00019-5. URL https://doi.org/10.1016/S0168-0072(97)00019-5. Joint AILA-KGS Model Theory Meeting (Florence, 1995).
Kim and Pillay [1998] Byunghan Kim and Anand Pillay. From stability to simplicity. Bull. Symbolic Logic, 4(1):17–36, 1998. ISSN 1079-8986,1943-5894. doi: 10.2307/421004. URL https://doi.org/10.2307/421004.
Kruckman and Ramsey [2024] Alex Kruckman and Nicholas Ramsey. A New Kim’s Lemma. Model Theory, 3(3):825–860, 2024. ISSN 2832-9058,2832-904X. doi: 10.2140/mt.2024.3.825. URL https://doi.org/10.2140/mt.2024.3.825.
Nešetřil and Rödl [1983] Jaroslav Nešetřil and Vojtěch Rödl. Ramsey classes of set systems. J. Combin. Theory Ser. A, 34(2):183–201, 1983. ISSN 0097-3165,1096-0899. doi: 10.1016/0097-3165(83)90055-9. URL https://doi.org/10.1016/0097-3165(83)90055-9.
Scow [2015] Lynn Scow. Indiscernibles, EM-types, and Ramsey classes of trees. Notre Dame J. Form. Log., 56(3):429–447, 2015. ISSN 0029-4527,1939-0726. doi: 10.1215/00294527-3132797. URL https://doi.org/10.1215/00294527-3132797.
Scow [2010] Lynn Cho Scow. Characterization theorems by generalized indiscernibles. ProQuest LLC, Ann Arbor, MI, 2010. ISBN 978-1124-52093-3. URL http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:3444383. Thesis (Ph.D.)–University of California, Berkeley.
Shelah [1990] S. Shelah. Classification theory and the number of nonisomorphic models, volume 92 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam, second edition, 1990. ISBN 0-444-70260-1.
Shelah [1971] Saharon Shelah. The number of non-isomorphic models of an unstable first-order theory. Israel J. Math., 9:473–487, 1971. ISSN 0021-2172. doi: 10.1007/BF02771463. URL https://doi.org/10.1007/BF02771463.
Shelah [1980] Saharon Shelah. Simple unstable theories. Ann. Math. Logic, 19(3):177–203, 1980. ISSN 0003-4843. doi: 10.1016/0003-4843(80)90009-1. URL https://doi.org/10.1016/0003-4843(80)90009-1.
Shelah [1996] Saharon Shelah. Toward classifying unstable theories. Ann. Pure Appl. Logic, 80(3):229–255, 1996. ISSN 0168-0072,1873-2461. doi: 10.1016/0168-0072(95)00066-6. URL https://doi.org/10.1016/0168-0072(95)00066-6.
Shelah [2000] Saharon Shelah. On what I do not understand (and have something to say). I. volume 166, pages 1–82. 2000. doi: 10.4064/fm-166-1-2-1-82. URL https://doi.org/10.4064/fm-166-1-2-1-82. Saharon Shelah’s anniversary issue.
Shelah [2012] Saharon Shelah. Model theory. 2012. URL https://arxiv.org/abs/1208.1301.

A walk on the wild side: Notions of maximality in first-order theories

Abstract.

1. Introduction

Theorem (Shelah,[19]).

Question 1.1.

Theorem (See 6.11).

2. Preliminaries

2.1. Dividing lines

Definition 2.1.

Fact 2.2.

Proof.

2.2. Generalized indiscernibles

Definition 2.3.

Fact 2.4 (Stretching indiscernibles, see [17]).

Fact 2.5.

Fact 2.6.

3. Patterns of consistency and inconsistency

Definition 3.1.

Definition 3.2.

Proposition 3.3.

Proof.

Definition 3.4.

Definition 3.5.

Remark 3.6.

Proposition 3.7.

Definition 3.8.

Remark 3.9.

Remark 3.10.

Definition 3.11.

Proposition 3.12.

Proof.

Remark 3.13.

Proposition 3.14.

Proof.

4. Notions of Maximality

Definition 4.1.

4.1. Shelah’s maximality

Definition 4.2.

Proposition 4.3.

Proof.

Proposition 4.4.

Proof.

4.2. Cooper’s maximality

Definition 4.5 (Cooper, [7]).

Definition 4.6 (Cooper, [7]).

Fact 4.7 (Cooper, [7]).

Remark 4.8.

Definition 4.9.

Proposition 4.10.

Proof.

Remark 4.11.

4.3. Examples of S​MSM theories

Example 4.12 (Infinite atomic Boolean algebra).

Non-example 4.13 (Atomless Boolean algebras).

Example 4.14 (Skolem arithmetic).

Example 4.15 (ω\omega-categorical S​MSM theory).

Lemma 4.16.

Proof.

5. Weakenings of S​MSM

5.1. Positive maximality

Definition 5.1.

Definition 5.2.

Remark 5.3.

Remark 5.4.

Proposition 5.5.

Proof.

Remark 5.6.

Example 5.7 (A positive maximal N​S​O​P(4)NSOP_{(4)} theory).

Proposition 5.8.

Proof.

Proposition 5.9.

Proof.

5.2. Consistency maximality

Definition 5.10.

Remark 5.11.

Proposition 5.12.

Proof.

Example 5.13.

Proposition 5.14.

Proof.

A walk on the wild side:
Notions of maximality in first-order theories

4.3. Examples of $SM$ theories

Example 4.15 ( $\omega$ -categorical $SM$ theory).

5. Weakenings of $SM$

Example 5.7 (A positive maximal $NSOP_{(4)}$ theory).

6. The $PM_{k}$ hierarchy

Example 6.13 ( $PM_{k}$ $NPM_{k+1}$ theory).