| Izvestiya: Mathematics |
|
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper) On the coprimeness relation from the viewpoint of monadic second-order logic S. O. Speranskia, F. N. Pakhomovab a Steklov Mathematical Institute of Russian Academy of Sciences, Moscow b Ghent University
Bibliographic databases:
     § 1. IntroductionWe shall be concerned with relatively weak arithmetical structures; so our work can be seen as a study in “weak arithmetics” (using the terminology of [1]). Many interesting questions in this area are about two kinds of definability: (i) first-order definability; (ii) monadic second-order definability.1 In particular, there are beautiful results on (i), concerned with divisibility and coprimeness, e.g. those in [4], inspired by the seminal paper of Robinson [5] (see also [6]). As for (ii), divisibility has been investigated in [7]. The present article will deal with coprimeness. In what follows by a formula we shall mean a monadic second-order formula, unless otherwise specified. Notice that the symbol $=$ will be treated as non-logical (which may or may not belong to a given signature). For convenience, zero will not be viewed as an element of $\mathbb{N}$, i.e. A subset of $\mathbb{N}$ is called a $\Pi^1_n$-set if it is definable in the standard model of Peano arithmetic by a $\Pi^1_n$-formula. Let $\sigma$ be a signature and $\mathfrak{A}$ a $\sigma$-structure with domain $\mathbb{N}$. Now consider the following condition: From the viewpoint of monadic second-order logic, if $\mathfrak{A}$ satisfies $(*)$, then we have a very good understanding of what can be defined in $\mathfrak{A}$.It was proved in [3] that $(*)$ holds for the standard model of Presburger’s arithmetic. Next, it was shown in [7] that $(*)$ holds for the structure of the natural numbers with the divisibility relation, as well as for all its expansions (including the standard model of Skolem’s arithmetic). But what happens if we replace divisibility by coprimeness? Take Here $\bot$ is a binary predicate symbol, whose intended interpretation is the coprimeness relation. Denote the corresponding $\sigma_{\circ}$-structure by $\mathfrak{C}$. So for all $m, n \in \mathbb{N}$
