Description Complexity of Unary Structures in First-Order Logic with Links to Entropy

This paper investigates the resources needed to define finite models with a unary relational vocabulary. While unary models are very simple, it turns out that proving limits on the formula sizes for defining them is non-trivial. Furthermore, unary models are important as they give a direct relational representation of Boolean data sets, consisting simply of data points and their properties – thereby providing one of the simplest data representation schemes available. In practice all tabular data can be discretized and modeled via a Boolean data set. This relates to applications in, e.g., explainability and compression.

Given a logic $ℒ$ and a class $ℳ$ of models, the description complexity $C(𝔐)$ of a model $𝔐$ is the minimum length of a formula $\phi \in ℒ$ that defines $𝔐$ with respect to $ℳ$. In the main scenario of this paper, $ℳ$ is the class of models with the same domain of a finite size $n$ and with the same unary vocabulary $\tau$. We mostly study the setting via first-order logic FO. However, as description complexity links to the themes of compressibility and compression, we also investigate the restricted languages ${\mathrm{FO}}_d$ where the quantifier rank of every formula is limited to a positive integer $d$. This will lead to dramatically shorter description lengths (cf. Section 3) via a natural lossy compression phenomenon.

We also investigate how the Shannon entropies of unary structures are linked to their description complexities, the general trend being that higher entropy relates to higher description complexity. Shannon entropy is a well-known measure of intrinsic complexity, or randomness, from information theory. The Shannon entropy of a probability distribution $\mathbb{P}:X\to [0,1]$ over a finite set $X$ is given by $-{\sum }_{x\in X}\mathbb{P}(x){\log }_2\mathbb{P}(x).$ A relational structure $𝔐$ of size $n$ over a unary vocabulary $\tau$ naturally defines a probability distribution over its domain. Indeed, let $T$ be the set of unary quantifier-free types over $\tau$, i.e., subsets of $\tau$. A point $a$ of a model $𝔐$ realizes a type $\pi \subseteq \tau$ if $\pi$ is the set of relation symbols corresponding to exactly those unary relations that contain the point $a$. Now a $\tau$-model $𝔐$ of size $n$ naturally defines the probability distribution $\mathbb{P}:T\to [0,1]$ such that $\mathbb{P}(\pi )=\frac{|\pi |}{n}$, where $|\pi |$ is the number of points of $𝔐$ realizing the type $\pi$. The Shannon entropy of $𝔐$ is then naturally defined to be equal to the Shannon entropy of the distribution $\mathbb{P}:T\to [0,1]$.

While the Shannon entropy of $𝔐$ gives an intrinsic measure of complexity (or randomness) of $𝔐$, another entropy measure may perhaps be easier to grasp intuitively. Boltzmann entropy has its origins in statistical mechanics, and it was originally defined as $k\ln \mathrm{\Omega }$, where $k$ is the Boltzmann constant and $\mathrm{\Omega }$ the number of microstates of a system. In our setting, we follow [14] and define Boltzmann entropy of a model class $𝒜$ as ${\log }_2|𝒜|$, thus dropping the Boltzmann constant $k$, using binary logarithms and associating models with microstates. Now, it is natural to then define the Boltzmann entropy of a model $𝔐$ as ${\log }_2|ℳ|$, where $ℳ$ is the isomorphism class of $𝔐$ (recall here that in our setting, all models have the same domain of size $n$, so $ℳ$ is finite). The reason why the Boltzmann entropy of $𝔐$ is a reasonable measure of intrinsic complexity of $𝔐$ is now easy to motivate. Firstly, consider a $\tau$-model ${𝔐}_0$ of size $n$ where each $P\in \tau$ is interpreted as the empty relation. This is a very simple model whose isomorphism class has size $1$ and the Boltzmann entropy of ${𝔐}_0$ is thus very low: ${\log }_{2}1=0$. On the other hand, models with the predicates in $\tau$ distributed in more disordered ways have larger isomorphism classes and thus greater Boltzmann entropies.

