2.1 Families of sets

In the sequel, our applications will build on heavy use of combinatorial results in the subfield often called set-system combinatorics. We start with commonly used notions.

We use standard set-theoretic notation, including the shorthands

\[ \bigcup\mathcal{A} = \bigcup_{A\in\mathcal{A}}A \text{ and } \bigcap\mathcal{A} = \bigcap_{A\in\mathcal{A}}A,\]

the latter being unambiguous only if $\mathcal{A}\neq\emptyset$ . In addition, we write

\[ [A,B] = \{ C \mid A\subseteq C\subseteq B \},\]

for any sets A and B. Note that if $A\not\subseteq B$ , then $[A,B]=\emptyset$ .

Note that if a family of sets is downward closed or a Sperner family, then it is also convex. The concept of a upward closed family is also useful in set theory but is lacking here, as applications of our methods are very much leaning towards downward closed families.

The concept of Zorn condition is mainly relevant in the context of infinite families. Our emphasis is, however, on finite families of finite sets, for which the Zorn condition, as we have formulated it, trivially holds. We have weakened the standard condition by imposing the requirement only on nonempty chains. The only notable effect is that the empty set is not required to be included in a family fulfilling the Zorn condition, thus allowing all the finite families to meet the condition.

For $\mathcal{A}$ a family of sets, we denote the family of all maximal (with respect to inclusion) sets in $\mathcal{A}$ by $\mathrm{Max}(\mathcal{A})$ . Similarly, $\mathrm{Min}(\mathcal{A})$ is the set of all minimal sets in $\mathcal{A}$ . Observe that $\mathrm{Max}(\mathcal{A})$ and $\mathrm{Min}(\mathcal{A})$ are always Sperner families.

In other words, a family $\mathcal{A}$ is dominated by a set D if and only if D is the largest element in $\mathcal{A}$ with respect to inclusion. Similarly, $\mathcal{A}$ is supported by a set S if and only if S is the smallest element in $\mathcal{A}$ with respect to inclusion. We spell out some of the easily seen connections between the basic concepts in the following lemma.

We proceed to the central dimension concepts which will be studied throughout this paper. The upper dimension was first defined for downwards closed families in Hella et al. (Reference Hella, Luosto, Sano and Virtema2014) and subsequently generalized for arbitrary families in Lück and Vilander (Reference Lück and Vilander2019). The definition presented here is an equivalent reformulation of the latter. We also introduce two new dimension concepts. The idea of the dual upper dimension is that many of the underlying ideas behind the upper dimension work if the inclusion order is reversed, as the previous lemma indicates. The third concept, cylindrical dimension, can be seen as a combination of the two mentioned dimension concepts.

The upper dimension of the family is $\mathcal{A}$

\[\mathrm{D}(\mathcal{A})=\min\{|\mathcal{G}| \mid \text{$\mathcal{G}$ dominates the family $\mathcal{A}$}\},\]

the dual upper dimension is

\[\mathrm{D}^{\mathrm{d}}(\mathcal{A})=\min\{|\mathcal{G}| \mid \text{$\mathcal{G}$ supports the family $\mathcal{A}$}\}\]

and the cylindrical dimension is

\[ \mathrm{CD}(\mathcal{A})=\min\{|I| \mid \text{$(\mathcal{A}_i)_{i\in I}$ is an indexed family of intervals with $\bigcup\limits_{i\in I}\mathcal{A}_i=\mathcal{A}$}\}.\]

If, in addition, $\mathcal{A}$ is convex, then

\[ \mathrm{CD}(\mathcal{A})\le\mathrm{D}(\mathcal{A})\mathrm{D}^{\mathrm{d}}(\mathcal{A}).\]

For the last part of the proposition, assume now that $\mathcal{A}$ is convex. Let $\mathcal{G}$ be a family of minimal size that dominates $\mathcal{A}$ and $\mathcal{K}$ be a family of minimal size that supports $\mathcal{A}$ . Then $\mathrm{D}(\mathcal{A})=|\mathcal{G}|$ and $\mathrm{D}^{\mathrm{d}}(\mathcal{A})=|\mathcal{K}|$ . Let I be the set of pairs $(G,K)\in \mathcal{G}\times\mathcal{K}$ with $K\subseteq G$ . By convexity of $\mathcal{A}$ , we have $[K,G]\subseteq\mathcal{A}$ , for each $(G,K)\in I$ . On the other hand, if $A\in\mathcal{A}$ , then there has to be $G\in\mathcal{G}$ such that $A\subseteq G$ , as $\mathcal{G}$ dominates $\mathcal{A}$ , and similarly $K\in\mathcal{K}$ such that $K\subseteq A$ . This means that $A\in[K,G]$ , for some interval [K,G] with $(G,K)\in I$ . Consequently,

\[ \mathcal{A}=\bigcup_{(G,K)\in I}[K,G],\]

which implies

\[ \mathrm{CD}(\mathcal{A})\le|I|\le |\mathcal{G}\times\mathcal{K}|=\mathrm{D}(\mathcal{A})\mathrm{D}^{\mathrm{d}}(\mathcal{A}).\]

Clearly, if $\mathcal{A}\subseteq\mathcal{P}(X)$ with $n=|X|\in\mathbb{N}$ , then $\mathrm{CD}(\mathcal{A})\le 2^n$ . One gets easily a modest improvement to this result, which is the best possible upper bound, as the succeeding example shows.

Proposition 6. Let X be a nonempty finite set with $n=|X|$ , and let $\mathcal{A}\subseteq\mathcal{P}(X)$ . Then

\[ \mathrm{CD}(\mathcal{A})\le 2^{n-1}.\]

Hence also, $\mathrm{D}(\mathcal{A})\le 2^{n-1}$ and $\mathrm{D}^{\mathrm{d}}(\mathcal{A})\le 2^{n-1}$ .

Example 7. Let X be a nonempty finite set of n elements. Consider the family

\[ \mathcal{E}=\{A\subseteq X \mid |A|\text{ is even} \}.\]

Let $\mathcal{G}$ be a subfamily of $\mathcal{E}$ which dominates $\mathcal{E}$ . Let $A\in\mathcal{E}$ and suppose that A is dominated by $G\in\mathcal{G}$ , which means that A belongs to certain dominated convex family $\mathcal{D}_G$ where $\mathcal{D}_G\subseteq\mathcal{E}$ and $\bigcup\mathcal{D}_G=G$ . By convexity, $[A,G]\subseteq\mathcal{D}_G\subseteq\mathcal{E}$ . Note that $A,G\in\mathcal{E}$ both have even size. However, the interval [A,G] would contain sets of odd size unless $A=G$ . As this holds for arbitrary $A\in\mathcal{E}$ , we conclude that $\mathcal{G}=\mathcal{E}$ . Hence, $\mathrm{D}(\mathcal{E})=|\mathcal{E}|=2^{n-1}$ . By symmetry, we get $\mathrm{D}^{\mathrm{d}}(\mathcal{E})=2^{n-1}$ , too. Combined with the last two propositions, we have that $\mathrm{CD}(\mathcal{E})=2^{n-1}$ .

2.2. Operators

In addition to studying the dimensions of fixed families of sets, we are also interested in the behavior of dimensions under various operators. An operator on families of sets on a fixed base set X is a function $\Delta\colon \mathcal{P}(\mathcal{P}(X))^n\to\mathcal{P}(\mathcal{P}(X))$ for some positive integer n. In some applications to team semantics, it is useful to consider more general operators of the form $\Delta\colon \mathcal{P}(\mathcal{P}(X))^n\to\mathcal{P}(\mathcal{P}(Y))$ with different base sets X and Y. We list in the next example some natural set-theoretic operators that we will study further in the forthcoming sections. For the related topic of Boolean algebras B with operators $B^n\to B$ see e.g. Venema (Reference Venema2007).

Similarly, we define an operator $\Delta^X_{\forall i}\colon\mathcal{P}(\mathcal{P}(X))\to\mathcal{P}(\mathcal{P}(Y))$ that corresponds to universal quantification: Given a set $B\in\mathcal{P}(Y)$ , let $B[X_i/i]=\{(a_0,\ldots,a_{m-1})\in X\mid(a_0,\ldots,a_{i-1},a_{i+1},\ldots,a_{m-1})\in B, a_i\in X_i\}$ . Then we let $\Delta^X_{\forall i}(\mathcal{A})=\{B\in\mathcal{P}(Y)\mid B[X_i/i]\in \mathcal{A}\}$ .

Note that the union and intersection operators $\Delta^X_\cup$ and $\Delta^X_\cap$ do not depend on the base set X. Thus, in the sequel we will denote these operators for the sake of simplicity by $\cup$ and $\cap$ , as they actually are what is usually denoted $\cup$ and $\cap$ . The same holds for tensor disjunction and conjunction, whence we will use the notation $\mathcal{A}\lor\mathcal{B}:=\Delta^X_\lor(\mathcal{A},\mathcal{B})$ and $\mathcal{A}\land\mathcal{B}:=\Delta^X_\land(\mathcal{A},\mathcal{B})$ . On the other hand, both complementation $\Delta^X_c$ and tensor negation $\Delta^X_\lnot$ depend on X, whence we do not introduce any shorthand notation for them.