$$
\begin{equation*}
\mathfrak{C} \models {m \bot n} \quad \Longleftrightarrow \quad m \text{ and }n\text{ have no common prime divisors}.
\end{equation*}
\notag
$$
In this article, we shall establish that: (a) $\mathfrak{C}$ satisfies $(*)$; (b) there is an expansion $\mathfrak{C}'$ of $\mathfrak{C}$ such that some computable subsets of $\mathbb{N}$ that are closed under automorphisms of $\mathfrak{C}'$ cannot be defined in $\mathfrak{C}'$ by monadic second-order formulas.2 Obviously, (b) implies that ($*$) fails for certain expansions of $\mathfrak{C}$. Therefore the case of coprimeness is quite different from that of divisibility. Remark. For simplicity, $(*)$ is stated for subsets of $\mathbb{N}$, but it can also be stated for subsets of $\mathbb{N}^2$, $\mathbb{N}^3$, etc. The proofs in our article can be easily modified to work with such subsets, and the same applies to [7]; since the proofs in [3] were much simpler, they were initially presented in this way. So in particular, $\mathfrak{C}$ will satisfy the analogues of $(*)$ for subsets of $\mathbb{N}^2$, $\mathbb{N}^3$, etc. § 2. PreliminariesLet $\sigma$ be a signature. Recall that a $\sigma$-formula is in $\Pi^1_n$ if it has the form
$$
\begin{equation*}
\underbrace{{\forall\, \vec{X}_1}\ {\exists\, \vec{X}_2}\dots \vec{X}_n}_{n-1 \text{ alternations}} \Psi,
\end{equation*}
\notag
$$
where $\vec{X}_1,\vec{X}_2,\dots,\vec{X}_n$ are tuples of set variables and $\Psi$ contains no set quantifiers. Further, a $\Pi^1_n$-$\sigma$-formula will be called special if each of $\vec{X}_1,\vec{X}_2,\dots,\vec{X}_n$ has length one. Take Here $+$ is a ternary predicate symbol (not a binary function symbol), whose intended interpretation is the graph of the addition function. Denote the corresponding $\sigma_{\bullet}$-structure by $\mathfrak{P}$; thus $\mathfrak{P}$ may be viewed as the standard model of Presburger’s arithmetic. To show that $(*)$ holds for $\mathfrak{C}$, we shall use Theorem 2.1 (see [3]). Let $n \in \mathbb{N}$ and $S \subseteq \mathbb{N}$. Suppose $S$ is a $\Pi^1_n$-set. Then $S$ is definable in $\mathfrak{P}$ by a special $\Pi^1_n$-formula. In other words, $\mathfrak{P}$ satisfies $(*)$. Let $\mathbb{P}$ denote the set of all prime numbers. One can easily verify that $\mathbb{P}$ is not closed under automorphisms of $\mathfrak{C}$, and hence not definable in $\mathfrak{C}$. Take
$$
\begin{equation*}
\begin{aligned} \, \mathbb{P}^{\sharp} &:=\text{the set of all prime powers} \\ &\, =\{ p^n \mid p \in \mathbb{P}\text{ and }n \in \mathbb{N}\}. \end{aligned}
\end{equation*}
\notag
$$
Evidently, $\{1\}$ and $\mathbb{P}^{\sharp}$ are definable in $\mathfrak{C}$ by the first-order formulas
$$
\begin{equation*}
\begin{aligned} \, \operatorname{One}(x) &:= \forall\, u\ u \bot x\quad\!\! \text{and}\quad\!\! \\ \operatorname{PPow}(x) &:= \neg\, \operatorname{One}(x) \wedge \forall\, u\ \forall\, v\ (\neg\, u \bot x \wedge \neg\, v \bot x \to \neg\, u \bot v), \end{aligned}
\end{equation*}
\notag
$$
respectively. These formulas will be employed in our proofs. Next, for each $n \in \mathbb{N}$ we write $[\![n]\!]$ for the set of all prime divisors of $n$, i.e.
$$
\begin{equation*}
[\![n]\!]:= \{ p \in \mathbb{P} \mid p \text{ divides }n\}.
\end{equation*}
\notag
$$
Obviously, for all $m, n \in \mathbb{N}$,
$$
\begin{equation*}
\mathfrak{C} \models m \bot n \quad \Longleftrightarrow \quad [\![m]\!] \cap [\![n]\!]= \varnothing.
\end{equation*}
\notag
$$
Intuitively, if $[\![m]\!]$ and $[\![n]\!]$ coincide, then $m$ and $n$ are indistinguishable in $\mathfrak{C}$ by second-order or even higher order formulas. To make this claim more precise, consider Let $\mathscr{C}$ be the $\sigma_{\circ}$-structure with domain $\mathcal{N}$ in which the symbol $\bot$ is interpreted as
$$
\begin{equation*}
\{(M, N) \in \mathcal{N}^2 \mid M \cap N=\varnothing\}.
\end{equation*}
\notag
$$
Then we have the following. Proof. Take $\approx$ to be the relation “$m$ and $n$ have the same prime divisors”, i.e. Obviously, $\approx$ is a congruence relation on $\mathfrak{C}$. Consider the quotient-structure $\mathfrak{C} /{\approx}$ of $\mathfrak{C}$ modulo $\approx$. Define the function $\eta$ from $\mathbb{N} /{\approx}$ to $\mathcal{N}$ by where $[n]_{\approx}$ denotes the equivalence class of $n$ modulo $\approx$. Then $\eta$ is an isomorphism from $\mathfrak{C}/{\approx}$ onto $\mathscr{C}$. Thus for any $\sigma$-formula $\Phi(x)$ and $n\in\mathbb{N}$, as desired. $\Box$ For every set $S$ we shall denote by $\operatorname{card}(S)$ the cardinality of $S$. Define the function $\iota$ from $\mathbb{N}$ to $\mathbb{N}$ by In particular, $\iota(n)=1$ iff $n=1$. Now consider
$$
\begin{equation*}
\begin{aligned} \, \sim &:= \{(m,n) \in \mathbb{N}^2 \mid \iota(m)=\iota(n)\} \quad \text{and} \\ \oplus &:=\{ (m,n,k) \in \mathbb{N}^3 \mid \iota(m)+\iota(n)=\iota(k)\}. \end{aligned}
\end{equation*}
\notag
$$
Let $\mathfrak{P}^{\iota}$ be the $\sigma_{\bullet}$-structure with domain $\mathbb{N}$ in which the symbols $+$ and $=$ are interpreted as $\oplus$ and $\sim$ respectively. There is an intimate relationship between $\mathfrak{P}$ and $\mathfrak{P}^{\iota}$. Proof. Clearly, $\sim$ is a congruence relation on $\mathfrak{P}^{\iota}$. Consider the quotient-structure $\mathfrak{P}^{\iota}/{\sim}$ of $\mathfrak{P}^{\iota}$ modulo $\sim$. Define the function $\xi$ from $\mathbb{N}/{\sim}$ to $\mathbb{N}$ by where $[n]_{\sim}$ denotes the equivalence class of $n$ modulo $\sim$. Then $\xi$ is an isomorphism from $\mathfrak{P}^{\iota}/{\sim}$ onto $\mathfrak{P}$. Thus the result follows. $\Box$ Later it will be shown that $\sim$ and $\oplus$ are “$\Delta^1_1$-definable” in $\mathfrak{C}$. More precisely, we shall prove that these relations and their complements are definable in $\mathfrak{C}$ by $\Pi^1_1$-formulas.3 § 3. Definability in $\mathfrak{C}$The aim of this section is to prove that $\mathfrak{C}$ satisfies $(*)$. Theorem 3.1. Let $n \in \mathbb{N}$ and $S \subseteq \mathbb{N}$. Suppose $S$ is a $\Pi^1_n$-set closed under automorphisms of $\mathfrak{C}$. Then $S$ is definable in $\mathfrak{C}$ by a special $\Pi^1_n$-formula. Our argument will use several lemmas. We start with a simple fact about $\iota$. Lemma 3.2. For any $n \in \mathbb{N}$ and $S \subseteq \mathbb{N}$: (i) if $S$ is a $\Pi^1_n$-set, then $\iota [S]$ and $\iota^{-1} [S]$ are also $\Pi^1_n$-sets; (ii) $S$ is closed under automorphisms of $\mathfrak{C}$ iff $S=\iota^{-1} [\iota[S]]$. Proof. (i) It is known that the class of all $\Pi^1_n$-subsets of $\mathbb{N}$ is closed under computable images and preimages (see [8], Theorem 16-III). Notice that $\iota$ is computable.
(ii) From right to left, suppose $S=\iota^{-1} [\iota[S]]$. Observe that for each $m \in \mathbb{N}$ the predicate “$x$ has exactly $m$ prime divisors” is first-order definable in $\mathfrak{C}$, e.g. by
$$
\begin{equation*}
\begin{aligned} \, &\exists\, u_1, u_2, \dots, u_m\ \biggl( \biggl( \bigwedge_{i=1}^{m-1} \bigwedge_{j=i+1}^{m} u_i \bot u_j \biggr) \wedge \biggl( \bigwedge_{i=1}^{m} \neg\, x \bot u_i \biggr) \biggr) \\ &\qquad \wedge \neg\, \exists u_1, u_2, \dots, u_{m+1}\ \biggl( \biggl( \bigwedge_{i=1}^{m} \bigwedge_{j=i+1}^{m+1} u_i \bot u_j \biggr) \wedge \biggl( \bigwedge_{i=1}^{m+1} \neg\, x \bot u_i \biggr) \biggr). \end{aligned}
\end{equation*}
\notag
$$
So if $k \in S$, and $\xi$ is an automorphism of $\mathfrak{C}$, then $\iota(\xi(k))=\iota(k)$, which gives $\xi(k) \in \iota^{-1}[\iota[S]]$, i.e. $\xi(k)\in S$. Thus $S$ is closed under automorphisms of $\mathfrak{C}$.
From left to right, suppose $S$ is closed under automorphisms of $\mathfrak{C}$. Obviously, $S$ is a subset of $\iota^{-1} [\iota[S]]$. For the other direction, let $m \in \iota^{-1} [\iota[S]]$, i.e. $\iota (m)=\iota(k)$ for some $k \in S$. Then we can find an automorphism $\xi$ of $\mathfrak{C}$ such that $\xi(k)=m$. Hence $m \in S$. Therefore $S$ coincides with $\iota^{-1} [\iota[S]]$. $\Box$ For what follows, we introduce two extensions of $\sigma_{\circ}$:
$$
\begin{equation*}
\sigma_{\circ}[U]:= \sigma_{\circ} \cup \{U^1\} \quad \text{and} \quad \sigma_{\circ}[U, V]:= \sigma_{\circ}[U] \cup \{V^1\}.
\end{equation*}
\notag
$$
Here $U$ and $V$ are distinct unary predicate symbols, which may also be treated as set variables if needed. In the proofs below, a key role will be played by the first-order $\sigma_{\circ}$-formulas
$$
\begin{equation*}
\begin{aligned} \, \operatorname{Cup} (x,y,z) &:= \forall\, u\ ((u \bot x \wedge u \bot y) \leftrightarrow u \bot z) \quad \text{and} \\ \operatorname{DCup}(x,y,z) &:= \operatorname{Cup}(x,y,z) \wedge x \bot y. \end{aligned}
\end{equation*}
\notag
$$
Clearly, for any $n, m, k \in \mathbb{N}$,
$$
\begin{equation*}
\begin{aligned} \, \mathfrak{C} \models \operatorname{Cup}(n,m,k) \quad &\Longleftrightarrow \quad [\![n]\!] \cup [\![m]\!]=[\![k]\!]; \\ \mathfrak{C} \models \operatorname{DCup}(n,m,k) \quad &\Longleftrightarrow \quad [\![n]\!] \cup [\![m]\!]=[\![k]\!] \text{ and } [\![n]\!] \cap [\![m]\!]=\varnothing. \end{aligned}
\end{equation*}
\notag
$$
Given $S \subseteq \mathbb{N}$, denote $\bigcup_{n \in S} [\![n]\!]$ by $[\![S]\!]$. Lemma 3.3. Suppose $A \subseteq \mathbb{N}$ is such that both $[\![A]\!]$ and $\mathbb{P} \setminus [\![A]\!]$ are infinite. Take Then there exist two first-order $\sigma_{\circ} [U,V]$-formulas $\operatorname{Eq}(x,y)$ and $\operatorname{Add}(x,y,z)$ that define $\sim$ and $\oplus$ respectively in the $\sigma_{\circ} [U,V]$-expansion $\langle \mathfrak{C}, A, B \rangle$. Proof. Evidently, for all $m, n, k \in \mathbb{N}$,
$$
\begin{equation*}
\begin{aligned} \, m \sim n \quad &\Longleftrightarrow \quad \operatorname{card}([\![m]\!])=\operatorname{card}([\![n]\!]); \\ (m,n,k) \in \oplus \quad &\Longleftrightarrow \quad 1+\operatorname{card}([\![m]\!])+\operatorname{card}([\![n]\!])= \operatorname{card} ([\![k]\!]). \end{aligned}
\end{equation*}
\notag
$$
Moreover, if $\operatorname{Eq}(x,y)$ is a first-order $\sigma_{\circ}[U,V]$-formula that defines $\sim$ in $\langle \mathfrak{C}, A, B \rangle$, then one can use the first-order $\sigma_{\circ} [U,V]$-formula
$$
\begin{equation*}
\begin{aligned} \, \operatorname{Add}(x,y,z) := \exists\, \widetilde{x}, \widetilde{y}, u, v \ &\bigl( \operatorname{Eq}(x,\widetilde{x}) \wedge \operatorname{Eq}(y, \widetilde{y}) \wedge \operatorname{DCup}(\widetilde{x}, \widetilde{y}, u) \\ &\qquad\wedge \operatorname{PPow}(v) \wedge \operatorname{DCup}(u,v,z)\bigr) \end{aligned}
\end{equation*}
\notag
$$
to define $\oplus$ in $\langle \mathfrak{C}, A, B \rangle$. Therefore we shall focus on $\sim$.
Let us start by proving that
$$
\begin{equation*}
R:= \{(m,n) \in \mathbb{N}^2 \mid [\![m]\!] \subseteq [\![A]\!], \, [\![n]\!] \subseteq \mathbb{P} \setminus [\![A]\!] \text{ and } \operatorname{card}([\![m]\!])=\operatorname{card}([\![n]\!])\}
\end{equation*}
\notag
$$
is first-order definable in $\langle \mathfrak{C}, A, B \rangle$. To this end, consider the first-order $\sigma_{\circ}[U]$-formulas
$$
\begin{equation*}
\begin{aligned} \, \Theta_1(x) &:= \forall\, u\ \bigl( \operatorname{PPow}(u) \wedge \neg\, u \bot x \to \exists\, y\ (U(y) \wedge \neg\, u \bot y)\bigr) \quad \text{and} \\ \Theta_2(x) &:= \forall\, u\ \bigl( \operatorname{PPow}(u) \wedge \neg\, u \bot x \to \forall\, y\ (U(y) \to u \bot y) \bigr). \end{aligned}
\end{equation*}
\notag
$$
Obviously, for every $n \in \mathbb{N}$,
$$
\begin{equation*}
\begin{aligned} \, \langle \mathfrak{C}, A\rangle \models \Theta_1(n) \quad &\Longleftrightarrow \quad [\![n]\!] \subseteq [\![A]\!]; \\ \langle \mathfrak{C}, A\rangle \models \Theta_2(n) \quad &\Longleftrightarrow \quad [\![n]\!] \subseteq \mathbb{P} \setminus [\![A]\!]. \end{aligned}
\end{equation*}
\notag
$$
Hence the first-order $\sigma_{\circ}[U,V]$-formula
$$
\begin{equation*}
\Phi_R(x,y) := \Theta_1(x) \wedge \Theta_2(y) \wedge \exists\, z\ \bigl( \operatorname{Cup}(x,y,z) \wedge V(z) \bigr)
\end{equation*}
\notag
$$
defines $R$ in $\langle \mathfrak{C}, A, B \rangle$. Next, we wish to show that
$$
\begin{equation*}
Q:= \{(m,n) \in \mathbb{N}^2 \mid [\![m]\!] \subseteq [\![A]\!] \text{ and } \operatorname{card}([\![m]\!])= \operatorname{card}([\![n]\!])\}
\end{equation*}
\notag
$$
is first-order definable in $\langle \mathfrak{C}, A, B \rangle$ too. Informally, this can be done as follows: (a) find $k \in \mathbb{N}$ such that $[\![k]\!] \subseteq \mathbb{P} \setminus [\![A]\!]$, $[\![k]\!] \cap [\![n]\!]=\varnothing$ and $\operatorname{card} ([\![k]\!])=\operatorname{card}([\![n]\!] \cap [\![A]\!])$; (b) check whether $\operatorname{card}([\![m]\!])= \operatorname{card}([\![k]\!] \cup ([\![n]\!] \setminus [\![A]\!]))$.
Formally, we use the first-order $\sigma_{\circ} [U,V]$-formula
$$
\begin{equation*}
\begin{aligned} \, \Phi_Q(x,y) &:= \Theta_1(x) \wedge \exists\, u, v, \widetilde{u}, \widetilde{y}\ \bigl( \Theta_1(u) \wedge \Theta_2(v) \wedge \operatorname{Cup}(u,v,y) \\ &\qquad \wedge \Theta_2(\widetilde{u}) \wedge \Phi_R(u, \widetilde{u}) \wedge \operatorname{DCup}(\widetilde{u}, v, \widetilde{y}) \wedge \Phi_R(x, \widetilde{y}) \bigr) \end{aligned}
\end{equation*}
\notag
$$
to define $Q$ in $\langle \mathfrak{C}, A, B \rangle$. Finally, consider the first-order $\sigma_{\circ} [U,V]$-formula One easily verifies that it defines $\sim$ in $\langle \mathfrak{C}, A, B \rangle$. $\Box$ Furthermore, we have the following. Lemma 3.4. There exists a first-order $\sigma_{\circ} [U,V]$-sentence $\operatorname{PrA}$ such that for every $\sigma_{\circ} [U,V]$-expansion $\mathfrak{A}$ of $\mathfrak{C}$, Proof. Clearly, if $\operatorname{Eq}(x,y)$ defines $\sim$ in $\mathfrak{A}$, then $\operatorname{Add}(x,y,z)$ defines $\oplus$ in $\mathfrak{A}$. Therefore we shall focus on $\operatorname{Eq}(x,y)$. Let $\operatorname{PrA}$ be the conjunction of the following first-order $\sigma_{\circ} [U,V]$-sentences:
(i) $\forall\, x, y\ \bigl(\operatorname{One}(x) \to (\operatorname{Eq}(x,y) \leftrightarrow \operatorname{One}(y)) \bigr)$; (ii) $\forall\, x, y\ \bigl( \operatorname{One}(y) \to (\operatorname{Eq}(x,y) \leftrightarrow \operatorname{One}(x)) \bigr)$; (iii) $\forall\, x, y\ \bigl( \operatorname{PPow}(x) \wedge \operatorname{PPow}(y) \to \operatorname{Eq}(x,y) \bigr)$; (iv) $\forall \, x, y, z, u, v, w\ \bigl(\operatorname{DCup} (x,y,z) \wedge \operatorname{DCup}(u,v,w) \wedge \operatorname{Eq}(x,u) \to (\operatorname{Eq}(y,v) \leftrightarrow \operatorname{Eq}(z,w)) \bigr)$. Suppose $\operatorname{Eq}(x,y)$ defines $\sim$ in $\mathfrak{A}$. Then $\operatorname{PrA}$ holds in $\mathfrak{A}$, as can be readily verified. In the other direction, suppose $\mathfrak{A} \models \operatorname{PrA}$. We want to show that for all $m, n \in \mathbb{N}$,
$$
\begin{equation*}
\mathfrak{A} \models \operatorname{Eq}(m,n) \quad \Longleftrightarrow \quad m \sim n.
\end{equation*}
\notag
$$
By induction on $\lambda (m,n):= \min\{\iota(m), \iota(n)\}$: – Suppose $\lambda (m,n)=1$. Then $m=1$ or $n=1$. So the result follows from (i) or (ii). – Suppose $\lambda(n,m) \geqslant 2$. Then there exist $p, q \in \mathbb{P}^{\sharp}$ and $i, j \in \mathbb{N}$ such that
$$
\begin{equation*}
\mathfrak{C} \models \operatorname{DCup}(p,i,m) \quad \text{and} \quad \mathfrak{C} \models \operatorname{DCup}(q,j,n).
\end{equation*}
\notag
$$
Notice that $\mathfrak{A} \models \operatorname{Eq}(p,q)$ by (iii). Moreover, since $\lambda(i,j)=\lambda(n,m) -1 < \lambda(n,m)$, we can apply the inductive hypothesis to $i$, $j$. Hence
$$
\begin{equation*}
\mathfrak{A} \models \operatorname{Eq}(m,n) \quad \stackrel{\text{(iv)}}{\Longleftrightarrow} \quad \mathfrak{A} \models \operatorname{Eq}(i, j) \quad \Longleftrightarrow \quad i \sim j \quad \Longleftrightarrow \quad n \sim m.
\end{equation*}
\notag
$$
Thus $\operatorname{Eq}(x,y)$ defines $\sim$ in $\mathfrak{A}$. $\Box$ We will also need Lemma 3.5. Let $n \in \mathbb{N}$ and $S \subseteq \mathbb{N}$. Suppose $S$ is defined $\mathfrak{C}$ by a formula $\Phi(x)$ of the form where $X_1$, …, $X_n$, $X_n'$ are distinct set variables, $\{\mathrm{Q}_1, \dots, \mathrm{Q}_n\} \subseteq \{ \forall, \exists\}$ and $\Psi$ contains no set quantifiers. Then $S$ can also be defined in $\mathfrak{C}$ by a formula of the form with $\widetilde{\Psi}$ containing no set quantifiers. Proof. By Proposition 2.2, we may use $\mathscr{C}$ instead of $\mathfrak{C}$. Given $p \in \mathbb{P}$, take Denote by $\mathscr{C}_p$ the substructure of $\mathscr{C}$ with domain $\mathcal{N}_p$. It is easy to show that for any $p \in \mathbb{P}$ and $N \in \mathcal{N}_p$ there exists an isomorphism $\xi^N_p$ from $\mathscr{C}$ onto $\mathscr{C}_p$ such that $\xi^N_p(N)=N$. These isomorphisms will play a key role in what follows.
Now let $n$, $S$ and $\Phi(x)$ be as in the statement of our lemma. Without loss of generality, we may assume $\mathrm{Q}_n=\forall$; otherwise one can pass from $S$ to its complement. Obviously, the part $\Psi$ may contain free occurrences not only of $x$ but also of $X_1, \dots, X_n$ or $X_n'$. Thus Fix an individual variable $\mathtt{p}$ that does not occur in $\Psi$ – it will be treated as a parameter of a special kind. Take
$$
\begin{equation*}
\Psi^{\mathtt{p}}:= \text{the relativization of }\ \Psi \text{ to }x \bot \mathtt{p}.
\end{equation*}
\notag
$$
In other words, $\Psi^p$ is obtained from $\Psi$ by replacing all subformulas of the forms $\forall\, u\ \Theta$ and $\exists\, u\ \Theta$ by
$$
\begin{equation*}
\forall\, u\ (u \bot p \to \Theta) \quad \text{and} \quad \exists\, u\ (u \bot p \to \Theta)
\end{equation*}
\notag
$$
respectively. Intuitively, if $\mathtt{p}$ is assigned $\{p\}$, then all quantifiers in $\Psi^{\mathtt{p}}$ range over $\mathcal{N}_p$. Then for any $p \in \mathbb{P}$, $N \in \mathcal{N}_p$ and $S_1, \dots, S_n, S_n' \subseteq \mathcal{N}$,
$$
\begin{equation*}
\mathscr{C} \models \Psi(N, S_1, \dots, S_n, S_n') \quad \Longleftrightarrow \quad \mathscr{C} \models \Psi^{\mathtt{p}}\bigl(\{p\}, N, \xi^N_p[S_1], \dots, \xi^N_p[S_n], \xi^N_p[S_n'] \bigr),
\end{equation*}
\notag
$$
which easily implies
$$
\begin{equation*}
\begin{aligned} \, &\mathscr{C} \models \forall\,X_n\ \forall\, X_n'\ \Psi(N, S_1, \dots, S_{n-1}, X_n, X_n') \\ &\qquad \Longleftrightarrow \quad \mathscr{C} \models \forall\, X_n\ \forall\, X_n'\ \Psi^{\mathtt{p}}\bigl(\{p\}, N, \xi^N_p[S_1], \dots, \xi^N_p[S_{n-1}], X_n, X_n'\bigr). \end{aligned}
\end{equation*}
\notag
$$
Here it does not matter whether $\forall\, X_n$ and $\forall\, X_n'$ on the right-hand side range over subsets of $\mathcal{N}$ or over subsets of $\mathcal{N}_p$. In what follows we shall abbreviate
$$
\begin{equation*}
(S_1, \dots, S_{n-1}) \quad \text{and} \quad (\xi^N_p[S_1], \dots, \xi^N_p[S_{n-1}])
\end{equation*}
\notag
$$
to $\vec{S}$ and $\xi^N_n[\vec{S}]$ respectively. Observe that $\bigl\{\{p\} \mid p \in \mathbb{P} \bigr\}$ can be defined in $\mathscr{C}$ by the first-order formula $\operatorname{PPow}(x)$, i.e. for every $N \in \mathcal{N}$
$$
\begin{equation*}
\mathscr{C} \models \operatorname{PPow}(N) \quad \Longleftrightarrow \quad N=\{p\} \text{ for some }p \in \mathbb{P}.
\end{equation*}
\notag
$$
Hence for any $N \in \mathcal{N}$ and $S_1, \dots, S_{n-1} \subseteq \mathcal{N}$,
$$
\begin{equation*}
\begin{aligned} \, &\mathscr{C} \models \forall\, X_n\ \forall\, X_n'\ \Psi(N,\vec{S}, X_n, X_n') \\ &\qquad \Longleftrightarrow \quad \mathscr{C} \models \forall\, \mathtt{p}\ \bigl( \operatorname{PPow}(\mathtt{p}) \wedge N \bot \mathtt{p} \to \forall\, X_n\ \forall\, X_n'\ \Psi^{\mathtt{p}}(\mathtt{p}, N, \xi^N_p[\vec{S}], X_n, X_n')\bigr). \end{aligned}
\end{equation*}
\notag
$$
Further, for any $p \in \mathbb{P}$ and $A, B \subseteq \mathcal{N}_p$ there exists $C \subseteq \mathcal{N}$ such that
$$
\begin{equation*}
A=C \cap \mathcal{N}_p \quad \text{and} \quad B=\bigl\{ M \setminus \{p\} \bigm| M \in C \text{ and }p \in M \bigr\}.
\end{equation*}
\notag
$$
So pairs of subsets of $\mathcal{N}_p$ can be viewed as subsets of $\mathcal{N}$, and vice versa. More formally, let $\widetilde{\Psi}^{\mathtt{p}}$ be the result of replacing every $y \in X_n'$ by $\exists\, u\ (\operatorname{DCup}(u, \mathtt{p},y) \wedge u \in X_n)$ in $\Psi^{\mathtt{p}}$. Then
$$
\begin{equation*}
\begin{aligned} \, &\mathscr{C} \models \forall\, X_n\ \forall\, X_n'\ \Psi(N, \vec{S}, X_n, X_n') \\ &\qquad \Longleftrightarrow \quad \mathscr{C} \models \forall\, \mathtt{p}\ \bigl( \operatorname{PPow}(\mathtt{p}) \wedge N \bot \mathtt{p} \to \forall\, X_n\ \widetilde{\Psi}^{\mathtt{p}}(\mathtt{p}, N, \xi^N_p[\vec{S}], X_n) \bigr) \\ &\qquad \Longleftrightarrow \quad \mathscr{C} \models \forall\, X_n\ \forall\, \mathtt{p}\ \bigl( \operatorname{PPow}(\mathtt{p}) \wedge N \bot \mathtt{p} \to \widetilde{\Psi}^{\mathtt{p}}(\mathtt{p}, N, \xi^N_p[\vec{S}], X_n) \bigr). \end{aligned}
\end{equation*}
\notag
$$
Consequently, the set $S$ defined in $\mathscr{C}$ by $\Phi(x)$ can also be defined by Thus we have managed to eliminate $X_n'$ in $\Phi(x)$. $\Box$ Now we are ready to obtain the main result. Proof of Theorem 3.1. By Lemma 3.2, $\iota [S]$ is a $\Pi^1_n$-set and $S=\iota^{-1}[\iota[S]]$. Furthermore, by Theorem 2.1, there exists a special $\Pi^1_n$-$\sigma_{\bullet}$-formula $\Phi(x)$ defining $\iota[S]$ in $\mathfrak{P}$. In particular, $\Phi(x)$ has the form where $\Psi$ contains no set quantifiers. Without loss of generality, we may assume that neither $U$ nor $V$ is among $X_1, X_2, \dots, X_n$.4 Obviously, each atomic subformula of $\Psi$ has the form
$$
\begin{equation*}
+(x,y,z), \quad =(x,y) \quad \text{or} \quad x \in X.
\end{equation*}
\notag
$$
Now let $\Psi^{\iota}$ denote the result of replacing every $+ (x,y,z)$ by $\operatorname{Add}(x,y,z)$ and every $=(x,y)$ by $\operatorname{Eq}(x,y)$ in $\Psi$. Take
$$
\begin{equation*}
\Phi^{\iota}:=\begin{cases} \forall\, X_1\ \exists\, X_2\ \dots\ \forall\, X_n\ \forall\, U\ \forall\, V\ (\operatorname{PrA} \to \Psi^{\iota}) &\text{if } n\text{ is odd}, \\ \forall\, X_1\ \exists\, X_2\ \dots \ \exists\, X_n\ \exists\, U\ \exists\, V\ (\operatorname{PrA} \wedge \Psi^{\iota}) &\text{if }n \text{ is even}. \end{cases}
\end{equation*}
\notag
$$
Clearly, for all $n \in \mathbb{N}$,
$$
\begin{equation*}
\mathfrak{C} \models \Phi^{\iota}(n) \quad \stackrel{\text{Lemmas 3.3, 3.4}}{\Longleftrightarrow} \quad \mathfrak{P}^{\iota} \models \Phi(n) \quad \stackrel{\text{Proposition 2.3}} {\Longleftrightarrow} \quad \mathfrak{P} \models \Phi(\iota(n)).
\end{equation*}
\notag
$$
Thus the $\Pi^1_n$-$\sigma_{\circ}$-formula $\Phi^{\iota}$ defines $S$ in $\mathfrak{C}$. Finally, we can apply Lemma 3.5 (twice) to turn $\Phi^{\iota}$ into a special $\Pi^1_n$-$\sigma_{\circ}$-formula. $\Box$ Using Theorem 3.1, one can easily prove that for each $n \in \mathbb{N}$, the set of all special $\Pi^1_n$-sentences true in $\mathfrak{C}$ is $\Pi^1_n$-complete – in this way we strengthen the complexity result about $\mathfrak{C}$ in [7] (see Theorem 5.3). § 4. Concerning expansions of $\mathfrak{C}$The aim of this section is to provide an example of an expansion of $\mathfrak{C}$ that does not satisfy $(*)$. Our example will employ the extended signature where $\operatorname{sq}$ is a unary function symbol, whose intended interpretation is the square function. We shall write $\langle \mathbb{N}; \operatorname{sq}, \bot,=\rangle$ for the corresponding structure.Theorem 4.1. There exists a computable $S \subseteq \mathbb{N}$ such that: $\bullet$ $S$ is closed under automorphisms of $\langle \mathbb{N}; \operatorname{sq}, \bot,= \rangle$; $\bullet$ $S$ is not definable in $\langle \mathbb{N}; \operatorname{sq}, \bot,=\rangle$ (by a monadic formula). Our argument will use some amount of two-sorted monadic second-order logic. Recall that in this logic we have two sorts of individual variables:
$$
\begin{equation*}
x^0,\ y^0,\ z^0,\ \dots \quad \text{and} \quad x^1,\ y^1,\ z^1,\ \dots\,.
\end{equation*}
\notag
$$
There are also two sorts of set variables:
$$
\begin{equation*}
X^0,\ Y^0,\ Z^0,\ \dots \quad \text{and} \quad X^1,\ Y^1,\ Z^1,\ \dots\,.
\end{equation*}
\notag
$$
For each $\varepsilon \in \{ 0, 1 \}$, denote by $\operatorname{Var}^{\varepsilon}$ the collection of all variables of sort $\varepsilon$. Next, let $\sigma_0$ and $\sigma_1$ be two disjoint (one-sorted) signatures. By an atomic $(\sigma_0, \sigma_1)$-formula we mean an atomic $\sigma_0$-formula over $\operatorname{Var}^0$ or an atomic $\sigma_1$-formula over $\operatorname{Var}^1$. For example: $\bullet$ both $x^0 \in X^0$ and $x^1 \in X^1$ are atomic $(\sigma_0,\sigma_1)$-formulas; $\bullet$ neither $x^0 \in X^1$ nor $x^1 \in X^0$ is an atomic $(\sigma_0, \sigma_1)$-formula. Now $(\sigma_0, \sigma_1)$-formulas are built up from atomic $(\sigma_0, \sigma_1)$-formulas using connective symbols and quantifiers in the customary way. Of course, $(\sigma_0, \sigma_1)$-formulas containing no variables of sort $0$ or $1$ may be identified with $\sigma_1$-formulas or $\sigma_0$-formulas respectively. Turning to semantics, for each $\varepsilon \in \{0, 1\}$, let $\mathfrak{A}_{\varepsilon}$ be a $\sigma_{\varepsilon}$-structure. Take $(\mathfrak{A}_0, \mathfrak{A}_1)$ to be the corresponding two-sorted $(\sigma_0, \sigma_1)$-structure. So for every $\varepsilon \in \{0,1\}$: – individual variables of sort $\varepsilon$ range over elements of the domain of $\mathfrak{A}_{\varepsilon}$; – set variables of sort $\varepsilon$ range over subsets of the domain of $\mathfrak{A}_{\varepsilon}$; – the symbols of $\sigma_{\varepsilon}$ are interpreted in $(\mathfrak{A}_0, \mathfrak{A}_1)$ exactly as they are interpreted in $\mathfrak{A}_{\varepsilon}$. Here is a simple but useful fact. Lemma 4.2. Let $\sigma_0$ and $\sigma_1$ be two disjoint signatures, and let $\Phi$ be a $(\sigma_0, \sigma_1)$-formula. Then $\Phi$ is equivalent to a Boolean combination of $\sigma_0$-formulas over $\operatorname{Var}^0$ and $\sigma_1$-formulas over $\operatorname{Var}^1$. Proof. By induction on the complexity of $\Phi$. Without loss of generality, we can assume that $\vee$, $\to$ and $\forall$ do not occur in $\Phi$, although $\wedge$, $\neg$ and $\exists$ may occur in $\Phi$.
– Suppose $\Phi$ is atomic. Then it already has the required form. – Suppose $\Phi=\Psi \wedge \Theta$. By the inductive hypothesis, $\Psi$ and $\Theta$ are equivalent to appropriate Boolean combinations $\Psi'$ and $\Theta'$ respectively. Thus $\Phi$ is equivalent to $\Psi' \wedge \Theta'$, which has the required form. – Suppose $\Phi=\neg \Psi$. Then we can argue as in the previous case. – Suppose $\Phi=\exists\, \mathfrak{u}\ \Psi$ where $\mathfrak{u} \in \operatorname{Var}^0 \cup \operatorname{Var}^1$. By the inductive hypothesis, $\Psi$ is equivalent to an appropriate Boolean combination $\Psi'$. By using propositional logic we can put $\Psi'$ into the form
$$
\begin{equation*}
(\Theta_1^0 \wedge \Theta_1^1) \vee \dots \vee (\Theta_n^0 \wedge \Theta_n^1)
\end{equation*}
\notag
$$
where $\Theta^0_1$, …, $\Theta^0_n$ are $\sigma_0$-formulas over $\operatorname{Var}^0$ and $\Theta^1_1$, …, $\Theta^1_n$ are $\sigma_1$-formulas over $\operatorname{Var}^1$. So $\Phi$ is equivalent to
$$
\begin{equation*}
\exists\, \mathfrak{u}\ \bigl((\Theta_1^0 \wedge \Theta_1^1) \vee \dots \vee (\Theta_n^0 \wedge \Theta_n^1) \bigr),
\end{equation*}
\notag
$$
which in turn is equivalent to:
$\bullet$ $(\exists\, \mathfrak{u}\ \Theta_1^0 \wedge \Theta_1^1) \vee \dots \vee (\exists\, \mathfrak{u}\ \Theta_n^0 \wedge \Theta_n^1)$ if $\mathfrak{u} \in \operatorname{Var}^0$; $\bullet$ $(\Theta_1^0 \wedge \exists\, \mathfrak{u}\ \Theta_1^1) \vee \dots \vee (\Theta_n^0 \wedge \exists\, \mathfrak{u}\ \Theta_n^1)$ if $\mathfrak{u} \in \operatorname{Var}^1$. In each case, we obtain the desired Boolean combination. $\Box$ Remember that $S \subseteq \mathbb{N}$ is called eventually periodic iff there exist natural numbers $p$ and $a$ such that for every natural number $n$ greater than $a$, Consider the signature $\{ \mathsf{s}^1, =^2\}$ where $\mathsf{s}$ is a unary function symbol, whose intended interpretation is the successor function; we write $\langle \mathbb{N}; \mathsf{s},=\rangle$ for the corresponding structure. The following result can be extracted easily from works of Büchi.Theorem 4.3 (see [9], [10]). A subset of $\mathbb{N}$ is definable in $\langle \mathbb{N}; \mathsf{s},=\rangle$ (by a monadic formula) iff it is eventually periodic. Proof. As a consequence of Theorem 1 in [10] (see the fourth remark after it), Büchi shows that for every $S \subseteq \mathbb{N}$ the following are equivalent:
(i) $S$ is definable in $\langle \mathbb{N}; \mathsf{s},=\rangle$; (ii) $S$ is definable in $\langle \mathbb{N}; \mathsf{s},=\rangle$ in the “weak sense”, namely when all set quantifiers are restricted to range over finite subsets of $\mathbb{N}$. Moreover, by Corollary 2 in [9], § 5: (ii) holds iff $S$ is eventually periodic. $\Box$ Clearly, since the usual ordering relation is definable in $\langle \mathbb{N}; \mathsf{s},=\rangle$ and the successor function is definable in $\langle \mathbb{N}; \leqslant \rangle$, we can restate Theorem 4.3 with $\langle \mathbb{N}; \leqslant \rangle$ in place of $\langle \mathbb{N}; \mathsf{s},=\rangle$. Lemma 4.4. Let $S \subseteq \mathbb{N}$ and $m \in \mathbb{N}$. Suppose that: $\bullet$ $S$ is definable in $\langle \mathbb{N}; \operatorname{sq}, \bot,=\rangle$ (by a monadic formula); $\bullet$ $m$ is not the square of a natural number, i.e. $\sqrt{m} \notin \mathbb{N}$. Then there exists an eventually periodic $K \subseteq \mathbb{N}$ such that for every $n \in \mathbb{N}$, Proof. We shall deal with two special signatures:
$$
\begin{equation*}
\sigma_0:= \{ \operatorname{sq}^1, \bot^2, \operatorname{Co}_m^1, =^2\} \quad \text{and} \quad \sigma_1:= \{ \operatorname{sq}^1, =^2 \}.
\end{equation*}
\notag
$$
Here $\operatorname{Co}_m$ is a unary predicate symbol, whose intended interpretation is the relation “$x$ and $m$ have no common prime divisors”. Formally, $\sigma_0$ and $\sigma_1$ must be disjoint, but the interpretations of $\operatorname{sq}$ and $=$ will always be clear from the context, so this requirement can be dropped. Clearly, every term of $\sigma_0$/$\sigma_1$ contains exactly one (individual) variable. Let We use $\chi_D$ to denote the characteristic function of $D$. It can be extended to finite sequences of natural numbers by Notice that both $D$ and $\mathbb{N} \setminus D$ are closed under the square function. Now take We assume that in these structures the symbols of $\sigma_0$ and $\sigma_1$ are interpreted as the restrictions of their standard interpretations to $\mathbb{N} \setminus D$ and $D$ respectively.
For convenience, let $\sigma$ denote $\{\operatorname{sq}^1, \bot^2, =^2\}$. Consider an arbitrary $\sigma$-formula Our next task is to construct an indexed family of $(\sigma_0,\sigma_1)$-formulas
$$
\begin{equation*}
\langle \Phi^{\tau}(x_1^{\tau_1}, \dots, x_n^{\tau_n}, X_1^0, \dots, X_k^0, X_1^1, \dots, X_k^1) \colon \tau \in \{0,1\}^n \rangle
\end{equation*}
\notag
$$
such that for any $a_1, \dots, a_n \in \mathbb{N}$ and $A_1, \dots, A_k \subseteq \mathbb{N}$ the following conditions are equivalent:
(i) $\langle \mathbb{N}; \operatorname{sq}, \bot,=\rangle \models \Phi(a_1, \dots, a_n, A_1, \dots, A_k)$; (ii) $(\mathfrak{A}_0, \mathfrak{A}_1) \models \Phi^{\chi_D(a_1, \dots, a_n)} (a_1, \dots, a_n, A_1 \setminus D, \dots, A_k \setminus D, A_1 \cap D, \dots, A_k \cap D)$. Without loss of generality, we assume that $\vee$, $\to$ and $\forall$ do not occur in $\Phi$. The formulas $\Phi^\tau$ are then defined by induction on the complexity of $\Phi$: – if $\Phi$ has the form $t(x_i) \in X_l$, then take $\Phi^\tau$ to be $t(x_i^{\tau_i}) \in X_l^{\tau_i}$; – if $\Phi$ has the form $s(x_i) \bot t(x_j)$, then take
$$
\begin{equation*}
\Phi^\tau:= \begin{cases} s(x_i^0) \bot t(x_j^0) &\text{if }\tau_i=\tau_j=0, \\ \operatorname{Co}_m(s(x_i^0)) &\text{if } \tau_i=0\text{ and }\tau_j=1, \\ \operatorname{Co}_m(t(x_j^0)) &\text{if } \tau_i=1 \text{ and } \tau_j=0, \\ x_i^1 \ne x_i^1 &\text{if } \tau_i=\tau_j=1; \end{cases}
\end{equation*}
\notag
$$
– if $\Phi$ has the form $s (x_i)=t (x_j)$, then take
$$
\begin{equation*}
\Phi^\tau:= \begin{cases} s(x_i^{\tau_i})=t(x_j^{\tau_i}) &\text{if } \tau_i=\tau_j, \\ x_i^{\tau_i} \ne x_i^{\tau_i} &\text{if } \tau_i \ne \tau_j; \end{cases}
\end{equation*}
\notag
$$
– if $\Phi$ has the form $\Psi \wedge \Theta$, then take $\Phi^\tau$ to be $\Psi^\tau \wedge \Theta^\tau$; – if $\Phi$ has the form $\neg\, \Psi$, then take $\Phi^\tau$ to be $\neg\, \Psi^\tau$; – if $\Phi$ has the form $\exists\, y\ \Psi(x_1, \dots, x_n, y, X_1, \dots, X_k)$, then take
$$
\begin{equation*}
\Phi^\tau:= \bigvee_{\varepsilon \in\{0,1\}} \exists\, x_{n+1}^{\varepsilon}\ \bigl( \Psi(x_1, \dots, x_n, x_{n+1}, X_1, \dots, X_k) \bigr)^{(\tau_1, \dots, \tau_n, \varepsilon)};
\end{equation*}
\notag
$$
– if $\Phi$ has the form $\exists\, Y\ \Psi(x_1, \dots, x_n, X_1, \dots, X_k, Y)$, then take
$$
\begin{equation*}
\Phi^\tau:= \exists\, X_{k+1}^0\ \exists\, X_{k+1}^1\ \bigl( \Psi(x_1, \dots, x_n, X_1, \dots, X_k, X_{k+1}) \bigr)^\tau.
\end{equation*}
\notag
$$
It is straightforward to check that the resulting family has the required property.
Finally, let $\Phi(x)$ be a $\sigma$-formula that defines $S$ in $\langle \mathbb{N}; \operatorname{sq}, \bot,=\rangle$. Then the construction from the previous paragraph gives us $(\sigma_0, \sigma_1)$-formulas $\Phi^0(x^0)$ and $\Phi^1(x^1)$ such that for all $a \in \mathbb{N}$:
$$
\begin{equation*}
\begin{aligned} \, a\notin D \quad &\Longrightarrow \quad \bigl( \langle \mathbb{N}; \operatorname{sq}, \bot,=\rangle \models \Phi (a) \ \ \Longleftrightarrow \ \ (\mathfrak{A}_0, \mathfrak{A}_1) \models \Phi^0 (a)\bigr); \\ a\in D \quad &\Longrightarrow \quad \bigl( \langle \mathbb{N}; \operatorname{sq}, \bot,=\rangle \models \Phi (a) \ \ \Longleftrightarrow \ \ (\mathfrak{A}_0, \mathfrak{A}_1) \models \Phi^1(a)\bigr). \end{aligned}
\end{equation*}
\notag
$$
Further, by Lemma 4.2, $\Phi^1 (x^1)$ is equivalent to a Boolean combination of $\sigma_0$-sentences $\Psi_i$ and $\sigma_1$-formulas $\Theta_j (x^1)$. Evidently, we can replace each $\Psi_i$ in this Boolean combination by:
$\bullet$ $x^1=x^1$ if $\mathfrak{A}_0 \models \Psi_i$; $\bullet$ $x^1 \ne x^1$ if $\mathfrak{A}_0 \not \models \Psi_i$. Thus $\Phi^1 (x^1)$ can be transformed into a $\sigma_1$-formula $\widetilde{\Phi}(x^1)$. So for any $a \in D$,
$$
\begin{equation*}
a\in S \quad \Longleftrightarrow \quad \langle D; \operatorname{sq},=\rangle \models \widetilde{\Phi}(a).
\end{equation*}
\notag
$$
Notice that $\bigl(m^{2^n}\bigr)^2 = m^{2^{n+1}}$ for all $n \in \mathbb{N}$. So if $\operatorname{sq}$ and $\mathsf{s}$ are treated as the same symbol, then the function $n \mapsto m^{2^n}$ is an isomorphism from $\langle \mathbb{N}; \mathsf{s},=\rangle$ onto $\langle D; \operatorname{sq},=\rangle$. Take
$$
\begin{equation*}
\widehat{\Phi}:= \text{the result of replacing }\operatorname{sq} \text{ in }\widetilde{\Phi}\text{ by } \mathsf{s}.
\end{equation*}
\notag
$$
Denote by $K$ the set defined in $\langle \mathbb{N}; \mathsf{s},=\rangle$ by $\widehat{\Phi}$. It follows that for every $n \in \mathbb{N}$,
$$
\begin{equation*}
m^{2^n}\in S \quad \Longleftrightarrow \quad \langle D; \operatorname{sq}, =\rangle \models \widetilde{\Phi}(m^{2^n}) \quad \Longleftrightarrow \quad \langle \mathbb{N}; \mathsf{s},=\rangle \models \widehat{\Phi}(n) \quad \Longleftrightarrow \quad n\in K.
\end{equation*}
\notag
$$
Moreover, $K$ is eventually periodic by Theorem 4.3. $\Box$ We are ready to prove Theorem 4.1. Proof of Theorem 4.1. Take
$$
\begin{equation*}
S:= \bigl\{ m^{2^{2^k}} \bigm| m, k \in \mathbb{N} \text{ and }\sqrt{m} \notin \mathbb{N} \bigr\}.
\end{equation*}
\notag
$$
Evidently, $S$ is computable and closed under automorphisms of $\langle \mathbb{N}; \operatorname{sq}, \bot,= \rangle$. Now suppose $S$ is definable in $\langle \mathbb{N}; \operatorname{sq}, \bot,=\rangle$ (by a monadic formula). Fix some $\mathtt{m} \in \mathbb{N}$ such that $\sqrt{\mathtt{m}} \notin \mathbb{N}$, e.g. one can take $\mathtt{m} := 2$. Then by Lemma 4.4, there exists an eventually periodic $K \subseteq \mathbb{N}$ such that for every $n \in \mathbb{N}$, Hence $K$ coincides with $\{ 2^k \mid k \in \mathbb{N}\}$, which contradicts the eventual periodicity of $K$. $\Box$ The technique developed for proving Theorem 4.1 can be adapted to give other examples of expansions of $\mathfrak{C}$ that do not satisfy $(*)$. In particular, consider the signature where $\sqsubseteq$ is a binary predicate symbol, whose intended interpretation is the relation
$$
\begin{equation*}
\{ (m,n) \in \mathbb{N}^2 \mid [\![m]\!]=[\![n]\!] \text{ and }m\text{ divides }n \}.
\end{equation*}
\notag
$$
We shall write $\langle \mathbb{N}; \bot, \sqsubseteq \rangle$ for the corresponding structure. Though $\langle \mathbb{N}; \operatorname{sq}, \bot,=\rangle$ may seem more natural than $\langle \mathbb{N}; \bot, \sqsubseteq \rangle$, the latter is closer to the structure over $\mathbb{N}$ with the divisibility relation, which has been studied in [7]: $=$, $\bot$ and $\sqsubseteq$ are first-order definable by means of the divisibility relation, but $\operatorname{sq}$ is not. Theorem 4.5. There exists a computable $S \subseteq \mathbb{N}$ such that: $\bullet$ $S$ is closed under automorphisms of $\langle \mathbb{N}; \bot, \sqsubseteq \rangle$; $\bullet$ $S$ is not definable in $\langle \mathbb{N}; \bot, \sqsubseteq \rangle$. To prove this, we shall use an analogue of Lemma 4.4. Lemma 4.6. Let $S\,{\subseteq}\, \mathbb{N}$ and $p\,{\in}\,\mathbb{P}$. Suppose that $S$ is definable in $\langle \mathbb{N}; \bot, \sqsubseteq \rangle$. Then there exists an eventually periodic $K \subseteq \mathbb{N}$ such that for every $n \in \mathbb{N}$, Proof. This time we shall deal with
$$
\begin{equation*}
\sigma_0:= \{ \bot^2, \operatorname{Co}_p^1, \sqsubseteq^2\} \quad \text{and} \quad \sigma_1:= \{ \sqsubseteq^2 \}.
\end{equation*}
\notag
$$
As before, $\operatorname{Co}_p$ will be interpreted as the relation “$x$ and $p$ have no common prime divisors”, i.e. “$x$ is not divisible by $p$”. Let $D$ be $\{ p^n \mid n \in \mathbb{N}\}$. Take
$$
\begin{equation*}
\mathfrak{A}_0:= \langle {\mathbb{N} \setminus D}; \bot, \operatorname{Co}_p, \sqsubseteq \rangle \quad \text{and} \quad \mathfrak{A}_1:= \langle D; \sqsubseteq \rangle.
\end{equation*}
\notag
$$
For convenience, denote $\{ \bot^2, \sqsubseteq^2\}$ by $\sigma$. As in the proof of Lemma 4.1, it is straightforward to show that for each $\sigma$-formula $\Phi$ we can inductively define a suitable indexed family of $(\sigma_0, \sigma_1)$-formulas $\Phi^{\tau}$.
Let $\Phi(x)$ be a $\sigma$-formula that defines $S$ in $\langle \mathbb{N}; \bot, \sqsubseteq \rangle$. The same reasoning as in the proof of Lemma 4.1 gives us a $\sigma_1$-formula $\widetilde{\Phi}(x^1)$ such that for any $a \in D$,
$$
\begin{equation*}
a\in S \quad \Longleftrightarrow \quad \langle D; \sqsubseteq \rangle \models \widetilde{\Phi}(a).
\end{equation*}
\notag
$$
Obviously, if $\leqslant$ and $\sqsubseteq$ are treated as the same symbol, then the function $n \mapsto p^n$ is an isomorphism from $\langle \mathbb{N}; \leqslant \rangle$ onto $\langle D; \sqsubseteq \rangle$. Take
$$
\begin{equation*}
\widehat{\Phi}:= \text{the result of replacing }\leqslant\text{ in } \widetilde{\Phi}\text{ by }\sqsubseteq.
\end{equation*}
\notag
$$
Denote by $K$ the set defined in $\langle \mathbb{N}; \sqsubseteq \rangle$ by $\widehat{\Phi}$. It follows that for every $n \in \mathbb{N}$,
$$
\begin{equation*}
p^n\in S \quad \Longleftrightarrow \quad \langle D; \sqsubseteq \rangle \models \widetilde{\Phi}(p^n) \quad \Longleftrightarrow \quad \langle \mathbb{N}; \leqslant \rangle \models \widehat{\Phi}(n) \quad \Longleftrightarrow \quad n\in K.
\end{equation*}
\notag
$$
Moreover, $K$ is eventually periodic by Theorem 4.3. $\Box$ This lemma allows us to obtain the desired result. Proof of Theorem 4.5. Take
$$
\begin{equation*}
S:= \{ p^{2^n} \mid p \in \mathbb{P} \text{ and }n \in \mathbb{N} \}.
\end{equation*}
\notag
$$
Clearly, $S$ is computable and closed under automorphisms of $\langle \mathbb{N}; \bot, \sqsubseteq \rangle$. Suppose $S$ is definable in $\langle \mathbb{N}; \bot, \sqsubseteq \rangle$. Fix some $\mathtt{p} \in \mathbb{P}$. Then by Lemma 4.6, there exists an eventually periodic $K \subseteq \mathbb{N}$ such that for every $n \in \mathbb{N}$, Hence $K$ coincides with $\left\{ 2^k \mid k \in \mathbb{N} \right\}$, which is a contradiction. $\Box$ 
Citation in format AMSBIB
\Bibitem{SpePak22} |
|
||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|