Let $\tau =\{P_1,\mathrm{\dots },P_k\}$ be a monadic vocabulary and let $\mathrm{𝑉𝑎𝑟}=\{x_1,x_2,\mathrm{\dots }\}$ be a countably infinite set of variables. The syntax of first-order logic $\mathrm{FO}[\tau ]$ is generated by the grammar: $\phi ::=x=y\mid P(x)\mid \neg \phi \mid \phi \vee \phi \mid \phi \wedge \phi \mid \exists x\phi \mid \forall x\phi ,$ where $x,y\in \mathrm{𝑉𝑎𝑟}$ and $P\in \tau$. The quantifier rank of a formula $\phi \in \mathrm{FO}[\tau ]$ is the maximum number of nested quantifiers in the formula. We denote by ${\mathrm{FO}}_d[\tau ]$ the fragment of $\mathrm{FO}[\tau ]$ that only includes the formulas with quantifier rank at most $d$. A formula $\phi \in \mathrm{FO}[\tau ]$ is in negation normal form if negations are only applied to atomic formulas $x=y$ or $P(x)$. We assume all formulas are in negation normal form and treat the notation $\neg \phi$ as shorthand for the negation normal form formula obtained from $\phi$ by pushing the negation to the level of atomic formulas.

The size of a formula $\phi \in \mathrm{FO}[\tau ]$ is defined as the number of atomic formulas, conjunctions, disjunctions and quantifiers in $\phi$. Note that negations do not contribute to the size of $\phi$. This choice together with using negation normal form means that positive and negative atomic information is treated as equal in terms of formula size. In line with this thinking, we will refer also to $x\ne y$ and $\neg P(x)$ as atomic formulas in the sequel.

A formula $\phi \in \mathrm{FO}[\tau ]$ is in prenex normal form if it is of the form $Q_1{x}_1\mathrm{\dots }{Q}_m{x}_m\psi ,$ where $Q_i\in \{\exists ,\forall \}$ for $i\in \{1,\mathrm{\dots },m\}$ and $\psi \in \mathrm{FO}[\tau ]$ has no quantifiers. It is well-known that every $\mathrm{FO}$-formula can be transformed into an equivalent formula in prenex normal form which has the same size as the original formula.

A $𝝉$-model is a tuple $𝔐=(M,P_1^{𝔐},\mathrm{\dots },P_k^{𝔐})$, where $M=\{1,\mathrm{\dots },n\}$ and $P_i^{𝔐}\subseteq M$ for $i\in \{1,\mathrm{\dots },k\}$. A model $𝔐$ is a model of size $n$ if $|M|=n$. A partial function $s:\mathrm{𝑉𝑎𝑟}\rightharpoonup M$ is called an interpretation. We also call pairs $(𝔐,s)$ models and identify the pair $(𝔐,\mathrm{\varnothing })$ with the model $𝔐$. The truth relation $(𝔐,s)\models \phi$ is defined in the usual way for $\mathrm{FO}[\tau ]$.

Let $𝔐=(M,P_1^{𝔐},\mathrm{\dots },P_k^{𝔐})$ be a $\tau$-model of size $n$. We say that a formula $\phi \in \mathrm{FO}[\tau ]$ defines $𝔐$ if for all $\tau$-models ${𝔐}^{\prime }$ of size $n$ we have $({𝔐}^{\prime },\mathrm{\varnothing })\models \phi$ iff ${𝔐}^{\prime }$ is isomorphic to $𝔐$. As first-order logic cannot distinguish between isomorphic structures, we can in some sense identify the model $𝔐$ with the class of models isomorphic to $𝔐$. The description complexity $C(𝔐)$ of $𝔐$ is the size of the smallest formula in $\mathrm{FO}[\tau ]$ that defines $𝔐$.

Note that our definition of description complexity concerns separating $𝔐$ only from other models of the same size $n$. Requiring separation from all other models would unduly emphasize the size of the model, making even very simple models have a high description complexity. For example, the model $𝔐=(M,P^{𝔐})$ of size $n$, where $P^{𝔐}=M$, would already require a formula with size in the order of $n$. In our setting, $C(𝔐)=2$, because $𝔐$ is defined by the formula $\forall xP(x)$.

