<p>In fact, we can always stay in the second-order realm (as long as our &quot;base structure&quot; is infinite)!</p>
<p>First, let's look at the particular case where our base structure is <span class="math-container">$\mathcal{N}=(\mathbb{N};+,\times)$</span>. Over <span class="math-container">$\mathcal{N}$</span> we can code finite sequences of sets as individual sets as follows: the set <span class="math-container">$X\subseteq\mathbb{N}$</span> codes a finite sequence of sets iff every element of <span class="math-container">$X$</span> has the form <span class="math-container">$2^x3^y$</span> for some <span class="math-container">$x,y\in\mathbb{N}$</span>, and there is some <span class="math-container">$m$</span> such that whenever <span class="math-container">$2^k\vert u\in X$</span> we have <span class="math-container">$k&lt;m$</span>. The idea then is that such an <span class="math-container">$X$</span> codes the sequence whose <span class="math-container">$i$</span>th term is <span class="math-container">$\{j: 2^i3^j\in X\}$</span>.</p>
<p>Now suppose <span class="math-container">$R$</span> is a second-order binary operation on <span class="math-container">$\mathcal{N}$</span>. Given <span class="math-container">$A,B\subseteq\mathbb{N}$</span>, we have that <span class="math-container">$A$</span> is <span class="math-container">$R$</span>-connected to <span class="math-container">$B$</span> iff there is some <span class="math-container">$X$</span> which codes a finite sequence of sets <span class="math-container">$(X_i)_{i&lt;m}$</span> with the property that <span class="math-container">$X_0=A$</span>, <span class="math-container">$X_{m-1}=B$</span>, and for each <span class="math-container">$i&lt;m-1$</span> we have <span class="math-container">$X_iRX_{i+1}$</span>. This is purely second-order over <span class="math-container">$\mathcal{N}$</span>, so we've avoided third-order quantification.</p>
<hr />
<p>OK, but what if we're looking at a very low-expressive-complexity structure, such as a(n infinite) pure set? Well, we can still do the job!</p>
<ul>
<li><p>In pure second-order logic, we can determine when a set <span class="math-container">$X$</span> is finite (&quot;Every well-order on <span class="math-container">$X$</span> is also a co-well-order&quot; - and if you want to avoid reliance on the axiom of choice here, you can also include the clause &quot;<span class="math-container">$X$</span> is well-orderable,&quot; which interestingly <a href="https://math.stackexchange.com/questions/3765978/the-complexity-of-finiteness">is optimal in a precise sense</a>).</p>
</li>
<li><p>We now can express &quot;<span class="math-container">$A$</span> is <span class="math-container">$R$</span>-connected to <span class="math-container">$B$</span>&quot; as &quot;There is a pairing operation <span class="math-container">$\langle\cdot,\cdot\rangle$</span>, a set <span class="math-container">$X$</span>, and a binary relation <span class="math-container">$\trianglelefteq$</span> such that</p>
<ul>
<li><p>the set <span class="math-container">$L:=\{x:\exists y(\langle x,y\rangle\in X)\}$</span> is finite,</p>
</li>
<li><p><span class="math-container">$\trianglelefteq$</span> is a binary relation on <span class="math-container">$L$</span>,</p>
</li>
<li><p>if <span class="math-container">$x$</span> is the <span class="math-container">$\trianglelefteq$</span>-least (resp. greatest) element of <span class="math-container">$L$</span> then <span class="math-container">$\{y: \langle x,y\rangle\in X\}$</span> is <span class="math-container">$A$</span> (resp. <span class="math-container">$B$</span>), and</p>
</li>
<li><p>if <span class="math-container">$x,x'\in L$</span> and <span class="math-container">$x'$</span> is the <span class="math-container">$\trianglelefteq$</span>-successor of <span class="math-container">$x$</span> then we have <span class="math-container">$$\{y: \langle x,y\rangle\in X\}R\{y: \langle x',y\rangle\in X\}.$$</span></p>
</li>
</ul>
</li>
</ul>
<p>Note, though, that there was a cost: over <span class="math-container">$\mathcal{N}$</span> we just needed to quantify over <em>sets</em>, whereas here we need to quantify over <em>relations</em>. This is unavoidable: <em>monadic</em> second-order logic is not strong enough to perform this sort of construction without a sufficiently rich base structure.</p>

CC BY-SA 4.0
2023-09-17T06:38:04.150Z
Thanks, this is really interesting! How many quantifier alternations do you think are needed to express all these things?
Nicola Gigante
CC BY-SA 4.0
2023-09-16T23:03:00.677Z
2023-09-16T23:03:00.677Z
Noah Schweber
<p>By <em>second-order reachability</em> I mean a second-order lifting of the reachability problem on first-order structures. So let <span class="math-container">$R(X,Y)$</span> be a second-order binary predicate (<em>i.e.</em> it links a set of elements <span class="math-container">$X$</span> to another set of elements <span class="math-container">$Y$</span>. Then we have some first-order predicates <span class="math-container">$P(x)$</span> and <span class="math-container">$Q(y)$</span>.</p>
<p>Lifting how I would express reachability in second-order logic, I can express this second-order reachability in third-order logic:</p>
<p><span class="math-container">$$
 \forall \mathbb{P} \bigl(\mathbb{P}(P) \land \forall X Y ((\mathbb{P}(X) \land R(X,Y)) \to\mathbb{P}(Y)) \to \mathbb{P}(Q)\bigr)
$$</span></p>
<p>But is this needed?
Is this second-order reachability problem expressible in second-order logic, or do I need third-order quantifiers, similarly to how first-order reachability needs second order ones?</p>

<first-order-logic>
Second-order reachability in second-order logic
Nicola Gigante
# Second-order reachability in second-order logic

(Asked by: username_0 on 2023-09-16)

By *second-order reachability* I mean a second-order lifting of the reachability problem on first-order structures. So let $R(X,Y)$ be a second-order binary predicate (*i.e.* it links a set of elements $X$ to another set of elements $Y$. Then we have some first-order predicates $P(x)$ and $Q(y)$.

Lifting how I would express reachability in second-order logic, I can express this second-order reachability in third-order logic:

$$
\forall \mathbb{P} \bigl(\mathbb{P}(P) \land \forall X Y ((\mathbb{P}(X) \land R(X,Y)) \to\mathbb{P}(Y)) \to \mathbb{P}(Q)\bigr)
$$

But is this needed?
Is this second-order reachability problem expressible in second-order logic, or do I need third-order quantifiers, similarly to how first-order reachability needs second order ones?

**Tags:** first-order-logic


---

## 1 answers

### Answer by username_1 on 2023-09-16. Score: 2

In fact, we can always stay in the second-order realm (as long as our "base structure" is infinite)!

First, let's look at the particular case where our base structure is $\mathcal{N}=(\mathbb{N};+,\times)$. Over $\mathcal{N}$ we can code finite sequences of sets as individual sets as follows: the set $X\subseteq\mathbb{N}$ codes a finite sequence of sets iff every element of $X$ has the form $2^x3^y$ for some $x,y\in\mathbb{N}$, and there is some $m$ such that whenever $2^k\vert u\in X$ we have $k. The idea then is that such an $X$ codes the sequence whose $i$th term is $\{j: 2^i3^j\in X\}$.

Now suppose $R$ is a second-order binary operation on $\mathcal{N}$. Given $A,B\subseteq\mathbb{N}$, we have that $A$ is $R$-connected to $B$ iff there is some $X$ which codes a finite sequence of sets $(X\_i)\_{i with the property that $X\_0=A$, $X\_{m-1}=B$, and for each $i we have $X\_iRX\_{i+1}$. This is purely second-order over $\mathcal{N}$, so we've avoided third-order quantification.

---

OK, but what if we're looking at a very low-expressive-complexity structure, such as a(n infinite) pure set? Well, we can still do the job!

* In pure second-order logic, we can determine when a set $X$ is finite ("Every well-order on $X$ is also a co-well-order" - and if you want to avoid reliance on the axiom of choice here, you can also include the clause "$X$ is well-orderable," which interestingly [is optimal in a precise sense](https://math.stackexchange.com/questions/3765978/the-complexity-of-finiteness)).
* We now can express "$A$ is $R$-connected to $B$" as "There is a pairing operation $\langle\cdot,\cdot\rangle$, a set $X$, and a binary relation $\trianglelefteq$ such that

  + the set $L:=\{x:\exists y(\langle x,y\rangle\in X)\}$ is finite,
  + $\trianglelefteq$ is a binary relation on $L$,
  + if $x$ is the $\trianglelefteq$-least (resp. greatest) element of $L$ then $\{y: \langle x,y\rangle\in X\}$ is $A$ (resp. $B$), and
  + if $x,x'\in L$ and $x'$ is the $\trianglelefteq$-successor of $x$ then we have $$\{y: \langle x,y\rangle\in X\}R\{y: \langle x',y\rangle\in X\}.$$

Note, though, that there was a cost: over $\mathcal{N}$ we just needed to quantify over *sets*, whereas here we need to quantify over *relations*. This is unavoidable: *monadic* second-order logic is not strong enough to perform this sort of construction without a sufficiently rich base structure.

> **Comments:**
> **username_0**: Thanks, this is really interesting! How many quantifier alternations do you think are needed to express all these things?  

---

