<p>By a <strong>fragment</strong> of second-order logic (SO) I mean a recursive (= computable) subset of the set of sentences of SO. Such a fragment  <span class="math-container">$L$</span> is <strong>decidable</strong>, if there is an algorithm which determines whether a given sentence of <span class="math-container">$L$</span> is satisfiable, i.e., has a model.</p>
<p>Given two logics <span class="math-container">$L_1,L_2$</span>, we say that they have the <strong>same expressive power</strong>, if for each sentence <span class="math-container">$\varphi$</span> of <span class="math-container">$L_1$</span> there is a sentence of <span class="math-container">$L_2$</span> which is equivalent with <span class="math-container">$\varphi$</span> (defines the same class of models), and vice versa.</p>
<p><strong>Question:</strong> does there exist a decidable fragment of SO which has the same expressive power as SO?</p>
<p><strong>Some remarks:</strong> First, if we do not require that a fragment needs to consist of a recursive set of sentences, then clearly there exist such a fragment. Secondly, if we replace SO with first-order logic (FO), the answer is no, because the set of valid sentences of FO is RE. Thirdly, if we restrict our attention to finite models, then there is such a fragment. For more discussion on this, see <a href="https://arxiv.org/abs/2112.14996" rel="nofollow noreferrer">this note</a>.</p>

CC BY-SA 4.0
2024-11-30T20:39:46.427Z
By sentences $\phi_i$ being equivalent in $L_i$, you mean something like $SO \models \phi_1 \leftrightarrow \phi_2$? Or equi-satisfiability?
Martin Berger
CC BY-SA 4.0
2024-11-30T21:01:18.227Z
@MartinBerger I mean semantic equivalence, i.e., for each model $M$ we have that $M \models \phi_1$ iff $M \models \phi_2$.
Reijo Jaakkola
CC BY-SA 4.0
2024-12-01T13:54:39.320Z
What does $M$ range over in $M \models \phi_i$?
Martin Berger
CC BY-SA 4.0
2024-12-01T14:06:15.810Z
@MartinBerger It ranges over the class of all models (= structures) over the (common) vocabulary of $\phi_1,\phi_2$.
Reijo Jaakkola
<lo.logic><first-order-logic><second-order-logic>
Decidable fragment of second-order logic
Reijo Jaakkola
# Decidable fragment of second-order logic

(Asked by: username_0 on 2024-11-30)

By a **fragment** of second-order logic (SO) I mean a recursive (= computable) subset of the set of sentences of SO. Such a fragment $L$ is **decidable**, if there is an algorithm which determines whether a given sentence of $L$ is satisfiable, i.e., has a model.

Given two logics $L\_1,L\_2$, we say that they have the **same expressive power**, if for each sentence $\varphi$ of $L\_1$ there is a sentence of $L\_2$ which is equivalent with $\varphi$ (defines the same class of models), and vice versa.

**Question:** does there exist a decidable fragment of SO which has the same expressive power as SO?

**Some remarks:** First, if we do not require that a fragment needs to consist of a recursive set of sentences, then clearly there exist such a fragment. Secondly, if we replace SO with first-order logic (FO), the answer is no, because the set of valid sentences of FO is RE. Thirdly, if we restrict our attention to finite models, then there is such a fragment. For more discussion on this, see [this note](https://arxiv.org/abs/2112.14996).

**Tags:** lo.logic, first-order-logic, second-order-logic
> **Comments:**
> **username_1**: By sentences $\phi_i$ being equivalent in $L_i$, you mean something like $SO \models \phi_1 \leftrightarrow \phi_2$? Or equi-satisfiability?  
> **username_0**: @MartinBerger I mean semantic equivalence, i.e., for each model $M$ we have that $M \models \phi_1$ iff $M \models \phi_2$.  
> **username_1**: What does $M$ range over in $M \models \phi_i$?  
> **username_0**: @MartinBerger It ranges over the class of all models (= structures) over the (common) vocabulary of $\phi_1,\phi_2$.  

---

## 0 answers