A $\tau$-type $\pi$ is a subset of $\tau$. A point $a\in M$ realizes a $\tau$-type $\pi$ if for all $P\in \tau$ we have $a\in P^{𝔐}$ iff $P\in \pi$. We let ${|\pi |}_{𝔐}$ denote the number of points in $𝔐$ realizing $\pi$. We often omit the subscript when the model is clear from the context. Note that two $\tau$-models $𝔐$ and ${𝔐}^{\prime }$ are isomorphic iff each type is realized in the same number of points in both models.

We also consider more coarse ways to divide models into classes than isomorphism. For each positive integer $d$ we can define an equivalence relation ${\equiv }_d$ over $\tau$-models of size $n$ as follows. Given two $\tau$-models $𝔐$ and ${𝔐}^{\prime }$ of size $n$, we define that $𝔐{\equiv }_d{𝔐}^{\prime }$ iff for each $\tau$-type $\pi$ with , we have that ${|\pi |}_{𝔐}={|\pi |}_{{𝔐}^{\prime }}$. In other words, $𝔐{\equiv }_d{𝔐}^{\prime }$ iff each type that is realized in less than $d$ points in $𝔐$ is realized in the same number of points in both models. It is easy to show that $𝔐{\equiv }_d{𝔐}^{\prime }$ iff they satisfy the same sentences of ${\mathrm{FO}}_d[\tau ]$. The $𝒅$-description complexity $C_d(𝔐)$ of a $\tau$-model $𝔐$ is the size of the smallest ${\mathrm{FO}}_d[\tau ]$-formula that defines the equivalence class of $𝔐$ in ${\equiv }_d$.

To characterize model classes, we use tuples with $t=2^{|\tau |}$ numbers. For an isomorphism class, the tuple is simply $(|{\pi }_1|,\mathrm{\dots },|{\pi }_t|).$ For an equivalence class $ℳ$ of ${\equiv }_d$, we only use numbers up to $d$. For a tuple $\overline{m}=(m_1,\mathrm{\dots },m_t)$, if $m_i=d$, then there are at least $d$ realizing points of type ${\pi }_i$ in models of the class $ℳ$. If , then each model has exactly $m_i$ points realizing the type ${\pi }_i$. The notation ${ℳ}_{\overline{m}}$ refers to classes of ${\equiv }_d$ via these tuples. The tuples that correspond to some class of ${\equiv }_d$ are characterized by the conditions $m_i\le d$ for $i\in \{1,\mathrm{\dots },t\}$, ${\sum }_{i=1}^t{m}_i\le n$ and if , then $m_j=d$ for some $j\in \{1,\mathrm{\dots },t\}$. If ${\sum }_{i=1}^t{m}_i=n$, then ${ℳ}_{\overline{m}}$ is an isomorphism class.

Since $\tau$-types partition the points of a $\tau$-model $𝔐$, we may consider a natural probability distribution over the types in $𝔐$. The probability $p_{\pi }$ of a type $\pi$ is simply $|\pi |/n$, that is, the probability of hitting a point of type $\pi$ when selecting a point from $𝔐$ randomly. The Shannon entropy of $𝔐$ is the quantity $H_S(𝔐):={\sum }_{i=1}^t-p_{{\pi }_i}\log (p_{{\pi }_i})={\sum }_{i=1}^t-\frac{|{\pi }_i|}{n}\log \left(\frac{|{\pi }_i|}{n}\right).$ Here we follow the convention $0\log (0)=0$. Shannon entropy is an information theoretic way of measuring randomness of probability distributions. Uniform distributions have maximal Shannon entropy, as the uncertainty of the outcome of choosing a random point is maximized. Conversely, for a distribution that places all of the probability mass on a single event, Shannon entropy is zero. Hence, a model realizing each type the same number of times (or as close as possible) has maximal Shannon entropy, while for a model that realizes only a single type Shannon entropy is zero.

