| Izvestiya: Mathematics |
|
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers) On the decision problem for quantified probability logics S. O. Speranski Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia
Bibliographic databases:
    § 1. IntroductionThe decision problem for (classical) first-order logic can be stated as: given a signature $\sigma$, let $\mathrm{Val}_{\sigma}$ be the set of all valid first-order $\sigma$-sentences; we want to know which prefix fragments of $\mathrm{Val}_{\sigma}$ are decidable. Here, each prefix fragment is denoted by a suitable element of Recall that a first-order $\sigma$-formula is $\Sigma_n$ if and only if it has the form
$$
\begin{equation*}
\underbrace{{\exists\, \vec{x}_1}\ \forall\, \vec{x}_2\ \dots\ \vec{x}_n}_{n-1\ \text{alternations}}\ \Psi,
\end{equation*}
\notag
$$
where $\vec{x}_1$, …, $\vec{x}_n$ are tuples of variables and $\Psi$ contains no quantifiers; the definition of $\Pi_n$ results by interchanging1 $\exists$ and $\forall$. By using dummy quantifiers, we may order the prefix fragments in the natural way: Thus the above problem can be restated as: given a signature $\sigma$, find the minimal undecidable (or alternatively, maximal decidable) prefix fragments of $\mathrm{Val}_{\sigma}$. Considerable effort has been devoted to this problem, leading to a complete solution; see [2] for more information. Of course, similar problems arise for other quantified logics. Roughly, if $\mathscr{L}$ is a language with one sort of variables and two standard quantifiers, that is, $\forall$ and $\exists$, then the decision problem for $\mathscr{L}$ is stated in a way similar to that for first-order language.2 In this article, we shall be concerned with the decision problem for quantified probability logics. In particular, we shall consider a one-sorted elementary language for reasoning about probability spaces, denoted by $\mathsf{QPL}^{\mathrm{e}}$, which can be viewed as obtained from the well-known “polynomial” language from § 5 in [4] by adding quantifiers over arbitrary events. As was proved in [13] (cf. [11]), the validity problem for $\Pi_2$-$\mathsf{QPL}^{\mathrm{e}}$-sentences is decidable, but that for $\Pi_3$-$\mathsf{QPL}^{\mathrm{e}}$-sentences is not. We are going to improve this result by replacing $\Pi_3$ by $\Sigma_2$, which yields the desired solution of the decision problem for $\mathsf{QPL}^{\mathrm{e}}$. Furthermore, using the technique developed for $\mathsf{QPL}^{\mathrm{e}}$, we shall solve the decision problems for two other languages, denoted by $\mathscr{L}_1$ and $\mathscr{L}_2$, which are natural one-sorted fragments of the “first-order” languages studied in [1]. Both of these include quantifiers over elements of a given domain; however, $\mathscr{L}_1$ uses probability distributions on the domain, while $\mathscr{L}_2$ utilizes external distributions on an additional set of possible worlds, each of which can be identified with a first-order structure. It should also be remarked that unlike $\mathsf{QPL}^{\mathrm{e}}$, these depend on the choice of a signature3 $\varsigma$. Briefly, we aim to show that, for each $i \in \{ 1, 2 \}$ and any sufficiently rich $\varsigma$, the minimal undecidable prefix fragment of $\mathscr{L}_i(\varsigma)$ is $\Sigma_2$; so, the maximal decidable one is $\Pi_2$. Here, “sufficiently rich” agrees with the richness conditions of the complexity results in [1]. In effect, we shall prove more than what is mentioned above. For instance, the $\Sigma_2$-fragment of the $\mathsf{QPL}^{\mathrm{e}}$-theory of finite probability spaces turns out to be hereditarily undecidable; similarly for $\mathscr{L}_1$ and $\mathscr{L}_2$. Also $\mathscr{L}_1$ and $\mathscr{L}_2$ have the finite model property for $\Pi_2$-sentences. § 2. Quantifying over eventsBy a probability space, or simply a space, we mean a pair $\langle \mathscr{A}, \mathsf{P} \rangle$ where:
Elements of $\mathscr{A}$ are called events, which are measurable with respect to $\mathsf{P}$. Note, in passing, that the countable additivity of $\mathsf{P}$ implies $\mathsf{P}(\bot)=0$, where $\bot$ is the least element of $\mathscr{A}$. We shall write $\mathcal{K}_{\mathrm{all}}$ for the class of all spaces. The formal language $\mathsf{QPL}^{\mathsf{e}}$ includes:
The Boolean terms are build up from $\bot$, $\top$ and the Boolean variables by use of $\wedge$, $\vee$ and $\neg$ :
Naturally, they represent Boolean combinations of events. By a $\mu$-term we mean an expression of the form $\mu(\phi)$, where $\phi$ is a Boolean term. Intuitively, $\mu(\phi)$ is the probability of $\phi$. We shall use $\wedge$, $\vee$ and $\neg$ to denote the Boolean operations as well as the ordinary logical connectives. Since their Boolean versions will not occur outside the scope of $\mu$, the interpretations of $\wedge$, $\vee$ and $\neg$ will always be clear from the context. By a basic $\mathsf{QPL}^{\mathsf{e}}$-formula we mean an expression of the form
$$
\begin{equation*}
f(\mu(\phi_1), \dots, \mu(\phi_m))\leqslant g(\mu(\phi_{m+1}), \dots, \mu(\phi_{m+n})),
\end{equation*}
\notag
$$
where $f$ and $g$ are polynomials with integer coefficients, and $\phi_1,\dots,\phi_{m+n}$ are Boolean terms. The $\mathsf{QPL}^{\mathsf{e}}$-formulas are built up from the basic $\mathsf{QPL}^{\mathsf{e}}$-formulas in the obvious way, as in classical first-order logic. We treat $t_1 = t_2$ as an abbreviation for $t_1 \leqslant t_2 \wedge t_2 \leqslant t_1$ and also adopt other standard abbreviations. Traditionally, a $\mathsf{QPL}^{\mathrm{e}}$-sentence is a $\mathsf{QPL}^{\mathrm{e}}$-formula with no free variable occurrences. Denote by $\mathrm{Sent}^{\mathrm{e}}$ the collection of all $\mathsf{QPL}^{\mathrm{e}}$-sentences. The satisfiability relation $\Vdash$ for $\mathsf{QPL}^{\mathsf{e}}$ can be defined in the customary way, treating the logical connective symbols and quantifiers classically. For example, consider
$$
\begin{equation*}
\Theta(X) := \mu(X) \ne 0 \wedge \forall\, Y\, (\mu(X \wedge Y) \ne 0 \to \mu (X\wedge \neg Y) = 0).
\end{equation*}
\notag
$$
Let $\mathscr{P} = \langle \mathscr{A}, \mathsf{P} \rangle$ be a probability space. Then, for every $A \in \mathscr{A}$, $\mathscr{P} \Vdash \Theta(A)$ if and only if $A$ is an atom of $\mathscr{A}$ modulo events of measure zero. Remark 2.1. The quantifier-free fragment of $\mathsf{QPL}^{\mathrm{e}}$ is essentially the “polynomial” logic studied in § 5 of [4], provided that we treat variables as constant symbols. Next, a $\mathsf{QPL}^{\mathsf{e}}$-formula $\Phi(X_1,\dots, X_n)$ is called valid if $\mathscr{P} \Vdash \Phi(A_1,\dots,A_n)$ for every space $\mathscr{P}$ and all $A_1,\dots,A_n$ in $\mathscr{A}$. Using Tarski’s algorithm from [16], it is rather easy to obtain the following result. Proposition 2.2 (see [4]). The validity problem for quantifier-free $\mathsf{QPL}^{\mathsf{e}}$-formulas is decidable.5 Denote by $\mathrm{Val}^{\mathrm{e}}$ the collection of all valid $\mathsf{QPL}^{\mathsf{e}}$-sentences. Given a class $\mathcal{K}$ of spaces, define the $\mathsf{QPL}^{\mathrm{e}}$-theory of $\mathcal{K}$ to be
$$
\begin{equation*}
\mathrm{Th}(\mathcal{K}) := \{\Phi \in \mathrm{Sent}^{\mathrm{e}} \mid \mathscr{P} \Vdash \Phi\ \text{for every}\ \mathscr{P} \in \mathcal{K}\}.
\end{equation*}
\notag
$$
Thus $\mathrm{Val}^{\mathrm{e}}$ coincides with $\mathrm{Th}(\mathcal{K}_{\mathrm{all}})$. In this paper, however, we shall deal mainly with finite probability spaces. For each $n \in \mathbb{N}$, let
$$
\begin{equation*}
\mathcal{K}_n := \text{the class of all spaces with at most}\ n\ \text{events}.
\end{equation*}
\notag
$$
We write $\mathcal{K}_{\mathrm{fin}}$ for the union of $\{\mathcal{K}_n \mid n \in \mathbb{N}\}$, that is, the class of all finite spaces. The following result is obtained by an argument similar to that for Proposition 2.2. Proposition 2.3 (see [13]). $\mathrm{Th}(\mathcal{K}_n)$ is decidable, uniformly in $n$. Finally, the notions of $\Sigma_n$- and $\Pi_n$-formula in $\mathsf{QPL}^{\mathrm{e}}$ are analogous to those in first-order logic, as described in the introduction. Sometimes we say that $\Phi$ is existential instead of “$\Phi$ is $\Sigma_1$.” Given $\Gamma \subseteq \mathrm{Sent}^{\mathrm{e}}$, take
$$
\begin{equation*}
\Sigma_n \text{-} \Gamma := \{\Phi \in \Gamma \mid \Phi\ \text{is}\ \Sigma_n\}.
\end{equation*}
\notag
$$
Similarly for $\Pi_n \text{-} \Gamma$. Observe that the validity problem for $\Sigma_n$-$\mathsf{QPL}^{\mathrm{e}}$-formulas (which may contain free variables) is equivalent to that for $\Pi_{n+1}$-$\mathsf{QPL}^{\mathrm{e}}$-sentences, and thus corresponds to $\Pi_{n+1} \text{-} \mathrm{Val}^{\mathrm{e}}$. So, Proposition 2.2 establishes the decidability of $\Pi_1 \text{-} \mathrm{Val}^{\mathrm{e}}$. This can be improved. Theorem 2.4 (see [13]). $\Pi_2 \text{-} \mathrm{Th}(\mathcal{K}_{\mathrm{fin}})$ is decidable. Moreover, On the other hand, as was also shown in [13], $\Pi_3 \text{-} \mathrm{Val}^{\mathrm{e}}$ is undecidable. But what about $\Sigma_2$? We are going to prove that $\Sigma_2 \text{-} \mathrm{Val}^{\mathrm{e}}$ and $\mathrm{Sent}^{\mathrm{e}} \setminus \Sigma_2 \text{-} \mathrm{Th}(\mathcal{K}_{\mathrm{fin}})$ are computably inseparable. This implies, in particular, the undecidability of $\Sigma_2 \text{-} \mathrm{Val}^{\mathrm{e}}$. Remark 2.5. Our work may be compared to the study of prefix fragments of elementary theories in [7]; cf. also [10]. See [14] and [15] for more results about $\mathsf{QPL}^{\mathrm{e}}$. § 3. Probabilities on the domainWe are about to describe a natural one-sorted fragment $\mathscr{L}_1$ of Halpern’s “first-order” logic of probability of type $1$. In brief, $\mathscr{L}_1$ is obtained from the language of § 2 in [1] by: (i) excluding quantifiers over reals, but keeping those over elements of the domain, which are more significant; (ii) requiring that $\mu$ can only be applied to quantifier-free first-order formulas. In particular, (ii) implies that no nested occurrences of $\mu$ are allowed. Notice that the lower bound arguments provided in [1] agree with (ii). Consider a (first-order) signature $\varsigma$. For technical reasons, we shall restrict ourselves to signatures containing no function symbols; cf. the richness conditions in [1]. By an $\mathscr{L}_1 (\varsigma)$-structure we mean a triple $\langle D, \pi, \mathsf{p} \rangle$ where:
Note, in passing, that given $\mathsf{p}$ as above and a non-zero $k \in \mathbb{N}$, we can define a discrete distribution $\mathsf{p}^k$ on $D^k$ by
$$
\begin{equation*}
\mathsf{p}^k(d_1, \dots, d_k) := \mathsf{p}(d_1) \cdot \ldots \cdot \mathsf{p}(d_k),
\end{equation*}
\notag
$$
which, of course, generates the measure $\mathsf{P}^k$ on the powerset of $D^k$. Evidently, if $A \subseteq D^k$, and $A'$ is obtained from $A$ by permuting some of the coordinates, then $\mathsf{P}^k(A')$ coincides with $\mathsf{P}^k(A)$. Remark 3.1. We assume that if the equality symbol belongs to $\varsigma$, then it has arity $2$ and is always interpreted as the equality relation on the corresponding domain. Let $\mathrm{var}$ be a countable set of individual variables; denote by $\mathrm{Form}^{\circ}_{\varsigma}$ the set of all quantifier-free first-order $\varsigma$-formulas. Then the $\mathscr{L}_1 (\varsigma)$-formulas are built up exactly as in $\mathsf{QPL}^{\mathrm{e}}$, except that:
Next, consider an $\mathscr{L}_1 (\varsigma)$-structure $\mathcal{M} = \langle D, \pi, \mathsf{p} \rangle$. Hence the variables are intended to range over elements of $D$. Given a function $\zeta$ from $\mathrm{var}$ to $D$, we interpret each $\mu_{(x_1, \dots, x_k)}(\phi)$ as
$$
\begin{equation*}
\mathsf{P}^k \bigl( \bigl\{(d_1, \dots, d_k) \in D^k \bigm| \phi \text{ is true in } \pi \text{ under } \zeta^{\vec{x}}_{\vec{d}}\bigr\} \bigr),
\end{equation*}
\notag
$$
where $\zeta^{\vec{x}}_{\vec{d}}$ is the function from $\mathrm{var}$ to $D$ such that
$$
\begin{equation*}
\zeta^{\vec{x}}_{\vec{d}}(u) = \begin{cases} {d_i} &\text{if }u = x_i \text{ with } i \in\{ 1, \dots, k\}, \\ \zeta(u) &\text{otherwise}. \end{cases}
\end{equation*}
\notag
$$
Now the satisfiability relation for $\mathscr{L}_1 (\varsigma)$ can be defined in the natural way, like that for $\mathsf{QPL}^{\mathrm{e}}$. We shall ambiguously denote it by $\Vdash$, since this should cause no confusion. We can proceed as in $\mathsf{QPL}$. The corresponding notations are given in Table 1, where $n \in \mathbb{N}$ and $\mathscr{K} \subseteq \mathscr{K}^1_{\mathrm{all}} (\varsigma)$. As one would expect, we have the following result. Table 1
Proposition 3.2 (see [1]). $\mathrm{Th}(\mathscr{K}^1_n (\varsigma))$ is decidable, uniformly in $n$. We are going to prove that, for every sufficiently rich $\varsigma$, the sets
$$
\begin{equation*}
\Sigma_2 \text{-} \mathrm{Val}^1_{\varsigma} \quad \text{and} \quad \mathrm{Sent}^1_{\varsigma} \setminus \Sigma_2 \text{-} \mathrm{Th} \bigl( \mathscr{K}^1_{\mathrm{fin}} (\varsigma) \bigr)
\end{equation*}
\notag
$$
are computably inseparable; this implies, among other things, the undecidability of $\Sigma_2 \text{-} \mathrm{Val}^1_{\varsigma}$. We shall also obtain the analogue of Theorem 2.4 for $\mathscr{L}_1$.
§ 4. Probabilities on possible worldsWe now turn to a natural one-sorted fragment $\mathscr{L}_2$ of Halpern’s “first-order” logic of probability of type $2$. It is obtained from the language of § 3 in [1] in a way similar to that of $\mathscr{L}_1$. Consider a signature $\varsigma$. By an $\mathscr{L}_2 (\varsigma)$-structure we mean a quadruple $\langle D, \Omega, \pi, \mathsf{p} \rangle$, where:
In this context, elements of $\Omega$ are called possible worlds. The $\mathscr{L}_2 (\varsigma)$-formulas are built up exactly as in $\mathscr{L}_1 (\varsigma)$, except that the subscripts $\vec{x}$ are dropped: we use $\mu$ instead of $\mu_{\vec{x}}$ throughout. Next, consider an $\mathscr{L}_2 (\varsigma)$-structure $\mathcal{M} = \langle D, \Omega, \pi, \mathsf{p} \rangle$. Given a function $\zeta$ from $\mathrm{var}$ to $D$, we interpret each $\mu(\phi)$ as
$$
\begin{equation*}
\mathsf{P}(\{ \omega \in \Omega \mid \phi \text{ is true in } \pi(\omega) \text{ under } \zeta\}),
\end{equation*}
\notag
$$
where $\mathsf{P}$ is the probability measure (on the powerset of $\Omega$) generated by $\mathsf{p}$. Then the satisfiability relation for $\mathscr{L}_2 (\varsigma)$ can be defined in the obvious way. We shall denote it by $\Vdash$ as well. Remark 4.1. Z. Ognjanović and his colleagues have developed suitable infinitary calculi for some languages similar to $\mathscr{L}_2$; see [9] for details. The notation for $\mathscr{L}_2$ is perfectly similar to that for $\mathscr{L}_1$, but with $1$ replaced by $2$, and one additional modification: we write $\mathscr{K}^2_n (\varsigma)$ for the class of all $\mathscr{L}_2 (\varsigma)$-structures with at most $n$ elements and at most $n$ worlds. Proposition 4.2 (see [1]). $\mathrm{Th}(\mathscr{K}^2_n (\varsigma))$ is decidable, uniformly in $n$. Our theorems for $\mathscr{L}_2$ will be analogous to those for $\mathscr{L}_1$. See [1] and [5] for more results about Halpern’s “first-order” logics of probability. § 5. Finite spacesGiven a signature $\sigma$, denote by $\mathrm{Sent}_{\sigma}$ the set of all (first-order) $\sigma$-sentences. Following [7], we call $\Gamma \subseteq \mathrm{Sent}_{\sigma}$ hereditarily undecidable if, for every $\Delta \subseteq \mathrm{Sent}_{\sigma}$,
$$
\begin{equation*}
\mathrm{Val}_{\sigma} \cap \Gamma \subseteq \Delta \subseteq \Gamma \quad \Longrightarrow \quad \Delta \text{ is undecidable}
\end{equation*}
\notag
$$
(or equivalently, $\mathrm{Val}_{\sigma} \cap \Gamma$ and $\mathrm{Sent}_{\sigma} \setminus \Gamma$ are computably inseparable). This notion can be readily adapted to $\mathsf{QPL}^{\mathrm{e}}$, $\mathscr{L}_1$ and $\mathscr{L}_2$. In particular, let $\sigma$ be $\langle R^2 \rangle$, where $R$ is a binary predicate symbol. By a simple graph we mean a $\sigma$-structure $\mathfrak{G}$ such that $R^{\mathfrak{G}}$, that is, the interpretation of $R$ in $\mathfrak{G}$, is irreflexive and symmetric. We take $\mathbf{G}_{\mathrm{fin}}$ to be the class of all finite simple graphs. Theorem 5.1 (see [7]). $\Sigma_2 \text{-} \mathrm{Th}(\mathbf{G}_{\mathrm{fin}})$ is hereditarily undecidable.6 We want to have the same for the $\Sigma_2$-fragment of the $\mathsf{QPL}^{\mathrm{e}}$-theory of finite probability spaces. A key role in our argument will be played by the following result. Proposition 5.2. There are an existential $\mathsf{QPL}^{\mathrm{e}}$-formula $\Phi_{\mathrm{all}}(X)$ and a quantifier-free $\mathsf{QPL}^{\mathrm{e}}$-formula $\Phi_R(X_1, X_2)$ such that, for every $\mathfrak{G} \in \mathbf{G}_{\mathrm{fin}}$, one can find $\mathscr{P} \in \mathcal{K}_{\mathrm{fin}}$ satisfying the following conditions: a) $H := \{ A\in \mathscr{A} \mid \mathscr{P} \Vdash \Phi_{\mathrm{all}}(A)\}$ is non-empty; b) the $\sigma$-structure $\mathfrak{H}$ with domain $H$ in which $R$ is interpreted by $\Phi_R(X_1, X_2)$, that is, is isomorphic to $\mathfrak{G}$. Proof. Consider an arbitrary finite simple graph $\mathfrak{G}$. For convenience, we may assume that where $N$ is the cardinality of7 $G$. Further, the relation $R^{\mathfrak{G}}$, being irreflexive and symmetric, can be identified with Let $K$ be the cardinality of $R(\mathfrak{G})$ and $\nu$ be a one-one function from $R(\mathfrak{G})$ onto $\{1,\dots,K\}$. In this way, each $\{i, j\} \in R(\mathfrak{G})$ is coded by $\nu(\{i, j\})$. Given $n \in G$, we define that is, $I_n$ is the set of all codes of edges that are incident on $n$.
We begin by describing a suitable finite probability space $\mathscr{P}$, and then show how the desired quantifier-free $\mathsf{QPL}^{\mathrm{e}}$-formulas emerge. Take $\Omega$ to be a set of cardinality $N + K + 3$, say
$$
\begin{equation*}
\Omega := \{\gamma_1, \dots, \gamma_N\} \cup \{\delta_1, \dots, \delta_K\} \cup \{ \lambda_1, \lambda_2, \lambda_{\ast}\},
\end{equation*}
\notag
$$
and define $\mathsf{p}\colon \Omega \to [0,1]$ by
$$
\begin{equation*}
\begin{gathered} \, \mathsf{p}(\gamma_n) := r - \sum_{k \in I_n} \frac{r}{3^k}, \qquad \mathsf{p}(\delta_k):= \frac{r}{3^k}, \\ \mathsf{p}(\lambda_1) := \frac{r}{2}, \qquad \mathsf{p}(\lambda_2) := \frac{1}{3} - \frac{r}{2} \quad \text{and} \quad \mathsf{p}(\lambda_{\ast}) := \frac{2}{3} - \sum_{n = 1}^N \mathsf{p}(\gamma_n) - \sum_{k = 1}^K \mathsf{p}(\delta_k), \end{gathered}
\end{equation*}
\notag
$$
where $r$ equals $1/(6N+3)$, just to make everything work. Observe that
$$
\begin{equation*}
\begin{aligned} \, &\sum_{n = 1}^N \mathsf{p}(\gamma_n) + \sum_{k = 1}^K \mathsf{p}(\delta_k) = \sum_{n = 1}^N \biggl(r - \sum_{k \in I_n} \frac{r}{3^k} \biggr) + \sum_{k = 1}^K \frac{r}{3^k} \\ &\qquad< N \cdot r + \frac{r}{2} = \biggl( N + \frac{1}{2} \biggr) \cdot r = \frac{2N + 1}{2} \cdot r = \frac{2N + 1}{2 \cdot (6N + 3)} = \frac{1}{2 \cdot 3} = \frac{1}{6} \end{aligned}
\end{equation*}
\notag
$$
(hence, in particular, $0 \leqslant \mathsf{p}(\lambda_{\ast}) \leqslant 1$). Moreover, we have $\sum_{\omega \in \Omega} \mathsf{p} (\omega) = 1$. Let $\mathscr{P} = \langle \mathscr{A}, \mathsf{P} \rangle$ be the corresponding discrete space; so $\mathscr{A}$ is the power set of $\Omega$, and $\mathsf{P}\colon \mathscr{A} \to [0,1]$ is given by Then $\{\lambda_1\}$ and $\{\lambda_2\}$ can be distinguished from the other events in $\mathscr{A}$ by using the quantifier-free $\mathsf{QPL}^{\mathrm{e}}$-formula To put it formally.
Claim 1. Let $\mathfrak{G}$ and $\mathscr{P}$ be as above. Then, for any $A_1, A_2 \in \mathscr{A}$, Proof. $\Longleftarrow$. Obviously, $\mathsf{P}(\{\lambda_1\} \cap \{\lambda_2\}) = 0$, $\mathsf{P}(\{\lambda_1\} \cup \{\lambda_2\}) = 1/3$ and $\mathsf{P}(\{\lambda_1\})> 0$. Moreover, since $r \leqslant 1/9$, we also have These imply $\mathsf{P}(\{\lambda_1\}) < \mathsf{P}(\{\lambda_2\})$.
$\Longrightarrow$. Suppose that $\mathsf{P}(A_1 \cap A_2) = 0$, $\mathsf{P}(A_1 \cup A_2) = 1/3$ and $0 < \mathsf{P}(A_1) < \mathsf{P}(A_2)$. Clearly, if $\{\lambda_1, \lambda_2\} \subseteq A_1 \cup A_2$, then $A_1 = \{\lambda_1\}$ and $A_2 = \{\lambda_2\}$. Thus it suffices to show that both $\lambda_1$ and $\lambda_2$ belong to $A_1 \cup A_2$. First, note that $\lambda_{\ast}$ cannot be in $A_1 \cup A_2$, since
$$
\begin{equation*}
\mathsf{p}(\lambda_{\ast}) > \frac{2}{3} - \frac{1}{6} = \frac{1}{2}.
\end{equation*}
\notag
$$
Now if $\lambda_2 \notin A_1 \cup A_2$, then
$$
\begin{equation*}
\mathsf{P}(A_1 \cup A_2) \leqslant \mathsf{P}(\Omega \setminus \{\lambda_2, \lambda_{\ast}\}) = 1 - \mathsf{p} (\lambda_2) - \mathsf{p}(\lambda_{\ast}) < 1 - \frac{5}{18} - \frac{1}{2} = \frac{2}{9},
\end{equation*}
\notag
$$
which is a contradiction. Hence $\lambda_2 \in A_1 \cup A_2$, and therefore Further, for each $n \in \{1, \dots, N\}$, $\gamma_n$ cannot be in $A_1 \cup A_2$, since $\mathsf{p}(\gamma_n) > r - r/2 = r/2$. So, if $\lambda_1$ is not in $A_1 \cup A_2$, then which is a contradiction. Hence $\lambda_1 \in A_1 \cup A_2$. $\Box$ Next, with each $n \in G$ we associate the event
$$
\begin{equation*}
{[\![ n ]\!]}\ :=\ {\left\{ \gamma_n \right\} \cup \left\{ \delta_k \mid k \in I_n \right\}}.
\end{equation*}
\notag
$$
Denote by $[\![ \Omega ]\!]$ the collection of all these events. It turns out that $[\![ \Omega ]\!]$ can be defined in $\mathscr{P}$ by the existential $\mathsf{QPL}^{\mathrm{e}}$-formula
$$
\begin{equation*}
{\Phi_{\mathrm{all}} (X)}\ :=\ {\exists U}\, {\exists V}\, {\left( \Phi_{\circ} \left( U, V \right) \wedge \mu (X) = 2 \mu \left( U \right) \right)},
\end{equation*}
\notag
$$
which has the same meaning as $\mu (X) = r$, of course. Proof. $\Longleftarrow$. By the construction of $[\![ \Omega ]\!]$.
$\Longrightarrow$. Suppose that $\mathsf{P} (A) = r$. Recall that
$$
\begin{equation*}
r< \frac{1}{9}, \qquad {\mathsf{p} (\lambda_2)}\geqslant \frac{5}{18} \quad \text{and} \quad \mathsf{p} (\lambda_{\ast})>\frac{1}{2}.
\end{equation*}
\notag
$$
So, neither $\lambda_2$ nor $\lambda_{\ast}$ can be in $A$. Moreover, if $\lambda_1 \in A$, then
$$
\begin{equation*}
\mathsf{P}(A \setminus \{\lambda_1\})= \mathsf{P} (A) - \mathsf{p} (\lambda_1)= \frac{r}{2},
\end{equation*}
\notag
$$
which implies that $\gamma_1, \dots, \gamma_N$ do not belong to $A$ (since $\mathsf{p}(\gamma_n) > r/2$ for each $n \in \{ 1, \dots, N\}$), and therefore
$$
\begin{equation*}
\mathsf{P}(A \setminus \{\lambda_1\}) \leqslant \mathsf{P}(\{\delta_1, \dots, \delta_K\})< \frac{r}{2},
\end{equation*}
\notag
$$
which is a contradiction. Hence $\lambda_1$ cannot be in $A$ as well. To summarize, we have Clearly, there exists precisely one $n \in \{1, \dots, N\}$ such that $\gamma_n \in A$. This gives us It is easy to verify that $A \setminus \{\gamma_n\}$ equals $\{\delta_k \mid k \in I_n\}$. Thus $A$ coincides with $[\![ n ]\!]$. $\Box$ Finally, observe that, for all $i, j \in G$,
$$
\begin{equation*}
\begin{aligned} \, (i, j)\in R^{\mathfrak{G}} \quad &\Longleftrightarrow \quad \{i,j\}\in R(\mathfrak{G}) \\ &\Longleftrightarrow \quad i \ne j \text{ and } I_i \cap I_j \ne \varnothing \\ &\Longleftrightarrow \quad i \ne j \text{ and } [\![ i ]\!] \cap [\![ j ]\!] \ne \varnothing \\ &\Longleftrightarrow \quad 0< \mathsf{P}([\![ i ]\!] \cap [\![ j ]\!]) < \mathsf{P}([\![ i ]\!] \cup [\![ j ]\!]). \end{aligned}
\end{equation*}
\notag
$$
So, we can take
$$
\begin{equation*}
\Phi_R(X_1, X_2) := 0 < \mu(X_1 \wedge X_2) < \mu(X_1 \vee X_2).
\end{equation*}
\notag
$$
Then the corresponding $\sigma$-structure $\mathfrak{H}$ (as in the statement of the proposition) turns out to be isomorphic to $\mathfrak{G}$ via the mapping $n \mapsto [\![ n ]\!]$. $\Box$ Now we are ready to obtain the desired result. Theorem 5.3. $\Sigma_2 \text{-} \mathrm{Th}(\mathcal{K}_{\mathrm{fin}})$ is hereditarily undecidable. Proof. For convenience, we shall assume that the logical connective symbols in classical first-order logic are the same as those in $\mathsf{QPL}$ (namely $\wedge$, $\vee$, $\neg$) and associate with each individual variable $x$ a distinguished Boolean variable $X$.
Let $\Phi_{\mathrm{all}} (X)$ and $\Phi_R (X_1,X_2)$ be as in the statement of Proposition 5.2. Given a $\sigma$-sentence $\Phi$, we define $\tau (\Phi)$ recursively by
$$
\begin{equation*}
\begin{aligned} \, \tau (R(x,y)) &:=\Phi_R (X,Y), \\ \tau(\Psi \wedge \Theta)&:= \tau (\Psi) \wedge \tau (\Theta), \\ \tau(\Psi \vee \Theta) &:= \tau (\Psi) \vee \tau (\Theta), \\ \tau(\neg\, \Psi) &:= \neg\, \tau (\Psi), \\ \tau(\forall\, x \Psi) &:= \forall\, X\ (\Phi_{\mathrm{all}} (X) \to \tau (\Psi)), \\ \tau(\exists\, x\ \Psi) &:= \exists\, X\ (\Phi_{\mathrm{all}} (X) \wedge \tau (\Psi)). \end{aligned}
\end{equation*}
\notag
$$
To avoid clashes of variables, we require that $\Phi$ contain no occurrences of the individual variables whose uppercase versions are bound in $\Phi_{\mathrm{all}} (X)$ or $\Phi_R (X_1,X_2)$. Take
$$
\begin{equation*}
\tau^{\ast} (\Phi) :=\Phi_{\mathrm{spec}} \to \tau (\Phi),
\end{equation*}
\notag
$$
where $\Phi_{\mathrm{spec}}$ denotes the “specification” sentence
$$
\begin{equation*}
\exists\, X\ \Phi_{\mathrm{all}} (X) \wedge \forall\, X\ \neg\, \Phi_R(X,X) \wedge \forall\, X_1\ \forall\, X_2\ (\Phi_R(X_1,X_2) \to \Phi_R(X_2,X_1)).
\end{equation*}
\notag
$$
Observe that, for every $\sigma$-sentence $\Phi$,
$$
\begin{equation*}
\begin{aligned} \, \Phi\in \mathrm{Val}_{\sigma} \quad \Longrightarrow \quad &\tau^{\ast}(\Phi)\in \mathrm{Val}^{\mathrm{e}}, \\ \Phi\in \mathrm{Th}(\mathbf{G}_{\mathrm{fin}})\quad \Longleftrightarrow \quad &\tau^{\ast}(\Phi)\in \mathrm{Th}(\mathcal{K}_{\mathrm{fin}}). \end{aligned}
\end{equation*}
\notag
$$
And if $\Phi$ is in $\Sigma_2$, then we can effectively convert $\tau^{\ast} (\Phi)$ to an equivalent $\Sigma_2$-$\mathsf{QPL}^{\mathrm{e}}$-sentence $\rho (\Phi)$. In this way $\rho$ maps the $\Sigma_2$-$\sigma$-sentences into the $\Sigma_2$-$\mathsf{QPL}^{\mathrm{e}}$-sentences.
Now suppose $\Delta$ is such that $\Sigma_2 \text{-} \mathrm{Val}^{\mathrm{e}} \subseteq \Delta \subseteq \Sigma_2 \text{-} \mathrm{Th}(\mathcal{K}_{\mathrm{fin}})$. Clearly, we have Therefore $\rho^{-1}[\Delta]$ cannot be decidable. Evidently, $\rho^{-1}[\Delta]$ is reducible to $\Delta$ via $\rho$. It follows that $\Delta$ must be undecidable, as desired. $\Box$It is known that $\Sigma_2 \text{-} \mathrm{Th}(\mathbf{G}_{\mathrm{fin}})$ is $\Pi^0_1$-complete; see Theorem 4.2 in [7] and Corollary 3.8 in [12]. This quickly leads us to the following result. Proof. Let $\rho$ be as in the proof of Theorem 5.3. Obviously, $\rho$ reduces $\Sigma_2 \text{-} \mathrm{Th}(\mathbf{G}_{\mathrm{fin}})$ to $\Sigma_2 \text{-} \mathrm{Th}(\mathcal{K}_{\mathrm{fin}})$; hence $\Sigma_2 \text{-} \mathrm{Th}(\mathcal{K}_{\mathrm{fin}})$ is $\Pi^0_1$-hard. On the other hand, $\Sigma_2 \text{-} \mathrm{Th}(\mathcal{K}_{\mathrm{fin}})$ is trivially reducible to $\mathrm{Th}(\mathcal{K}_{\mathrm{fin}})$, which is $\Pi^0_1$-bounded by Proposition 2.3. $\Box$ At the same time, Theorem 5.3 implies the undecidability of the validity problem for $\Sigma_2$-$\mathsf{QPL}^{\mathrm{e}}$-sentences. In view of Theorem 2.4, this means that $\Sigma_2$ is the minimal undecidable prefix fragment of $\mathsf{QPL}^{\mathrm{e}}$, which completes the analysis of the decision problem for $\mathsf{QPL}^{\mathrm{e}}$. § 6. Finite structures of type 1Next, we wish to adapt the technique developed in the previous section to deal with $\mathscr{L}_1$. Instead of Proposition 5.2, we shall use the following result. Proposition 6.1. Let $\varsigma$ be $\langle = \rangle$. Then there are existential $\mathscr{L}_1 (\varsigma)$-formulas such that, for every $\mathfrak{G} \in \mathbf{G}_{\mathrm{fin}}$, one can find $\mathcal{M} \in \mathscr{K}^1_{\mathrm{fin}} (\varsigma)$ satisfying the following conditions: a) $H := \{d \in D \mid \mathcal{M} \Vdash \Phi_{\mathrm{all}}(d)\}$ is non-empty; b) for all $d_1, d_2 \in H$,
$$
\begin{equation*}
\mathcal{M} \Vdash \Phi_R^1 (d_1,d_2)\quad \Longleftrightarrow \quad\mathcal{M} \nVdash \Phi_R^0 (d_1,d_2);
\end{equation*}
\notag
$$
c) the $\sigma$-structure $\mathfrak{H}$ with domain $H$ in which $R$ is interpreted by $\Phi_R^1 (x_1,x_2)$, that is, is isomorphic to $\mathfrak{G}$. Proof. Since $\varsigma$ is fixed by the context, we shall write $\mathscr{L}_1$ instead of $\mathscr{L}_1 (\varsigma)$.
Consider an arbitrary finite simple graph $\mathfrak{G}$. As before, we may assume that $G = \{ 1, \dots, N \}$, where $N$ is the cardinality of $G$, and also identify the relation $R^{\mathfrak{A}}$ with
$$
\begin{equation*}
R(\mathfrak{G}) := \bigl\{ \{i,j\} \bigm| (i,j) \in R^{\mathfrak{A}}\bigr\}.
\end{equation*}
\notag
$$
Denote by $G_2$ the collection of all subsets of $G$ containing exactly two elements. For each $S \in G_2$, let $\varepsilon_S$ tell us whether or not $S$ belongs to $R(\mathfrak{G})$:
$$
\begin{equation*}
\varepsilon_S := \begin{cases} 1 &\text{if } S \in R(\mathfrak{G}), \\ 0 &\text{otherwise}. \end{cases}
\end{equation*}
\notag
$$
Now we are ready to describe a suitable finite $\mathscr{L}_1$-structure $\mathcal{M}$. Take
$$
\begin{equation*}
\Omega := \{\gamma_n \mid n \in G\} \cup \{ \delta_S \mid S \in G_2 \} \cup \{ \lambda_1, \lambda_2, \lambda_{\ast} \},
\end{equation*}
\notag
$$
and define $\mathsf{p}: \Omega \to [0,1]$ by
$$
\begin{equation*}
\begin{gathered} \, \mathsf{p}(\gamma_n) := r - \frac{r}{3^n}, \qquad \mathsf{p}(\delta_{\{i,j\}}) := \frac{r}{3^i} + \frac{r}{3^j} + \varepsilon_{\{i,j\}} \cdot r, \\ \mathsf{p}(\lambda_1) := \frac{r}{2}, \qquad \mathsf{p} (\lambda_2) := \frac{1}{3} - \frac{r}{2} \quad \text{and} \quad \mathsf{p} (\lambda_{\ast}) := \frac{2}{3} - \sum_{n = 1}^N \mathsf{p}(\gamma_n) - \sum_{S \in G_2} \mathsf{p}(\delta_S), \end{gathered}
\end{equation*}
\notag
$$
where $r$ equals $1/(6N^2 + 3)$. Observe that
$$
\begin{equation*}
\begin{aligned} \, &\sum_{n = 1}^N \mathsf{p}(\gamma_n) + \sum_{S \in G_2} \mathsf{p}(\delta_S) = \sum_{n = 1}^N \biggl(r - \frac{r}{3^n}\biggr) + \sum_{i = 1}^{N-1} \sum_{j = i+1}^N\biggl( \frac{r}{3^i} + \frac{r}{3^j} + \varepsilon_{\{i,j\}} \cdot r \biggr) \\ &\qquad< N \cdot r + \frac{N \cdot (N-1)}{2} \cdot \biggl( \frac{r}{2} + r \biggr) = N \cdot r + N \cdot (N - 1) \cdot \frac{3r}{4} \\ &\qquad< N \cdot r + N \cdot (N - 1) \cdot r = N^2 \cdot r= \frac{N^2}{6N^2 + 3}< \frac{1}{6}. \end{aligned}
\end{equation*}
\notag
$$
Trivially, we have $\sum_{\omega \in \Omega} \mathsf{p} (\omega) = 1$. Let $\mathcal{M}$ be the $\mathscr{L}_1$-structure $\langle D, \pi, \mathsf{p} \rangle$, where $D$ coincides with $\Omega$, and $\pi$ is a (unique) $\varsigma$-structure with domain $D$. Similarly to before, we can distinguish $\lambda_1$ and $\lambda_2$ from the other elements of $D = \Omega$ by using the quantifier-free $\mathscr{L}_1$-formula
$$
\begin{equation*}
\begin{aligned} \, \Phi_{\circ} (u,v) &:= \mu_z( z = u \wedge z = v) = 0 \wedge 3 \mu_z( z = u \vee z = v) = 1 \\ &\qquad \wedge 0 < \mu_z (z = u) < \mu_z( z = v). \end{aligned}
\end{equation*}
\notag
$$
To be precise, it is easy to show that, for all $d_1, d_2 \in D$,
$$
\begin{equation*}
\mathcal{M} \Vdash \Phi_{\circ} (d_1,d_2) \quad \Longleftrightarrow \quad d_1 = \lambda_1 \ \ \text{and} \ \ d_2 = \lambda_2;
\end{equation*}
\notag
$$
cf. the proof8 of Claim 1 (in the proof of Proposition 5.2).
Intuitively, we are going to identify each $n \in G$ with $\gamma_n$. Note that $\{ \gamma_1, \dots, \gamma_N \}$ can be defined in $\mathcal{M}$ by the existential $\mathscr{L}_1$-formula
$$
\begin{equation*}
\Phi_{\mathrm{all}} (x) := \exists\, u\ \exists\, v\ \bigl(\Phi_{\circ} (u,v) \wedge \mu_z (z = u) < \mu_z(z = x) < 2 \mu_z(z = u)\bigr),
\end{equation*}
\notag
$$
which has the same meaning as $r/2 < \mu_z(z = x) < r$.
Next, observe that, for every $\{i,j\} \in G_2$, there exists a unique $\omega \in \Omega$ satisfying
$$
\begin{equation}
\mathsf{p}(\omega)= \frac{r}{3^i} + \frac{r}{3^j} + r \quad \text{or} \quad \mathsf{p}(\omega)= \frac{r}{3^i} + \frac{r}{3^j}.
\end{equation}
\tag{$\dagger$}
$$
The existence of $\omega$ is obvious, since we can substitute $\delta_{\{i,j\}}$ for $\omega$. As for the uniqueness, suppose that $\omega$ satisfies $(\dagger)$. So, in particular, either $r < \mathsf{p} (\omega) < {3r}/2$ or $\mathsf{p} (\omega) < r/2$.
Thus the only element of $\Omega$ that satisfies ($\unicode{8224}$) is $\delta_{\{i,j\}}$. In addition, we have
$$
\begin{equation*}
\begin{aligned} \, \varepsilon_{\{i,j\}}= \varepsilon \quad &\Longleftrightarrow \quad \mathsf{p}(\delta_{\{i,j\}}) = \frac{r}{3^i} + \frac{r}{3^j} + \varepsilon \cdot r \\ &\Longleftrightarrow \quad \mathsf{p} (\gamma_i) + \mathsf{p} (\gamma_j) + \mathsf{p} (\delta_{\{i,j\}}) = (2 + \varepsilon) \cdot r \\ &\Longleftrightarrow \quad \mathsf{p}(\gamma_i) + \mathsf{p} (\gamma_j) + \mathsf{p} (\delta_{\{i,j\}}) = (4 + 2 \varepsilon) \cdot \mathsf{p} (\lambda_1), \end{aligned}
\end{equation*}
\notag
$$
where $\varepsilon$ is either $0$ or $1$. Finally, take
$$
\begin{equation*}
\begin{aligned} \, \Phi_R^{\varepsilon} (x_1, x_2, y) &:= \exists\, u\ \exists\, v\ \exists\, y\ \bigl( \Phi_{\circ} (u,v) \wedge \mu_z( z = x_1 \wedge z = x_2) = 0 \\ &\qquad\wedge \mu_z(z = x_1 \vee z = x_2 \vee z = y) = (4 + 2 \varepsilon) \mu_z (z = u)\bigr). \end{aligned}
\end{equation*}
\notag
$$
It follows that $\Phi_{\mathrm{all}} (x)$, $\Phi_R^1 (x_1,x_2)$, and $\Phi_R^0 (x_1,x_2)$ do the job. $\Box$ Naturally, since we have two formulas for $R$, the corresponding translation should be slightly more subtle than that of Theorem 5.3; cf. also Lemma 3.1 in [7]. Theorem 6.2. Suppose that $\varsigma$ contains the equality symbol. Then $\Sigma_2 \text{-} \mathrm{Th} (\mathscr{K}^1_{\mathrm{fin}} (\varsigma))$ is hereditarily undecidable. Proof. Recall that we treat $\to$ as defined, rather than primitive.
Let $\Phi_{\mathrm{all}} (x)$, $\Phi_R^1 (x_1,x_2)$ and $\Phi_R^0 (x_1,x_2)$ be as in the statement of Proposition 6.1. Now, given a $\sigma$-sentence $\Phi$, we define $\tau (\Phi)$ by
$$
\begin{equation*}
\begin{alignedat}{2} & &\qquad \tau(R(x,y)) &:= \neg\, \Phi_R^0 (x,y), \\ \tau(\neg \neg \,\Psi) &:= \tau(\Psi), &\qquad \tau( \neg\, R(x,y)) &:= \neg\, \Phi_R^1 (x,y), \\ \tau(\neg\,(\Psi \wedge \Theta)) &:= \tau(\neg\, \Psi \vee \neg\, \Theta), &\qquad \tau( \Psi \wedge \Theta) &:= \tau(\Psi) \wedge \tau(\Theta), \\ \tau(\neg\, (\Psi \vee \Theta)) &:= \tau(\neg\, \Psi \wedge \neg \, \Theta), &\qquad \tau(\Psi \vee \Theta) &:= \tau(\Psi) \vee \tau (\Theta), \\ \tau(\neg\, \forall\, x\ \Psi) &:= \tau(\exists\, x\ \neg\, \Psi), &\qquad \tau(\forall\, x\ \Psi) &:= \forall \, x \ (\Phi_{\mathrm{all}} (x) \to \tau (\Psi)), \\ \tau(\neg\, \exists x\, \Psi) &:= \tau( \forall\, x\ \neg \Psi), &\qquad \tau(\exists\, x\ \Psi) &:= \exists \, x\ (\Phi_{\mathrm{all}}(x) \wedge \tau(\Psi)) \end{alignedat}
\end{equation*}
\notag
$$
(avoiding clashes of variables, of course). Clearly, if $\Phi$ is quantifier-free, then $\tau (\Phi)$ is equivalent to a $\Pi_1$-$\mathscr{L}_1 (\varsigma)$-formula. Take
$$
\begin{equation*}
\tau^{\ast} (\Phi) := \Phi_{\mathrm{spec}} \to \tau (\Phi),
\end{equation*}
\notag
$$
where $\Phi_{\mathrm{spec}}$ denotes the “specification” sentence
$$
\begin{equation*}
\begin{aligned} \, &\exists\, x\ \Phi_{\mathrm{all}} (x) \wedge \forall\, x_1\ \forall\, x_2\ \bigl( \Phi_R^1 (x_1,x_2) \leftrightarrow \Phi_R^0 (x_1,x_2) \bigr) \\ &\qquad \wedge \forall\, x\ \neg\, \Phi_R^1 (x,x) \wedge \forall\, x_1\ \forall\, x_2\ \bigl( \Phi_R^1 (x_1,x_2) \to \Phi_R^1 (x_2,x_1) \bigr). \end{aligned}
\end{equation*}
\notag
$$
We proceed as in the proof of Theorem 5.3. $\Box$ In addition, we have the following result. Corollary 6.3. Suppose that $\varsigma$ contains the equality symbol. Then $\Sigma_2 \text{-} \mathrm{Th}(\mathscr{K}^1_{\mathrm{fin}} (\varsigma))$ is $\Pi^0_1$-complete. Proof. The argument is like that for Corollary 5.4, except that we use Proposition 3.2 instead of Proposition 2.3. $\Box$ Evidently, the condition “$\varsigma$ contains the equality symbol” can be replaced by “$\varsigma$ contains at least one predicate symbol of arity greater than or equal to $2$.” On the other hand, as was proved in [1] (by using a representation result from [5]), if $\varsigma$ consists only of unary predicate symbols, then the validity problem for $\mathscr{L}_1 (\varsigma)$-sentences, and even those in the full language of § 2 in [1] over $\varsigma$, is decidable. Consequently, for every sufficiently rich $\varsigma$, the validity problem for $\Sigma_2$-$\mathscr{L}_1 (\varsigma)$-sentences is undecidable. It will be shown in § 8 that this cannot be improved. § 7. Finite structures of type 2In the case of $\mathscr{L}_2$, we shall need two analogues of Proposition 5.2. This might be expected because of the richness conditions in [1]. Proposition 7.1. Let $\varsigma$ be $\langle =; c \rangle$, where $c$ is a constant symbol. Then there are existential $\mathscr{L}_2 (\varsigma)$-formulas such that, for every $\mathfrak{G} \in \mathbf{G}_{\mathrm{fin}}$, one can find $\mathcal{M} \in \mathscr{K}^2_{\mathrm{fin}} (\varsigma)$ satisfying the following conditions: a) $H := \{ d \in D \mid \mathcal{M} \Vdash \Phi_{\mathrm{all}}(d)\}$ is non-empty; b) for all $d_1, d_2 \in H$,
$$
\begin{equation*}
\mathcal{M} \Vdash \Phi_R^0 (d_1,d_2) \quad \Longleftrightarrow \quad \mathcal{M} \nVdash \Phi_R^1 (d_1,d_2);
\end{equation*}
\notag
$$
c) the $\sigma$-structure $\mathfrak{H}$ with domain $H$ in which $R$ is interpreted by $\Phi_R^1 (x_1,x_2)$, that is, is isomorphic to $\mathfrak{G}$. Proof. The argument is like that for Proposition 6.1, except that:
In fact, a similar trick was used in [1] to transfer certain complexity results. $\Box$ It gives us two formulas for $R$, as in Proposition 6.1. Theorem 7.2. Suppose that $\varsigma$ extends $\langle =; c \rangle$. Then $\Sigma_2 \text{-} \mathrm{Th}(\mathscr{K}^2_{\mathrm{fin}} (\varsigma))$ is hereditarily undecidable. The proof is similar to that of Theorem 6.2. In addition, we have the following result. Corollary 7.3. Suppose that $\varsigma$ extends $\langle =; c \rangle$. Then $\Sigma_2 \text{-} \mathrm{Th}(\mathscr{K}^2_{\mathrm{fin}} (\varsigma))$ is $\Pi^0_1$-complete. Proof. The argument is like that for Corollary 5.4, except that we use Proposition 4.2 instead of Proposition 2.3. $\Box$ Here is another analogue of Proposition 5.2. Proposition 7.4. Let $\varsigma$ be $\langle P^1 \rangle$, where $P$ is a unary predicate symbol, and take Then, for every $\mathfrak{G} \in \mathbf{G}_{\mathrm{fin}}$, one can find $\mathcal{M} \in \mathscr{K}^2_{\mathrm{fin}} (\varsigma)$ such that the $\sigma$-structure $\mathfrak{H}$ with domain $D$ (the first component of $\mathcal{M}$) in which $R$ is interpreted by $\Phi_R (x_1,x_2)$, that is, is isomorphic to $\mathfrak{G}$. Proof. We shall apply a simplified version of the argument for Proposition 5.2.
Consider an arbitrary finite simple graph $\mathfrak{G}$. Let $\Omega$, $\mathsf{p}$ and $[\![ \,{\cdot}\, ]\!]$ be as in the proof of Proposition 5.2. For each $\omega \in \Omega$, define $\pi (\omega)$ to be the $\varsigma$-structure with domain $G$ in which $P$ is interpreted as $\{ n \in G \mid \omega \in [\![ n ]\!] \}$. So, by construction, for every $n \in G$,
$$
\begin{equation*}
\{ \omega \in \Omega \mid \pi (\omega) \vDash P(n)\}= [\![ n ]\!].
\end{equation*}
\notag
$$
Let $\mathcal{M}$ be the $\mathscr{L}_2 (\varsigma)$-structure $\langle D, \Omega, \pi, \mathsf{p} \rangle$, where $D$ coincides with $G$. Then, for all $i, j \in G$,
$$
\begin{equation*}
\begin{aligned} \, (i,j)\in R^{\mathfrak{G}} \quad \Longleftrightarrow {}&\quad 0 < \mathsf{P}([\![ i ]\!] \cap [\![ j ]\!]) < \mathsf{P}([\![ i ]\!] \cup [\![ j ]\!]) \\ \Longleftrightarrow {}&\quad 0< \mathsf{P}(\{ \omega \in \Omega \mid \pi (\omega) \vDash P(i) \wedge P(j)\}) \\ &\quad\hphantom{0}< \mathsf{P}(\{\omega \in \Omega \mid \pi (\omega) \vDash P(i) \vee P(j)\}) \\ \Longleftrightarrow {}&\quad \mathcal{M} \Vdash \Phi_R (i,j), \end{aligned}
\end{equation*}
\notag
$$
as desired. $\Box$ Naturally, the corresponding translation is going to be simpler. Theorem 7.5. Suppose that $\varsigma$ extends $\langle P^1 \rangle$. Then $\Sigma_2 \text{-} \mathrm{Th}(\mathscr{K}^2_{\mathrm{fin}} (\varsigma))$ is hereditarily undecidable. Proof. Let $\Phi_R (x_1,x_2)$ be as in the statement of Proposition 7.4. Given a $\sigma$-sentence $\Phi$, define $\rho (\Phi)$ to be the result of replacing each $R (x,y)$ in $\Phi$ by $\Phi_R (x,y)$. Take
$$
\begin{equation*}
\tau^{\ast} (\Phi) := \Phi_{\mathrm{spec}} \to \tau (\Phi),
\end{equation*}
\notag
$$
where $\Phi_{\mathrm{spec}}$ denotes the “specification” sentence
$$
\begin{equation*}
\forall\, x\ \neg \Phi_R (x,x) \wedge \forall\, x_1\ \forall\, x_2\ (\Phi_R (x_1,x_2) \to \Phi_R (x_2,x_1)).
\end{equation*}
\notag
$$
Then one can proceed as in the proof of Theorem 5.3. $\Box$ Of course, we also have the following result. Corollary 7.6. Suppose that $\varsigma$ extends $\langle P^1 \rangle$. Then $\Sigma_2 \text{-} \mathrm{Th}(\mathscr{K}^2_{\mathrm{fin}} (\varsigma))$ is $\Pi^0_1$-complete. Evidently, the condition “$\varsigma$ extends $\langle =, c \rangle$ or $\langle P^1 \rangle$” can be replaced by “$\varsigma$ does not coincide with $\langle = \rangle$”. On the other hand, it is rather easy to prove that the validity problem for $\mathscr{L}_2( \langle = \rangle )$-sentences is decidable. Consequently, for every sufficiently rich $\varsigma$, the validity problem for $\Sigma_2$-$\mathscr{L}_2 (\varsigma)$-sentences is undecidable. It will soon be shown that this cannot be improved. § 8. Concerning $\Pi_2$-fragmentsWe aim to prove the analogues of Theorem 2.4 for $\mathscr{L}_1$ and $\mathscr{L}_2$. Technically, it is easier to start with $\mathscr{L}_2$, and then deduce the desired result for $\mathscr{L}_1$ from that for $\mathscr{L}_2$. Assume $\varsigma$ contains at least one constant symbol. For convenience, we shall write $\mathrm{Sent}_{\varsigma}^{\circ}$ for the collection of all quantifier-free $\sigma$-sentences. Given a $\varsigma$-structure $\mathfrak{A}$, let
$$
\begin{equation*}
\mathrm{Th}^{\circ} (\mathfrak{A}) := \{ \Phi \in \mathrm{Sent}_{\varsigma}^{\circ} \mid \mathfrak{A} \vDash \Phi \}.
\end{equation*}
\notag
$$
Now consider an arbitrary $\mathscr{L}_2 (\varsigma)$-structure $\mathcal{M} = \langle D, \Omega, \pi, \mathsf{p} \rangle$. We are going to describe a special $\mathscr{L}_2 (\varsigma)$-structure
$$
\begin{equation*}
\mathcal{M}_{\circ} = \langle D_{\circ}, \Omega_{\circ}, \pi_{\circ}, \mathsf{p}_{\circ} \rangle
\end{equation*}
\notag
$$
which satisfies the same quantifier-free $\mathscr{L}_2 (\varsigma)$-sentences. For this purpose, we define the equivalence relation $\equiv$ on $\Omega$ as follows:
$$
\begin{equation*}
\omega_1 \equiv \omega_2 \quad :\Longleftrightarrow \quad \mathrm{Th}^{\circ}(\pi (\omega_1))= \mathrm{Th}^{\circ}(\pi (\omega_2)).
\end{equation*}
\notag
$$
For each $\omega \in \Omega$, denote by $[\omega]$ the equivalence class of $\omega$ under $\equiv$. Take $\Omega_{\circ}$ to be the set of all such classes. The discrete distribution $\mathsf{p}_{\circ}$ on $\Omega_{\circ}$ is then given by
$$
\begin{equation*}
\mathsf{p}_{\circ} ([\omega]) := \sum_{\omega' \in [\omega]} \mathsf{p}(\omega').
\end{equation*}
\notag
$$
Finally, let $D_{\circ}$ consist of all constant symbols in $\varsigma$, and for each $\omega \in \Omega$, define $\pi_{\circ} ([\omega])$ to be the $\varsigma$-structure with domain $D_{\circ}$ such that10
$$
\begin{equation*}
\begin{aligned} \, c^{\pi_{\circ} ([\omega])} &:= c, \\ P^{\pi_{\circ} ([\omega])} &:= \{ (t_1, \dots, t_n) \in D_{\circ}^n \mid \pi (\omega) \vDash P (t_1, \dots, t_n)\}. \end{aligned}
\end{equation*}
\notag
$$
This completes the description of $\mathcal{M}_{\circ}$. And it is straightforward to verify that, for every quantifier-free $\mathscr{L}_2 (\varsigma)$-sentence $\Phi$,
$$
\begin{equation}
\mathcal{M} \Vdash \Phi \quad \Longleftrightarrow \quad \mathcal{M}_{\circ} \Vdash \Phi.
\end{equation}
\tag{$\star$}
$$
From $(\star)$ we can get the finite model property for $\mathscr{L}_2 (\varsigma)$-sentences without quantifiers and, with the help of Proposition 4.2, the corresponding decidability result. Proposition 8.1. The quantifier-free fragments of $\mathrm{Th}(\mathscr{K}^2_{\mathrm{all}} (\varsigma))$ and $\mathrm{Th}(\mathscr{K}^2_{\mathrm{fin}} (\varsigma))$ coincide. Moreover, the fragment in question is decidable. Proof. Clearly, we may assume $\varsigma$ is finite, provided that our decision procedure will be uniform in $\varsigma$, of course. Take $N$ to be the number of atomic $\varsigma$-sentences. Then, for any $\mathscr{L}_2 (\varsigma)$-structure $\mathcal{M}$, so, in particular, $\mathcal{M}_{\circ}$ is finite.
Let us now consider an arbitrary quantifier-free $\mathscr{L}_2 (\varsigma)$-sentence $\Phi$. Obviously, if $\Phi \in \mathrm{Th}(\mathscr{K}^2_{\mathrm{all}} (\varsigma))$, then $\Phi \in \mathrm{Th}(\mathscr{K}^2_{\mathrm{fin}} (\varsigma))$. For the converse, suppose that $\Phi$ does not belong to $\mathrm{Th}(\mathscr{K}^2_{\mathrm{all}} (\varsigma))$, that is, $\mathcal{M} \nVdash \Phi$ for some $\mathscr{L}_2 (\varsigma)$-structure $\mathcal{M}$. Then $\mathcal{M}_{\circ} \nVdash \Phi$ by $(\star)$. Thus the quantifier-free theories of $\mathscr{K}^2_{\mathrm{all}} (\varsigma)$ and $\mathscr{K}^2_{\mathrm{fin}} (\varsigma)$ coincide with that of $\mathscr{K}^2_{2^N} (\varsigma)$, which is decidable by11 Proposition 4.2. $\Box$ Further, by modifying the above argument we get the following result. Theorem 8.2. $\Pi_2 \text{-} \mathrm{Th}(\mathscr{K}^2_{\mathrm{fin}} (\varsigma))$ is decidable. Moreover, Proof. Again, we may assume $\varsigma$ is finite.
Consider an arbitrary $\Pi_2$-$\mathscr{L}^2 (\varsigma)$-sentence $\Phi$. By definition, $\Phi$ has the form
$$
\begin{equation*}
\forall\, x_0 \, \dots\, \forall\, x_n\ \exists\, y_0 \, \dots\, \exists\, y_k\ \Psi(x_0, \dots, x_n, y_1, \dots, y_0),
\end{equation*}
\notag
$$
where $\Psi$ is quantifier-free. Let $\varsigma^{\ast}$ be the signature obtained from $\varsigma$ by adding $n$ new constant symbols $c_0$, …, $c_n$. Denote by $\mathrm{C}$ the collection of all constant symbols in $\varsigma^{\ast}$. Take $N$ to be the number of atomic $\varsigma^{\ast}$-sentences.
Next, we call a $\mathscr{L}^2(\varsigma^{\ast})$-structure $\mathcal{M}$ special if and only if each $c \in \{ c_1, \dots, c_n\}$ is interpreted rigidly, that is, for all $\omega_1, \omega_2 \in \Omega$, Denote by $\mathscr{K}_{\bullet}$ the class of all such structures. Observe that
$$
\begin{equation*}
\Phi\in \mathrm{Th} \bigl( \mathscr{K}^2_{\mathrm{all}} (\varsigma) \bigr) \quad \Longleftrightarrow \quad \exists\, \vec{y}\ \Psi (\mathbf{c},\vec{y})\in \mathrm{Th}(\mathscr{K}_{\bullet}),
\end{equation*}
\notag
$$
where $\Psi (\mathbf{c},\vec{y})$ abbreviates $\Psi(c_1, \dots, c_n, y_1, \dots, y_k)$. And this remains true if we restrict ourselves to finite structures on both sides. So, it suffices to show that
$$
\begin{equation*}
\exists\, \vec{y}\ \Psi (\mathbf{c},\vec{y})\in \mathrm{Th}(\mathscr{K}_{\bullet}) \quad \Longleftrightarrow \quad \exists\, \vec{y}\ \Psi (\mathbf{c},\vec{y})\in \mathrm{Th}(\mathscr{K}_{\bullet} \cap \mathscr{K}^2_{\mathrm{fin}} (\varsigma)).
\end{equation*}
\notag
$$
The implication from left to right is obvious. For the other direction, suppose that $\exists\, \vec{y}\ \Psi (\mathbf{c},\vec{y}\,)$ does not belong to $\mathrm{Th}(\mathscr{K}_{\bullet})$, that is, $\mathcal{M} \nVdash \exists\, \vec{y}\ \Psi (\mathbf{c},\vec{y}\,)$ for some special $\mathscr{L}^2(\varsigma^{\ast})$-structure $\mathcal{M}$. Hence we also have $\mathcal{M} \nVdash \bigvee_{\vec{t} \in \mathrm{C}^k}\Psi(\mathbf{c}, \vec{t}\;)$. Then $\mathcal{M}_{\circ} \nVdash \bigvee_{\vec{t} \in \mathrm{C}^k} \Psi(\mathbf{c}, \vec{t}\;)$ by $(\star)$. Since $D_{\circ}$ equals $\mathrm{C}$, this is equivalent to $\mathcal{M}_{\circ} \nVdash \exists\, \vec{y}\ \Psi (\mathbf{c},\vec{y}\,)$. Note that $\mathcal{M}_{\circ}$ is special and has size at most $2^N$.
It follows that the $\Pi_2$-theories of $\mathscr{K}^2_{\mathrm{all}} (\varsigma)$ and $\mathscr{K}^2_{\mathrm{fin}} (\varsigma)$ coincide with that of $\mathscr{K}^2_{2^N} (\varsigma)$, which is decidable by Proposition 4.2. $\Box$ Then, instead of proving the analogous result for $\mathscr{L}_1$ directly, one can utilize a special translation of $\mathscr{L}_1$ into $\mathscr{L}_2$ described in § 6 of [1]. Given a signature $\varsigma$, let $\varsigma'$ be obtained from $\varsigma$ by adding countably many new constant symbols $c_0,c_1,c_2,\dots$ . Theorem 8.3 (see [1]). Suppose that $\varsigma$ contains the equality symbol. Then there exists a computable translation $\tau^{12}$ of $\mathscr{L}_1 (\varsigma)$ into $\mathscr{L}_2 (\varsigma')$ such that, for all $\mathscr{L}_1 (\varsigma)$-sentences $\Phi$ and $\mathtt{s} \in \{ \mathrm{all}, \mathrm{fin}\}$, Moreover, for each $n \in \mathbb{N}$, if $\Phi$ is in $\Pi_{n + 2}$, so is $\tau^{12} (\Phi)$. Combining Theorems 8.2 and 8.3, we get the following result. Theorem 8.4. $\Pi_2 \text{-} \mathrm{Th}(\mathscr{K}^1_{\mathrm{fin}} (\varsigma))$ is decidable. Moreover, Consequently, the undecidability results of §§ 6 and 7 turn out to be precise. So, the decision problems for $\mathscr{L}_1$ and $\mathscr{L}_2$ are solved. 
Citation in format AMSBIB
\Bibitem{Spe25} |
|
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|