Note further that the projections $\Delta^X_{\exists i}$ do not depend on $X=X_0\times\cdots\times X_{m-1}$ , since the length and the i-th component of any tuple $\vec{a}$ is uniquely determined: $(a_0,\ldots,a_{m-1})=(b_0,\ldots,b_{m'-1})$ if and only if $m=m'$ and $a_i=b_i$ for all $i< m$ . However, the universal projection operator $\Delta^X_{\forall i}$ clearly depends on the base set X. Thus, for the sake of uniformity, we keep using the notation $\Delta^X_{\exists i}$ .

2.3 Tensor operators

We have seen in Example 8 that the disjunction and conjunction connectives give rise to tensor disjunction and tensor conjunction operators. This idea can of course be generalized to arbitrary connectives. We introduce here the related concept of tensor operator and show that they preserve intervals but not necessarily dominated convex or supported convex families.

Definition 9. Fix a base set X and let $\circledast$ be a binary operation on the set $\{0,1\}$ , i.e., $\circledast$ is a map $\{0,1\}\times\{0,1\}\to\{0,1\}$ . Then the corresponding set-theoretic operation is $*\colon\mathcal{P}(X)^2\to\mathcal{P}(X)$ ,

\[ A*B=\{x\in X \mid \chi_A(x)\circledast\chi_B(x)=1\}\]

where $\chi_C$ is the characteristic function related to a set C. The tensor operator corresponding to $\circledast$ is $\Delta^X_{\circledast}\colon \mathcal{P}(\mathcal{P}(X))^2\to\mathcal{P}(\mathcal{P}(X))$ ,

\[ \Delta^X_{\circledast}(\mathcal{A},\mathcal{B})=\{A*B \mid A\in\mathcal{A},B\in\mathcal{B}\}.\]

Note that we always have $\mathcal{A}\circledast\emptyset=\emptyset\circledast\mathcal{B}=\emptyset$ .

There are $2^4=16$ binary operations on the set $\{0,1\}$ , 4 of which (constant functions and projections) are rather trivial. Among the 8 zero-preserving (i.e., $0\circledast 0=0$ ) operations, there are 5 non-trivial tensor operations, which are listed below except for the case $\mathcal{A}\circledast\mathcal{B}=\mathcal{B}-\mathcal{A}$ , which is the set difference with the roles reversed.

\begin{align*}\begin{array}{l@{\quad}l@{\quad}l}\textit{connective} & \textit{set-theoretic operation} & \textit{tensor operation} \\[5pt]disjunction\,\lor & union\,\cup & \mathcal{A}\lor\mathcal{B} = \{ A\cup B \mid A\in\mathcal{A},\,B\in\mathcal{B} \} \\[5pt]conjunction\,\land & intersection\,\cap & \mathcal{A}\land\mathcal{B} = \{ A\cap B \mid A\in\mathcal{A},\,B\in\mathcal{B} \} \\[5pt]``p\;but\;not\;q'' & set\;difference\,\smallsetminus & \mathcal{A}-\mathcal{B} = \{ A\smallsetminus B \mid A\in\mathcal{A},\,B\in\mathcal{B} \} \\[5pt]exclusive\;disjunction\,\oplus & symmetric\;difference\,\triangle & \mathcal{A}\oplus\mathcal{B} = \{ A\triangle B \mid A\in\mathcal{A},\,B\in\mathcal{B} \}\end{array}\end{align*}

If the connective $\circledast$ is commutative (resp. associative), then the corresponding tensor operation is commutative (resp. associative), too, but as we shall see in the next example, the same does not apply to idempotence. In general, the well-known logical equivalences do not transfer to equalities about tensor operations. This means that, in contrast to propositional logic where we often reduce problems to some small set of basic connectives, it is better to consider tensor operators separately.

Example 11. Suppose the base set X is infinite and $\mathcal{A}=\{\{x\} \mid x\in X\}$ . Consider the families

\[ \mathcal{A}_n=\underbrace{\mathcal{A}\lor\ldots\lor\mathcal{A}}_{n\text{ times}},\]

for $n\in\mathbb{Z}_+$ . An easy induction shows that $\mathcal{A}_n=\{B\subseteq X \mid B\neq\emptyset,|B|\le n\}$ , so these families are all different. In particular, $\mathcal{A}\lor\mathcal{A}=\mathcal{A}_2\neq\mathcal{A}$ , so the tensor operation $\lor$ is not idempotent, though the binary operation $\lor$ on $\{0,1\}$ is. A similar example shows that $\land$ (as a tensor operator) is not idempotent either.

Elaborating on this example, one sees that distributive law does not hold for $\lor$ and $\land$ , either. Choose $\mathcal{B}=\mathcal{C}=\{X\}$ with $\mathcal{A}$ as above; then

\[ \mathcal{A}\land(\mathcal{B}\lor\mathcal{C})=\mathcal{A}\land\{X\}=\mathcal{A}\neq \mathcal{A}\lor\mathcal{A}=(\mathcal{A}\land\mathcal{B})\lor(\mathcal{A}\land\mathcal{C}).\]

We do not aim at a complete analysis on how the tensor operations behave, but we shall show that they preserve intervals. In connection with the following lemma, we will have thus one way to compute the result of tensor operation.

Lemma 12. Let $\circledast$ be a binary operation on $\{0,1\}$ , and let $\mathcal{A}_i,\mathcal{B}_j\in\mathcal{P}(\mathcal{P}(X))$ be families of sets, for $i\in I$ and $j\in J$ . Then

\[\left(\bigcup_{i\in I}\mathcal{A}_i\right)\circledast\left(\bigcup_{j\in J}\mathcal{B}_j\right)=\bigcup_{\substack{i\in I,\\j\in J}}(\mathcal{A}_i\circledast\mathcal{B}_j).\]

We need some auxiliary concepts to handle intervals and tensor operators. We depart for a moment from classical logic (Kleene introduced his logic in Kleene Reference Kleene1952, Section 64) and introduce a new truth value for “unknown.” ^{Footnote 3}

Definition 13. Let $\circledast$ be a binary operation on $\{0,1\}$ . We define Kleene’s extension $\widetilde\circledast$ of $\circledast$ as follows. Write $V_0=\{0\}$ , $V_1=\{1\}$ , and $A\circledast B=\{a\circledast b \mid a\in A, b\in B\}$ , for $A,B\subseteq\{0,1\}$ . Then $\widetilde\circledast$ is determined by the rule:

\[ u\widetilde\circledast v = w \text{ if and only if }V_u\circledast V_v = V_w,\]

for . Overloading once again the notation, we shall denote also the extension by $\circledast$ instead of $\widetilde\circledast$ in the sequel.

Lemma 17. Let $\circledast$ be a binary operation on $\{0,1\}$ and $\mathcal{A},\mathcal{B}\subseteq\mathcal{P}(X)$ . Then for every $x\in X$ , it holds that

\[\xi_{\mathcal{A}\circledast\mathcal{B}}(x)=\xi_\mathcal{A}(x)\circledast\xi_\mathcal{B}(x).\]

Proof. Write $E_\mathcal{C}(x)=\{\chi_C(x) \mid C\in\mathcal{C}\}$ , for $\mathcal{C}\subseteq\mathcal{P}(X)$ and $x\in X$ . Then

\begin{align*}E_{\mathcal{A}\circledast\mathcal{B}}(x) & = \{ \chi_C(x) \mid C\in \mathcal{A}\circledast\mathcal{B} \} \\ & = \{ \chi_{A*B}(x) \mid A\in \mathcal{A},\,B\in\mathcal{B} \} \\ & = \{ \chi_A(x)\circledast \chi_B(x) \mid A\in \mathcal{A},\,B\in\mathcal{B} \} \\ & = \{ \chi_A(x) \mid A\in \mathcal{A}\} \circledast \{\chi_B(x)\mid B\in\mathcal{B} \} \\ & = E_\mathcal{A}(x) \circledast E_\mathcal{B}(x).\end{align*}

Employing the notation that was used to define Kleene’s extension, we may write this equation as

\[ V_{\xi_{\mathcal{A}\circledast\mathcal{B}}(x)} = V_{\xi_\mathcal{A}(x)} \circledast V_{\xi_\mathcal{B}(x)},\]

i.e., $\xi_{\mathcal{A}\circledast\mathcal{B}}(x) = \xi_\mathcal{A}(x) \circledast \xi_\mathcal{B}(x)$ .

2.4 Families of teams

The abstract concept of a family of sets is so general that it arises naturally in numerous contexts in mathematics. However, in this paper, our focus is on families of sets arising in logic, with applications to logic in mind. These families are collections of sets on the base set of the form of a Cartesian product $M^m$ . This is because we will consider sets of so-called assignments into a model M. Thus, the elements of our base set are assignments. This particular form of the base set leads to dimension computations which do not arise in the abstract setting. This is simply because finite tuples manifest more complicated combinatorial properties than mere elements. To avoid trivialities, we assume $|M|\ge 2$ .

Let us see how sets of what we call assignments arise in logic. In classical logic, one associates with a given formula $\phi(x_0,\ldots,x_{m-1})$ with the free variables $x_0,\ldots,x_{m-1}$ and a given structure M the set of m-tuples satisfying the formula $\phi$ in M:

\[ \phi^{{M,\vec x}}=\{(a_0,\ldots,a_{m-1})\in M^m\mid M\models \phi(a_0,\ldots,a_{m-1})\}.\]

Here $``M\models \phi(a_0,\ldots,a_{m-1})"$ refers to the truth definition (a.k.a. satisfaction relation) of the logic that $\phi(x_0,\ldots,x_{m-1})$ is considered a formula of. For first-order logic, the truth definition is given in standard textbooks of logic and can be found e.g. in Väänänen (Reference Väänänen2011, Section 6.2). We follow the usual convention and call elements $(a_0,\ldots,a_{m-1})$ of $\phi^{{M,\vec x}}$ assignments. Sets $\phi^{{M,\vec x}}$ of assignments are aptly called definable subsets of $M^m$ . The definable subsets of $M^m$ form a Boolean algebra with Boolean operations corresponding to the logical operations of first-order logic. The study of this algebra is a well-known method in logic.

In the same way as classical logic gives rise to definable sets of assignments, so-called dependence logic (Väänänen Reference Väänänen2007) that we will now recall gives rise to definable families of sets of assignments as follows. If M is a model, a team in M is a set T of assignments s (i.e., functions) which map a fixed set $\mathrm{dom}(s)=\{x_0,\ldots,x_{m-1}\}$ of variables, called the domain of s (and of T), to M. See Table 1 for an example of a team. The rows of a team are assignments. In principle, a team is simply a table of data. The source of the data can be anything. A good intuition is that the data comes from some experiments concerning the “attributes” $\{x_0,\ldots, x_{m-1}\}$ , each row representing one experiment. Another useful intuition is that the table of data is (a part of) a database. We identify the function s with the tuple $(s(x_0),\ldots,s(x_{m-1}))$ and a team with a subset of $M^m$ .

Table 1. A team

Teams can manifest phenomena that single assignments cannot. For example, the team of Table 1 manifests the circumstance that $x_0$ does not completely determine $x_2$ but $x_1$ does. In dependence logic (Väänänen Reference Väänänen2007), we have so-called dependence atoms (see Definition 20) the semantics of which is defined by means of teams and could not be defined meaningfully in terms of single assignments. Every formula $\phi$ of dependence logic, or any other logic the semantics of which is based on teams, with free variables in $\vec x=(x_0,\ldots,x_{m-1})$ , gives rise to the set of teams

(1) \begin{equation} \left\Vert \phi \right\Vert^{{M,\vec x}}=\{T\subseteq M^m \mid M\models_T\phi\},\end{equation}

where $M\models_T\phi$ is the satisfaction relation defined in Definitions 19 and 20 below. We consider the families $\left\Vert \phi \right\Vert^{{M,\vec x}}$ an interesting special case of families of subsets of $M^m$ .

If $\ell< m$ , there is a canonical projection $M^m\to M^\ell$ . We may identify $T\subseteq M^\ell$ with $T^*=\{s\in M^m : s\restriction \ell\in T\}$ . In this way, it is possible to think of a subset of $M^\ell$ at the same time, via $T^*$ , as a subset of $M^m$ , although literally, of course, $T \ne T^*$ .

Many of the results of this paper hold for arbitrary families of sets but when applied to families of the form $\left\Vert \phi \right\Vert^{{M,\vec{x}}}$ , results pertaining to dependence and independence logics obtain.

In order to make (1) more exact, we now recall the inductive definition of $M\models_T\phi$ from Väänänen (Reference Väänänen2007), first for logical operations (Definition 19) and then for new atoms (Definition 20). If $a\in M$ , then $s(a/x)$ is the unique assignment s’ such that $s'(x)=a$ and $s'(y)=s(y)$ for variables y in the domain of s other than x. If $F:T\to \mathcal{P}(M)\smallsetminus\{\emptyset\}$ , then $T[F/x]=\{s(a/x)\mid s\in T, a\in F(s)\}$ . Finally, $T[M/x]=\{s(a/x) \mid a\in M, s\in T\}$ .

This defines $M\models_T\phi$ for every first-order formula $\phi$ in negation normal form (i.e., negation occurs in front of atomic formulas only). Note that Väänänen (Reference Väänänen2007) uses only the first two of the four binary connectives in Definition 19. We have kept here the usual notation $\land$ and $\lor$ for these connectives. Intuitionistic disjunction was mentioned in Väänänen (Reference Väänänen2007) and elaborated on in Abramsky and Väänänen (Reference Abramsky and Väänänen2009). Tensor conjunction does not seem to have been studied before, and its role is minor here, too.

It might seem that $\phi\underline{\vee}\psi$ is a more “natural” disjunction than $\phi\vee\psi$ . What is natural depends, of course, on one’s intuition about $\models_T$ . In Väänänen (Reference Väänänen2007) an alternative game-theoretic definition of $M\models_T\phi$ is given and in that context $\phi\vee\psi$ is a natural connective corresponding perfectly to the disjunction of classical propositional calculus.

By Definition 19(a), for every first-order literal (i.e., atomic or negated atomic) $\phi,$ we have $\left\Vert \phi \right\Vert^{{M,\vec x}}=[\emptyset,\phi^{{M,\vec x}}]$ . The same is true if $\phi$ is any formula of first order logic. Thus, for first-order $\phi,$ the family $\left\Vert \phi \right\Vert^{{M,\vec{x}}}$ is dominated (by $\phi^{{M,\vec x}}$ ), downward closed, convex, and supported (by $\emptyset$ ).

Note further that for composite $\phi$ the family $\left\Vert \phi \right\Vert^{{M,\vec x}}$ can be obtained from the corresponding families for the components of $\phi$ by applying one of the operators introduced in Example 8. For conjunction and (tensor) disjunction, we have

$$\begin{array}{lcl}\left\Vert \phi\wedge\psi \right\Vert^{{M,\vec x}}&= &\left\Vert \phi \right\Vert^{{M,\vec x}}\cap\left\Vert \psi \right\Vert^{{M,\vec x}} \\\left\Vert \phi\vee\psi \right\Vert^{{M,\vec x}}&= &\left\Vert \phi \right\Vert^{{M,\vec x}}\lor\left\Vert \psi \right\Vert^{{M,\vec x}} \\\end{array} $$

Furthermore, for tensor conjunction and intuitionistic disjunction, we have

$$\begin{array}{lcl}\left\Vert \phi\,{\wedge}\,\psi \right\Vert^{{M,\vec x}}&= &\left\Vert \phi \right\Vert^{{M,\vec x}}\land\left\Vert \psi \right\Vert^{{M,\vec x}} \\\left\Vert \phi\ \underline{\vee}\ \psi \right\Vert^{{M,\vec x}}&= &\left\Vert \phi \right\Vert^{{M,\vec x}}\cup\left\Vert \psi \right\Vert^{{M,\vec x}} \\\end{array} $$

Note, however, that in the case of existential and universal quantifiers, the quantified variable needs to be dropped from the tuple $\vec x=(x_0,\ldots,x_{m-1})$ , as it has become a bound variable:

$$\begin{array}{lcl}\left\Vert \exists x_i\phi \right\Vert^{{M,{\vec{x}\hspace{0.3 mm}}^-}}&= &\Delta_{\exists i}^{M^m}(\!\left\Vert \phi \right\Vert^{{M,\vec{x}}}) \\\left\Vert \forall x_i\phi \right\Vert^{{M,{\vec{x}\hspace{0.3 mm}}^-}}&= &\Delta_{\forall i}^{M^m}(\!\left\Vert \phi \right\Vert^{{M,\vec{x}}}), \\\end{array} $$

where ${\vec{x}\hspace{0.3 mm}}^-$ is the tuple obtained from $\vec{x}$ by deleting the component $x_i$ .

We now recall the extension of $M\models_T\phi$ from first-order $\phi$ to new non first-order atoms. Below, the restriction of a team T to $\vec{x}$ , in symbols $T\restriction\vec{x}$ , is the set $\{s\restriction\vec{x}:s\in T\}$ . We use $\mathrm{len}(\vec{x})$ to denote the length of the variable (or other) sequence $\vec{x}$ .

By closing the respective atom under the logical operations (b), (c), (f) and (g) of Definition 19 we obtain, respectively, dependence logic, constancy logic, exclusion logic, inclusion logic, anonymity logic, and (pure or conditional) independence logic.

Note that we defined $\,=(\vec{x},y)$ for single variable y only. This is because $\,=(\vec{x},\vec{y})$ for a vector $\vec{y}=(y_1\ldots,y_n)$ , which we adopt now as a shorthand, can be defined as

$$\,=(\vec{x},y_1)\wedge\ldots\wedge\,=(\vec{x},y_n).$$

We use the same convention for $\,=(\vec{y})$ .

If $\phi$ is a dependence atom or an exclusion atom, then $\left\Vert \phi \right\Vert^{{M,\vec{x}}}$ is, as can be easily verified, downward closed and supported by $\emptyset$ but not necessarily closed under unions or dominated. If $\phi$ is an inclusion atom or an anonymity atom, then $\left\Vert \phi \right\Vert^{{M,\vec{x}}}$ is, as can be likewise easily verified, closed under unions and dominated by $M^{\mathrm{len}(\vec{x})}$ but not necessarily downward closed or supported. For details we refer to Väänänen (Reference Väänänen2007), Galliani (Reference Galliani2012).

Example 21. An example of a sentence combining dependence atoms and logical operations is the following formula which is satisfied by a team T in a model of size n if and only if $|\hspace{1pt} T\restriction \vec{x} \hspace{1pt}|\le n^k/2$ , where $\mathrm{len}(\vec{x})=k$ :

$$\exists\vec{y}(\!=(\vec{y},\vec{x})\wedge \vec{x}\ |\ \vec{y}).$$

Here $\mathrm{len}(\vec{y})=k$ . An example of a sentence combining a number of different atoms as well as logical operations is the following formula which is satisfied by a team T if and only if $|\hspace{1pt} T\restriction \vec{x} \hspace{1pt}|$ is even:

$$\begin{array}{l}\exists u\exists v\exists\vec{y}\exists\vec{z}(\vec{y}\vec{z}\perp \vec{x}\wedge\vec{y}\subseteq\vec{x}\wedge\vec{z}\subseteq\vec{x}\\\qquad\wedge((u=v\wedge\vec{x}\subseteq\vec{y})\vee(u\ne v\wedge \vec{x}\subseteq\vec{z}))\\\qquad\wedge\ \vec{y}\ |\ \vec{z}\ \wedge \,=(\vec{z},\vec{y})\ \wedge \,=(\vec{y},\vec{z})).\end{array}$$

We will also consider the extension of first-order logic with Lindström quantifiers (see Lindström Reference Lindström1966 for definition). For the sake of simplicity, we restrict attention to Lindström quantifiers of type (r) for some positive integer r (i.e., quantifiers binding a single formula). Such a quantifier $Q_\mathcal{K}$ is associated to any isomorphism closed class $\mathcal{K}$ of structures of the form (A,R), $R\subseteq A^r$ . If $\psi$ is a formula and $\vec y$ is an r-tuple of variables, then applying the quantifier $Q_\mathcal{K}$ we obtain a new formula $Q_\mathcal{K}\vec y\,\psi$ in which all occurrences of the variables in $\vec y$ are bound.

Adding Lindström quantifiers to logics with team semantics was first considered by Engström (Reference Engström2012). We follow here his definition for the semantics of $Q_\mathcal{K}$ . First, we adapt the notation used for existential quantifier: if $F\colon T\to \mathcal{P}(M^r)$ , then $T[F/\vec y]=\{s(\vec b/\vec y)\mid s\in T, \vec b\in F(s)\}$ .

The semantics of Lindström quantifiers can also be formulated in terms of operators that map sets of the form $\left\Vert \psi \right\Vert^{{M,\vec{z}}}$ to sets $\left\Vert Q_\mathcal{K}\vec{y}\,\psi \right\Vert^{{M,\vec{x}}}$ , where $\vec{z}$ consists of the variables in the tuples $\vec{x}$ and $\vec{y}$ . To work out the details of these operators, we fix a quantifier $Q_\mathcal{K}$ of type (r), the length $m\ge r$ of $\vec{z}$ , the tuple $\vec\ell=(\ell_0,\ldots,\ell_{r-1})$ for which $\vec{y}=(z_{\ell_0},\ldots,z_{\ell_{r-1}})$ , and the universe M of the model. Note that there is no reason to assume that the components of $\vec\ell$ are in ascending order; the quantifier $Q_\mathcal{K}$ can be applied to any r-tuple of distinct variables in $\vec{z}$ . On the other hand, we can assume w.l.o.g. that $\vec{x}$ lists the rest of the variables in $\vec{z}$ in ascending order, i.e., for each $i<m-r$ , $x_i=z_j$ , where $j\not\in\{\ell_0,\ldots,\ell_{r-1}\}$ and $i=|\{k<j\mid k\notin\{\ell_0,\ldots,\ell_{r-1}\}\}|$ . Thus, $\vec{z}$ is obtained from $\vec{x}$ and $\vec{y}$ by re-ordering the latter and shuffling according to $\vec\ell$ . We use the notation $\vec{z}=\vec{x}\otimes_{\vec\ell}\vec{y}$ to denote this shuffling, and similarly $\vec{c}=\vec{a}\otimes_{\vec\ell}\vec{b}$ for tuples $\vec{c},\vec{a},\vec{b}$ of elements in M.

Assume then that $S\subseteq M^m$ is a team with domain $\{z_0,\ldots,z_{m-1}\}$ . For each $\vec{a}\in M^{m-r}$ the $\vec\ell$ -restriction of S on $\vec{a}$ is the set $S[\vec{a}]_{\vec\ell}:=\{\vec{b}\in M^r\mid \vec{a}\otimes_{\vec\ell}\vec{b}\in S\}$ . Furthermore, the $(\mathcal{K},\vec\ell)$ -projection of S is the set $\pi_{\mathcal{K},\vec\ell}\,(S):=\{\vec{a}\in M^{m-r}\mid (M,S[\vec{a}]_{\vec\ell})\in\mathcal{K}\}$ . The idea here is that if $T=\pi_{\mathcal{K},\vec\ell}\,(S)$ for some team $S\in\left\Vert \psi \right\Vert^{{M,\vec{z}}}$ , then defining $F\colon T\to\mathcal{P}(M^r)$ by $F(\vec{a})=S[\vec{a}]_{\vec\ell}$ for each $\vec{a}\in T$ , we see that the truth condition of Definition 22 holds for the team T, provided that $S=T[F/\vec{y}]$ . It is clear that $T[F/\vec{y}]\subseteq S$ , and the converse inclusion holds if and only if $\{\vec{a}\in M^{m-r}\mid S[\vec{a}]_{\vec\ell}\not=\emptyset\}\subseteq T$ . We say that T is the proper $(\mathcal{K},\vec\ell)$ -projection of S, in symbols $T=\pi^p_{\mathcal{K},\vec\ell}\,(S)$ , if this condition holds.

The argument above shows that if $T=\pi^p_{\mathcal{K},\vec\ell}\,(S)$ for some team $S\in\left\Vert \psi \right\Vert^{{M,\vec{z}}}$ , then $T\in\left\Vert Q_\mathcal{K}\vec{y}\,\psi \right\Vert^{{M,\vec{x}}}$ . Assuming that $(M,\emptyset)\notin\mathcal{K}$ , the converse implication is also true. Indeed, if $M\models_T Q_\mathcal{K}\vec y\,\psi$ , then there is a function $F\colon T\to \mathcal{P}(M^r)$ such that $M\models_{T[F/\vec{y}]}\psi$ and $(M,F(\vec{a}))\in \mathcal{K}$ for all $\vec{a}\in T$ . Since $(M,\emptyset)\notin\mathcal{K}$ , $F(\vec{a})\not=\emptyset$ for every $\vec{a}\in T$ , whence $T=\pi_{\mathcal{K},\vec\ell}\,(T[F/\vec{y}])$ . Moreover, the condition $\{\vec{a}\in M^{m-r}\mid S[\vec{a}]_{\vec\ell}\not=\emptyset\}\subseteq T$ clearly holds for any team S of the form $T[F/\vec{y}]$ . Thus, we see that $T=\pi^p_{\mathcal{K},\vec\ell}\,(T[F/\vec{y}])$ .

Note, however, that if $(M,\emptyset)\in\mathcal{K}$ , the argument for $T=\pi_{\mathcal{K},\vec\ell}\,(T[F/\vec{y}])$ fails: by the definition we always have $\pi_{\mathcal{K},\vec\ell}\,(T[F/\vec{y}])\subseteq T$ , but if $F(\vec{a})=\emptyset$ for some $\vec{a}\in T$ , then $\vec{a}\notin \pi_{\mathcal{K},\vec\ell}\,(T[F/\vec{y}])$ . In this case, the correct condition for a team T being in the family $\left\Vert Q_\mathcal{K}\vec{y}\,\psi \right\Vert^{{M,\vec{x}}}$ is that there exist teams $S\in\left\Vert \psi \right\Vert^{{M,\vec{z}}}$ and $T'\subseteq T$ such that $T'=\pi^p_{\mathcal{K},\vec\ell}\,(S)$ .

We are now ready to define the operators on families of teams corresponding to Lindström quantifiers.

• If $(M,\emptyset)\notin\mathcal{K}$ , then for each $\mathcal{A}\in\mathcal{P}(\mathcal{P}(M^m))$ ,

  $$ \Delta^{M^m}_{\mathcal{K},\vec\ell}(\mathcal{A})=\{B\in\mathcal{P}(\mathcal{P}(M^{m-r}))\mid B=\pi^p_{\mathcal{K},\vec\ell}\,(A)\text{ for some }A\in\mathcal{A}\}.$$

• If $(M,\emptyset)\in\mathcal{K}$ , then for each $\mathcal{A}\in\mathcal{P}(\mathcal{P}(M^m))$ ,

  $$ \Delta^{M^m}_{\mathcal{K},\vec\ell}(\mathcal{A})=\{B\in\mathcal{P}(\mathcal{P}(M^{m-r}))\mid \pi^p_{\mathcal{K},\vec\ell}\,(A)\subseteq B\text{ for some }A\in\mathcal{A}\}.$$

By the argument given before Definition 23, the operator $\Delta^{M^m}_{\mathcal{K},\vec\ell}$ captures the semantics of the quantifier $Q_\mathcal{K}$ :

$$\begin{array}{lcl} \left\Vert Q_\mathcal{K} \vec y\,\psi \right\Vert^{{M,\vec{x}}}&= &\Delta_{\mathcal{K},\vec\ell}^{M^m}(\!\left\Vert \psi \right\Vert^{{M,\vec{z}}}).\end{array}$$

Note further that the standard existential and universal quantifiers are special cases of Lindström quantifiers: $\exists=Q_{\mathcal{K}_\exists}$ for the class $\mathcal{K}_\exists=\{(A,R)\mid R\subseteq A, R\not=\emptyset\}$ , and $\forall=Q_{\mathcal{K}_\forall}$ for $\mathcal{K}_\forall=\{(A,R)\mid R= A\}$ . Thus, the corresponding operators are also identical: for each $i<m$ , $\Delta_{\exists i}^{M^m}= \Delta_{{\mathcal{K}_\exists},\vec\ell}^{M^m}$ and $\Delta_{\forall i}^{M^m}= \Delta_{{\mathcal{K}_\forall},\vec\ell}^{M^m}\,$ , where $\vec\ell=i$ (i.e., $\ell$ is of length 1, and $\ell_0=i$ ). For this reason there is no need to consider the operators $\Delta_{\exists i}^{M^m}$ and $\Delta_{\forall i}^{M^m}$ separately in the sequel.

3.1 Convex shadows and hulls

In this subsection, we develop some auxiliary tools useful in concrete dimension calculations. In particular, we introduce the notions of convex shadow and the dual notion of dual convex shadow, which facilitate the calculation of upper and dual upper dimension of a given family. The point is that when we need to check if a subfamily dominates the given family, the convex shadows are the canonical dominated convex families we need to relate to the sets in the dominating family.

Definition 25. Let $\mathcal{A}$ be a family of sets and $A\in\mathcal{A}$ . The convex shadow of A in the family $\mathcal{A}$ is the family

\[ \partial_A(\mathcal{A})=\{ B\subseteq A \mid [B,A]\subseteq\mathcal{A} \}.\]

Similarly, the dual convex shadow of A in $\mathcal{A}$ is

\[ \partial^A(\mathcal{A})=\{ B\in\mathcal{A} \mid A\subseteq B,\,[A,B]\subseteq\mathcal{A} \}.\]

A set $A\in\mathcal{A}$ is called critical in $\mathcal{A}$ if its convex shadow is maximal in the family

\[ \{ \partial_B(\mathcal{A}) \mid B\in\mathcal{A} \}.\]

We use the notation

\[ \mathrm{Crit}(\mathcal{A}) = \{ A\in\mathcal{A} \mid A\text{ critical in $\mathcal{A}$} \}.\]

Similarly, we define the notion of dual criticality. We denote the family of dually critical sets in $\mathcal{A}$ by $\mathrm{Crit}^{\mathrm{d}}(\mathcal{A})$ :lla.

1. (a) $\partial_A(\mathcal{A})$ is the largest dominated convex family $\mathcal{C}\subseteq\mathcal{A}$ with $\bigcup\mathcal{C}=A$ . Similarly, $\partial^A(\mathcal{A})$ is the largest supported convex family $\mathcal{C}\subseteq\mathcal{A}$ with $\bigcap\mathcal{C}=A$ .

2. (b) A family $\mathcal{G}\subseteq\mathcal{A}$ dominates $\mathcal{A}$ if and only if $\bigcup_{G\in\mathcal{G}}\partial_G(\mathcal{A})=\mathcal{A}$ . Dually, $\mathcal{H}\subseteq\mathcal{A}$ supports $\mathcal{A}$ if and only if $\bigcup_{H\in\mathcal{H}}\partial^H(\mathcal{A})=\mathcal{A}$ .

3. (c) Suppose that the family $\mathcal{A}$ satisfies Zorn condition. Then there is a family $\mathcal{G}$ dominating $\mathcal{A}$ such that $\mathcal{G}\subseteq\mathrm{Crit}(\mathcal{A})$ and $|\mathcal{G}|= \mathrm{D}(\mathcal{A})$ . The dual result also holds.

1. (a) Clearly, $\partial_A(\mathcal{A})$ is a dominated convex subfamily of $\mathcal{A}$ with $\bigcup\mathcal{A}=A$ . Suppose $\mathcal{C}\subseteq\mathcal{A}$ is another dominated convex subfamily with $\bigcup\mathcal{C}=A$ . For $C\in\mathcal{C}$ , we have $[C,A]\subseteq\mathcal{C}\subseteq\mathcal{A}$ by convexity of $\mathcal{C}$ , so $\mathcal{C}\subseteq\partial_A(\mathcal{A})$ .

2. (b) If $\bigcup_{G\in\mathcal{G}}\partial_G(\mathcal{A})=\mathcal{A}$ , then the dominated convex families $\partial_G(\mathcal{A})\subseteq\mathcal{A}$ , $G\in\mathcal{G}$ , witness that $\mathcal{G}$ dominates $\mathcal{A}$ .Conversely, suppose that $\mathcal{G}$ dominates $\mathcal{A}$ and the families $\mathcal{D}_G$ , $G\in\mathcal{G}$ , witness that (meaning that $\bigcup_{G\in\mathcal{G}}\mathcal{D}_G=\mathcal{A}$ and $\bigcup\mathcal{D}_G=G$ , for each $G\in\mathcal{G}$ ). Then by the preceding claim, we have that for every $G\in\mathcal{G}$ , $\mathcal{D}_G\subseteq\partial_G(\mathcal{A})$ , implying $\bigcup_{G\in\mathcal{G}}\partial_G(\mathcal{A})=\mathcal{A}$ .

3. (c) Pick a subfamily $\mathcal{G}_0\subseteq\mathcal{A}$ dominating $\mathcal{A}$ such that $|\mathcal{G}_0|=\mathrm{D}(\mathcal{A})$ . Let $G\in\mathcal{G}_0$ , and consider the family

   $$ \mathcal{B}_G = \{ A\in\mathcal{A} \mid \partial_G(\mathcal{A})\subseteq\partial_A(\mathcal{A}) \}.$$
   First we establish that $\mathcal{B}_G$ satisfies the Zorn condition. Indeed, let $\mathcal{K}\subseteq\mathcal{B}_G$ be a chain. As $\mathcal{K}\subseteq\mathcal{A}$ and $\mathcal{A}$ satisfies the Zorn condition, we have that $B=\bigcup\mathcal{K}\in\mathcal{A}$ . We need to show further that $\partial_G(\mathcal{A})\subseteq\partial_B(\mathcal{A})$ . Let $A\in\partial_G(\mathcal{A})$ and $C\in[A,B]$ . Studying the chain $\mathcal{K}'=\{C\cap K \mid K\in\mathcal{K} \}$ , we observe that for each $K\in\mathcal{K}$ , we have that $A=A\cap G\subseteq A\cap K\subseteq C\cap K\subseteq K$ , implying that $C\cap K\in [A,K]\subseteq\partial_K(\mathcal{A})$ , as $A\in\partial_G(\mathcal{A})\subseteq\partial_K(\mathcal{A})$ . Hence, $C\cap K\in\mathcal{A}$ and since this holds for each $K\in\mathcal{K}$ , we have that $\mathcal{K}'\subseteq\mathcal{A}$ . As $\mathcal{A}$ satisfies the Zorn condition, we have that $C=C\cap B=C\bigcup\mathcal{K}=\bigcup\mathcal{K}'\in\mathcal{A}$ . As $C\in\mathcal{A}$ , for every $C\in[A,B]$ , we get $[A,B]\subseteq\mathcal{A}$ and consequently $A\in\partial_B(\mathcal{A})$ . Summarizing, we have that $\partial_G(\mathcal{A})\subseteq\partial_B(\mathcal{A})$ implying $B\in\mathcal{B}_G$ , which means that $\mathcal{B}_G$ satisfies the Zorn condition.

As $\mathcal{B}_G$ satisfies the Zorn condition, by Zorn’s lemma, there is a maximal element in $\mathcal{B}_G$ , say, $D_G$ . The maximality of $D_G$ clearly impies that $D_G$ is critical in $\mathcal{A}$ . Recall that $D_G\in\mathcal{B}_G$ means also that $\partial_G(\mathcal{A})\subseteq \partial_{D_G}(\mathcal{A})$ . Collect these set together and put $\mathcal{G}=\{D_G \mid G\in\mathcal{G}_0 \}$ . As $\mathcal{G}_0$ dominates $\mathcal{A}$ , we have $\bigcup_{G\in\mathcal{G}_0}\partial_G(\mathcal{A})=\mathcal{A}$ , which now clearly implies

$$ \bigcup_{G\in\mathcal{G}}\partial_G(\mathcal{A})=\bigcup_{G\in\mathcal{G}_0}\partial_{D_G}(\mathcal{A})=\mathcal{A}.$$

Hence, $\mathcal{G}$ also dominates $\mathcal{A}$ , and $|\mathcal{G}|\le|\mathcal{G}_0|=\mathrm{D}(\mathcal{A})$ , so $|\mathcal{G}|=\mathrm{D}(G)$ .

Convex shadows and dual convex shadows are maximal subfamilies satisfying the appropriate properties. The similar operations that produce superfamilies instead of subfamilies are called hulls. We shall utilize these latter concepts in later sections.

Definition 27. Let $\mathcal{A}$ be a nonempty family of sets. The convex hull of $\mathcal{A}$ is

\[ \mathcal{H}(\mathcal{A})=\bigcup_{A,A'\in\mathcal{A}}[A,A'],\]

the dominated (convex) hull of $\mathcal{A}$ is

\[ \mathcal{H}_*(\mathcal{A})=\bigcup_{A\in\mathcal{A}}\left[A,\bigcup\mathcal{A}\right],\]

and the supported (convex) hull is

\[ \mathcal{H}^*(\mathcal{A})=\bigcup_{A\in\mathcal{A}}\left[\bigcap\mathcal{A},A\right].\]

We set also $\mathcal{H}(\emptyset)=\emptyset$ .

If the family of sets is finite, we may drop the braces from the notation in the customary manner, writing $\mathcal{H}_*(A_0,\ldots,A_{k-1})$ instead of $\mathcal{H}_*(\{A_0,\ldots,A_{k-1}\})$ , or $\mathcal{H}^*(A_0,\ldots,A_{k-1})$ instead of $\mathcal{H}_*(\{A_0,\ldots,A_{k-1}\})$ . Note the special cases $\mathcal{H}_*(A,B)=[A,A\cup B]\cup[B,A\cup B]$ and $\mathcal{H}^*(A,B)=[A\cap B,A]\cup[A\cap B,B]$ .

We omit the proof of the following lemma, as it is straightforward.

Note that there is no unique least dominated, or supported, convex family containing the empty family (all the singletons do).

3.2 Dimensions of particular families

In this subsection, we calculate the dimensions of some concrete families of sets that are relevant to team semantics but certainly are familiar from other contexts, too. These calculations will be the basis of our results in the next section.

For nonempty finite base sets X and Y, here is a list of families that we consider:

\begin{align*}\mathcal{F} &= \{ f\subseteq X\times Y \mid f\text{ is a mapping }\}, \\\mathcal{X} &=\{ R\subseteq X\times X \mid \mathrm{dom}(R)\cap\mathrm{rg}(R)=\emptyset \}\\\mathcal{I}_{\subseteq} &=\{ R\subseteq X\times X \mid \mathrm{dom}(R)\subseteq \mathrm{rg}(R) \}, \\\mathcal{Y} &=\{ R\subseteq X\times Y \mid {\textit{R}} \, \text{is anonymous} \,\\\mathcal{I}_{\perp} &=\{ A\times B \mid A\subseteq X,\,B\subseteq Y \},\end{align*}

where we call a relation $R\subseteq X\times Y$ anonymous if for all $x\in\mathrm{dom}(R)$ there exist distinct $y,y'\in Y$ with $(x,y),(x,y')\in R$ .

We calculate the dimensions of these families with the aid of shadows and critical sets. The families $\mathcal{F}$ and $\mathcal{X}$ are the easiest cases, as they are downward closed. We handle each of the other families in separate lemmas of their own.

1. (a) If $S\subseteq R$ , then

   \[ [S,R] \subseteq \mathcal{I}_{\subseteq} \text{ if and only if } \mathrm{dom}(R\smallsetminus\mathrm{id}_X)\subseteq\mathrm{rg}(S).\]

2. (b) We have

   \[ \partial_R(\mathcal{I}_{\subseteq})=\{ T\in\mathcal{I}_{\subseteq} \mid T\subseteq R,\,A\subseteq\mathrm{rg}(T)\}\]
   where $A=\mathrm{dom}(R\smallsetminus\mathrm{id}_X)$ .

3. (c) For $A\subseteq X$ , put $R_A=(A\times X)\cup\mathrm{id}_X$ . Then we have that $R_A\in\mathcal{I}_{\subseteq}$ and

   \[ \partial_{R_A}(\mathcal{I}_{\subseteq}) = \{ T\in\mathcal{I}_{\subseteq} \mid \mathrm{dom}(T\smallsetminus\mathrm{id}_X)\subseteq A\subseteq\mathrm{rg}(T) \}.\]

4. (d) We have $\mathrm{Crit}(\mathcal{I}_{\subseteq})= \{ R_A \mid A\subseteq X\}$ .

5. (e) $\mathrm{Crit}(\mathcal{I}_{\subseteq})\smallsetminus\{R_{\{a\}} \mid a\in X \}$ is a family of smallest size that dominates $\mathcal{I}_{\subseteq}$ .

6. (f) Denote $B=\mathrm{rg}(R)$ . Then

   \[ \partial^R(\mathcal{I}_{\subseteq}) =\{ T\in\mathcal{I}_{\subseteq} \mid R\subseteq T,\,\mathrm{dom}(T\smallsetminus\mathrm{id}_X)\subseteq B \} =[R,R_B].\]

7. (g) $\mathrm{Crit}^{\mathrm{d}}(\mathcal{I}_{\subseteq})=\{ R\in\mathcal{I}_{\subseteq} \mid R^{-1}\text{ is a mapping}\}$ .

8. (h) $\mathrm{Crit}^{\mathrm{d}}(\mathcal{I}_{\subseteq})\smallsetminus\{{\{(a,a)\}} \mid a\in X \}$ is the smallest family that supports $\mathcal{I}_{\subseteq}$ .

1. (a) If $|A|,|B|\ge 2$ , we have $\partial_{A\times B}(\mathcal{I}_{\perp})=\partial^{A\times B}(\mathcal{I}_{\perp})=\{A\times B\}$ .

2. (b) If $|A|\le 1$ or $|B|\le 1$ , then $\partial_{A\times B}(\mathcal{I}_{\perp})=\mathcal{P}(A\times B)$ .

3. (c) If $|A|=1$ and $|B|\ge 2$ , then

   \[ \partial^{A\times B}(\mathcal{I}_{\perp})=\{ A\times D \mid B\subseteq D\subseteq Y \}.\]
   Similarly, $|A|\ge 2$ and $|B|=1$ implies $\partial^{A\times B}(\mathcal{I}_{\perp})=\{ C\times B \mid A\subseteq C\subseteq X \}$ .

4. (d) If $|A|=|B|=1$ , then $\partial^{A\times B}(\mathcal{I}_{\perp})$ consists of set of the form $A\times D$ and $C\times B$ with $A\subseteq C\subseteq X$ and $B\subseteq D\subseteq Y$ .

5. (e) $\partial^\emptyset(\mathcal{I}_{\perp})$ consists of all the sets $C\times D$ where $C\subseteq X$ , $D\subseteq Y$ and $|C|\le 1$ or $|D|\le 1$ .

6. (f) The critical and dual critical families of $\mathcal{I}_{\perp}$ are

   \begin{align*} \mathrm{Crit}(\mathcal{I}_{\perp}) =&\{A\times B\subseteq X\times Y \mid |A|\ge 2,|B|\ge 2\} \\ &\cup \{ \{a\}\times Y \mid a\in X \}\\ &\cup \{ X\times \{b\} \mid b\in Y \}. \\ \mathrm{Crit}^{\mathrm{d}}(\mathcal{I}_{\perp})=&\{A\times B\subseteq X\times Y \mid |A|\ge 2,|B|\ge 2\} \cup \{\emptyset\}.\end{align*}

7. (g) For each $R\in\mathcal{I}_{\perp}$ , the shadow $\partial_R(\mathcal{I}_\perp)$ is an interval.

Theorem 32. Let X and Y be finite base sets with $\ell=|X|\ge 2$ and $n=|Y|\ge 2$ . Then:

\begin{align*}&\mathrm{D}(\mathcal{F})=n^\ell, && \mathrm{D}^{\mathrm{d}}(\mathcal{F})=1,&& \mathrm{CD}(\mathcal{F})=\mathrm{D}(\mathcal{F}), \\&\mathrm{D}(\mathcal{X})=2^\ell-2, && \mathrm{D}^{\mathrm{d}}(\mathcal{X})=1, && \mathrm{CD}(\mathcal{X})=\mathrm{D}(\mathcal{X}), \\&\mathrm{D}(\mathcal{I}_{\subseteq})=2^\ell-\ell, && \mathrm{D}^{\mathrm{d}}(\mathcal{I}_{\subseteq})=1+\sum^\ell_{k=2}\binom{\ell}{k}k^k, && \mathrm{CD}(\mathcal{I}_{\subseteq})=\mathrm{D}^{\mathrm{d}}(\mathcal{I}_{\subseteq}), \\&\mathrm{D}(\mathcal{Y})=2^\ell, &&\mathrm{D}^{\mathrm{d}}(\mathcal{Y})=\sum^\ell_{k=0}\binom{\ell}{k}\binom{n}{2}^k , && \mathrm{CD}(\mathcal{Y})=\mathrm{D}^{\mathrm{d}}(\mathcal{Y}).\\ &\mathrm{D}(\mathcal{I}_{\perp})= \scriptstyle (2^\ell-\ell-1)(2^n-n-1)+\ell+n, && \mathrm{D}^{\mathrm{d}}(\mathcal{I}_{\perp})= \scriptstyle (2^\ell-\ell-1)(2^n-n-1)+1, && \mathrm{CD}(\mathcal{I}_{\perp})=\mathrm{D}(\mathcal{I}_{\perp}),\end{align*}

The family $\mathcal{X}$ is obviously also downward closed, so we have $\mathrm{D}^{\mathrm{d}}(\mathcal{X})=1$ and $\mathrm{CD}(\mathcal{X})=\mathrm{D}(\mathcal{X})$ in this case, too. It is easy to see that the maximal set in $\mathcal{X}$ are of form $A\times B$ where $\{A,B\}$ is a partition of the set X. (In contrast, $\emptyset=\emptyset\times X=X\times\emptyset\in\mathcal{X}$ is not maximal, as $\{(a,b)\}\in\mathcal{X}$ for any distinct $a,b\in X$ .) The number of possible A’s, i.e., nonempty proper subsets of X is indeed $2^n-2$ .

In all the other cases, we have already determined dominating and supporting families of the smallest sizes in the previous lemmas, so the rest is simply combinatorial counting. By Lemma 29, items d and e,

\[ \mathrm{D}(\mathcal{I}_{\subseteq})=|\mathrm{Crit}(\mathcal{I}_{\subseteq})\smallsetminus\{R_{\{a\}} \mid a\in X \}| =|\mathcal{P}(X)|-|X|=2^\ell-\ell.\]

By item f, dual shadows are always intervals, so $\mathrm{CD}(\mathcal{I}_{\subseteq})=\mathrm{D}^{\mathrm{d}}(\mathcal{I}_{\subseteq})$ . A combinatorial calculation related to items g and h gives the formula for $\mathrm{D}^{\mathrm{d}}(\mathcal{I}_{\subseteq})$ .

By Lemma 30 item b, $\{ A\times Y \mid A\subseteq X\}$ is the unique smallest subfamily dominating $\mathcal{Y}$ , and obviously it is equipotent with $\mathcal{P}(X)$ , so $\mathrm{D}(\mathcal{Y})=2^\ell$ . By item c, the set in the smallest family supporting $\mathcal{Y}$ are of the form $f\cup g$ where $f,g\colon A\to Y$ with $A\subseteq X$ and for everu $x\in A$ we have $f(x)\neq g(x)$ . If the size $k=|A|$ is known, there are $\binom{\ell}{k}$ ways to choose A, and given that A and $x\in A$ , there are $\binom{n}{2}$ ways to choose the pair $\{f(x),g(x)\}$ (this is all that matters). So for every A with size k, there are $\binom{n}{2}^k$ ways to choose $f\cup g$ . Summing this up for different sizes of A, we get the display formula. $\mathrm{CD}(\mathcal{Y})=\mathrm{D}(\mathcal{Y})$ , as dual shadows are intervals.

By Lemma 31 item g, shadows are intervals, so $\mathrm{CD}(\mathcal{I}_{\perp})=\mathrm{D}(\mathcal{I}_{\perp})$ . Calculating the sizes of critical and dual critical subfamilies (determined in item f) with get the corresponding formulas for upper dimension and dual upper dimension.

There remains one interesting team-semantics-related class of families of sets we need to investigate. Let X, Y and Z be nonempty finite sets. We shall consider

$$\mathcal{I}_{\perp,\bullet}=\bigl\{\, \bigcup_{c\in Z} (A_c\times B_c\times\{c\}) \;\bigm\vert\; \forall c\in Z\, (A_c\subseteq X,\,B_c\subseteq Y) \,\bigr\}.$$

This time we will content ourselves on evaluating only lower and upper bounds for this family instead of the exact values. However, this is done within a more general framework which can be applied to other similar cases.

Definition 33. Families of sets $\mathcal{A}$ and $\mathcal{B}$ are called similar if there exists a bijection $f\colon X\to Y$ such that $\mathcal{A}\subseteq\mathcal{P}(X)$ and

$$ \mathcal{B} = \{ f[A] \mid A\in\mathcal{A} \}.$$

It is then straightforward to show that:

Definition 35. Let $(\mathcal{A}_i)_{i\in I}$ be an indexed family of families of sets. Then its general tensor disjunction is the family

$$\bigvee\limits_{i\in I}\mathcal{A}_i=\bigl\{\, \bigcup_{i\in I}A_i \;\bigm\vert\; \forall i\in I\,(A_i\in\mathcal{A}) \,\bigr\}.$$

Note that if the base sets of the families $\mathcal{A}_i\subseteq\mathcal{P}(X_i)$ are all disjoint, i.e., if $(X_i)_{i\in I}$ is a disjoint family, then there is a natural bijection $A\mapsto (A\cap X_i)_{i\in I}$ between $\bigvee\limits_{i\in I}\mathcal{A}_i$ and $\prod_{i\in I}\mathcal{A}_i$ . In the other end of the spectrum, if $\mathcal{A}$ is closed under unions, then $\bigvee\limits_{i\in I}\mathcal{A}=\mathcal{A}$ .

Proposition 36. Let $(\mathcal{A}_i)_{i\in I}$ be an indexed family of families of sets. Then

$$ \mathrm{CD}\Bigl(\bigvee\limits_{i\in I}\mathcal{A}_i\Bigr)\le\prod_{i\in I}\mathrm{CD}(A_i).$$

Proof. Pick, for each $i\in I$ , an index set $J_i$ and intervals $\mathcal{L}_{i,j}$ , $j\in J_i$ with $|J_i|=\mathrm{CD}(\mathcal{A}_i)$ and $\bigcup_{j\in J_i}\mathcal{L}_{i,j}=\mathcal{A}_i$ . Write $\mathcal{L}_{i,j}=[B_{i,j},C_{i,j}]$ . For each $f\in J=\prod_{i\in I}J_i$ , consider the interval $\mathcal{L}_f=[B_f,C_f]$ where

$$ B_f = \bigcup_{i\in I} B_{i,f(i)} \text{ and } C_f = \bigcup_{i\in I} C_{i,f(i)}.$$

Then clearly $|J|=\prod_{i\in I}|J_i|=\prod_{i\in I}\mathrm{CD}(\mathcal{A}_i)$ and $\bigvee\limits_{i\in I}\mathcal{A}_i=\bigcup_{\in I}\mathcal{L}_f$ .

As a corollary, we get the desired estimates.

Proposition 37. Let X, Y, and Z be finite base sets with $\ell=|X|\ge 2$ , $n=|Y|\ge 2$ and $s=|Z|\ge 1$ . Then

\begin{align*} (2^\ell-\ell-1)(2^n-n-1)+1 &\le\min\{\mathrm{D}(\mathcal{I}_{\perp,\bullet}),\mathrm{D}^{\mathrm{d}}(\mathcal{I}_{\perp,\bullet})\} \\ &\le\mathrm{CD}(\mathcal{I}_{\perp,\bullet}) \le ((2^\ell-\ell-1)(2^n-n-1)+\ell+n)^s.\end{align*}

Proof. For each $c\in Z$ , put

$$ \mathcal{J}_c=\mathcal{I}_{\perp,\bullet}\cap\mathcal{P}(X\times Y\times\{c\}) =\bigl\{\, A_c\times B_c\times\{c\} \;\bigm\vert\; A_c\subseteq X,\,B_c\subseteq Y) \,\bigr\}.$$

Clearly, $\mathcal{J}_c$ is similar to $\mathcal{I}_{\perp}$ , so by Theorem 32 and Proposition 34, case a, we have

$$(2^\ell-\ell-1)(2^n-n-1)+1 = \min\{\mathrm{D}(\mathcal{I}_{\perp}),\mathrm{D}^{\mathrm{d}}(\mathcal{I}_{\perp})\}=\min\{\mathrm{D}(\mathcal{J}_c),\mathrm{D}^{\mathrm{d}}(\mathcal{J}_c)\}.$$

Since $\mathcal{J}_c=\mathcal{I}_{\perp,\bullet}\cap\mathcal{P}(X\times Y\times\{c\})$ , Propositions 34 and 5, further imply that

$$\min\{\mathrm{D}(\mathcal{J}_c),\mathrm{D}^{\mathrm{d}}(\mathcal{J}_c)\}\le \min\{\mathrm{D}(\mathcal{I}_{\perp,\bullet}),\mathrm{D}^{\mathrm{d}}(\mathcal{I}_{\perp,\bullet})\}\le \mathrm{CD}(\mathcal{I}_{\perp,\bullet}).$$

It easy to see that $\bigvee\limits_{c\in Z}\mathcal{J}_c=\mathcal{I}_{\perp,\bullet}$ , so now when we combine the results of Theorem 32 and Proposition 36, we get the inequality

$$ \mathrm{CD}(\mathcal{I}_{\perp,\bullet})=\mathrm{CD}(\bigvee\limits_{c\in Z}\mathcal{J}_c) \le\prod_{c\in Z} \mathrm{CD}(\mathcal{J}_c)=((2^\ell-\ell-1)(2^n-n-1)+\ell+n)^s.$$

In our logical application, when we apply Theorem 32 and the previous proposition to determine the dimension functions of the corresponding atomic formulas, we shall face a technical complication: The dimension functions of formulas depend on the set of variables that are interpreted in the teams of assignments. The previous result corresponds exactly to the situation where only the variables occurring in the atomic formula are interpreted, but there might be dummy variables to be considered. We shall need the next proposition to overcome this difficulty: the effect of dummy variables is not critical. In this intended application, the surjective function in the proposition will be the restriction of the assignment to the occurring variables.

Proposition 38. Let $p\colon X\to Y$ be a surjection. Recall that the inverse projection is the operation $\Delta_{p^{-1}}\colon\mathcal{P}(\mathcal{P}(Y))\to\mathcal{P}(\mathcal{P}(X))$ ,

\[ \Delta_{p^{-1}}(\mathcal{Y})=\{A\in\mathcal{P}(X)\mid p[A]\in\mathcal{Y}\}.\]

Let $\mathcal{B}\subseteq\mathcal{P}(Y)$ and $\mathcal{A}=\Delta_{p^{-1}}(\mathcal{B})$ . Suppose that $s,r\in\mathbb{N}$ are constants such that for each $y\in Y$ , we have $|p^{-1}\{y\}|\le s$ , and for each $B\in\mathcal{B}$ , we have $|B|\le r$ .

Then

\[ \mathrm{D}(\mathcal{A})=\mathrm{D}(\mathcal{B}),\; \mathrm{D}^{\mathrm{d}}(\mathcal{A})\le s^r\mathrm{D}^{\mathrm{d}}(\mathcal{B}) \text{ and } \mathrm{CD}(\mathcal{A})\le s^r\mathrm{CD}(\mathcal{B}).\]

The cases of dual upper dimension and cylindrical dimension are slightly more involved. The point is that even if L were minimal in $\mathcal{B}$ , the inverse image $p^{-1}[L]$ is not in general minimal in $\mathcal{A}$ . Call A a selective inverse image of B, if $p[A]=B$ and $p\restriction A$ is an injection. Note that A is a selective inverse image of B if and only if A is a minimal set with $p[A]=B$ . Choose now $\mathcal{K}$ that supports $\mathcal{B}$ and $\mathrm{D}^{\mathrm{d}}(\mathcal{B})=|\mathcal{K}|$ . Consider the family $\mathcal{K}'$ of all sets $A\in\mathcal{A}$ such that A is selective inverse image of some $B\in\mathcal{K}$ . Clearly, $\mathcal{K}'$ supports $\mathcal{A}$ . Each $B\in\mathcal{K}$ has at most $s^{|B|}\le s^r$ selective inverse images, as for every $b\in B$ , we have $|p^{-1}\{b\}|\le s$ . Hence, $\mathrm{D}^{\mathrm{d}}(\mathcal{A})\le |\mathcal{K}'|\le s^r\mathrm{D}(\mathcal{B})$ . In the case of the cylindrical dimension, the proof is similar.

3.3 Dimensions of definable families

We have defined three dimension concepts for totally arbitrary families of sets on a finite base set. We now apply these concepts to definable families of subsets of a Cartesian product $M^m$ . In particular, we are interested in calculating the three dimensions for families of the form $\left\Vert \phi \right\Vert^{{M,\vec x}}$ . We rely totally on the computations performed in Section 3.2.

As alluded to in Section 2.4, team semantics permits the extension of first order logic by a number of new atoms (see Definition 20) leading to dependence logic (Väänänen Reference Väänänen2007), inclusion logic (Galliani Reference Galliani2012), exclusion logic (Galliani Reference Galliani2012), independence logic (Galliani Reference Galliani2012), and anonymity logic (Väänänen Reference Väänänen2023). In order to estimate the dimensions of families definable in these logics, we first note the following consequence of Theorem 32:

The following theorem, indicating the dimensions of the various atoms, is summarized also in Tables 2 and 3, where $f(n)\sim g(n)$ means, keeping m and k constant, $\lim_n f(n)/g(n)=1$ and $f(n)\in{\sim}[g(n),h(n)]$ means, keeping m, k, and s constant, asymptotically $g(n)\le f(n)\le h(n)$ , or more exactly $\liminf_n f(n)/g(n)\ge 1$ and $\liminf_n h(n)/f(n)\ge 1$ .

Table 2. Dimensions of atoms

Table 3. Approximate dimensions of independence atoms

1. (a) Let $\alpha$ be the dependence atom $\,=(\vec{x},y)$ , where $\mathrm{len}(\vec{x})=m$ , and let $\vec{z}=\vec{x} y$ . Then $\mathrm{D}(\!\left\Vert \alpha \right\Vert^{{M,\vec{z}}})=\mathrm{CD}(\!\left\Vert \alpha \right\Vert^{{M,\vec{z}}})=n^{n^m}$ and $\mathrm{D}^{\mathrm{d}}(\!\left\Vert \alpha \right\Vert^{{M,\vec{z}}})=1$ .

2. (b) Let $\alpha$ be the exclusion atom $\vec{x}\mid\vec{y}$ , where $\mathrm{len}(\vec{x})=\mathrm{len}(\vec{y})=m$ , and let $\vec{z}=\vec{x} \vec{y}$ . Then $\mathrm{D}(\!\left\Vert \alpha \right\Vert^{{M,\vec{z}}})=\mathrm{CD}(\!\left\Vert \alpha \right\Vert^{{M,\vec{z}}})=2^{n^m}-2$ and $\mathrm{D}^{\mathrm{d}}(\!\left\Vert \alpha \right\Vert^{{M,\vec{z}}})=1$ .

3. (c) Let $\alpha$ be the inclusion atom $\vec{x}\subseteq\vec{y}$ , where $\mathrm{len}(\vec{x})=\mathrm{len}(\vec{y})=m$ , and let $\vec{z}=\vec{x} \vec{y}$ . Then $\mathrm{D}(\!\left\Vert \alpha \right\Vert^{{M,\vec{z}}})=2^{n^m}-n^m$ and $\mathrm{D}^{\mathrm{d}}(\!\left\Vert \alpha \right\Vert^{{M,\vec{z}}})=\mathrm{CD}(\!\left\Vert \alpha \right\Vert^{{M,\vec{z}}}) =1+\sum^{n^m}_{k=2}\binom{n^m}{k}k^k$ .

4. (d) Let $\alpha$ be the anonymity atom $\vec{x}\mathrel{\Upsilon} y$ , where $\mathrm{len}(\vec{x})=m$ . Then $\mathrm{D}(\!\left\Vert \alpha \right\Vert^{{M,\vec{z}}})=\mathrm{CD}(\!\left\Vert \alpha \right\Vert^{{M,\vec{z}}})=2^{n^m}$ and $\mathrm{D}^{\mathrm{d}}(\!\left\Vert \alpha \right\Vert^{{M,\vec{z}}}) =\sum^{n^m}_{k=0}\binom{n^m}{k}\binom{n}{2}^k $ .

5. (e) Let $\alpha$ be the pure independence atom $\vec{x}\perp\vec{y}$ , where $\mathrm{len}(\vec{x})=m$ and $\mathrm{len}(\vec{y})=k$ , and let $\vec{z}=\vec{x} \vec{y}$ . Then $\mathrm{D}(\!\left\Vert \alpha \right\Vert^{{M,\vec{z}}})=\mathrm{CD}(\!\left\Vert \alpha \right\Vert^{{M,\vec{z}}})= (2^{n^m}-n^m-1)(2^{n^k}-n^k-1)+n^m+n^k$ and $\mathrm{D}^{\mathrm{d}}(\!\left\Vert \alpha \right\Vert^{{M,\vec{z}}})=(2^{n^m}-n^m-1)(2^{n^k}-n^k-1)+1$ .

6. (f) Let $\alpha$ be the conditional independence atom $ \vec{x}\perp_{\vec{u}} \vec{y}$ , where $\mathrm{len}(\vec{x})=m$ , $\mathrm{len}(\vec{y})=k$ , $\mathrm{len}(\vec{u})=s$ , and let $\vec{z}=\vec{x} \vec{u}\vec{y}$ . Then $(2^{n^m}-n^m-1)(2^{n^k}-n^k-1)+n^m+n^k\le\mathrm{D}(\!\left\Vert \alpha \right\Vert^{{M,\vec{z}}})\le\mathrm{CD}(\!\left\Vert \alpha \right\Vert^{{M,\vec{z}}})\le ((2^{n^m}-n^m-1)(2^{n^k}-n^k-1)+n^m+n^k)^{n^s}$ and $(2^{n^m}-n^m-1)(2^{n^k}-n^k-1)+1\le\mathrm{D}^{\mathrm{d}}(\!\left\Vert \alpha \right\Vert^{{M,\vec{z}}})\le((2^{n^m}-n^m-1)(2^{n^k}-n^k-1)+1)^{n^s}$ .

We may notice that, keeping m and k fixed, the upper and the cylindrical dimension of the dependence atom grows faster than the respective dimensions of the other atoms, except the relativized independence atom. Varying m and k we obtain a host of comparisons between dimensions of the atoms. These will become relevant below when we combine the atoms with logical operations.

Let us now define the important concept of locality:

Definition 41. A formula $\phi$ of any logic, with the free variables $\vec{x}$ , is said to be local if for all models M and teams T with $\vec{x}\subseteq\mathrm{dom}(T)$ we have

$$M\models_T\phi\ \Leftrightarrow\ M\models_{T\restriction\vec{x}}\phi.$$

All the atoms of Definition 20 are local and the logical operations of Definition 19, as well as all Lindström quantifiers (see Definition 22), preserve locality.

The semantics defined in Definition 58 has a variant called strict semantics (Galliani Reference Galliani2012). In strict semantics, we define the meaning of tensor disjunction by $M\models_T\phi\vee\psi$ if and only if $T=Y\cup Z$ such that $M\models_Y\phi$ , $M\models_Z\psi$ , and $Y\cap Z=\emptyset$ . The meaning of existential quantifier in strict semantics is $M\models_T\exists x\phi$ if and only if there is $F:T\to M$ such that $M\models_{T[F/x]}\phi$ . For dependence logic this change of semantics has no effect because of downward closure. However, inclusion logic with strict semantics is not local. We will not consider strict semantics in detail in this paper.

It is also important to notice that above we have calculated the dimensions of the families of teams related to certain atomic formulas relative to the variables occurring in the formulas. In general, we need to consider atomic formulas – and, furthermore, also other formulas – as subformulas of larger formulas, so we need to attach also other variables in the context. Usually, the following estimates are good enough for our purposes.

Proposition 42. Let M be a structure and $\phi$ a local formula with a common vocabulary, $\vec{y}$ the sequence of variables occurring in $\phi$ and $\vec{x}$ a finite sequence of variables extending $\vec{y}$ . Suppose M has size n, r is constant such that for every team T in variables $\vec{y}$ we have that $M\models_T\phi$ implies $|T|\le r$ , and $t=\mathrm{len}(\vec{x})-\mathrm{len}(\vec{y})$ . Then

\[ \mathrm{D}(\!\left\Vert \phi \right\Vert^{M,\vec{x}})=\mathrm{D}(\!\left\Vert \phi \right\Vert^{M,\vec{y}}),\, \mathrm{D}^{\mathrm{d}}(\!\left\Vert \phi \right\Vert^{M,\vec{x}})\le n^{tr}\mathrm{D}(\!\left\Vert \phi \right\Vert^{M,\vec{y}})\text{ and } \mathrm{CD}(\!\left\Vert \phi \right\Vert^{M,\vec{x}})\le n^{tr}\mathrm{CD}(\!\left\Vert \phi \right\Vert^{M,\vec{y}}).\]

4.1 Growth classes

As we apply our dimensional techniques to definability problems on the class of finite structures, we are constantly facing the dilemma that it is usually not sufficient to consider a single structure and families of sets arising from team semantics in that structure, but we rather have to consider the class of all appropriate finite structures. That means that we have to accept the possibility that the size of the base set may change, which calls for a dynamical way to handle matters. To that end, we consider growth classes.

In the definitions that follow, we generalize the arithmetical notation in a pointwise fashion, e.g., for functions $f,g\colon \mathbb{N}\to\mathbb{N}$ we set $f+g$ to be the function $\mathbb{N}\to\mathbb{N}$ such that $(f+g)(n)=f(n)+g(n)$ , for $n\in\mathbb{N}$ , and $f\le g$ means that $f(n)\le g(n)$ holds for every $n\in\mathbb{N}$ .

1. (a) If $g\in\mathbb{O}$ and $f\le g$ , then $f\in\mathbb{O}$ .

2. (b) If $f,g\in\mathbb{O}$ , then $f+g\in\mathbb{O}$ and $fg\in\mathbb{O}$ .

The point of growth classes is that they are closed under natural operators arising from logical operations. As it turns out, if we figure out the growth classes of some atoms, anything definable from those atoms by means of most of the logical operations we deal with will be in the same growth class. Thus, the growth classes represent important dividing lines.

We are interested in the following particular classes:

Definition 44. For $k\in\mathbb{N}$ , we use $\mathbb{E}_k$ to denote the class of functions $f\colon\mathbb{N}\to\mathbb{N}$ such that there exists a polynomial $p\colon\mathbb{N}\to\mathbb{N}$ of degree k and with coefficients in $\mathbb{N}$ such that for all $n\in\mathbb{N}$

$$f(n)\le 2^{p(n)}.$$

We use $\mathbb{F}_k$ to denote the class of functions $f\colon\mathbb{N}\to\mathbb{N}$ such that there exists a polynomial $p\colon\mathbb{N}\to\mathbb{N}$ of degree k and with coefficients in $\mathbb{N}$ such that for every $n\in\mathbb{N}\smallsetminus\{0,1\}$ we have that

\[ f(n)\le n^{p(n)}.\]

Note that $\mathbb{E}_0$ is the class of bounded functions and $\mathbb{F}_0$ the class of functions of polynomial growth. The following is immediate:

Proposition 45. Each $\mathbb{E}_k$ and $\mathbb{F}_k$ (for $k\in\mathbb{N}$ ) is a growth class. Furthermore, we have that

\[ \mathbb{E}_0\subsetneq\mathbb{F}_0\subsetneq\mathbb{E}_1\subsetneq\mathbb{F}_1\subsetneq\cdots\subsetneq\mathbb{E}_k\subsetneq\mathbb{F}_k\cdot\]

Definition 46. To each formula $\phi$ with free variables in $\vec{x}$ allowing a team-semantical interpretation we relate the following dimension functions:

The following examples follow from Theorem 40:

For a summary of the above example, see Table 4. Note that the last row of the table indicates an upper bound only.

Table 4. Growth classes of families arising from atoms

In the example above, the growth classes of the dimension functions of some atoms were determined relative to variables occurring in the formula. In the general case, it is conceivable that the dimension functions are not preserved in the same classes. We need the following concept to show that the situation is, by and large, conserved.

For a local formula with k free variables the degree is always at most k.