Another way to define entropy of a model $𝔐$ uses the model class $𝔐$ belongs to. Given an equivalence relation $\equiv$ over models of size $n$ (and thus domain $\{1,\mathrm{\dots },n\}$), the Boltzmann entropy of $𝔐$ with respect to $\equiv$ is $H_B(𝔐):=\log (|ℳ|),$ where $ℳ$ is the equivalence class of $𝔐$. In this paper the equivalence relation $\equiv$ is either isomorphism in the case of full $\mathrm{FO}$ or ${\equiv }_d$ for ${\mathrm{FO}}_d$. For isomorphism, we write $H_B(𝔐)$ and for ${\equiv }_d$ we write $H_B^d(𝔐)$.

Boltzmann entropy originates from statistical mechanics, where it measures the randomness of a macrostate (= a model class) via the number of microstates (= models) that correspond to it. The idea is that a larger macrostate is “more random” (or “less specific”) since it is more likely to be hit by a random selection. We show in Section 6 that $H_S(𝔐)\sim \frac{1}{n}{H}_B(𝔐),$ where $n$ is the size of the domain of $𝔐$. Thus the two notions of entropy are asymptotically equivalent up to normalization. This shows that both entropies indeed measure the randomness of a model from different points of view.

In this section we define arbitrary $\tau$-models via formulas of size linear in the size of the model. Recall that defining a model means separating it from all non-isomorphic models with the same domain size. To see why linear size formulas are quite succinct, note that the following naive formula ${\bigwedge }_{\mathrm{\ell }=1}^{2^{|\tau |}}\exists x_1\mathrm{\dots }\exists x_{|{\pi }_{\mathrm{\ell }}|}\left({\bigwedge }_{i=1}^{|{\pi }_{\mathrm{\ell }}|}{\pi }_{\mathrm{\ell }}(x_i)\wedge {\bigwedge }_{j=i+1}^{|{\pi }_{\mathrm{\ell }}|}{x}_i\ne x_j\right),$ which expresses that for each $1\le \mathrm{\ell }\le 2^{|\tau |}$ the type ${\pi }_{\mathrm{\ell }}$ is realized by at least $|{\pi }_{\mathrm{\ell }}|$ distinct points, is of quadratic size in the size $n$ of the model.

For clean results on formula size, we define a constant $c_{\tau }:=15|\tau |2^{|\tau |}$. Note that we consider $c_{\tau }$ to be constant as it only depends on the size of the alphabet $\tau$, which in our context is constant.

In this section, we show lower bounds that match the upper bounds of Section 3 up to a factor of 2. We use the formula size game for first-order logic defined in [10]. We modify the game slightly to correspond to formulas in prenex normal form as this form does not affect the size of the formula. In addition, we introduce a second resource parameter $q$ that corresponds to the number of quantifiers in the separating formula. The game consists of two phases: a quantifier phase, where only $\exists$-moves and $\forall$-moves can be made by S, and an atomic phase, where only $\vee$-moves, $\wedge$-moves and atomic moves can be made. Before the definition of the game, we define some notation.

Let $𝒜$ be a set of $\tau$-models and let $\phi \in \mathrm{FO}[\tau ]$. We denote $𝒜\models \phi$ to mean $(𝔐,s)\models \phi$ for all $(𝔐,s)\in 𝒜$. Similarly, we denote $𝒜\models \neg \phi$ to mean $(𝔐,s)⊭\phi$ for all $(𝔐,s)\in 𝒜$.

For an interpretation $s$, a point $a\in M$ and a variable $x\in \mathrm{𝑉𝑎𝑟}$, we denote by $s[a/x]$ the interpretation $s^{\prime }$ such that $s^{\prime }(x)=a$ and $s^{\prime }(y)=s(y)$ for all $y\in \mathrm{dom}(s)$, $y\ne x$. Let $𝒜$ be a set of $\tau$-models with the same domain $M$ and let $f:𝒜\to M$ be a function. We denote by $𝒜[f/x]$ the set $\{(𝔐,s[f(𝔐,s)/x])\mid (𝔐,s)\in 𝒜\}.$ Intuitively, the function $f$ gives the new interpretation of the variable $x$ for each model $(𝔐,s)\in 𝒜$. Additionally, we denote $𝒜[M/x]:=\{(𝔐,s[a/x])\mid (𝔐,s)\in 𝒜,a\in M\}.$ Here the variable $x$ is given all possible interpretations, usually leading to a larger set of models. We next define the game.

Let ${𝒜}_0$ and ${ℬ}_0$ be sets of $\tau$-models and let $r_0,q_0\in \mathbb{N}$ with $r_0>q_0$. The FO prenex formula size game ${\mathrm{FS}}^{\tau }(r_0,q_0,{𝒜}_0,{ℬ}_0)$ has two players: Samson (S) and Delilah (D). Positions of the game are of the form $(r,q,𝒜,ℬ)$, where $r,q\in \mathbb{N}$ and $𝒜$ and $ℬ$ are sets of $\tau$-models. The starting position is $(r_0,q_0,{𝒜}_0,{ℬ}_0)$. In a position $(r,q,𝒜,ℬ)$, if $r=0$, then the game ends and D wins. Otherwise, if $q>0$, the game is said to be in the quantifier phase and S can choose from the following three moves:

• $\mathrm{■}$

  $\mathbf{\exists }$-move: S chooses $f:𝒜\to M$ and $x_i\in \mathrm{𝑉𝑎𝑟}$. The new position is
  $(r-1,q-1,𝒜[f/x_i],ℬ[M/x_i])$.

• $\mathrm{■}$

  $\mathbf{\forall }$-move: The same as the $\exists$-move with the roles of $𝒜$ and $ℬ$ switched.

• $\mathrm{■}$

  Phase change: S moves on to the atomic phase and the new position is $(r,0,𝒜,ℬ)$.

In a position $(r,q,𝒜,ℬ)$, if $q=0$, the game is said to be in the atomic phase and S can choose from the following three moves:

• $\mathrm{■}$

  $\mathbf{\wedge }$-move: S chooses $r_1,r_2\in \mathbb{N}$ and ${ℬ}_1,{ℬ}_2\subseteq ℬ$ such that $r_1+r_2+1=r$ and ${ℬ}_1\cup {ℬ}_2=ℬ$. Then D chooses the next position from the options $(r_1,0,𝒜,{ℬ}_1)$ and $(r_2,0,𝒜,{ℬ}_2)$.

• $\mathrm{■}$

  $\mathbf{\vee }$-move: The same as the $\wedge$-move with the roles of $𝒜$ and $ℬ$ switched.

• $\mathrm{■}$

  Atomic move: S chooses an atomic formula $\alpha$. The game ends. If $𝒜\models \alpha$ and $ℬ\models \neg \alpha$, then S wins. Otherwise, D wins.

The prenex formula size game characterizes separation of model classes with formulas of limited size in the following way.

Using Theorems 1 and 8, we can determine asymptotically the expected description complexity of a random $\tau$-model. Here by random we mean that the model is sampled uniformly at random from the set of all $\tau$-models of size $n$. That is, we determine the asymptotic behavior of the quantity ${𝔼}_n[C]:=\frac{1}{2^{|\tau |n}}{\sum }_{𝔐}C(𝔐)$ as $n\to \mathrm{\infty }$, where the sum is taken over all the $\tau$-models $𝔐$ of size $n$.

We say that a $\tau$-model $𝔐$ is balanced, if for every $\tau$-type $\pi$, we have $|{|\pi |}_{𝔐}-\frac{n}{2^{|\tau |}}|=o(n).$ In other words, a model is balanced if every type is realized roughly the same number of times, allowing for a sublinear discrepancy. We use the well-known Chernoff bounds to establish that a random model is very likely balanced.

In this section we establish results that illustrate how entropy and description complexity relate to each other. As one can already imagine after seeing our results on description complexity, there can be models with very close entropies and quite different description complexities. We can nevertheless use our results to exclude many a priori possible combinations of description complexity and entropy. For notational simplicity, we adopt the notation $t:=2^{|\tau |}$.

We begin by showing that the Boltzmann and Shannon entropies of a single model are essentially the same up to normalization. This underlines the fact that both entropies measure the same thing: the randomness of a model.